Topics for Midterm Exam in COP 5021 $Date: 2024/02/13 14:36:05 $ This examination covers homeworks 1-3. REMINDERS This test is open book and notes, but no electronics. READINGS Chapter 1 and sections 2.1, 2.3, and 2.3 of our textbook: Principles of Programming Analysis by Flemming Nielson, Hanne Riis Nielson, and Chris Hankin (Springer-Verlag, 1999). If you have additional time, read chapter 4 sections 4.1-4.2 of our textbook. You might also look at our WhileLang project work (git clone github.com/leavens/WhileLang.git). 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. I. 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,p1: what are main ideas and goals of program analysis?] + What are its main ideas? + 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? + Show how you would apply program analysis techniques to calculate various properties of small programs. II. Comparing the 4 approaches A. The WHILE Language - Be able to explain the meaning of programs in the WHILE language B. Reaching Definitions analysis + What is the property sought in a reaching definitions analysis? + What does it mean for that analysis to be precise? Safe? + To find a solution, what should be the initial starting value? Why? [hw3,p5: what property of an analysis determines the starting value?] - 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? C. Taint Checking analysis + What is the property sought in the taint checking analysis? + What does it mean for that analysis to be more precise? Safe? + To find a solution, what should be the initial starting value? Why? [hw3,p5: what property of an analysis determines the starting value?] D. Dataflow Analysis (1.3) + What is the goal of dataflow analysis? + What is the basic idea? + What is a control flow graph? + How is a CFG used to model the semantics? - What modifications would be needed to CFGs to handle new kinds of statements? 1. the equational approach + What are the dataflow equations? - How to represent them mathematically? - How to solve them? 2. the constraint based approach + What are the constraints? - What's the connection to the equations? E. 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? F. 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 is a Galois connection? An adjunction? How are they related? - What does it mean for a functional that describes equations to be monotone? - Why use abstraction? Concretization? - How can one use abstraction and concretization to calculate an analysis? - What is the benefit of calculating the analysis? G. Type and Effect Systems (1.6) + What is the goal of this kind of analysis? + What is 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,p1: Which set theory expression has a type error or no type error? hw2,p2: Write type checking rules for set theory expressions.] 1. annotated base types - What's the meaning of the basic types for such an analysis? - What is the meaning of function types? - How is subsumption handled? Why have subsumption? - How is "if" handled? (i.e., what do the rules for if-statements look like?) 2. annotated type constructors - What's the idea here? - How does it relate to dataflow analysis? Abstract interpretation? H. type systems - What's the difference from standard type systems? I. Your own analysis + You should be able to answer similar questions about the analyses used in your project. [hw1,p2: what questions does your analysis answer?] J. Algorithms (1.7, esp. table 1.5) + What does Chaotic Iteration do? + How does Chaotic Iteration work? Why is it correct? + Be able to solve some dataflow equations to find a solution using Chaotic iteration. [hw3,p2-4: examples and small calculations of solutions] + Explain why Chaotic Iteration starts with a particular value for a given analysis. [hw3,p2-5: what property of an analysis determines the starting value?] III. Data Flow Analysis (Ch 2) A. Intraprocedural Analysis (2.1) + What are the relationships between statements, blocks and flows? + How are paths represented? + Why use reverse flows? When should they be used? 1. Available Expressions analysis (2.1.1) + What's the idea and goal? + What could this be used for in a compiler? + What answers are safe? Precise? + Be able to simulate this analysis by hand 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? 2. 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 simulate this analysis by hand on an example 3. 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 simulate this analysis by hand on an example 4. 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 simulate this analysis by hand on an example 5. Derived Data Flow Information (2.1.5) + What are use-definition (ud) chains? du chains? + What could they each 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? B. 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?