Sample Final 1Date:   Tuesday, November 27th

Administrative

This exam was given in the Fall semester of 2016.

QuestionGrade 
(1) Racket Programming /26
(2) Extending Racket: Macros /18
(3) Lazy Programming /18
(4) Type Systems /30
(5) Continuations /16
Total /108

Question 1. Racket Programming26 pts

One of the major ways in which Racket diverged from other Scheme implementations was when lists (and cons cells in general) were made immutable. In other Schemes there are two operations for mutating pairs: set-car! and set-cdr!, which change what the car part (or first) and the cdr part (or rest) point to. Note that set-car! and set-cdr! return a void result (i.e., their output type is Void).

Note also that in a world where cons is used only for lists, set-cdr! should be used with a list, otherwise the pair that it sets becomes something that is not a proper list.

Using these, a number of popular “destructive” utilities can be implemented, usually with the idea of reducing memory use, both overall, and the amount of work the garbage collector has to do. For example, consider this variant of map:

(define (map! f l)
  (when (pair? l)
    (set-car! l (f (car l)))
    (map! f (cdr l))))

This can be used in cases when we know that the input list is no longer needed, so we mutate it into the output list. Note, however, that calling this map! function is done in a different way than map, which can be seen in its type: this version would return a Void.

Question 1a.

To fix this, we can rewrite map! so the above is an internal helper function — fill in the missing part in the following (write only the missing part):

(define (map! f l)
  (define (helper! l)
    (when (pair? l)
      (set-car! l (f (car l)))
      (helper! (cdr l))))
  fill-in)

Question 1b.

What would be a good type declaration for this fixed version of map!?

  1. (: map! : (All (A B) (A -> B) (Listof A) -> (Listof B)))
  2. (: map! : (All (A B) (A -> B) (Listof A) -> (Listof (U A B))))
  3. (: map! : (All (A) (A -> Any) (Listof A) -> (Listof Any)))
  4. (: map! : (All (A) (A -> A) (Listof A) -> (Listof A)))
  5. (: map! : (Any -> Any) (Listof Any) -> (Listof Any))
  6. (: map! : (All (A) (A -> Void) (Listof A) -> Void))

Question 1c.

Another common destructive utility is reverse! which reverses a list “in-place”. The idea is to flip the cdr pointers back as we make our way down the list. This can also be done with a local helper function. Complete the following definition (write only the helper definition, no need for types):

(define (reverse! l)
  (define (helper! l r)
    fill-in)
  (helper! l null))

Note that this function changes the structure of the list rather than its contents, so you should use set-cdr!. Another hint: you will probably need either a let or a begin.

Question 1d.

The reason that the Racket implementors decided to make pairs immutable can be demonstrated by a nasty surprise that results from uses of this kind of mutation. To do this, assume that the following expressions are entered at the REPL, and write the printed values of the last two expressions:

> (define a (list 1 2 3))
> (define b (cons 0 a))
> (reverse! b)
'(3 2 1 0)
> a
fill-in
> b
fill-in

Question 2. Extending Racket: Macros18 pts

As we have seen, there are cases where dynamic scoping is useful, in particular for creating “dynamically customize-able bindings”. We mentioned the fact that Racket implements this via parameters. Before such a solution was popular, an approximate hack that was used was a form called fluid-let. The idea is that when

(fluid-let ([x E1])
  E2)

is evaluated, the following happens:

All of this can be implemented via a macro. Here is an interactive example of using this macro:

> (define x 1)
> (define (print-x) (printf "x = ~s\n" x))
> (fluid-let ([x 2]) (print-x) (+ x 3))
x = 2
5
> x
1

Implement fluid-let as a macro. For simplicity, make it a macro that handles exactly one “dynamic” binding, no more, and no less.

Question 3. Lazy Programming18 pts

An interesting puzzle is how to continue the following sequence:

1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 1, 3, 2, ...

This is a self-referential sequence: if you read the numbers in pairs, you’ll see that this sequence starts with 1, 1 and continues with a description of itself (as a run-length encoding). (This is described in more details in this page of the OIES.)

You need to implement this infinite list in our #lang pl lazy language. Given your implementation, we should be able to define the list with:

(define puzzle (cons 1 (cons 1 (cons 2 (cons 1 fill-in)))))

and get it to be the solution sequence:

> (take 120 puzzle)
'(1 1 2 1 1 2 2 1 2 2 1 1 2 2 2 1 3 2 1 1 1 3 1 2 3 1 1 3 1 1 1 2 1
  3 2 1 1 3 3 1 1 2 1 1 1 3 1 2 2 1 2 3 2 1 1 2 3 1 1 3 1 1 2 2 1 1
  1 2 1 3 1 2 2 1 1 2 1 3 2 1 1 3 2 1 2 2 3 1 1 2 1 1 1 3 1 1 2 2 2
  1 1 2 1 1 1 3 1 2 2 1 1 3 1 2 1 1 2 2 1 3)

Question 3a.

You need to implement this: fill in the missing part in the above definition, as well as any utillity function you need to make. Very thick and definitely non-subtle hint: look at the midterm solution for the first question (but don’t copy it blindly). [Another thick hint: since we build the description from the first 1,1, but we included the following 2,1, you will need a rest-of-rest there too, or the cddr function.]

Question 3b.

Note that the definition of puzzle starts with the first four elements instead of just the first two. Why is that? In other words, what would we get if we started with just the first two values of 1,1? (A short answer for this!)

Question 4. Type Systems30 pts

In this question we will extend the type system that we have seen in class so that in addition to the “kind of resulting value” property that we dealt with, it will also keep track of side-effects. First, we will do that for the language definition — we’ll use the Picky2 language for our work.

We start with the BNF which is extended with a set! expression (just so we have some side-effects), and we also extend the type so there’s an <STYPE> that wraps the usual type with a Pure or Impure that specify expressions that have no side-effects, and expressions that do respectively.

<PICKY> ::= <num>
          | <id>
          | { + <PICKY> <PICKY> }
          | { - <PICKY> <PICKY> }
          | { = <PICKY> <PICKY> }
          | { < <PICKY> <PICKY> }
          | { fun { <id> : <STYPE> } <PICKY> }    ; <-- STYPE
          | { call <PICKY> <PICKY> }
          | { with { <id> <PICKY> } <PICKY> }
          | { if <PICKY> <PICKY> <PICKY> }
          | { set! <id> <PICKY> }                ; <-- new
<STYPE> ::= (Pure <TYPE>)
          | (Impure <TYPE>)
<TYPE>  ::= Num | Number
          | Bool | Boolean
          | { <TYPE> -> <TYPE> }

The idea is that a type in this extended language is either a (Pure ...) or an (Impure ...) as an outer wrapper around the types that we have used previously. The typing axioms and judgments should be adjusted for this, for example, the two axioms about numerals and identifiers will now specify a Pure type (since there are no side effects in either of them):

Γ ⊢ n : (Pure Number)

Γ ⊢ x : (Pure Γ(x))

Continuing with the rule for smaller-than, to take a simple example, we get this, which is a bit tedious just because we use simple pattern-matching-like specification for these things:

Γ ⊢ a : (Pure Number)  Γ ⊢ b : (Pure Number)
—————————————————————————————————————————————
        Γ ⊢ {< a b} : (Pure Boolean)

Γ ⊢ a : (Impure Number)  Γ ⊢ b : (Pure Number)
———————————————————————————————————————————————
          Γ ⊢ {< a b} : (Impure Boolean)

Γ ⊢ a : (Pure Number)  Γ ⊢ b : (Impure Number)
———————————————————————————————————————————————
          Γ ⊢ {< a b} : (Impure Boolean)

Γ ⊢ a : (Impure Number)  Γ ⊢ b : (Impure Number)
—————————————————————————————————————————————————
          Γ ⊢ {< a b} : (Impure Boolean)

To make a long story short, we’ll assume that all other rules are adjusted properly. You only need to do the following:

Question 4a.

Define the type judgment for a set! expression. To do this, you need to know its semantics… For this extension, we’re going to say that to evaluate a {set! x E} expression, we evaluate E, assign the result to x (mutate it), and return that result. (That is, the mainstream feature where assignment as an expression returns the newly assigned value.) Another thing that you need to know is that set! cannot change the type of an identifier.

Now you can write this rule (which might need several instances similar to how the smaller-than rule above has four “clauses”).

Question 4b.

Now, for the code extension: first, the AST types are extended according to the BNF:

(define-type PICKY
  [Num  Number]
  [Id    Symbol]
  [Add  PICKY PICKY]
  [Sub  PICKY PICKY]
  [Equal PICKY PICKY]
  [Less  PICKY PICKY]
  [Fun  Symbol STYPE PICKY]        ; <---
  [Call  PICKY PICKY]
  [With  Symbol PICKY PICKY]
  [If    PICKY PICKY PICKY]
  [Set  Symbol PICKY])

(define-type STYPE
  [PureT  TYPE]
  [ImpureT TYPE])

(define-type TYPE
  [NumT]
  [BoolT]
  [FunT TYPE TYPE])

And assuming that everything else was done (ie, all of the TYPEs were converted to STYPEs when needed etc), you need to write two pieces of code from the typecheck* function:

Write the branch that would typecheck a Set expression:

[(Set id expr) fill-in]

Question 4c.

To deal with the arithmetics, we’ll change the two-nums helper so it also takes the type to return, so it’s used as follows:

[(Add  l r) (two-nums l r NumT)]
[(Sub  l r) (two-nums l r NumT)]
[(Equal l r) (two-nums l r BoolT)]
[(Less  l r) (two-nums l r BoolT)]

You now need to change the definition of two-nums so that it does the right thing based on the purity of the two expressions.

Question 5. Continuations16 pts

In the final exam that was given last semester, students had to implement a CPS rule for converting if expressions. Reminder: the solution that was given is:

[(CPS (if C T E))
(lambda (k)
  ((CPS C)
    (lambda (c)
      (if c ((CPS T) k) ((CPS E) k)))))]

And a little shorter alternative:

[(CPS (if C T E))
(lambda (k)
  ((CPS C)
    (lambda (c)
      ((if c (CPS T) (CPS E)) k))))]

One student had this incorrect answer:

[(CPS (if C T E))
(lambda (k)
  ((CPS C)
    (lambda (c)
      ((CPS T)
      (lambda (t)
        (if c
          (k t)
          ((CPS E)
            (lambda (e)
              (k e)))))))))]

This answer is incorrect in a way that is hard to see at first. Describe what’s wrong with it. Note: this is not an essay question. You answer should describe exactly how (if C T E) gets evaluated with this implmentation, which would explain what’s wrong with it.

As an example, the description of the correct implementation of if above is:

1. Evaluate C
2. If the result is true, evaluate T and return its result
3. Otherwise, evaluate E and return its result