Sample Final 4Date:   Tuesday, November 27th

Administrative

This exam was given in the Spring semester of 2018.

QuestionGrade 
(1) Extending Racket: Macros and Side Effects /20
(2) Extending Toy /24
(3) Type Systems /18
(4) Continuations /24
(5) Language Features /24
Total /110

Question 1. Extending Racket: Macros and Side Effects20 pts

Implement a lambda1 macro that is similar to Racket’s lambda except that it produces a one-shot function that can be called just once. Some examples for clarification:

(: f : Number -> Number)
(define f (lambda1 (x) (+ x 1)))
(test (f 1) => 2)
(test (f 2) =error> "already called")
;; works for other types too
(test ((lambda1 (x) (not x)) #f) => #t)
;; works for any "shape" of arguments, even including types
(test (map (lambda1 ([x : Number]) (* x x)) '(2))
      => '(4))
(test (map (lambda1 ([x : Number]) (* x x)) '(2 3))
      =error> "already called")
;; works for less/more than one argument too:
(test ((lambda1 () 123)) => 123)
(test ((lambda1 ([x : Number] [y : Number]) (+ x y)) 2 3) => 5)
;; this works since each `make-f` creates a new one-time `f`
(: make-f : (-> (Number -> Number)))
(define (make-f) (lambda1 (x) (+ x 1)))
(test ((make-f) 1) => 2)
(test ((make-f) 2) => 3)

The limitation should apply only for a successful application, so if there was an error during a call, the resulting function should still be callable. Some test cases to demonstrate this:

(: 1-over : Number -> Number)
(define 1-over
  (lambda1 (n)
    (if (zero? n)
      (error '1-over "division by zero")
      (/ 1 n))))
;; first run is an error
(test (1-over 0) =error> "division by zero")
;; so it can be called again, returning the `1-over` answer
(test (1-over 2) => 1/2)
;; ;; and now it cannot be called anymore
(test (1-over 3) =error> "already called")
;; ;; no matter what input it gets
(test (1-over 0) =error> "already called")

Implement this macro. Assume that you’re working in #lang pl, which means that types are used in the above — but note that our macros are not typed.

(Note: for simplicity you can assume that it has only one body expression, though you can also make it accept zero or more, or even better — one or more.)

Question 2. Extending Toy24 pts

So, there’s good news and there’s bad news. The good news is that your language (Turbo Toy, of course) was chosen by NASA to run on the next generation of remote-controlled exploration robots on other planets. (With the exception of one remote-controlled street cleaner that will be sent to the moon.)

The bad news is that this means that it is absolutely crucial that computations are reliable — especially in the harsh conditions in space where the lack of atmosphere can lead to more errors. To achieve this, you need to extend the Turbo Toy implementation with a new form: safe. The semantics of this new form should be that {safe E} evaluates E twice and aborts with a “panic” error if the two evaluations don’t return identical results. (The plan is to eventually have a third machine, and use a majority vote, but for now you’re implementing a prototype.)

Note: obviously, speed is important too, so the NASA people would prefer a compiler. But somehow they get the feeling that you didn’t really read through the relevant homework back when you were in school, so instead of requiring a compiler, they offer a 5-point bonus if you extend the compiler instead of the interpreter. So, you need to choose whether you want to start with the interpreter or the compiler. (This bonus applies to anyone that does it, not only to master students.)

First, the BNF (and the parser) is extended with the safe form:

<TOY> ::= ...same...
        | { safe <TOY> }

the AST is extended with a corresponding form:

(define-type TOY
  ...same...
  [Safe TOY])

The missing bit is the actual evaluation rule for Safe forms. Start with implementing this. (Write only the evaluation fragment for SafeDO NOT copy the whole code.)

Now that you have this, people started using it too often — and soon enough they ran into a major problem. If there is a safe nested in the dynamic scope of another safe, then the expression of the inner one gets evaluated four times. If it happens in a loop, then the number can go up exponentially.

To solve this, you could add an argument to eval (or to compiled functions, if you’re doing that) that tracks whether you’re currently in a safe expression or not. But instead, we’ll choose a more convenient (and less desirable — but this is a quick prototype…) way to achieve this is to add a global flag in a box that will keep track of this:

(: in-safe : ...)
(define in-safe ...)

Add the missing bits, and change your code so that if safe is encountered while already inside a safe, then the inner one is just ignored and will be evaluated once as usual (since the whole thing will be done twice anyway).

Note: your answer should have only this version of the evaluation fragment, no need to keep around the previous version.

[Please do either the compiler version or the interpreter version NOT both.]

[WARNING: Please don’t think that you have to do the compiler version! It can be more confusing, so you should really try it only if you’re very clear on how things should compile. If you just try some random stuff with the compiler, it is more likely that you’ll get the answer wrong.]

Question 3. Type Systems18 pts

In the last class we’ve seen the typed Picky language. The typing judgment that we had for if expressions is:

Γ ⊢ C : Boolean  Γ ⊢ T : τ  Γ ⊢ E : τ
———————————————————————————————————————
          Γ ⊢ {if C T E} : τ

This rule makes Picky different from Racket and Toy, because it requires the condition expression C to have a boolean type. Say that we want to modify the language to be like Racket and Toy — to treat any value as a boolean, and #f is the only one taken as false. (Note that the fact that #f is the only false is irrelevant for type-checking.)

There are two possible ways to do this:

Only one of these results in a sound type system — the other fails in that it leads to an unsafe language. Determine which rule is the bogus one, and provide a simple example that demonstrates that the language it defines is unsafe.

Question 4. Continuations24 pts

The exam from the last semester had the following implementation of a “bank account application” that returns the number of transactions that were done up to the point where the balance got to zero or lower:

(define (bank-app/k balance transactions k)
  (web-read/k (format "[~s] Withdraw amount" balance)
    (lambda (amount)
      (let ([new-balance (- balance amount)])
        (if (> new-balance 0)
          (bank-app/k new-balance (add1 transactions) k)
          (k transactions))))))

And here is a sample run of this app:

> (bank-app/k 100 1 web-display)
; web-read: enter (submit N) to continue the following
;  [100] Withdraw amount:
> (submit 50)
; web-read: enter (submit N) to continue the following
;  [50] Withdraw amount:
> (submit 20)
; web-read: enter (submit N) to continue the following
;  [30] Withdraw amount:
> (submit 20)
; web-read: enter (submit N) to continue the following
;  [10] Withdraw amount:
> (submit 10)
; web-display: 4

We want to redo this example with two changes that will make things more interesting. These two changes are related, so make sure you know both before you start working.

  1. We want to drop the transactions argument from the function argument. Note that I’m not saying that you should add it in some other way, but that it is completely dropped. (Note: this is effectively changing it from a (translation of a) tail-recursive definition to a non-tail-recursive one.)

  2. We also want to make change it so that the continuation that is given to the function is one that expects two inputs. Instead of one argument that represents the number of transactions, it would be two arguments that represent the number of transactions and the final balance. (It will be easier to remember this if you rename the k argument to k2.)

Combining both, the above interaction would have a different beginning and ending:

> (bank-app/k 100 (lambda (n balance) (web-display (list n balance))))
; web-read: enter (submit N) to continue the following \
;  [100] Withdraw amount:                              \
> (submit 50)                                            \
; web-read: enter (submit N) to continue the following    \
;  [50] Withdraw amount:                                  \  same
> (submit 20)                                              \  as
; web-read: enter (submit N) to continue the following      / above
;  [30] Withdraw amount:                                  /
> (submit 20)                                            /
; web-read: enter (submit N) to continue the following  /
;  [10] Withdraw amount:                              /
> (submit 10)                                          /
; web-display: (4 0)

Implement this change.

(Note: you should NOT use a helper function to do implement this.)

Question 5. Language Features24 pts

Unless told otherwise, choose the best answer in each of the following questions. (Note that there could be several answers that are correct, but one should be the most accurate.)

Question 5a.

What will happen if we use the lambda1 wrapper around the (x x) in an omega-combinator? Something like:

((lambda1 (x) (x x)) (lambda1 (x) (x x)))
  1. This will keep throwing type errors, which means that it would never be actually executed.

  2. It will fail with an “already called” error.

  3. It will run forever as usual.

  4. It is a bogus question since the omega combinator cannot be typed, so the code won’t even compile (this is not Schlac).

  5. It will work fine since lambda1 will keep recreating new one-shot functions on each call, but since this involves allocation of a box on every call, it will be much slower.

  6. It will work fine since lambda1 will keep recreating new one-shot functions on each call, but since this involves allocation of a box on every call, it will eventually consume all memory and crash.

Question 5b.

A requirement in the lambda1 question was that if an error is thrown then the function is still available for use. How does this affect its functionality?

  1. It’s a macro, so it’s a strictly syntax-level tool, and no functionality is implied by it.

  2. It requires a check that is done after calling the input function, therefore the resulting function is never tail-recursive, even if the input function is.

  3. It makes the resulting function much slower, since allowing an error through involves expensive continuation capturing.

  4. It will not have any noticeable effect.

  5. Being able to run it again after an error means that it cannot be part of a statically typed language, so it can only works in an untyped language.

Question 5c.

In Question 4, why did I ask you to drop the transactions argument rather than just using a continuation of two arguments?

  1. It wouldn’t change the code much, but it would result in a much more inefficient execution.

  2. It wouldn’t make any difference.

  3. It needs to have both changes since using a two-argument continuation mean that we cannot use it as a callback for a function that receives two arguments.

  4. If it only had the change of a two-argument continuation, then the answer would have been trivial, since k is used as-is (as expected from a translated tail-call).

  5. If it only had the change of a two-argument continuation, then the answer would have been been much more difficult since we would get two input arguments and two output values, which would mean four cases to implement in the code.

Question 5d.

You’re given a Racket REPL that is either in #lang pl untyped or in #lang pl lazy. You need to write one expression that evaluates to either 1 if it’s the former or 2 if it’s the latter (plain evaluation, no errors etc).

Write an expression that does this (a SHORT one) if possible,
–or–
write a BRIEF explanation why it’s impossible.