Topics for Final Exam in COP 5021 This oral examination covers all homeworks in the class. (You are to set up an oral examination time, a 1/2 hour appointment during Tuesday through Friday of finals week by email.) REMINDERS This test is open book and notes. (However, we will note when you need to consult your book and notes, so their use will be somewhat discouraged.) READINGS Chapter 1-2 of our textbook: Principles of Programming Analysis by Flemming Nielson, Hanne Riis Nielson, and Chris Hankin (Springer-Verlag, 1999). You should also read our solutions to the homework problems (on WebCT). If you have additional time, read chapter 4 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? + 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? + 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. + Show how you would use and explain operational semantic descriptions of programming languages. + Explain and show how to prove the soundness of an analysis with respect to the operational semantics of a language. * 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? - 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 data flow graph? + How is that used to model the semantics? + What modifications would be needed to data flow graphs to handle new kinds of statements? *** the equational approach + What are the dataflow equations? + How to represent them mathmatically? + 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? *** 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? * 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? ** Theoretical Properties (2.2) + Why are formal correctness proofs useful for program analysis? *** denotational semantics + Explain how denotational semantics works for expressions? + Why use denotational semantics for expressions? + Why is the state a parameter to the meaning of arithmetic expressions? *** structural operational semantics (2.2.1) + What's the difference between big step and small step operational semantics? + What are the basic ideas behind little step operational semantics? + What do the various kinds of configurations mean? + What do side conditions mean? + How are loops and recursion handled? + How are errors handled in operational semantics? + How would you define semantics for various new control structures (such as break, return, continue, throw, catch, parallel composition, nondeterministic choice, etc.)? + How does the operational semantics relate to data flow graphs? + What properties of flow graphs are preserved by transitions in the semantics? + How does the correctness proof of the live variables analysis work? + Why is a constraint system necessary, instead of an equational system, for the proof? + How would the correctness proof for live variables be done using abstract interpretation techniques? ** 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 monotoone frameworks helpful? ** Interprocedural Analysis (2.5) + What complications arise in analysis when trying to deal with procedures? + How does one deal with these problems? *** operational semantics (2.5.1) + How is a procedure different from a macro? + How is that reflected in their semantics? + How does the semantics handle lexical scoping? Recursion? + What is a store? An envrionment? + What is bind used for in the semantics? + What would be different if we had dynamic binding as in OO languages? *** flow graphs + How are flow graphs affected by procedures? *** problems with adapting earlier techniques (2.5.2) + If we don't use inter-flow* in an analysis, what happens? + How do we use context in an embellished monotone framework? + How can we get more precision? What are the cost tradeoffs? + How can we trade precision for speed? *** flow insensitive analyses (2.5.6) + What does it mean for an analysis to be flow (in)sensitive? + Why would we want to use a flow insensitive analysis? + What are some examples? ** Shape Analysis (2.6) + What changes in the language when we add pointers or explicit references? + What happens to the analysis if we allow pointer arithmetic? *** structural operational semantics (2.6.1) + What changes in the sematics to support references? + Describe how states are used in the denotational semantics of expressions. + Describe how heaps are used in the denotational semantics of expressions. + What do the configurations in the operational semantics mean? + How does garbage collection interact with the operational semantics? *** property space (2.6.2) - What is a compatible shape graph? - What do abstract locations stand for? - How are abstract states and heaps constructed? - Explain the need for each invariant on compatible shape graphs. - What is strong update? How does the invariant help achieve that? * abstract interpretation (Chapter 4) ** A Mundane Approach to Correctness (4.1) + What kinds of analyses are mundane? What's an example? A counterexample? + How does the constant propogation analysis work? *** correctness relations (4.1.1) + What is a correctness relation? Why is it useful? + How does it relate to a lattice? + What is the correctness relation for the constant propogation example? *** representation functions (4.1.2) + What is a representation function? Why is it useful? + How does a representation function generate a correctness relation? + How does a correctness relation generate a representation function? + How does that work for constant propogation? + Does the representation function for shape graphs generate the appropriate correctness relation? *** generalization (4.1.3) + What's a logical relation? ** Approximation of Fixed Points (4.2) + Why do we care about fixed points? + Why do we need to approximate fixed points? *** Widening Operators (4.2.1) + What is an upper bound operator? + What is a widening operator? + Why are they useful? + Give an example of how to build a widening operator?