Topics for Exam 3 in Com S 342 $Date: 2006/12/04 16:59:15 $ This exam covers topics from homeworks 5-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. READINGS - Essentials Of Programming Languages, Sections 1.3, 2.1-2.3, 3.1-3.6 - Code Examples Web Page for the above EOPL2e sections (see http://www.cs.iastate.edu/~cs342/docs/code-examples.html) You may also want to look at the following readings if you have time: - Structure And Interpretation Of Programming Languages, Sections 1.1.6, 1.3, 2.1, 4.1 (on-line at http://mitpress.mit.edu/sicp/full-text/book) - A Type Notation For Scheme (http://www.cs.iastate.edu/~cs342/docs/typedscm_toc.html) - Revised^5 Report On The Algorithmic Language Scheme 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. * Scoping and Binding of Variables (Section 1.3) - static vs. dynamic properties ++ free and bound variable occurrences (uses) in an expression, free and bound variable names in an expression (Fall 95, Spring 96, Fall 97, Fall 98, Spring 99, Fall 00, Spring 04, Spring 05, Spring 06: free and bound variables, also in let and letrec; Fall 01: free and bound variables with nested lambdas) - combinators + you should be able to write procedures like free?, bound?, free-vars, bound-vars over various grammars, including new ones (the grammars will be provided.) [free-vars, free?, bound-vars, bound?, free-vars and bound-vars for lambda-if-exp, bound-vars in hw4] (Fall 95: count-free-occurrences, Fall 00: write free-vars over lambda with assignment expressions) + What are the free or bound variables (variable uses) in a let? + What are the free and bound variables are in a letrec? + region and scope of a declaration, hole in a scope, shadowing - you should be able to draw arrows from a variable reference to the declaration it refers to (Fall 97, Spring 99, Fall 00, Fall 01: draw arrows) - you should be able to draw contours showing the regions of variable declarations (Fall 00, Fall 01: draw contours) ++ lexical address of a variable reference ++ you should be able to give the lexical address form of an expression [lexical address idea] (Fall 95, Fall 97, Spring 99, Fall 00, Fall 01: give lexical address form) + you should be able to write parts of lexical-address [lexical-address] * Data Abstraction (Chapter 2) ** Specifying Data via Interfaces (2.1) - What is an interface? - What is a specification? + What is the importance of data abstraction? Can you give examples? (Both positive and negative ones) [lambda-helpers] + What is the importance of representation independence? Can you give examples? (Both positive and negative ones) [type checking and abstraction] (Spring 96: what is the importance of rep indep, give example) + How does the type of an ADT's operations relate to the types of the implementation's operations? [set-ops, inf-set-as-proc] (Spring 04: implement text-file with empty? and read-line procedures; Fall 01: give implementation of colors with defrep and abstract colors) ** An abstraction for inductive data types (define-datatype and cases) (2.2) + In what sense is define-datatype a syntactic abstraction? cases? [define-datatype and cases as syntactic abstractions] - What is a variant record? Give examples. What would this look like in other languages? + what does define-datatype do? How are the procedures it produces used? [bintree-to-list] - What does parse do? What does unparse do? + What is the abstract syntax for some concrete syntax? e.g., given a concrete syntax in the form of a BNF, give the corresponding define-datatype declarations. [abstract syntax for a grammar] (Spring 96: give abstract syntax for command grammar) + You should be able to write recursions over abstract syntax, using cases [eval-arith-expr, strength-reduce, bound-vars] (Fall 95: in-order traversal of tree, syntax expand "let", Spring 96: nary-sub1 over nary trees, Fall 97, desugar "and" expressions, Fall 98, strength-reduce, Spring 99, desugar when expressions, Fall 00: desugar do-unless expression, Fall 01: desugar multiple argument lambdas with "bind", Spring 04: desugar freeze and thaw expressions) * Representation Strategies for Data Types (2.3.1-2.3.3) + Be able to implement an ADT using a procedural representation [inf-set-as-proc] ++ Be prepared to transform a procedural representation of some data to an abstract syntax tree representation, or vice versa [inf-set-as-ast] (Spring 06: transform digraph; Spring 05: transform exception handlers; Spring 04: transform sparse-matrix; Fall 01: transform schedule operations (add-meeting, etc.); Fall 00: transform music-generator, transpose, note-at, etc.; Fall 98, transform image-generator, etc.; Fall 97, transform geometric regions code; Spring 96: transform 2D boards) - Be able to answer questions about the behavior of the environment ADT. (E.g., given an example, what is the output?) * 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 envrionment; 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; 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 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 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; 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). * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.