Sample Final 2Date:   Tuesday, November 27th

Administrative

This exam was given in the Spring semester of 2017.

QuestionGrade 
(1) Macros and Continuations /28
(2) Type Systems /24
(3) Lazy Language /24
(4) Language Extension: Toy /24
Total /100

Question 1. Macros and Continuations28 pts

The full Racket language has for loops. The complete details of these loops are not needed for this question, it is enough to know that their general shape is

(for (...what to loop over...)
  ...body...)

These loops are used only for their side-effects. (There are also other loop forms that can collect an output list of values and more, these are also not relevant for this question.)

Just to give a little more “taste” of how these things are used, here are two examples of looping over integers and over elements of a list:

(for ([i 100]) (printf "i=~s\n" i)) ; prints numbers from 0 to 99
(for ([x (in-list l)]) (foo x))    ; call `foo` on values in `l`

We want to extend this with constructs that are common in C-like languages:

We will do that via a new forx macro. For example, the following code (reminder: when is a one-sided conditional):

(forx ([i 10000])
  (when (even? i) (continue))
  (printf "i=~s\n" i)
  (when (> i 10) (break)))

will print 1, 3, 5, 7, 9, 11.

The macro should be implemented using continuations. Here is a template for your definition:

(define-syntax-rule (forx range body ...)
  ...fill-in...)

Notes:

Question 1a.

Implement the macro. (Note: it needs to expand into a for.)

Question 1b.

What would happen if we use value of break or continue instead of directly calling it?

  1. It won’t work: we’ll get an error. Continuations have no “value” in the same way that other macros like if and define don’t have a value.

  2. It will work, but it would be useless since the continuations will become invalid as soon as we exit the loop. This means that we can pass them around as values only to eventually call them only while the loop is running.

  3. It will work, and calling them at any point – inlucding after the loop is done – will jump to the same context. Using the value of break after the loop will jump to the continuation of the loop again, and using the continue value will jump again into the loop.

  4. Continuations are stack snapshots, or in other words, they’re just buffers holding data. It is therefore not possible to call them as functions.

Question 2. Type Systems24 pts

The type system that we have discussed in class was very simple. We talked about its explict lack of overlapping types which simplifies things to the point that there is no choice for types. What if we extend the type system with a typed-racket-like union type?

Extending the picky type system with a U type constructor would require a few things. (Note that we’re talking about the type system specification here, not the code implementation.) Add the following to the Picky1 rules to get an extended system:

Question 2a.

Add a new rule for introducing a union, as a result of a conditional if expression where the two results are not restricted to have the same type.

Scratch that – I’ll do it for you as an example:

G |- C : Boolean  G |- T : t1  G |- E : t2
--------------------------------------------
        G |- {if C T E} : (U t1 t2)

Question 2b.

We also need a subtyping rule, saying that if we want to prove that E has some type t2, and we know that it has type t1 which is a subtype of t2 (written as t1 <: t2), then that proves that E has type t2 too. Since this is essentially the rule, I’ll do it for you also:

G |- E : t1  t1 <: t2
----------------------
    G |- E : t2

Note that the right goal is not a typechecking goal, it is rather a check on the actual types to verify that the first is a subtype of the second. We therefore need to specify the subtyping rules too. We’ll do that in plain logic terms (or rather pseudo-logic, to keep it less formal):

Question 2c.

Specify the subtyping rules for U – union types. Well, I can just as well do this quick bit for you too:

t1 <: (U t1 t2)

This works as a specification of the subtype relation, together with a bunch of trivia that we won’t care about (like transitivity, reflexivity, etc).

Question 2d.

What about function types? Aha! Finally something that I’ll leave for you to do. This should describe the subtype relationship between two function types, say (t1a -> t2a) and (t1b -> t2b). You need to express the relationshiip between the two types in the form of some implication, some logical rule like the one in (c) (except that this one has some implication).

Question 2e.

Finally, all of that is not too useful if we don’t have a flip side of the if rule – some way to use a union type. The way typed racket does this is via “occurrence typing”, which is a rule about specific uses of an if conditional with a type-distinguishing predicate that can identify members of a specific type. For example, the number? predicate is true only for values that are Numbers. This is described by a rule that you need to complete:

...something about E1...  ...something about E2...
---------------------------------------------------
          G |- {if {number? x} E1 E2} : t

Fill in the left goal specification for E1. (Ignore the right goal.)

Question 2f.

Why didn’t I ask you to fill in the right goal in the above rule?

  1. It’s trivial: it would be completely symmetric to the left goal.

  2. It’s easy: symmetric to the left goal except that x is not a number, and in our simple type system that means that x must be a boolean.

  3. It’s not needed, since if the predicate is false, then it doesn’t say anything on E2.

  4. It’s more difficult since it requires also a notion of type subtraction which we didn’t define.

Question 3. Lazy Language24 pts

Consider the core eval of our lazy Sloth language:

(: eval : SLOTH ENV -> VAL)
;; evaluates SLOTH expressions.
(define (eval expr env)
  ;; convenient helper
  (: eval* : SLOTH -> VAL)
  (define (eval* expr) (ExprV expr env))
  (cases expr
    [(Num n)  (RktV n)]
    [(Id name) (lookup name env)]
    [(Bind names exprs bound-body)
    (eval bound-body                                      ; (1)
          (extend names (map eval* exprs) env))]          ; (2)
    [(Fun names bound-body)
    (FunV names bound-body env)]
    [(Call fun-expr arg-exprs)
    (let ([fval (strict (eval* fun-expr))]                ; (3)
          [arg-vals (map eval* arg-exprs)])              ; (4)
      (cases fval
        [(PrimV proc) (proc arg-vals)]
        [(FunV names body fun-env)
          (eval body (extend names arg-vals fun-env))]    ; (5)
        [else (error 'eval ...)]))]
    [(If cond-expr then-expr else-expr)
    (eval*                                                ; (6)
      (if (cases (strict (eval* cond-expr))                ; (7)
            [(RktV v) v] ; Racket value => use as boolean
            [else #t])  ; other values are always true
        then-expr
        else-expr))]))

On review of this code, something looks fishy: we use eval* as a way to delay evaluations and get lazy semantics as a result – but how come we didn’t convert all of the eval calls to be lazy? (Note: we’re ignoring the eval/eval* difference of an extra argument – focus only on eval as plain evaluation and eval* as wrapping it in an ExprV promise.)

So let’s review each of these calls.

Clearly, in (3) and (7) there is no difference between using delayed evaluation or not, since the result is fed into strict anyway (and we used eval* just because it was more convenient).

Question 3a.

(2) and (4) are similar, due to the similarity of applying a function and using a local binder (recall with vs call with an immediate fun).

So let’s focus on just (2): is that lazy eval* needed? If it is needed, demonstrate the need by writing an expression that will evaluate in a wrong way if it wasn’t lazy. If it’s not needed, explain why (in a short-one-sentence comment).

Question 3b.

(1) and (5) are also similar, so consider only (1). How come it is using the plain non-lazy eval? Is this a bug? If so, demonstrate the bug with an expression that is evaluated in a wrong way, and if it is not a bug, explain why that particular evaluation doesn’t need to be delayed (in a short-one-sentence comment).

Question 3c.

Finally, what about (6)? It uses a delayed evaluation – is that needed? Again, if it is, demonstrate the need by writing an expression that will evaluate in a wrong way if it wasn’t lazy. If it’s not needed, explain why (in a short-one-sentence comment).

Question 4. Language Extension: Toy24 pts

In the “Turbo Toy” homework (Homework #12) we have implemented an extension to the Toy language that has by-reference rfun functions. In contrast, C achieves similar functionality via an alternative approach: extend the language with a new kind of “reference” values which hold the box that is the location of some variable.

This kind of an extension should be a familiar process: we’re taking some feature of our language that is currently second-class, and we promote it to a first class value that is accessible from inside the language. In the C case, this means exposing raw machine pointers; and in our case, we take the boxes that are used to store binding values and expose them. These boxes are currently available only in the extended Toy implementation – in Racket code. We will make them accessible inside the language, so they can be passed around and used as any other kind of values in Toy code.

To get a quick idea of how this extension will look like, here is a test that will eventually work:

(test (run "{bind {{x 1}
                  {incref! {fun {x} {setref! x {+ x 1}}}}}
              {bind {{r {ref x}}}
                {incref! r}
                {incref! r}
                r}}")
      => 3)

As usual, we begin by extending the BNF,

<TOY> ::= <num>
        | <id>
        | { ref <id> }        ; <-- new special form
        | { set! <id> <TOY> }
        | ...same...

the AST type definition,

(define-type TOY
  [Num  Number]
  [Id  Symbol]
  [Ref  Symbol]          ; <-- new variant
  [Set  Symbol TOY]
  ...same...)

and the parser is extended accordingly. We then extend the kind of TOY values with a new “reference” type:

(define-type VAL
  [BogusV]
  [RktV  Any]
  [RefV  (Boxof VAL)]              ; <-- new value type
  [FunV  (Listof Symbol) (Listof TOY) ENV Boolean] ; `byref?' flag
  [PrimV ((Listof VAL) -> VAL)])

And we now proceed to implement the new functionality: evaluating the new special form and a function that uses the new kind of values.

Question 4a.

To evaluate the new special form, we need to have an additional case in the body of the eval function for a Ref syntax, which should return a new RefV value holding the appropriate box:

[(Ref name) (RefV ...fill-in...)]

Fill in the missing code here.

Question 4b.

Now that we have a working way to construct these values, we need to implement a way to use them. We do this with a new setref! primitive function, that can be used as:

{setref! foo bar}

to set the value referenced by foo to the bar value. However, we need to implement it directly rather than construct it with racket-func->prim-val. First, the binding is added with:

(define global-environment
  (FrameEnv (list (list '+ (racket-func->prim-val +))
                  ...same...
                  (list 'setref! (box (PrimV setref-function)))
                  ;; values
                  ...same...)
            (EmptyEnv)))

and now we need to implement it as setref-function. We need to follow the same calling protocol as for all primitive functions, meaning that it should be a function from a list of VAL inputs to a VAL output, and and this means that we need to check that we’re getting the right number of input arguments. Finally, we also need to make sure that the value that we receive is indeed a RefV:

(: setref-function : (Listof VAL) -> VAL)
;; the implementation of the builtin "set-ref!" function that
;; changes the contents of a ref value
(define (setref-function args)
  (if (= (length args) 2)
    (cases (first args)
      [(RefV b) ...fill-in...]
      [else (error 'setref! "got a non-ref value: ~s" (first args))])
    (error 'setref! "bad number of arguments, expecting two")))

Fill in the missing code.

(Hint: there are two expressions that are needed there. (But both are very short.))

Question 4c.

Now comes an important part: users will often want features that make their life easier, even when in the long run the potential for problems is higher. In this case, your users want to be able to treat these reference values (RefV for you) as if they were not there. For example, in the sample test code given above note that the mutation expression is:

{setref! x {+ x 1}}

so x is used as a plain value too. To give our users the maximum comfort (and maximize their chance of shooting their feet), we’re going to implement this. First, we write a utility function that consumes some VAL, and if it happens to be a RefV, it will dereference it, otherwise it will return the value it received as-is:

(: deref-value : VAL -> VAL)
;; utility function that automatically converts a ref value to a
;; plain value
(define (deref-value val)
  ...fill-in...)

Fill in the missing part. Note that this is again a very simple function.

Question 4d.

Finally, we need to use this deref-value in places where a value is needed. The first such place is in the primitive function application, in the function that racket-func->prim-val uses: unwrap-rktv. This code:

(cases x
  [(RktV v) v]
  [else (error 'racket-func "bad input: ~s" x)])

needs the value held in a – so we change it to:

(cases (deref-value x)
  [(RktV v) v]
  [else (error 'racket-func "bad input: ~s" x)])

There are three more places that need to use deref-value (in eval and in run), find them. You only need to specify which expressions need it, there’s no need to actually change the code.