Sample Final 3Date:   Tuesday, November 27th

Administrative

This exam was given in the Fall semester of 2017.

QuestionGrade 
(1) Extending Racket: Macros /22
(2) Extending Sloth: Cat /22
(3) Type Systems /22
(4) CPS /22
(5) Language Features /20
Total /108

Question 1. Extending Racket: Macros22 pts

Emacs Lisp follows its ancestry, and it has a catch/throw pair of forms that is one of the rough predecessors to the modern try/catch construct in many languages. A quick example from the ELisp manual:

(defun foo-outer ()
  (catch 'foo (foo-inner)))
(defun foo-inner ()
  (if (< 1 2) (throw 'foo 10))
  20)

You don’t need to know ELisp to follow the above: the basic idea is that you have some catch form with a piece of data which is the tag value to catch, and somewhere while evaluating the body, a throw can be used with that tag value to “jump out” to that level, and a second argument which is the result of the catch expression. If no such throw occurs, the evaluation proceeds as usual, returning to whatever the body evaluated to.

We want to extend Racket with this functionality, but in a more “rackety” way — we’ll use proper bindings instead of arbitrary tag values. In other words, (catch x ...) will bind x to a value that can be used with throw. Here’s a simple example:

(test (* 10 (catch x (+ 1 (throw x 3)))) => 30)

and a translation of the above example requires passing the tag value to the called function (and we convert the one-sided-if to a when):

(define (foo-outer)
  (catch foo (foo-inner foo)))
(define (foo-inner foo)
  (when (< 1 2) (throw foo 10))
  20)

You need to implement both of these — catch and throw. The obvious tool to implement this is using continuations — either call/cc (or let/cc which is slightly easier to use).

One of these should be a function, and one should be a macro. Each correct definition should be very short: if you need more than one line, you’re probably doing something wrong. (No need for type declaration or purpose statement.)

Remember: calling a continuation with a value means that we “return” from that continuation with that value.

Question 2. Extending Sloth: Cat22 pts

We have discussed some of the problems of using a language that is lazy by default, such as Haskell, or our Sloth language. On the other hand, there are obviously advantages in lazy evaluation too.

One approach that attempts to get advantages from both sides is a language that is eager by default, but also has a delay expression that delays the evaluation of a specific value (as is the case with Racket’s delay that we mentioned briefly) resulting in a promise value — and these delayed values get implicitly forced into a proper value whenever their value is needed (unlike Racket, which requires using force with promise values).

We want to modify Sloth to make it into such a language: eager by default, but with a delay. (Turn it into a “Cat” language, of course, since cats are lazy when they want to; but we’ll skip the renaming.) To do this, assume that the language was properly extended to include a new kind of a {delay E} expression:

#| The BNF:
  <SLOTH> ::= ...same...
            | { delay <SLOTH> }
|#

;; A matching abstract syntax tree datatype:
(define-type SLOTH
  ...same...
  [Delay SLOTH])

(define (parse-sexpr sexpr)
  (match sexpr
    ...same...
    [(list 'delay expr)
    (Delay (parse-sexpr expr))]
    ...))

The last thing to change in addition to the above is the eval function. You need to do this. There are exactly two things that need to be done in eval, and one of them is the evaluation fragment for a Delay AST node. Write this new code fragment and specify which other part of the code should change. (This should be a specific specification of some code and its replacement; this replacement should be focused in a single place, and (very) small.)

Here are some modified Sloth tests that demonstrate the resulting language:

;; Modified laziness tests
(test (run "{{fun {x} 1} {delay {/ 9 0}}}") => 1)
(test (run "{{fun {x} 1} {delay {{fun {x} {x x}} {fun {x} {x x}}}}}") => 1)
(test (run "{bind {{x {delay {{fun {x} {x x}} {fun {x} {x x}}}}}} 1}") => 1)

And more interesting are the following tests that demonstrate the force-on-demand feature of this language:

;; Modified lazy constructor test
(test (run "{bind {{l {list {delay 1} {delay {/ 9 0}} {delay 3}}}}
              {+ {first l} {first {rest {rest l}}}}}")
      => 4)

;; Implicit forcing of lazy values
(test (run "{bind {{x {delay {/ 9 0}}} {y {delay {/ 9 3}}}}
              {delay {+ y {delay {delay {delay 1}}}}}}")
      => 4)

Question 3. Type Systems22 pts

Consider the Picky language implementation that we have discussed. Specifically, in the Picky1 implementation we have the following typechecking fragment that verifies with expressions:

[(With bound-id itype named-expr bound-body)
(typecheck named-expr itype type-env)
(typecheck* bound-body
            (ExtendTypeEnv bound-id itype type-env))]

If we extend the language with a recursive rec binder (which is implemented as a WRec AST constructor), we would need a similar fragment to do the corresponding type-checking in typecheck*. Do this, assuming that WRec has the same type of arguments as With (an identifier, represented as a symbol, the binding type, a named expression, and a bound body expression). You need to write only the new rule — and you should use the above snippet, since it is (unsurprisingly) similar.

(Note that even though you’re writing a short fragement, it should still be good code.)

Question 4. CPS22 pts

In the last lecture, we have seen some translations of code to continuation passing style. We wish to implement a similar “bank web app” that starts with a given “balance” amount, then proceeds to reads amounts in a loop and subtracting them from the balance, stopping as soon as it goes down to zero or below, and return the number of transactions that were performed.

The simple version of this code is as follows (the format is just a way to compose a useful prompt that shows the current balance):

(define (bank-app balance transactions)
  (let ([new-balance (- balance
                        (web-read (format "[~s] Withdraw amount"
                                          balance)))])
    (if (> new-balance 0)
      (bank-app new-balance (add1 transactions))
      transactions)))
;; use it with an initial balance of 100
(bank-app 100 1)

You need to convert this code into its CPS-ed form:

(define (bank-app/k balance transactions k)
  ...fill-in...)

Here is an interaction example that demonstrates how this function would work:

> (bank-app/k 100 1 web-display)
web-read: ... [100] Withdraw amount:
> (submit 50)
web-read: ... [50] Withdraw amount:
> (submit 30)
web-read: ... [20] Withdraw amount:
> (submit 30)
web-display: 3

Question 5. Language Features20 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.

In the catch/throw question, our implementation is different from the ELisp version in that we bind the given name (the “tag”) whereas in ELisp we use an arbitrary value. This means that it’s easy to throw from any place to any other place by just using the same value in both places. In the given translated example, we needed to pass foo as an argument from foo-outer to foo-inner. Longer call chaings would require threading the tag through all functions in the chain.

Say that we wanted to be able to achieve the ELisp flexibility without passing tags as arguments — what would be the language tool most suitable for the task?

  1. Laziness

  2. Parameters

  3. Eager macros

  4. Global bindings

  5. Currying

Question 5b.

In the “Type Systems” question we worked in the context of the Picky1 implementation. This seems like an odd choice: why didn’t we do it in the context of Picky2 or Picky3? Is there any problem with that?

  1. It is impossible to implement a recursive binder in a statically typed language without either declaring a specific type or without laziness.

  2. Since the bound name is available in the named expression, we will not be able to infer the type of this named expression without knowing in advance its expected type. We’d run into a chicken-or-egg problem.

  3. If there is no type specification for the recursive binding, then we would need to write more complicated code that ensures that these recursive bindings are only used inside function expressions.

  4. There is no specific reason — it just makes sense to go about this in the same way that we implemented Picky: start with a fully explicitly typed version, and only then proceed with simplifying it into more and more implicit versions in the style of Picky2 and Picky3.

Question 5c.

Our discussion of the modern coding style that makes extensive use of callbacks in Node is reminiscent of how we have implemented side-effects like IO in our lazy language. This means that there is some core conceptual similarity that leads to the similarity in the coding style. What is this similarity?

  1. The callback style in Node is essentially implementing a lazy language, and therefore IO and other side-effects need to be done in a similar way.

  2. A lazy language cannot be compiled efficiently, and therefore there are slight differences between the two — but if it could be compiled, it would essentially be the exact same solution.

  3. In both cases we’re dealing with a language that cannot deal with some feature (side-effects in the lazy case, threads in the second case), and therefore we need to interact with a backend that can do these things, and the communication leads to back-and-forth between the two sides which is implemented via callbacks.

  4. The similarity between the two is purely coincidental: it just happens that both of these things use callbacks, but there is no meaningful similarity other than that.

Question 5d.

In the midterm we had the following blank question:

((lambda (blank) (blank blank)) (blank blank))

In the explanation of the solution I wrote:

;; This looks like omega too, but it's not: the first function takes
;; its input, which is (blank blank) and applies that to itself, so
;; it's *similar* to ((blank blank) (blank blank)), so a solution is:

Why did I write “similar” and not “the same”?

  1. As usual, deciding whether two things are equal is an undecidable problem.

  2. Depending on the value that blank is bound to, the expression might end up being equivalent to omega and an infinite loop is something that we cannot reason about.

  3. To say that it is the same as […] requires reasoning about how this code behaves in a lazy language too, and that’s harder to do.

  4. To say that it is the same as […] requires reasoning about how this code behaves in a lazy language too, and in that case the two options are not equal.

  5. Since the question is in the context of full Racket, there will be a difference between the two expressions if the blank function does some side-effect, like printing.