Topics for Exam 4 in Com S 342 $Date: 2006/12/04 17:02:49 $ This test covers topics from homeworks 7-10. Although we will emphasize homeworks 8-10, we may still covering some of the material on interpreter basics from homework 7 that some people had trouble with on exam 3. (These topics are especially when the interpreter evaluates expression ASTs, and the difference between forming a closure and calling it.) REMINDERS For this test, you can use one (1) page (8.5 by 11 inches, one (1) side, no less than 9pt font) of notes. Handwriting is okay. No photo-reduction is permitted. Don't use anything with printing on the other side, please. These notes are to be handed in at the end of the test. Have your name in the top right corner. Use of other notes or failure to follow these instructions will be considered cheating. If you need more space, use the back of a page. Note when you do that on the front. This test is timed. We will not grade your test if you try to take more than the time allowed. Therefore, before you begin, please take a moment to look over the entire test so that you can budget your time. For programs, indentation is important to us for ``clarity'' points; if your code is sloppy or hard to read, you will lose points. Correct syntax also matters. Check your code over for syntax errors. You will lose points if your code has syntax errors. You can use helping procedures whenever you like. READINGS We suggest that, in addition to the following, you look at the old exams to see the ``boilerplate'' material that describes the interpreter. This may save you reading time during the exam. - Essentials Of Programming Languages, Sections 3.1-3.8, especially sections 3.6-3.8 - Code Examples Web Page for the above EOPL2e sections (see http://www.cs.iastate.edu/~cs342/docs/code-examples.html) which gives access to the interpreters in lib342 named ch3-*.scm You may also want to look at the following readings if you have time: - Essentials Of Programming Languages, Chapter 5 and Appendix A (especially pages 351-357) - Code Examples Web Page for the above EOPL2e chapter 5 (see http://www.cs.iastate.edu/~cs342/docs/code-examples.html) which gives access to the interpreters in lib342 named ch5-*.scm - Structure And Interpretation Of Programming Languages, Chapter 4 (on-line at http://mitpress.mit.edu/sicp/full-text/book) TOPICS Topics marked + below are more important than topics marked - below. Topics marked ++ are even more important than the others. Names of relevant homework problems are [given in square brackets]. Descriptions of old exam problems are (given in parentheses). In general, things that are more like the homework will be more important. * Environment-Passing Interpreters (3) ** A Simple Interpreter (3.1) - Give the value of an expression written in the defined language [transcripts for run and read-eval-print with 4 commas] [calculate 3**8] + Write code to or explain how to make the interpreter deal with literals, variable references, and applications of built-in primitives. [order of evaluation of arguments to primitives] (Spring 04: add truth as a new expression) - What's the difference between a denoted value and an expressed value? + What does each of the procedures in the simple interpreter do? (Describe its job.) What is its type? - Write code to implement, or explain how to implement environments. - Explain how environments are used in the simple interpreter - What is the purpose/role of the initial environment? - Write code to add (or explain how to add) new built-in variables to the environment (like emptylist) [add emptylist to interpreter] (Spring 06: add identity procedure to initial environment; Spring 05: add "ten" to initial environment; Spring 04: add "true" to initial environment; Fall 01, add "five"; Fall 00: add "one" to interpreter; Fall 97: define initial environment with constant "e" in environment with assignment; Spring 96: add "pi") - Write code to add (or explain how to add) new built-in primitives (like print, minus, or cons) to the defined language's interpreter. [add print and minus to the interpreter] [add cons, car, cdr, list to interpreter] [add if, equal?, zero?, greater?, less?, null?] (Spring 06: add member? primitive, add append primitive; Spring 05: add exponentiation primitive; Fall 01: add second to take second element of a list; Fall 00: add isPositive; Fall 99: add tail; Fall 98: add isZero; Fall 97: add lessOrEqual; Spring 96: add notequal; Fall 95: add negative) ** The Front-End (3.2) - What does the parser do? (Spring 96: write expression to construct the abstract syntax tree that would result from parsing a string) - How does the parser work? What is the connection between SLLGEN and the parsers and define-datatypes for the abstract syntax? - What is the difference between a scanner and a parser? - What does run do? What does read-eval-print do? - What is the difference between the parser's input and an abstract syntax tree (AST)? + What is the difference between an expression and an expressed value? How does one get an expressed value from an expression? - Be able to write SLLGEN descriptions based on concrete syntax described in BNF. [add if] [add cond to interpreter] [add unpack to defined language] [traceproc syntax and semantics] [define at the top level] + Be able to read SLLGEN descriptions of concrete syntax. ** Conditional Evaluation (3.3) - What numbers represent true and false in the defined language? [add if, equal?, zero?, greater?, less?, null?] (Spring 04: what if does in a let) + What's the difference between the defined language's truth values and those of Scheme? (Spring 04: what if does in a let) + Write code to (or explain how to) make the interpreter processes if expressions. [add if] (Spring 04: what if does in a let) - How does the coding for if expressions follow the grammar? - Write code to add (or explain how to add) new conditional constructs (like cond, an if without an else, etc.) [add cond to interpreter] (Spring 06: add all expression; Spring 04: add typecase expression; Fall 01: add "implies ... ==>" expressions; Fall 00: add "or" expressions; Fall 99, Fall 95: add "do-until" expressions; Fall 98: add "unless-do" expressions and "foreach-do" expressions; Fall 97: add "and" expressions; Fall 97: add "case" expressions and "foreach-do" expressions; Spring 96: add "repeat" expressions) ** Local Binding (3.4) - Write code to (or explain how to) implement let or a similar local binding expression in the interpreter. [add unpack to defined language] (Fall 00: add "with-do" expressions to defined language; Fall 99: add "within-use" expressions; Fall 98, Spring 96: explain changes needed to implement "let") + Give value of let expressions in the defined language (Spring 06: questions about procedures, scoping and recursion; Spring 05: value of let with static scoping; Spring 04: what if does in a let; Fall 01: calculate value of if with lists) - Write code in the defined language using let [calculate 3**64] - Write code for (or explain how) the interpreter uses environments to process let expressions. How do they relate to static scoping? - Why must the interpreter pass the environment to recursive calls of eval-expression? (Spring 05: would interpreter be able to implement static scoping if didn't pass environment? Fall 01: what's wrong with interpreter that uses a global env?) - Explain how the definition of let gives static, as opposed to dynamic scoping. (See section 3.5) ** Procedures (3.5) *** statically scoped - Write simple procedures using the defined language. (Fall 00: write average; Fall 99: write largest) - Write code in the defined language that uses higher-order procedures in the defined language, to deal with recursion. [factorial using higher-order procedures] + Write code to (or explain how to) implement a closure. Explain the purpose of closures in the interpreter. How does the interpreter use them? Why are closures needed? How do they relate to static scoping? (Spring 06: add implicitly curried procedures with static scoping; Spring 06: add freeze and thaw expressions, questions about procedures, scoping and recursion; Spring 04: how procedures and let work with static scoping; Fall 01: implement varargsproc; Spring 96: What is a closure? Why are closures needed? Are closures needed in a language that does not allow nested procedures?) - Explain how a closure is like an object in an object-oriented language (and vice versa). (Fall 97: explain how closures are like objects) + Write code to (or explain how to) make the interpreter process user-defined procedures and calls to such procedures, or similar mechanisms. [checked apply-procval] [traceproc syntax and semantics] (Spring 05: implement raise and within statically scoped; Spring 04: add isProcedure as a primitive; Fall 00, Fall 99: What changes needed to support proc) - Draw pictures of the run-time environment (stack) showing how closures are made and applied. - Change the interpreter to use lexical addresses instead of variable names. *** dynamically scoped - What programming languages/systems use dynamic scoping? - How is dynamic scoping useful? - How does dynamic scoping relate to exception handling? - Draw a picture of the run-time stack, as described in class, at some point during the evaluation of an expression under dynamic scoping. - Give the output of an expression using dynamic scoping [Understanding dynamic binding/scoping] (Spring 06: value of let with dynamic scoping; Spring 05: value of let with dynamic scoping; Spring 04: give output that shows how exception handlers work; Fall 99, Fall 98, Fall 97, Spring 96, Fall 95: draw picture and give output of program) - Write code to (or explain how to) implement dynamic scoping. [Implementing dynamic binding/scoping] (Fall 97: explain changes made to implement dynamic scoping) - Explain how dynamic scoping makes reasoning about programs easier or harder. Give an example. What advantages and disadvantages does dynamic scoping have? (Spring 96: what are the advantages and disadvantages of dynamic scoping; Fall 95: why doesn't a curried example work with dynamic scoping?) *** scoping in general - Given a description of some behavior, or output of code, identify whether static or dynamic scoping is being used (Spring 06: give output of expression using let with static scoping; Spring 06: questions about procedures, scoping and recursion; Fall 01: identify the scope rule used to give a particular answer.; Fall 99: scope rule for the Unix shell) ** Recursion (3.6) + Give the value of an expression using recursion (letrec) in the defined language. (Spring 06: questions about procedures, scoping and recursion) + Write code to (or explain how to) implement a version of the environment ADT that supports mutual recursion among procedures. ++ Write code to (or explain how to) process mutually recursive procedure definitions, as in letrec or a similar construct. [define at the top level] - Explain the advantages and disadvantages of mutually recursive (circular) environments and closures (i.e., compare figure 3.9 and 3.10 to figure 3.11). ** Variable Assignment (3.7) + Write code to (or explain how to) implement a version of the environment ADT that supports variable assignment. + Give the value of an expression using assignment in the defined language. ++ Write code to (or explain how to) implement assignment statements or a similar construct. What changes had to be made to the interpreters? (Spring 06: add pre-increment expressions (++x) to defined language; Spring 96: add "swap" expressions to the defined language; Fall 95: explain changes needed to implement assignment) - What other statements are useful if one adds assignment to the language? + How does the presence of assignment change the denoted value domain of the defined language? - How are storage locations represented in the interpreter? - Write code to (or explain how to) implement the reference ADT. + Write code to (or explain how to) add begin expressions or some similar expression to the interpreter. + Write code to (or explain how to) add arrays to the interpreter. [arrays with array, arrayref, arraylen, and arrayset primitives] + Write code to (or explain how to) add explicit references to the interpreter. [ref with ref expressions, deref and setref primitives] ++ Explain how recursive bindings (for procedures) can be implemented as a desugaring that first uses let and then an assignment. [recursion using two passes and assignment] (Fall 97: implement letrec using let) ** Parameter Passing Variations (3.8) *** Call by reference vs. call by value and call by value-result + Write code to (or explain how to) implement call by reference. (Fall 97: What changes were made to implement call by reference?) - Be able to explain how are targets used in the interpreter for call by reference. Be able to explain how references are used in the interpreter. + Be able to explain the choices for implementing the "let" construct in a call by reference language. [let-semantics] + Be able to distinguish between call by value or call by reference mechanisms based on the output of a given expression or a description of the mechanism. - Know what calling mechanisms are used by various languages, like C, C++, Scheme, Java, and the defined language. (Fall 97: what is calling mechanism used in object version of the defined language? What mechanism is used in Scheme and Java?; Fall 95: describe mechanism used in your favorite programming language) + Draw a picture of the environment (stack), as described in class, at some point during the evaluation of an expression with call-by-value, call-by-reference, or call by value-result [drawing pictures for call by reference] [drawing pictures for call by value-result] (Spring 99 draw pictures for programs using various mechanisms) ++ Give the output of an expression in the defined language using call-by-value, call-by-reference, or call by value-result. (Spring 06, Spring 05, Spring 04, Fall 01, Fall 99, Fall 98, Fall 97, Spring 96, Fall 95: give output of program using various mechanisms) + Explain how to handle the case when a non-variable is passed by reference. + Be able to explain what variable aliasing is, and how it might arise in a call by reference language. - What difficulties are caused for reasoning by variable aliasing? + Write code to (or explain how to) implement call by value-result. [call by value-result] - Write code to (or explain how to) implement call by result. - How could a language design support two or more parameter passing mechanisms at the same time? - Explain the differences between the direct and indirect model of arrays or other objects. - What array model is used in Scheme? Java? C++? (Fall 97: array model used in Scheme and Java; Fall 95: array model of favorite programming language) - Draw pictures with various array mechanisms for a given program. (Spring 99, Fall 98, Spring 96, Fall 95: draw pictures for programs using various mechanisms and array models) + Give the output of an expression in the defined language with arrays using call-by-value, call-by-reference, or call by value-result and either the direct or indirect model of arrays. (Spring 99, Fall 98, Fall 97, Spring 96, Fall 95: give output of program using various mechanisms and array models) *** Call by name and call by need - Explain how users can delay evaluation of expressions in a language like Scheme. + Write code to (or explain how to) implement call by name and call by need. What does the interpreter do to make evaluation lazy? What is a thunk? What kinds of targets are used in the interpreter? How does eval-rand work? [conz, caz, cdz, random] + Explain how to tell if a feature (type of expression) is lazy or eager from the code of the interpreter? What code does that? [let-semantics] - What are the differences between call by name and call by need? ++ Give the output of an expression in the defined language using call-by-name and call-by-need (Spring 06: give value of expression using call-by-name and call-by-need) - Explain the advantages and disadvantages of call by name and call by need - What is memoization and how is it achieved in the call by need interpreter? + What kind of examples can be used to show whether a feature is lazy or eager? What output of these examples would show it? [let-semantics] (Spring 05: given output, say whether parameter passing is lazy or eager) + Write code in the defined language that takes advantage of a lazy interpreter to define a control construct as a procedure. [unless] + Compare the use of lazy evaluation vs. macros for defining control structures. [are macros needed?] + Implement, or explain how to implement lazy data structures. [conz, caz, cdz, random] ** Statements (3.9) + What is the difference between a statement and an expression? (Spring 05: explain difference between statements and expressions) - What is the difference between an if-statement and an if-expression? - What is the difference between an assignment statement and an assignment expression? - How are block statements implemented in the interpreter? - Explain how statements and expression interact in the defined language's interpreter. - Implement (or explain how to implement) new statements in the interpreter. [do-while] [assert statements] + Explain how to change the grammar of expressions to avoid side effects in expressions? [side-effect free expressions] - Design and implement a new kind of loop statement [for loops] (Fall 97: implement foreach loop) * Object-oriented Programming Languages (5) ** Concepts (5.1-5.2) - Explain the following concepts in the defined language, and how they are implemented in the interpreter: - state, instance variables - methods - instance, object - instance variable - class - message - subclass, child, descendant - superclass, parent, ancestor - single inheritance - inheritance of instance variables - inheritance of methods - self - super call - method overriding - dynamic dispatch - polymorphism + How is an object like a closure? - Translate an object with one method into a Scheme closure (Fall 97: How is a closure like an object?) - Explain the following concepts: - class variable - multiple inheritance - How might the above be implemented in the interpreter? - What is the region of a field declaration? Its scope? What is shadowing for fields? Explain an example involving shadowing of fields. - What kind of privacy do fields have in the defined language? - When does one method override another? + Given an example of code in defined language with objects, method calls, self, and super calls, give its output. (Spring 05: give output of defined language code) ** Language and its semantics (5.3-5.5) - Be able to explain the difference between a send expression and a super expression. - Be able to explain how new expressions are evaluated and how objects get initialized. - What parameter passing mechanism is used in the object-oriented interpreters? - Explain the domains used in the object-oriented interpreter. - Explain how the interpreter tracks class definitions. - Explain how the interpreter tracks methods. - What are the four procedures that need to be defined in the interpreters to implement the new expressions in the object-oriented language? - What is the (final) representation of objects? classes? methods? - How are fields accessed? What is the layout of an object? [fieldref and fieldset] - How does the interpreter guarantee that superclass methods can access fields of a subclass object? - What extra costs are there in a field access compared to a local variable access in a non-object-oriented language? - How are methods applied? [visibility for methods] - What extra costs are there in a method call compared to a normal procedure call? - What extra costs might there be in a language with multiple inheritance for field access or method calls? - Be able to implement in the interpreter the addition of new expressions to the language. [instanceof] [fieldref and fieldset] - Be able to write recursions over class hierarchy, i.e., the subclass-superclass relation [instanceof] (Spring 05: implement checked assignment) - Be able to implement new features in an object-oriented language. [visibility for methods] (Spring 05: implement checked assignment) * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.