Midterm
Date: ? Sunday, February 26th

Administrative

This exam is intended for two hours. The question scores sum up to a total of 122 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).

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

Question 1. Racket Programming
20 pts

In this question we’ll be dealing with “signal functions”: functions that read some value in the real world, and monitor it as it changes. An example of such a function can be a fuel-level reading function, that is used to display the level in your car’s dashboard.

The problem is that if we make the display show the result of calling the function periodically, the display is most likely going to constantly change as the gauge goes up and down when the car moves. One way to deal with this is to use a moving average: instead of using the actual readings as they come in, we use the average of the current measurement and the previous result (which is also such an average, etc).

We will start by implementing some simulation functionality for testing. First, a function->sequence function that takes a unary function and produces a signal function with values that are results of successive applications of this function starting from a given initial value. This function is implemented for you:

(: function->sequence : ...fill-in...)
;; given a function `f` and an initial value, return a nullary function
;; that returns f(init) when first called, then it returns f(f(init)),
;; f(f(f(init))) etc.  (Note that at each step `f` is called just once
;; with the previous value.)
(define (function->sequence f init)
  (define state (box init))
  (lambda ()
    (set-box! state (f (unbox state)))
    (unbox state)))

To test it, we implement a quick n-values helper:

(: n-values : ...fill-in...)
;; utility for testing side-effect nullary functions
(define (n-values n f)
  (if (<= n 0)
    '()
    (cons (f) (n-values (sub1 n) f))))

and here are some tests:

(test (n-values 10 (function->sequence add1 0))
      => '(1 2 3 4 5 6 7 8 9 10))
(test (n-values 10 (function->sequence - 1))
      => '(-1 1 -1 1 -1 1 -1 1 -1 1))
(test (n-values 4 (function->sequence reverse '(X Y Z)))
      => '((Z Y X) (X Y Z) (Z Y X) (X Y Z)))

Question 1a.

The only thing missing is the type for this function->sequence function and the n-values utility, fill them in. (Write just the two type declaration lines, no need to copy the body.) Note that these functions should be polymorphic.

Next, a list->signal simulation function. This should take in two values:

To clarify, here are two tests:

(test (n-values 10 (list->signal '(1 2 3) identity))
      => '(1 2 3 1 2 3 1 2 3 1))
(test (n-values 10 (list->signal '(X Y Z) reverse))
      => '(Z Y X X Y Z Z Y X X))

Note that the values of successive calls to the simulation function returns values from a list of values, where each cycle is taken from a list determined by the next function. The implementation of this is a generalization of the random-bag function from sample midterm #3, but instead of always using shuffle, we’re using the given next function over the list of values. Furthermore, instead of maintaining an additional state for the list of value, we use the above function->sequence.

(: list->signal : ...fill-in...)
;; consumes a list of things and a list-to-list function, and returns a
;; "signal function" that returns each of the items in turn, cycling
;; back to next-list(last-list) when done.
(define (list->signal things next)
  (define state (box '()))
  (define lists (function->sequence next things))
  (lambda ()
    (when (null? (unbox state))
      ...fill-in...)
    (let ([l (unbox state)])
      (set-box! state (rest l))
      (first l))))

Question 1b.

Fill in the missing type declaration and the missing line in the body. (Again, this function should be polymorphic.)

Question 1c.

Finally, you can now implement the moving average functionality, an averager function. Here you need to provide both the type and the implementation. Here is a test that demonstrates it:

(test (n-values 4 (averager (list->signal '(1 2) identity)))
      => '(1.5 1.25 1.625 1.3125))

Explanation: the (list->signal '(1 2) identity) function returns 1 on its first call, then 2, then 1, then 2, etc. The averager function initializes its internal state to the first call — 1. When the resulting moving-average function is called, it will invoke the signal function again, getting 2, and returning the average of 2 and the previous state of 1, resulting in 1.5. On a second call, the signal function returns 1, which is averaged with 1.5, resulting in 1.25. We then get the average of the next signal value of 2 and 1.25, resulting in 1.625 etc.

(Note that this unlike the previous ones, this function cannot be polymorphic.)

Question 2. Fill in the blanks
15 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)

is:

(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. ((lambda (x) blank) (lambda (x) (x x)))

b. (blank (map blank '()))

c. (map blank (blank '()))

d. (if (blank) (blank) (/ blank 0))

e. (letrec ([blank (lambda () (blank))]) (blank))

Question 3. BNF Grammar
16 pts

Write a BNF grammar for a limited variant of the FLANG. The idea is restricting it so that fun expressions are only called immediately, but we want to still allow curried calls. We therefore allow fun expressions in only two places: either the first sub-expression in a call, or as the immediate body expression of a fun. Here is an example for demonstration:

{call {call {fun {x} {fun {y} {+ x y}}} 1} 2}

(Ideally we would also enforce a kind of a curried arity check so the above would be valid, but not if there was another nested fun or if there was one less fun — but this cannot be done in a BNF grammer.)

Begin with a copy of the FLANG BNF, and modify it accordingly to the above.

Question 4. Structural Recursion with ASTs
18 pts

We will now implement the restricted language properly: implement a syntactic predicated called valid? which determines when the input expression is valid in that:

Hint: an easy way to implement this functionality is to have the main work done by a recursive function with an extra argument which is the expected number of nested fun expressions. If you do it right, you will also allow more “interesting” nestings of call and fun expression as long as the overall arity matches.

Here are some tests for demonstration:

(: v? : String -> Boolean)
;; quick utility for the tests below
(define (v? str) (valid? (parse str)))

(test (v? "{call {fun {x} x} 1}"))
(test (v? "{call {call {fun {x} {fun {y} x}} 1} 2}"))
(test (v? "{call {call {call {fun {x} {fun {y} {fun {z} x}}} 1} 2} 3}"))
;; the "interesting" cases
(test (v? "{call {call {fun {x} {call {fun {y} {fun {z} x}} 1}} 2} 3}"))
(test (v? "{call {fun {x} {call {call {fun {y} {fun {z} x}} 1} 2}} 3}"))
(test (v? "{call {fun {x} {call {fun {y} {call {fun {z} x} 1}} 2}} 3}"))
;; unexpected `fun`s
(test (not (v? "{fun {x} x}")))
(test (not (v? "{+ {fun {x} x} 2}")))
(test (not (v? "{with {f {fun {x} x}} {call f 1}}")))
;; bad curried arity
(test (not (v? "{call 1 2}")))
(test (not (v? "{call {fun {x} {fun {y} x}} 1}")))

Don’t forget a type declaration and a purpose statement for valid?!

Question 5. Extending the FLANG Language
20 pts

When we talked about dynamic scope, we’ve mentioned how a few languages solved the problem of introducing lexical scope into a language that was initially implemented as dynamically scoped. Specifically, we discussed how in Common Lisp (and Perl too, to some extent), some variables can be declared “special” and therefore they use dynamic scope, while other bindings are all lexical. In this question we will implement such a language.

We start from the plain FLANG language that we’ve worked with in class, we’ll use the one based on environments.

Most of the steps are the usual ones:

  1. We add a dwith binder form for dynamically-scoped names

    <FLANG> ::= <num>
              | ...same...
              | { with  { <id> <FLANG> } <FLANG> }
              | { dwith { <id> <FLANG> } <FLANG> }
              | ...same...
  2. Extend the type definition accordingly

    (define-type FLANG
      ...same...
      [With  Symbol FLANG FLANG]
      [DWith Symbol FLANG FLANG]
      ...same...)
  3. Extend the parser with a rule similar to with

    (define (parse-sexpr sexpr)
      (match sexpr
        ...same...
        [(cons 'dwith more)
        (match sexpr
          [(list 'dwith (list (symbol: name) named) body)
            (DWith name (parse-sexpr named) (parse-sexpr body))]
          [else (error 'parse-sexpr "bad `dwith' syntax in ~s" sexpr)])]
        ...same...))

Now, for the actual implemntation, we will cheat and use Racket’s parameters for the implementation of dynamically-scoped names — the same functionality that we’ve seen when we talked about the advantage of using a dynamically scoped value for customizing code.

  1. We will need to define a new kind of values that hold Racket parameters:

    (define-type VAL
      [NumV Number]
      [FunV Symbol FLANG ENV]
      [ParamV (Parameterof VAL)]) ; new kind of values
  2. The next step is to make such bindings evaluate to the value that is stored in the parameter, for this, we need a helper function

    (: deref-param : VAL -> VAL)
    ;; if the input value is a ParamV, dereference it, otherwise return it
    (define (deref-param val)
      (cases val
        [(ParamV param) (param)]
        [else          val]))

Question 5a.

Finally something for you to do: write the new evaluation case for Id to use this utility. (This is about the eval code fragment.)

Question 5b.

Implement the new case for DWith: this would be very similar to the current With case, except that you should use the new ParamV and a parameter (using Racket’s make-parameter that creates a parameter with an initial value).

We’re almost done now — the last thing to do is to make the evaluator extend an environment in one of two ways based on whether we get a dynamic binding or not.

  1. We will use a helper function to do the work — so the evaluation of With and Call change to:

    [(With bound-id named-expr bound-body)
    (extend-and-eval bound-id (eval named-expr env) env bound-body)]
    [(Call fun-expr arg-expr)
    (let ([fval (eval fun-expr env)])
      (cases fval
        [(FunV bound-id bound-body f-env)
          (extend-and-eval bound-id (eval arg-expr env) f-env bound-body)]
        [else (error 'eval "`call' expects a function, got: ~s"
                            fval)]))]

Note that the extend-and-eval function takes four arguments:

Question 5c.

Implement extend-and-eval, using this template:

(: extend-and-eval : Symbol VAL ENV FLANG -> VAL)
;; evaluates an expression in an extended environment, where the
;; extension happens either lexically or dynamically
(define (extend-and-eval bound-id val env bound-body)
  ;; param will be either a parameter if its dynamic, or `#f` if
  ;; it's lexical (or unbound)
  (define param (get-param bound-id env))
  (if param
    ...fill-in...))

Note that you will need to use Racket’s parameterize, which looks like this:

(parameterize ([some-parameter some-value])
  ... body in which that parameter is bound to that value ...)

For reference, here is the definition of the get-param utility that is used above — there’s nothing here that you need to do. This code is very similar to lookup, only it returns #f instead of an error, and in case of a non-ParamV value.

(: get-param : Symbol ENV -> (U (Parameterof VAL) #f))
;; look for a dynamic binding, and return the matching parameter if
;; found, or #f if the name is not dynamically scoped
(define (get-param name env)
  (cases env
    [(EmptyEnv) #f]
    [(Extend id val rest-env)
    (if (eq? id name)
      (cases val
        [(ParamV param) param]
        [else #f])
      (get-param name rest-env))]))

Question 6. Schlac
18 pts

At the end of the “Alternative Church Encoding” (Lecture #13) section we have seen a way to define types in a way that is similar to our own define-type and cases. This could have been used, for example, to implement natural numbers, based on their structural definition. Roughly speaking, we’d say that a natural number is either zero or a successor of some other natural number. With out type definitions:

(define-type Natural
  [Zero]
  [Succ Natural])

Using the method in that section, we would implement natural numbers as

(lambda (z s) ...)

where z is used for for the zero case, and s for the successor case. Following this, we would write the following definitions for Zero and Succ:

(define Zero (lambda (z s) z))
(define Succ (lambda (n)
              (lambda (z s) (s n))))

Note that Zero is a constant, and therefore doesn’t take any arguments, whereas Succ takes n, the preceding natural number.

As a usage example, here is addition in Racket (with the Racket define-type):

(define (add n1 n2)
  (cases n2
    [(Zero)    n1]
    [(Succ n2-) (Succ (add n1 n2-))]))
(define (sub n1 n2)
  (cases n2
    [(Zero)    n1]
    [(Succ n2-) (cases n1
                  [(Zero)    n1] ; no negatives: 0 - n = n
                  [(Succ n1-) (sub n1- n2-)])]))

and in Schlac:

(define/rec add
  (lambda (n1 n2)
    (n2 n1
        (lambda (n2-) (Succ (add n1 n2-))))))
(define/rec sub
  (lambda (n1 n2)
    (n2 n1
        (lambda (n2-)
          (n1 n1 ; same
              (lambda (n1-) (sub n1- n2-)))))))

Your task is to write utility functions to convert our regular Church encoded numbers to/from this encoding. Let’s use nnat to refer to these “new naturals”, so name the two conversion functions accordingly.

Question 6a.

Implement nat->nnat, converting a regular church encoded natural to the above.

Question 6b.

Implement nnat->nat, going back

If your implementation is correct, it would make the following two tests pass:

(test (->nat (nnat->nat (add (nat->nnat (+ 5 2))
                            (nat->nnat (+ 1 3)))))
      => '11)
(test (->nat (nnat->nat (sub (nat->nnat (+ 5 2))
                            (nat->nnat (+ 1 3)))))
      => '3)

Hints:

Question 7. Language Features
15 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.

Why couldn’t we specify the proper restrction of matching arities in the BNF question?

  1. Because our language is strict.

  2. Because the arity property is dynamic, and we cannot use eval.

  3. Because this cannot be done by a context free grammar, including BNF.

  4. Because, as seen in the AST question, it requires actual Racket code to check that kind of validity.

Question 7b.

What’s the main problem with the restricted language that we have specified correctly in the AST question?

  1. It requires laziness, otherwise we will not be able to treat functions as first-class.

  2. It requires lexical scope, otherwise we will not be able to treat functions as first-class.

  3. By forbidding other uses of fun forms, we make the language dynamically scoped.

  4. call + fun is equivalent to with, so we lose the ability to deal with first class functions.

  5. call + fun is equivalent to with, so we lose the ability to abstract over code, we lose actual functions.

Question 7c.

How does our extended FLANG + dwith language compare to a dynamically scoped laguage? (Reminder: choose the best answer.)

  1. We implemented dynamic scope, so it’s no wonder that the result is suffering from exactly the same issues as a dynamically scoped language — it’s just as bad.

  2. We added dynamic scope to a lexically scoped language, which means that not only can we not rely on meanings of identifiers, but we also get potential confusion between the two scopes, so things are much worse.

  3. It is slightly better since we have some lexical scope, and we can choose to not use the dynamic dwith.

  4. Things are a little better because we have some number of lexically scoped variables, and therefore we can do the same reasoning (and compiler optimizations etc) for some parts of the code.

  5. It is much better because the dynamic scope is delimited by dwith expressions, and therefore there is no global change in code from other programmers whose code we use.

  6. It could be much better because we control the scope as #5 says, but in practice this is because our language is limited, specifically, there is no way to combine multiple pieces of code from different people.