MidtermDate: ? Sunday, February 25th


This exam is intended for two hours. The question scores sum up to a total of 125 points, but it will be graded “out of a 100” so you can skip a question, a few pieces, or just shoot for a bonus.

Note about Typed Racket: unless told otherwise, make sure that you write proper type declarations for functions that you implement. Grading will not be strict about type declarations syntax, but we will be looking at them. Note that some given examples might be missing type annotations for brevity. This should not be a problem for understanding them.

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 (and they should also be short).

(1) Stateful Racket Programming /15
(2) Fill in the blanks /15
(3) BNF Grammar /15
(4) Extending the FLANG Language /20
(5) Structural Recursion with ASTs /20
(6) Schlac /20
(7) Language Features /20
Total /125

Question 1. Stateful Racket Programming15 pts

As we have seen in class, the configuration aspect of dynamic scoping can be a useful feature in itself. Often, this feature is mimicked using plain mutable values: the idea is to change the value when starting a dynamic scope, run some code, then restore the value.

In this question you need to do just that. Implement a with-box-value function that takes in a box, a new value for the box, and a thunk (a nullary function that takes no argument). with-box-value will then proceed by doing exactly the above: set the box to the given value, run the thunked code, restore the box, and return the result of the thunk. To demonstrate it, here is a simple example as a test case:

(: a-box : (Boxof Number))
(define a-box (box 1))
(test (+ (unbox a-box)
        (with-box-value a-box 2 (lambda () (* 10 (unbox a-box))))
        (* 100 (unbox a-box)))
      => 121)
(test (cons (unbox a-box)
            (with-box-value a-box 3 (lambda () (list (unbox a-box)))))
      => '(1 3))

In this example the a-box is a global binding, but this would work with local boxes too.

Make sure that you write a proper (polymorphic) type and purpose statement too. (You do not need to add tests…)

Question 2. Fill in the blanks15 pts

For each one of the following expressions, write a definition for blank in Racket that makes the expression evaluate to 660. For example, a correct answer for this expression:

(* (blank) 2)


(define blank (lambda () 330))

If you think that it is impossible to write such a definition, explain why this is the case. Remember: this is Racket, not Schlac or FLANG, or any other language that we’ve seen. In other words, assume a language of #lang pl. More accurately, unless explicitly asked, assume a #lang pl untyped — the language that doesn’t do any type checking — so you do not need to write types. Also, assume NO MUTATION is allowed.

(Note: you’re doing the “filling-in” via a definition of blank, not with some literal substitution.)

Do this for the following expressions.

a. (first (blank))

b. ((+ blank 40))

c. ((blank) (blank) blank)

d. (and (blank) blank)

e. (let ([blank "foo!"] [x blank]) x)

Question 3. BNF Grammar15 pts

In homework 2 we had a version of the AE language that had sequences of expressions with a get and set. One thing that some people asked about was further restricting the syntax to make get required, as a way to avoid the ambiguity. To show that this is possible, start with the simple AE syntax that we changed into a variant that allows a get:

<AEg> ::= <num>
        | { + <AEg> <AEg> }
        | { - <AEg> <AEg> }
        | { * <AEg> <AEg> }
        | { / <AEg> <AEg> }
        | get

and create a grammar for a new “AEg1” language that requires one get operation, not more, and not less. In other words, only a single get, and it must be included. In your answer, it will be useful to refer to <AE> as the original language, defined as:

<AE> ::= <num>
      | { + <AE> <AE> }
      | { - <AE> <AE> }
      | { * <AE> <AE> }
      | { / <AE> <AE> }

Note: you can just use it, no need to copy this bit of a BNF, and specifically, you should not modify it. Also, no mention of set in this question — just ignore it.

Question 4. Extending the FLANG Language20 pts

A common approach for having an evaluation function in a language is to expose its own evaluation rather than re-implement the language in itself. In this question we will do just that.

First, we need to have a kind of values that we can use to represent code, and strings are the usual obvious choice (at least in non-Lisp circles). Assume a version of the environment-based FLANG language that is extended to include string values. That is, the FLANG type definition becomes:

(define-type FLANG
  [Num  Number]
  [Str  String]

and we also need parsing,

(define (parse-sexpr sexpr)
  (match sexpr
    [(number: n)    (Num n)]
    [(string: s)    (Str s)]


(define-type VAL
  [NumV Number]
  [StrV String]
  [FunV Symbol FLANG ENV])

and finally, evaluation:

(define (eval expr env)
  (cases expr
    [(Num n) (NumV n)]
    [(Str s) (StrV s)]

Now to implement an eval, we need to further extend the FLANG AST:

(define-type FLANG
  [Num  Number]
  [Str  String]
  [Eval FLANG])

Using this type definition, you need to implement two additional bits:

Question 4a.

Extend the parse-sexpr function to parse eval expressions into Eval instances. (Please DO NOT copy the function, just write the single new match case that is needed.)

Question 4b.

And the meat of the implementation: the evaluation semantics. You need to write the evaluation fragment that deals with Eval instances. Since we’re simply exposing our own eval, this fragment should be relatively short. Note that we need to ensure that the given value is a string — but since we need to do it just once, you should do it in your evaluation fragment (similar to function values in the call case) rather than a helper function (in the style of NumV->number).

You need to write just the new case for Eval, no need for the rest of the eval code.

Demonstrating Tests

Just to show off what we get, here is a test case (note that the syntax for string values in arguments to string->sexpr uses single-quotes) that shows how it works:

(test (run "{with {x 1}
              {with {y 10}
                {with {foo '{+ x y}'}
                  {with {f {fun {x} {+ {eval foo} 100}}}
                    {call f 2}}}}}")
      => 112)

Even better, we demonstrate a nested use of eval (to get a quote in a string->sexpr string, we use two single quotes):

(test (run "{with {x 1}
              {with {y 10}
                {with {foo '{eval ''{+ x y}''}'}
                  {with {f {fun {x} {+ {eval foo} 100}}}
                    {call f 2}}}}}")
      => 112)

Question 5. Structural Recursion with ASTs20 pts

Usually, using a raw eval function as we did in the previous question is bad in that it can be slow since it essentially performs the complete pipeline from code to execution at runtime. In other words, if we view our parser as part of compilation of the language, then we are basically compiling code dynamically, at runtime.

But there could be cases that could be “pre-compiled”: when the evaluated string is known in advance. You need to implement such a function, flatten-evals, which takes in a piece of syntax in our extended language, and “flattens” out string literals in eval expressions so there is no need for the eval.

To make this more concrete, here are some simple test cases that show what this function does (note that we’re using parse in the expected test result to make these tests more readable):

;; simple use -- flatten all occurrences
(test (flatten-evals (parse "{+ {eval '1'} {eval '2'}}"))
      => (parse "{+ 1 2}"))
;; this is done regardless of free or bound identifiers
(test (flatten-evals (parse "{with {x 1} {+ {eval 'x'} {eval 'y'}}}"))
      => (parse "{with {x 1} {+ x y}}"))
;; nested evals show that all levels are flattened
(test (flatten-evals (parse "{+ 1 {eval '{+ 2 {eval ''{+ 3 foo}''}}'}}"))
      => (parse "{+ 1 {+ 2 {+ 3 foo}}}"))
;; only literal string arguments are done
(test (flatten-evals (parse "{with {foo '1'} {+ {eval foo} {eval '1'}}}"))
      => (parse "{with {foo '1'} {+ {eval foo} 1}}"))

Remember to write a type and a purpose statement.

(You don’t need to worry about errors.)

Question 6. Schlac20 pts

To continue in an eval-themed spirit, we can show that we can implement a “universal lambda calculus evaluator” by using the same code that we had in class — we’ll use WAE to keep it simple. To implement this, we will use the “match-style” definitions which we’ve talked about in class.

To see the class text, open Lecture #13, and it’s about 25% down the text (look for “Another interesting way to implement…”).

To make it even shorter, we will not use a parser, and we’ll stick to just addition expressions (and Num will stand for the simple natural numbers that we’ve used in class).

Question 6a. Type definition

First, the translated type definition:

;; Num: Number -> WAE
(define Num
  (lambda (n)
    (lambda (num add id with)
      (num n))))
;; Add: WAE WAE -> WAE
(define Add
  (lambda (l r)
    (lambda (num add id with)
      (add l r))))
;; Id: Num -> WAE                <--- use a number for identifier names
(define Id
  (lambda (name)
    (lambda (num add id with)
      (id name))))

You need to fill-in the definition of the With constructor (note that it also uses a number for the bound id name):

;; With: Num WAE WAE -> WAE

Write just this definition, don’t copy the above.

Question 6b. Substitution

Next is the subst function: we assume to have a = function (such as the one you have or will imlement in the homework):

;; subst: WAE Num WAE -> WAE
(define subst
  (lambda (expr from to)
    ;; Note: this is the translated `cases`
    (expr ;; Num
          (lambda (n) expr)
          ;; Add
          (lambda (l r) (Add (subst l from to) (subst r from to)))
          ;; Id
          (lambda (name) (if (= name from) to expr))
          ;; With
          (lambda (bound-id named-expr bound-body)

Fill in just the With case — the last lambda above.

Question 6c. Evaluation

Finally, the evaluation function: again, fill in just the With case.

;; eval: WAE -> Number
(define eval
  (lambda (expr)
    (expr ;; Num
          (lambda (n) n)
          ;; Add
          (lambda (l r) (+ (eval l) (eval r)))
          ;; Id => fake an "error"
          (lambda (name) ((lambda (x) (x x)) (lambda (x) (x x))))
          ;; With
          (lambda (bound-id named-expr bound-body)

Question 7. 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 7a.

Regarding the eval implementation in question 4, is there any practical benefit for exposing our own eval rather than re-implementing our own language?

  1. No. In fact, the opposite is true: as we have seen several times, implementing the language instead of exposing features of the host language is a better explanation of how the language works.

  2. No. In fact, the opposite is true, as clearly demonstrated by the fact that our own language is something that we implemented ourselves instead of using Racket’s eval function.

  3. The two approaches would end up in an implementation of the same language and therefore the way to get there makes no difference.

  4. Yes: beyond having no duplicated code we are also guaranteed to get the same exact language on both levels. For example, if there is a bug in our language implementation we want the same bug to happen in our exposed eval so it is a faithful evaluator of the same exact language.

  5. Yes: it avoids duplicating code. However, there is a problem that we might inherit bugs from our own language into the one implemented by the new eval.

Question 7b.

Continuing with discussing our eval implementation: how come our eval function has two arguments, but the one inside the extended FLANG has just one?

  1. This is a trick question: they both have the exact same arguments.

  2. This is only because our eval is a Racket function, but in our FLANG language it is not a binding but a fixed operator similar, in the same way we implemented +, - etc, all with a different arity than Racket’s same-named functions.

  3. The extra env argument is not needed when we go one level down from our language to the language implemented within our language.

  4. What we did in this question is expose eval to users, but we did not expose the concept of “the runtime environment”. We could have done that too, which would make the exposed eval require two arguments as well.

Question 7c.

Still sticking with our Flang with eval implementation, how would it look like if we had chosen to extend the substitution-based evaluator rather than the environment-based one? To make this more specific, consider the test case that we’ve seen:

(test (run "{with {x 1}
              {with {y 10}
                {with {foo '{+ x y}'}
                  {with {f {fun {x} {+ {eval foo} 100}}}
                    {call f 2}}}}}")
      => 112)

Would this test change?

  1. No, it would still be a valid test, with the same result.

  2. Yes, the result will be 111.

  3. Yes, there is a problem with having eval that makes it behave in a similar way to dynamic scope, and if we extend the substitution-based evaluator we don’t run into this problem — and we would get 111 instead of 112.

  4. We will get an error since the string is an opaque value and by the time we get to perform the evaluation the x and y names are no longer there.

  5. We would get an error as said above, except if we complicate the implementation to somehow perform substitutions in strings too, and then we would get 111.

Question 7d.

In the Schlac question we’re using a language that is dynamically typed, why is it crucial that we stick with strict proper types for every bit of code that we write?

  1. It is not needed to keep the types, it just makes it a little easier to explain the code.

  2. Schlac has no errors at all, so any value can be used as any type, and if we make a mistake we get nonsensical results. We need the types to make sense.

  3. Schlac has no errors at all, so any value can be used as any type, and if we make a mistake we get nonsensical results. We need to stick to known types in each of the constructors since we cannot tell types of values apart when working inside the language.

  4. The dynamic typing of Schlac means that scope can get messed up. We need to have proper types to get proper lexical scoping.

  5. It’s a low-level assembly-like language, it would be impossible to read and write such code unless we keep things very organized.