Topics for Exam 4 in Com S 342 This test covers topics from homeworks 6-8. 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, Chapter 3, sections 3.1-3.8 up to p. 114 Interpreters for chapter 3, in files $PUB/lib/3-*.scm and loaded files. If you have extra time, you may also want to look at the following readings: Essentials Of Programming Languages, Section 3.9 and 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) ** 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. - 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] (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?] (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 an 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?] + What's the difference between the defined language's truth values and those of Scheme? + Write code to (or explain how to) make the interpreter processes if expressions. [add if] + 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] (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 (Fall 01: calculate value of if with lists) ++ Write code in the defined language using let [calculate 3**8] + 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 have to pass the environment to recursive calls of eval-expression? (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? (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] (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] (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 (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. + 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) + Give the value of an expression using assignment in the defined language. - Write code to (or explain how to) implement a version of the environment ADT that supports variable assignment. + 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) - How does the presence of assignment change the denoted value domain of the defined language? - 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] ** Parameter Passing Variations (3.8) + 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 or call-by-reference [drawing pictures for call by reference] [call by value-result] ++ Give the output of an expression in the defined language using call-by-value or call-by-reference. (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. - Write code to (or explain how to) implement call by reference. (Fall 97: What changes were made to implement call by reference?) - Write code to (or explain how to) implement call by value-result. ** The Rest of Chapter 3 This won't be on the test, however reading it might might give you some more perspectives on what we are covering. In particular, section 3.9 may help clarify some issues for you. The rest of section 3.8 (past page 114) is also interesting... * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line. See also the hints for reading chapter 3 and the interpreter code, found in the beginning of homework 6.