Sample Final 3

Date: Monday, April 26th

 
Name:

Administrative

This exam was given in the Spring semester of 2009.

Question Grade  
(1) Scheme Programming /20
(2) Language Extension: Extending Scheme /20
(3) Language Features /21
(4) Language Extension: Extending Toy /20
(5) Programming in a Lazy Language /21
(6) Type System /20
Total /122
 

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.



 

Question 1: Scheme Programming

 20 pts 

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:

null ; an empty cache (cons (list 1 2) cache) ; extending cache by mapping 1 to 2 assoc ; looking up a value (will be implemented as lookup below)
But since we need the cache to be mutable, we will need to put the cache value in a mutable box:
(box null) ; an empty cache (set-box! the-cache ...) ; change the cache
And here is the lookup function:
(: lookup : Number (Boxof (Listof (List Number Number))) -> (U #f Number)) ;; looks up the value in the cache; returns the mapped number, or ;; #f if not found (define (lookup val cache) (define (helper alist) (cond [(null? alist) #f] [(= val (first (first alist))) (second (first alist))] [else (helper (rest alist))])) (helper (unbox cache)))

  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.)


 

Question 2: Language Extension: Extending Scheme

 20 pts 

We now solve the memoization problem with a different approach: instead of a function, we implement a define-memoized macro. Using it to define a memoized fib function will look like:
(: fib : Number -> Number) (define-memoized (fib n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
This will solve the above problem; specifically, all of the interactions in this sequence:
> (fib 40) 165580141 > (fib 40) 165580141 > (fib 39) 102334155
will happen very fast. (Note that the machinery of creating an maintaining the cache is not going to reuse stuff from the first question, but you can still use lookup.)


 

Question 3: Language Features

 21 pts 

  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.


 

Question 4: Language Extension: Extending Toy

 20 pts 

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

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:

[(LetCC name bound-body) ... your code here ...]
Note that your solution should use the let/cc in Scheme to implement LetCC evaluation: what you need to do is For simplicity, ignore the fact that you’re writing code in Typed Scheme. Also, you can assume that the user’s continuation function (the PrimV value) will always be used with a single input argument, so no need to check the arguments.

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.



 

Question 5: Programming in a Lazy Language

 21 pts 

What will the following three expressions evaluate to:
  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)


 

Question 6: Type System

 20 pts 

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:

<PICKY> ::= <num> | <id> | { fun { <id> : <TYPE> } : <TYPE> <PICKY> } | { + <PICKY> <PICKY> } | { cons <PICKY> <PICKY> } ; <<<\ | { car <PICKY> } ; <<< > new expressions | { cdr <PICKY> } ; <<</ | { call <PICKY> <PICKY> } <TYPE> ::= Number | ( <TYPE> -> <TYPE> ) | Pair(<TYPE>,<TYPE>) ; <<<-- new type

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.