Topics for Test on EOPL Sections 3.5-3.6, 4.5-4.6, 5.1-5.4 * 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. WARNING: you won't have time to learn the material on during the test. Just write down what would be too tedious to remember otherwise. Topics marked `+' below are more important than topics marked `-' below. In general, things that are more like the last part of homework 5 and homework 6 will be more important. I have cited [in square brackets] problems from homeworks 5 and 6 that are illustrate the relevant ideas for this test. Note that I may ask some questions that integrate ideas from previous parts of the course, although this test will mostly focus on this part of the course. Don't panic, this test will be like all of the other tests in this course. * Chapter 3 ** data abstraction (3.5) + What is the importance of data abstraction? Can you give examples? (Both positive and negative ones) + What is the importance of representation independence? Can you give examples? (Both positive and negative ones) [transparent reps] ++ What implementation techniques (in Scheme) enforce representation independence? [representation independence and transparency, i.e., HW5, problem 31] ++ What implementation techniques (in Scheme) give transparent representations? Which give opaque representations? [representation independence and transparency, i.e., HW5, problem 31] + how does the type of an ADT's operations relate to the types of the implementation's operations? [vector rep of records, list rep of records] * Transformation of Procedural to Record Representations (3.6) + Be able to implement an ADT using a procedural representation [infinite-set-ADT] [store-proc-rep] [make-closure-with-apply] ++ Be prepared to transform a procedural representation of some data to a record representation, or vice versa [infinite-set-ADT-record] [store-record-rep] * Chapter 4 ** Section 4.5 ** reduction rules (This won't be on the test. But it might be good to skim over sections 4.2 and 4.3. Some students last year found that this really helped them understand lambda, and it's interesting...) ** sequencing and imperative programming (4.5) + What is a side-effect? Give an example. [cell ADT transcript] + What problems do side effects cause for reasoning about programs? What is referential transparency? - what is the order in which side effects happen in: a begin, in a call to a Scheme procedure, in a call to map or for-each? + Know how to use begin and implicit begin in Scheme programs. Give the output of Scheme expressions using implicit begin. - know what display, newline, write, read, read-char do in Scheme. what are these like in other languages? + how is output of a value different from returning a value? + How is data structure mutation different from assignment? ++ Know how to use vector-set!, and set! in programs, and how to give results or output of programs that use them. - Know how to use set-car!, set-cdr!, vector-set!, and set! in programs, and how to give results or output of programs that use them. + Be able to answer questions about the behavior of the cell ADT. (e.g., given an example, what is the output?) ** variable assignment and sharing (4.6) ++ Be able to write or explain the behavior of programs with shared bindings, including those in the OO style. [store-message-rep] - be able to draw diagrams showing the effect of vector-set!, and set! when there is sharing - be able to draw diagrams showing the effect of set-car!, set-cdr! when there is sharing * Chapter 5 ** simple interpreter (5.1) - give value of simple expressions in the defined language [transcripts for run and read-eval-print with 4 commas] [calculate 3**8] + explain how interpreter deals with literals, variable references, and applications of built-in procedures ++ add (or explain how to add) new built-in variables (like emptylist) and procedures (like minus or cons) to the defined language's interpreter. [add minus, cons, car, cdr, list, and emptylist] [add if, equal, zero, greater, less, null] + What does each of the procedures in the simple interpreter do? (Describe its job.) What's its type? + What's the difference between a denoted value and an expressed value? ** conditional evaluation (5.2) + 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? + explain how interpreter processes if expressions + how does it follow the grammar? ++ add (or explain how to add) new conditional constructs (like cond, an if without an else, etc.) [add if, equal, zero, greater, less, null] ** local binding (5.3) + give value of let expressions in the defined language [calculate 3**8] + write code for (or explain how) the interpreter processes let expressions ++ write code for (or explain how) environments are used in the interpreter ++ Why do you have to pass the environment to recursive calls of eval-exp? + implement let as a syntactic sugar + explain how the definition of let gives static, as opposed to dynamic scoping. (See section 5.7.1) ** procedures (5.4) + write simple procedures using the defined language [square written in defined language] [max written in defined language] ++ what is a closure? How does the interpreter use them? Why are closures needed and how do they relate to static scoping? + explain how the interpreter processes user-defined procedures - Compare to other languages (with second-class procedures), including those that don't allow nesting (like FORTRAN/C/C++) + how would the interpreter change if we used a different representation of closures (as in the apply-proc as apply homework)? [make-closure-with-apply] - What is the difference between a syntactic sugar and implementation directly in the interpreter? - What is the type of eval-exp vs. the type of syntax-expand? ** The Rest of Chapter 5 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 5.7.1 will make it more clear what is going on with closures and why they are needed to give static scoping. * Hints You might look at the suggested practice problems in the homework, and at the old tests on-line.