# Sample Midterm 2Date:   Tuesday, October 9th

## Administrative

This is a sample midterm that was given in the 2017 spring semester.

 Question Grade (1) Racket Programming /20 (2) Fill in the `blank`s /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 Programming20 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:

• things: a list of values to produce the signal,
• next: a list-to-list function that is used to determine the sequence of 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 `blank`s15 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 Grammar16 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 ASTs18 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:

• `fun` expressions are allowed only in the first argument subexpression of a `call` or as the nested body expression of such a `fun` expression.

• In fact, the first subexpression argument of `call` must be a `fun` (or a nested `call`).

• Even more: the number of nested `fun` expressions matches the number of surrrounding `call` expressions.

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 Language20 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:

• the name for the new binding,
• the value to bind it to,
• the environment to extend,
• and the body to evaluate in the extended environment.

### 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. Schlac18 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 = 0
[(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:

• this is relatively easy; both definitions are one-liners,
• don’t be tempted to use the above `add` and `sub`, they won’t help (really, they will only make your implementation redundantly longer).

## Question 7. Language Features15 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.