Final Exam CSE 340 Tuesday, May 6, 8:30-10:30 AM Towne 307 Open-book, open-notes, no computers In the last half of the class we covered chapters 4-8 of EOPL (not necessarily in that order). The final exam will roughly be equally divided between continuations and object-oriented languages. However, answering some of the exam questions may require that you understand material from the first half of the course, such as general Scheme programming, grammars, reduction-based evaluation, lexical/dynamic scope, closures, assignment, calling conventions and types. Notes: ">" in left--hand column marks sample questions. As in the midterm, there is no guarantee that these sample questions will cover all the sorts of questions that might be asked in the final. You should also study the related homework assignments and look at additional problems in the book for these chapters. + Continuations There's more to evaluation order than just arguments: how do recursive evaluations of sub-expression continue with the rest of the evaluation? A continuation, like a to-do list, exposes the staging of evaluation needed to recur on subexpressions. The "eval-expression" function takes three arguments: expression, environment, and continuation. When it arrives at a value, it applies the continuation. When it starts evaluations a subexpression, it extends the continuation. - execution of continuation-based programs (including interpreter) (define-datatype cont (halt-cont) (times-cont n cont)) (define fact-cont (lambda (n cont) (display "(fact-cont ") (display n) (display cont) (display ")") (if (zero? n) (apply-cont cont 1) (fact-cont (- n 1) (times-cont n cont))))) (define apply-cont (lambda (cont n) (display "(apply-cont ") (display cont) (display n) (display ")") (cases cont [halt-cont () (display n)] [times-cont (n' cont) (apply-cont cont (* n n'))] > By showing every call to "fact-cont" and "apply-cont", show completely how the following expression is evaluated: (fact-cont 4 (halt-cont)) ANS: (fact-cont 4 (halt-cont)) = (fact-cont 3 (times-cont 4 (halt-cont))) = (fact-cont 2 (times-cont 3 (times-cont 4 (halt-cont))) = (fact-cont 1 (times-cont 2 (times-cont 3 (times-cont 4 (halt-cont)))) = (fact-cont 0 (times-cont 1 (times-cont 2 (times-cont 3 (times-cont 4 (halt-cont)))))) = (apply-cont (times-cont 1 (times-cont 2 (times-cont 3 (times-cont 4 (halt-cont))))) 1) = (apply-cont (times-cont 2 (times-cont 3 (times-cont 4 (halt-cont)))) 1) = (apply-cont (times-cont 3 (times-cont 4 (halt-cont))) 2) = (apply-cont (times-cont 4 (halt-cont)) 6) = (apply-cont (halt-cont) 24) = 24 - environment vs. procedural representation of continuations (7.2) > Given factorial above, written with the data-structure representation of continuations, rewrite it with the procedural representation. ANS: (define fact-cont (lambda (n cont) (if (zero? n) (cont 1) (fact-cont (- n 1) (lambda (v) (cont (* v n))))))) - implementing an interpreter in assembly language (7.3) - extending a continuation-passing interpreter - exceptions (7.4) - user level control of continuations: let/cc and call/cc (Hw 7) - multi-threading (7.5) - conversion to continuation-passing style (ch 8) - head and tail positions - simple expressions and tail-form (homework 8 -- Practice) + Object-Oriented languages - untyped languages - possible variations in semantics (class based vs. object-based, static overloading, dynamic overloading, multiple inheritance) - scoping of methods and fields > What is the value of the following program? class c1 extends object method initialize() method m() 1 class c2 extends c1 method m() 10 method n1() send self m() method n2() super m() class c3 extends c2 method m() 100 let o = new c3() in +(send o n1(), send o n2()) ANS: The result is 101, because n1 uses the m in c3, while n2 uses the m in c1. - optimizing the interpreter of a Java-like language (flat representation of fields and methods) - typed languages - determining whether expressions should type check > What is the type (if any) of the following program? class c extends object method int initialize(int x) x new c(5) ANS: The type is "c" > What is the type (if any) of the following program? class c extends object method int initialize(int x) x new c(new c(10)) ANS: No type, because the initialization method, called by "new", wants an "int" instead of a "c". - type additions specific for objects - cast, instanceof - abstract methods and classes