Sample Final 3

Remember: the correct answers are short. Also, questions that ask for a verbal answer rather than code should still be answered correctly and based on facts.

A memoized function is a function that “remembers” its answers. That is, you construct a function as usual, except that each time it is applied, it will consult a local cache for the function. If there is no cached answer for the input value, then we compute it, store the result in the cache, and return it. Next time the function is called with the same value, it will just retrieve the result from the cache.

In this question, you will implement a memoization function — a higher order function that consumes a unary (numeric) function and produces a memoized version of it. It is common to use a hash table for the cache, but in this question you will implement it with an association list, stored in a box so you can add new cached results to it.

For the cache we will use these values:

1. Your job is to write a memoize function, such that (memoize f) is a memoized version of the input f, which is a one-argument numeric function. (Hint: see the make-counter definition in Lecture #16.) For example:

   (: fib : Number -> Number) (define (fib n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))

   and now to get a memoized version of fib:

   (define mfib (memoize fib))

2. Also, consider this interaction:

   > (mfib 40) 165580141 ; after a long time > (mfib 40) 165580141 ; immediately > (mfib 39) 102334155 ; after a long time still

   What’s wrong here — why is the first expression taking a long time to compute, and why is the last one taking a long time too, given that we’d expect the call with 40 to get the result of 39 already cached. (As a semi-hint, the next question will solve the problem.)

1. Is there a point in implementing some memoization facility in a lazy language? Explain (very) briefly.
2. Using the automaton macro, write an expression that would fail if Scheme macros were not hygienic. (Hint: this is easy, since un-hygienic macros break easily, as we have seen in class.)
3. In the automaton macro code, we relied on Scheme’s tail-call optimization in a crucial way: describe how, and show an example for code that would fail if Scheme didn’t have this property.

We want to extend the Toy evaluator with a let/cc, as in Scheme. The first part of this is straightforward:

• we add a new rule to the BNF:

  <TOY> ::= <num> | ... | { let/cc <id> <TOY> } | ...

• add a corresponding variant to the AST type definition:

  (define-type TOY ... [LetCC (name Symbol) (body TOY)] ...)

• and extend the parser for the new construct:

  ... [(cons 'let/cc more) (match sexpr [(list 'let/cc (symbol: name) body) (LetCC name (parse-sexpr body))] [else (error 'parse-sexpr "bad `let/cc' syntax in ~s" sexpr)])] ...

The second part is in the evaluator — where the real work is done. There are two common ways to implement continuations: either convert the input program to be in continuation passing style, or use the underlying system to provide them for us. The first way will involve substantially changing the evaluator, so we go with the second: expose the continuation facility in our underlying system. Specifically, we will use Scheme’s let/cc to implement our own let/cc. So, assuming that we have let/cc in our Scheme (with the right type), you need to write the evaluation case for the new Toy let/cc:

• Use let/cc to capture the evaluator’s continuation. Remember: the syntax of Scheme’s let/cc is (let/cc <id> <expr>) for a Scheme identifier and expression.
• In the expression that you put in your own let/cc, the identifier that you specify is bound to a continuation as a scheme function — you need to turn it into a value that is accessible for user code. You should use a PrimV value for this (you will need to construct the PrimV yourself, you can’t use scheme-func->prim-val — so pay attention to the types of the PrimV constructor).
• Finally, you should use extend to bind the user’s identifier to the new value, and continue the evaluation of the user’s expression in this environment. (Again, note the input types for extend.)

What all of this is doing is capturing the actual evaluator’s continuation, and wrapping it in a user-accessible PrimV — so we’re effectively embedding a PLT Scheme feature into our own language. As with other cases of feature embedding that we’ve seen, the result will not be an explanation of how continuations are implemented — and more specifically, you need to know very little about continuations to answer this question.

1. (letrec ([weird (list weird weird)]) (length weird))

2. (letrec ([x (+ z 1)] [y 3] [z (* y 2)]) x)

3. (letrec ([x (+ z 1)] [y (/ x 2)] [z (* y 2)]) x)

We start with the simple Picky language that we’ve been using in class to demonstrate static typing, and extend it with pairs. This means that we extend the syntax with cons, car, and cdr, and we also add a new Pair(A,B) type constructor:

Your job is to finish this work: write the three type judgement rules for the new operators — all three will use the new type constructor in some way.