Topics for Exam 4 in Com S 342 $Date: 2005/04/25 04:29:08 $ This test covers topics from homeworks 9-11 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. If you write recursive helping procedures, please give a deftype declaration for them. READINGS Essentials Of Programming Languages, Sections 3.7-.9, Chapter 5 Interpreters for these sections, found in files $PUB/lib/3-7.scm, 3-8ref.scm, 3-8name.scm, 3-8need.scm, 3-9.scm, 5-4-*.scm, and loaded files. If you have extra time, you may also want to look at the following readings: Essentials Of Programming Languages, Appendix A (especially pages 351-357) 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) ** 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 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. + 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 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 mechnisms 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 differentiates 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] + Write code in the defined lanuage 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? - 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 interepreter. [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 statment [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 implmented in the interpreter: + state, instance variables + methods + instance, object + instance variable + class + message + subclass, child, descendent + 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 an 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. ** 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] + Be able to implement new features in an object-oriented language. [visibility for methods] * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.