• Main
• Overview
• Resources
• Homeworks

Sample Final 2

Date: Thursday, April 18th

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: Racket Programming

 20 pts 

Sometimes it is useful to provide limited versions of given functions for various purposes. For example, we might want to limit a function so it can be used only a given number of times. Define a higher-order function called with-fuel which takes in an integer n and a function f, and returns a function that is identical to f except that it can be used only n times, and attempts to use it again will throw an error. (If n is zero or negative, the resulting function cannot be called even once.) Since you don’t know how to deal with variable arity functions in Racket, do this only for unary input functions.

Here are some tests that demonstrate how with-fuel is used (these definitions are only intended to make the tests easier):

(define add1* (with-fuel 3 add1))
(test (add1* 10) => 11)
(test (list (add1* 20) (add1* 30)) => '(21 31))
(test (add1* 40) =error> "out of fuel")

(define 1not (with-fuel 1 not))
(test (1not #t) => #f)
(test (1not #t) =error> "out of fuel")

Hints: you will need a box, and remember that in Racket we use a begin expression to sequence several expressions when side-effects are involved.

Question 2: Language Extension: Extending Racket

 20 pts 

As you should know very well now, being able to have anonymous functions is a very useful feature in a language. But there is an inconvenience with these functions — to write a recursive function we usually want to refer to “this function” by its name. (This is only “usually”, because we know how to use the Y combinator, but for this question we’re focusing on a pratcical construct.) We can do this, for example, using a letrec binder:

(letrec ([loop (lambda (x) (loop (add1 x)))])
  loop)

Here are some tests to demonstrate how it should work (note that the body of the second named-lambda has two expressions):

((named-lambda loop () (loop))) ; this will be an infinite loop
(test ((named-lambda foo (x)
                     (printf "~s\n" x)
                     (if (> x 0) (foo (sub1 x)) 'done))
       3)
      => 'done
      =output> "3\n2\n1\n0\n")

Question 3: Language Extension: Extending TOY

 20 pts 

Given that our TOY language has side-effects, it makes sense to extend it with loop forms. For this question, we will do that as additional core forms. We begin with the extended “Turbo Toy” language (see the solution to Homework #11), and add the following two forms to the BNF:

<TOY> ::= ...same as before...
        | { forever <TOY> ... }
        | { while <TOY> <TOY> ... }

(define-type TOY
  ...same as before...
  [Forever (Listof TOY)]
  [While   TOY (Listof TOY)])

The forever form will evaluate its body expressions forever in an infinite loop, and the while form will evaluate the first expression (which is the condition expression), and if the result is true (in the same sense as in the if case) it will evaluate the body forms in sequence, and then re-test the condition and so on, until the condition evaluates to false. The resulting value for the whole while form is the same bogus value (bound to the-bogus-value in the implementation) that we have used elsewhere.

1. As usual, you need to define the semantics for the two new forms, in other words, you need to extend eval to deal with them. Implementing a TOY loop will require a loop in the racket implementation that will do the iteration, which — as usual in racket — requires writing a (tail) recursive function. So you will do this extension outside of the main cases, in two utility functions. So eval is extended as follows:

   (: eval : TOY ENV -> VAL) ;; evaluates TOY expressions. (define (eval expr env) ;; convenient helper (: eval* : TOY -> VAL) (define (eval* expr) (eval expr env)) (: do-forever : —«fill-in»—) (define (do-forever body) —«fill-in»—) (: do-while : —«fill-in»—) (define (do-while test body) —«fill-in»—) (cases expr ...same as before... [(Forever body) (do-forever body)] [(while test body) (do-while test body)]))

   You need to finish writing the two definitions and their types. Include only these two functions, not the whole evaluator.

2. An additional question here: it seems that a natural way to implement do-forever is to re-use the do-while function like so:

   (define (do-forever body) (do-while (Id 'true) body))

   But this is wrong. Explain why it is wrong, by writing a TOY program with a forever loop that will not evaluate as expected. (Again, this is simple!)

Question 4: Lazy Languages

 20 pts 

We will now do something similar to the previous question, except that we extend the SLUG language (see the solution to Homework #12). Actually, since the language is lazy, we can just write functions for the loop constructs, so we can work inside the language rather than extend its implementation.

We need a few ingredients this to work:

• the convenient do form from the solution,
• recursive functions so we can actually loop,
• and it turns out that while is a little difficult in this framework, so we will do forever and repeat instead, where {repeat N expr} runs the body expression N times.

Because we have a macro facility in this language — with-stx — we can actually get recursion using the Y combinator, only because it’s easier to do as a quick hack. We get this by defining Y, and then defining a bindrec macro that uses Y (note that this is a limited version that doesn’t do mutual recursion). You’ll be happy to hear that you don’t really need to know anything about all of that, it’s all in here in case you’re curious, but you really don’t need to follow any of this beyond knowing how to use do from the solution works and how bindrec can create recursive definitions:

(run-io
 "{with-stx {do {<-}
                {{do {id <- {f x ...}} next more ...}
                 {f x ... {fun {id} {do next more ...}}}}
                {{do expr next more ...}
                 {begin2 expr {do next more ...}}}
                {{do expr}
                 expr}}
    {bind {{Y {fun {f} {{fun {x} {f {x x}}} {fun {x} {f {x x}}}}}}}
      {with-stx {bindrec {}
                         {{bindrec {{x expr} ...} body}
                          {bind {{x {Y {fun {x} expr}}} ...} body}}}
        ...the body...}}}")

1. Going to the body, where the real action happens, we should add the two functions using bindrec to implement a loop. We’ll do that in two parts — first, forever (this is the meat of the question, which is plugged into the above “the body” hole):

   {bindrec {{forever {fun {body} —«fill-in»—}}} {forever {do {print 'foo\n'} {print 'bar\n'}}}}

   You need to complete the body of the forever, and a correct implementation will make this piece of code alternate printing “foo” and “bar” in an infinite loop.
2. Now do repeat, which is just a little more complex:

   {bindrec {{repeat {fun {n body} —«fill-in»—}}} {repeat 3 {do {print 'foo\n'} {print 'bar\n'}}}}

   A correct implementation will print the alternating “foo” and “bar” only three times. (Note that this is simple, you don’t need boxes and mutation in the repeat implementation...)
   [You can assume that the given n is always >= 0.]
   You will need to return something when the loop is done, for this, you can use a {print ''} as a no-op IO result.

Question 5: Type System

 20 pts 

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

Γ ⊢ cond : Boolean   Γ ⊢ then : τ   Γ ⊢ else : τ
                                                   
           Γ ⊢ {if cond then else} : τ

There are two possible ways to do this:

• Simply remove the goal for c, so it doesn’t have to be a boolean:

  Γ ⊢ then : τ Γ ⊢ else : τ Γ ⊢ {if cond then else} : τ

• Don’t remove it, but instead of using Boolean use some new type τ₂, which is left unspecified:

  Γ ⊢ cond : τ2 Γ ⊢ then : τ Γ ⊢ else : τ Γ ⊢ {if cond then else} : τ

Question 6: Language Features

 20 pts 

Unless otherwise noted, choose the single best answer for each of the following.

1. In question 2 we have discussed named functions as a convenience for “not so anonymous” functions that can refer to themselves. We now consider the flip side: do we get anything by having anonymous lambda expressions in Racket, given that the language is lexically scoped and has internal definitions?
   Do we really gain something with anonymous functions — if, for example, we still have Racket’s internal definitions?
   1. Anonymity is always good, especially in an age of giant corporations that profit from tracking your identity, and identity theft being a new kind of crime. Having anonymous functions is a feature that can be used to implement network protocol that will protect us from such dangers.
   2. Yes, we get a language that has first-class function values, rather than a boring first-order language like Algae.
   3. No, we don’t get any benefits from lambda expressions. We’ve used them extensively in the course but we all know that in real programming they’re a useless academic exercise.
   4. If we have Racket’s lexically scoped internal functions, then we don’t gain new power with lambda, other than convenience. For example, we could define lambda as a macro that expands as

      (lambda (x ...) body) --> (let () (define (tmp x ...) body) tmp)

2. You may have noted that Schlac (like Haskell) does not have nullary functions (thunks). The grammar for the language was specifically forbidding lambdas and function calls without arguments:

   <SCHLAC> ::= <id> | (<SCHLAC> <SCHLAC> <SCHLAC> ...) | (lambda (<id> <id> ...) <SCHLAC>) | (define <id> <SCHLAC>)

   Is it really a feature that is missing in these languages? Is there any functionality that we will not be able to use because of this?
   1. No, because Schlac was a toy language anyway.
   2. Yes, of course. Just like in Racket, it is sometimes useful to wrap some code in a thunk to pass it around as a value. We got away without it in the Schlac language because it was a very limited language that mimicked the lambda calculus, but if we had a production language then we would definitely need to add this feature.
   3. No, we don’t need thunks, because every expression in a lazy language is basically a computation — implemented by something that is essentially equivalent to a thunk.
   4. Yes, we need nullary functions and function applications if we want to have a langugae that is turing-complete.
3. As we’ve seen in a few occasions, Racket has a time special form that evaluates its body and prints timing results. For example, we can use it with the ever so popular fib function:

   (define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))) (time (fib 37))

   Can this time be implemented as a function rather than a macro?
   1. Yes, and in fact it’s implemented this way. Roughly speaking, it’s defined as (using some fictitious timing functions):

      (define (time expr) (let* ([start (current-time)] [result expr] [end (current-time)]) (report-timing start end) result))

   2. No. It must be defined as a macro.
   3. No. It could be defined as a function if it were consuming a thunk, but since it is defined as a form that has just a sub-expression, it should be defined as a macro.
   4. Depends whether we want to use it in Typed Racket or not. In the untyped case, a simple function is enough, but in a statically typed language we need to deal with an expression that has an unknown result type so we must use a macro.
4. Continuing the discussion of the time form, what about implementing it in a lazy language? Could it be done as a function in this case, or does it have to be a macro? Maybe it can’t be done at all?
   1. In this case we certainly can use a function — since lazy languages don’t need thunk wrappers and instead delay everything, it can deal with the expression as a computation.
   2. Using a function will not work, because the expression itself will be delayed and therefore the runtime will always be the short time it takes to create a promise. We therefore have to use a macro.
   3. Nothing will work, because we cannot have any side effects in a lazy language, like dealing with a timer and reporting the time.
   4. Nothing will work, because all values are delayed, and even side-effects are achieved indirectly by dealing with descriptions. But if we had some strict special form that forces a strict evaluation of an argument, then we could do it — but then we would need a macro to avoid the usual delaying.