Topics for Midterm Exam in COP 5021 $Date: 2014/02/25 01:47:09 $ This examination covers all previous homework. REMINDERS This test is open book and notes. READINGS Chapter 1 and sections 2.1, 2.3, and 2.4 of our textbook: Principles of Programming Analysis by Flemming Nielson, Hanne Riis Nielson, and Chris Hankin (Springer-Verlag, 1999). You should also look at our WHILE project work. If you have additional time, read chapter 4 sections 4.1-4.2 of our textbook. TOPICS Topics marked + below are more important than topics marked - below. In general, conceptual questions, and questions that connect topics, techniques, examples, and ideas will be more important than details, so the exam will be somewhat of a different flavor from the homework. * The Nature of Program Analysis (aka the big questions; 1.1) + What is program analysis? Why study it? What's it good for? + What are the goals of program analysis? [HW1: what are main goals of program analysis?] + What are its main ideas? [HW1: what are main ideas of program analysis?] + Explain advantages of program analysis and its disadvantages. + What are its limitations? - How would you judge and improve the quality of various kinds of program analyses? + What are the mathematical ideas that are used in various program analysis techniques? + Show how you would apply program analysis techniques to calculate various properties of small programs. * Comparing the 4 approaches ** The While Language - Be able to explain the meaning of programs in the while language ** reaching definitions analysis + What is the property sought in a reaching definitions analysis? + What does it mean to be precise? Safe? + Why start with the value given? [HW3: start values for Chaotic Iteration] - What would the analysis look like if we only wanted to keep track of which variables were assigned? - What would the analysis look like if we want to keep track of what variables could influence the values of other variables? ** Dataflow Analysis (1.3) + What's the goal of dataflow analysis? + What's the basic idea? + What's a control flow graph? + How is that used to model the semantics? - What modifications would be needed to control flow graphs to handle new kinds of statements? *** the equational approach + What are the dataflow equations? - How to represent them mathematically? - How to solve them? *** the constraint based approach + What are the constraints? - What's the connection to the equations? ** constraint based analysis (1.4) + What's the goal of this kind of analysis? + What's the basic idea? - What's the difference between a data flow analysis and a control flow analysis? - Why isn't control flow obvious in all languages? - What is continuation passing style? - How would you write an operational semantics for the functional language? ** Abstract Interpretation (1.5) + What's the goal of this kind of analysis? + What's the basic idea? + How would you use it to do reaching definitions? - What's a Galois connection? An adjunction? How are they related? - What does it mean for a functional that describes equations to be monotone? - What is abstraction for? Concretization? - How can we use them to calculate an analysis? - What's the benefit of calculating the analysis? ** Type and Effect Systems (1.6) + What's the goal of this kind of analysis? + What's the basic idea? + What does it mean for a type system to be correct? + What are the two techniques? How do they differ? + Be able to read and write type inference rules [HW2: Which set theory expression has a type error or no type error? HW2: Write type checking rules for set theory expressions.] *** annotated base types + What's the meaning of the basic types for an analysis? + What is the meaning of function types? + How is subsumption handled? Why have subsumption? - How is "if" handled? *** annotated type constructors + What's the idea here? + How does it relate to dataflow analysis? Abstract interpretation? ** type systems + What's the difference from type systems? ** Your own analysis + You should be able to answer similar questions about new analyses used in your project. [HW1: what questions does your analysis answer? HW2: What are 3 analysis questions that your project needs to answer?] ** Algorithms (1.7) + What does Chaotic Iteration do? How does it work? [HW3: prove that an invariant property is preserved by the loop in the Chaotic iteration algorithm] + Be able to formulate an analysis as a function for use in Chaotic Iteration + Be able to calculate the fixed-point of a function using Chaotic Iteration [HW3: calculate the fixed-point of the Available Expressions analysis (using incorrect and correct starting values); HW3: calculate the fixed-point of the Very Busy Expressions analysis (using incorrect starting values); HW3: what property does the starting value need for a correct computation of an analysis fixed-point?] * Data Flow Analysis (Ch 2) ** Intraprocedural Analysis (2.1) + What's the relation between statements, blocks and flows? + How are paths represented? + Why use reverse flows? *** available expressions analysis (2.1.1) + What's the idea and goal? + What could this be used for? + What answers are safe? Precise? + Be able to do this analysis on an example + What are the gen and kill functions? What do they mean? + Why don't we have to define the analysis for while loops and if statements? *** Reaching Definitions Analysis (2.1.2) + What's the idea and goal? + What could this be used for? + What answers are safe? Precise? + Be able to do this analysis on an example *** Very Busy Expressions Analysis (2.1.3) + What's the idea and goal? + What could this be used for? + What answers are safe? Precise? + Be able to do this analysis on an example *** Live Variables Analysis (2.1.4) + What's the idea and goal? + What could this be used for? + What answers are safe? Precise? + Be able to do this analysis on an example *** Derived Data Flow Information (2.1.5) + What are use-definition (ud) chains? du chains? + What could this be used for? + What answers are safe? Precise? + Be able to derive this information for an example + What's the relation between the constructive and non-constructive versions? - What's the relation between ud and the LV or RD analysis? ** Monotone Frameworks (2.3) + What's a monotone framework? An instance of one? + What must be true about a property space in a monotone framework? + What is a transfer function? What arguments does it take? + How do each of the classic analyses fit into a monotone framework? + Why is the idea of monotone frameworks helpful?