Sample Midterm 1Date:   Tuesday, October 9th

Administrative

This is a sample midterm that was given in the 2016 fall semester.

QuestionGrade 
(1) Racket Programming /16
(2) Racket Higher Order Programming /12
(3) Fill in the blanks /15
(4) BNF Grammar /16
(5) Structural Recursion with ASTs /18
(6) Extending the FLANG Language /18
(7) Schlac /16
(8) Language Features /12
Total /123

Question 1. Racket Programming16 pts

In this question you need to implement a Run-Length encoder called encode: a function that takes in a list of things, and returns a list of two-element lists, each one has a number of occurrences and the thing that occurs that many times. This is best shown via examples, given as tests:

(test (encode '(1 1 1 0 1 0 0 0 1))
      => '((3 1) (1 0) (1 1) (3 0) (1 1)))
(test (encode '(1 1 1 1 2 2 3 4 4 4))
      => '((4 1) (2 2) (1 3) (3 4)))
(test (encode '(A B B C))
      => '((1 A) (2 B) (1 C)))

To make it simpler, we will assume that the input list is never empty.

For an implementation, we will write two functions — first, the toplevel encode function:

(: encode : fill-in)
;; take in a list of things and return a run-length encoded list
(define (encode things)
  (helper (first things) (rest things) 1))

What you need to do is:

Note: the result of a list of lists of two things: for a “list of two things” use the List type constructor (do not use Pairof)

Question 2. Racket Higher Order Programming12 pts

Currying, as we’ve seen in class, is of course not the only way to tweak argument passing to functions. It is the common way to curry a function, and the assumption is that a partial application with just the first argument is generally more useful. But in some cases it is useful to have a function curried in the other way: getting the second argument first, and then the first argument.

You need to implement such a function, called r-curry. Again, this is demonstrated using a quick test:

(define str1 (r-curry string-append))
(test ((str1 "one") "two") => "twoone")

Remember to write a proper type and a purpose statement. The function should work on any two-argument functions, with two inputs that might not be the same type.

(Note: the code in this case is very easy, so a proper type will have a substantial weight…)

Question 3. 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)

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. (map blank '())

b. (first (map blank (blank blank)))
  ;; Note: you can define blank as a function that tests whether
  ;; its input argument is equal? to blank (itself)

c. ((compose blank blank) 0)
  ;; compose is doing the obvious thing, it’s defined as
  ;;  (define (compose f g) (lambda (x) (f (g x))))

d. ((or blank (blank 3)))

e. (let* ([blonk (blank)]
          [blink (blonk)]
          [blank (blink)])
    (blink 'bling))
  ;; Remember that let* is equivalent to nested lets
  ;; (Note: in our language there are no default number of
  ;; arguments or any other kind of variable number of arguments.)

Question 4. BNF Grammar16 pts

The FLANG language that we have defined in class has the following BNF:

<FLANG> ::= <num>
          | { + <FLANG> <FLANG> }
          | { - <FLANG> <FLANG> }
          | { * <FLANG> <FLANG> }
          | { / <FLANG> <FLANG> }
          | { with { <id> <FLANG> } <FLANG> }
          | <id>
          | { fun { <id> } <FLANG> }
          | { call <FLANG> <FLANG> }

We want to extend it with two new constructs in an attempt to make it more widely applicable:

  1. if0: a form that has three subforms, the intention of this form is to evaluate the first subform, if the resulting value is 0, then we evaluate the second subform, otherwise we evaluate the third subform.

    Add this form. (You only need to write the newly added line, don’t copy the whole thing.)

  2. The second thing we want to add is a return — just to make it more appealing for mainstream programmers who are used to return statements. However, unlike many languages, we don’t want the usual semantics of return as a way of jumping out of a function: instead, we want to allow a return only in places where adding it doesn’t matter. This means that we should only allow a return expression to appear inside a fun expression, and only in tail position.

    As DrRacket demonstrates, this is something that can be checked syntactically, without ever running any code. But furthermore, we can even have this restriction as something that is built into the language’s grammar — and this is what you need to do now.

    (Hint: to get it done, you will need another non-terminal.)

    Here are some examples of valid and invalid uses of return:

    • {return 3} — invalid since we’re not inside a fun expression

    • {fun {x} {return {+ x 1}}} — valid

    • {fun {x} {return {call foo {* 2 x}}}} — valid

    • {fun {x} {call foo {* 2 x}}} — this is still valid too!

    • {fun {x} {call foo {return {* 2 x}}}} — invalid since it’s not in a tail position

    • {fun {x} {with {y 2} {return {* x y}}}} — valid since with itself is in tail position and the return is in a tail position of the with

    • {fun {x} {with {y {return 2}} {return {* x y}}}} — invalid: the first return is not in tail position

    • {fun {x} {+ 10 {with {y 2} {return {* x y}}}}} — invalid: the whole with is not in tail position

    • {fun {x} {+ 10 {return {if0 x y z}}}} — invalid: not in tail position

    • {fun {x} {return {if0 x y z}}} — valid (this would be invalid in languages that have statements, since a return in these languages cannot have an if since it’s a statement; but for us if0 is kind of a ternary ?: operator)

    • {fun {x} {if0 x {return y} {return z}}} — valid

    • {fun {x} {if0 {return x} {return y} {return z}}} — invalid because the first return is not in a tail position

Note that these instructions don’t say whether returns can be nested, so you can go either way with that.

Question 5. Structural Recursion with ASTs18 pts

In this question we’ll assume the usual FLANG AST definition, extended with if0 as described in the BNF question, and also a return expression. Unlike the case of the BNF question, assume that the syntax is simple, and returns are allowed anywhere (so semantically they’re effectively an identity). Here is the resulting type definition:

(define-type FLANG
  [Num  Number]
  [Add  FLANG FLANG]
  [Sub  FLANG FLANG]
  [Mul  FLANG FLANG]
  [Div  FLANG FLANG]
  [Id  Symbol]
  [With Symbol FLANG FLANG]
  [Fun  Symbol FLANG]
  [Call FLANG FLANG]
  ;; The extensions
  [If0  FLANG FLANG FLANG]
  [Ret  FLANG])

Your task in this question is to take a FLANG expression (following this type), and determine whether there are any bad return expressions that appear in a bad position — not in a function’s tail position. To keep it simple, use a single function that consumes the AST value and a boolean tail-pos? flag that says whether returns are allowed:

(: bad-returns? : fill-in)
(define (bad-returns? expr tail-pos?)
  (cases expr
    fill-in))

(a) Fill in the code: add a proper type (no purpose statement), and the actual code. This answer wouldn’t be too short since you’ll need to implement all of the cases, but it should still be easy to implement it.

This is actually the helper function that does the actual work, there is a second function which is used as the toplevel predicate:

(: has-bad-returns? : fill-in)
(define (has-bad-returns? expr)
  fill-in)

(b) Implement this function too. This one should be a short half-line job.

Note: the important point here is the value of the tail-pos? flag: how is it initialized in has-bad-returns?, when is it passed recursively as-is, when is it passed as true, and when is it passed as false.

Question 6. Extending the FLANG Language18 pts

Meta-note: there is a lot to read here, but the actual coding that you need to do is very short.

As we have seen in class, one way to approach the problem of implementing the ability to have recursive functions is to send the function its own value at the time it is called. This is what we did in the beginning of the first explanation of the Y combinator. Doing this properly inside the recursion-less language was a challenge (which ended with the Y combinator), but it can be much easier if we do so at the level of our language implementation — the eval interpreter.

We will now implement this functionality: we will start from the environment-based FLANG interpreter, and we’ll make it so that all with-named function can call themselves recursively. To make it easier to verify that things are working fine, we’ll add if0 too, as discussed in the previous two questions.

As usual, we’ll do this in small steps:

First, we’ll add if0. There are a few places that need to be updated for this. Extending the AST is simple: just add the new variant (exactly as done in the AST question):

(define-type FLANG
  …same as before…
  [If0 FLANG FLANG FLANG])

(a) We also need to extend the parser as follows — you need to fill in the missing expression (write only the new expression, don’t copy the whole thing):

(define (parse-sexpr sexpr)
  (match sexpr
    …same as before…
    [(list 'if0 val then else)
    fill-in]
    [else (error 'parse-sexpr "bad syntax in ~s" sexpr)]))

(b) The last bit that we need is the evaluation of the new if0 forms — again, fill in the missing evaluation code below (and again, write only the missing code, don’t copy the whole thing); note that you can compare values like (NumV 0) with other values using equal?:

(define (eval expr env)
  (cases expr
    …same as before…
    [(If0 val-expr then-expr else-expr)
    fill-in]))

Next, we add the actual functionality of making all functions recursive. To get that done, we need a way to detect when a function value (a FunV closure) was named by a with — so we need a new value variant for such named functions:

(define-type VAL
  …same as before…
  [NamedFunV Symbol Symbol FLANG ENV])

The intention here is to keep a structure that is similar to FunV, with an added bit of information — the first Symbol — which holds the name of the function.

Finally, we need to deal with two additions to eval: one to create these new kinds of closures, and one that will use them to make the functions recursive.

(c) The first thing is rather technical, and can be done easily since cases can deal with nested patterns. What we need to do is to identify code that looks like:

{with {foo {fun ...}} ...}

and make sure that we evaluate that named expression (the fun expression) into a NamedFunV value. Since cases tries each branch in turn until it finds a match, we need to add the new evaluation fragment before the fragment that deals with With (same deal, write just the new clause):

(define (eval expr env)
  (cases expr
    …same as before…
    [(With fill-in-the-pattern)
    fill-in-the-expression]
    ;; this precedes the usual evaluation rule we have for `With`
    ;; (which is the same as before):
    [(With bound-id named-expr bound-body)
    (eval bound-body
          (Extend bound-id (eval named-expr env) env))]
    …same…))

Reminder: we have seen a nested pattern on our first attempt at implementing Call — it looks like this:

(define (eval expr)
  (cases expr
   
    [(Call (Fun bound-id bound-body) arg-expr) ;*** nested pattern
    (eval (subst bound-body bound-id (eval arg-expr)))]
    [(Call something arg-expr)
    (error 'eval "`call' expects a function, got: ~s" something)]))

We’re now ready for the last bit of code which will actually make recursion possible. When we call a function, and in case we get a NamedFunV named function, we will arrange for its body to be evaluated in an environment that will have its own name bound to its own value.

(d) All of this happens in the case that handles function calls: this needs to be extended to deal with NamedFunV values, then evlauate the dunction’s bound-body in an environment that has both the argument value bound to the argument name, and itself bound to its own name. In the following, the code is identical to what we’ve seen in class, with one new NamedFunV case that you need to deal with:

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

Note that you need to pay attention to the order in which the two environment extensions are done: a foo function that takes in an argument named foo should be able to access the argument value as foo, but it will not be able to call itself recurively.

Here are some fun examples:

  1. Demonstrate a basic recursive function:

    (test (run "{with {sum {fun {n} {if0 n 0 {+ n {call sum {- n 1}}}}}}
                  {call sum 10}}")
          => 55)
  2. These two demonstrate the importance of the environment extension order:

    (test (run "{with {foo {fun {foo} {+ foo 1}}} {call foo 10}}")
          => 11)
    (test (run "{with {foo {fun {foo} {call foo 1}}} {call foo 10}}")
          =error> "expects a function")
  3. And finally, this is just for fun, showing how we can simulate mutual recursion using a simple recursive function. It’s a bit long and complicated, but it’s really just for fun — if it looks scary, just don’t read it.

    (test
    (run "{with {even_and_odd
                  {fun {n}
                    {if0 n
                      {fun {n} {if0 n 0 {call {call even_and_odd 1}
                                              {- n 1}}}}
                      {fun {n} {if0 n 1 {call {call even_and_odd 0}
                                              {- n 1}}}}}}}
            {with {is_even {call even_and_odd 0}}
              {with {sum_evens
                      {fun {n}
                        {if0 n 0 {+ {call sum_evens {- n 1}}
                                    {if0 {call is_even n} n 0}}}}}
                {call sum_evens 10}}}}")
    => 30)

Question 7. Schlac16 pts

We have talked in class about the main problem of the Schlac language: since everything is made of single-argument functions it is generally hard to do things like distinguishing different kinds of values. For example, it would be useful to have a value that is distinguishable from all numbers and all booleans. Such a value could be used as a “void”-like value, and if we can distinguish it from all numbers and booleans, then everywhere one of these types is expected, we can use this value to make the code do something else. In other words, we gain the ability to have function inputs of more types: (U Number Void) and (U Boolean Void).

Here is one such value, with a predicate that distinguishes it from all naturals and booleans:

(define void (lambda (x y) 0))
(define void? (lambda (x) (zero? (x 1 1))))

You can try applying void? on numbers, booleans and void to see how it works. The basic idea uses the fact that 1 is the same as identity. The following tests show this too:

(test (->bool (void? void)) => '#t)
(test (->bool (void? 0)) => '#f)
(test (->bool (void? 1)) => '#f)
(test (->bool (void? 2)) => '#f)
(test (->bool (void? #t)) => '#f)
(test (->bool (void? #f)) => '#f)

It would of course be even better if this special value can be distinguishable from pairs too. Unfortunately, this doesn’t work. In this question, you need to find a counter example: a pair of two things such that (void? the-pair) returns #t.

To do this, you should start with a general pair:

(define the-pair (cons A B)) ; where A and B are some values

Next, we need to reduce

(void? the-pair)

until we get a value: an expression that cannot be further reduced. From that value, we can derive the required counter example.

For example, if the resulting value expression is:

(A B 1 (lambda (x) #f) #t)

then an obvious counter example is making A be a function that takes three things and returns true, so the result of void? in this test is #t which makes the test fail, proving that this is indeed a counter example:

(test (->bool (void? (cons (lambda (a b c d) #t) 0))) => '#f)

To keep this short: this is actually the real result of reducing (void? the-pair), so all you need to do is to show this reduction:

(void? the-pair)
fill-in
(A B 1 (lambda (x) #f) #t)

Question 8. Language Features12 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 8a.

In the extended Flang question we have made it always possible for functions to call themselves recursively. We therefore have a language where binders for functions are always recursive, and binders for other kinds of values are not. Is there any difference between the resulting language and using a “proper” rec binder that creates recursive bindings?

  1. No, the resulting language is exactly the same as if we’re always binding functions with a rec binder.

  2. No difference at all: our evaluation strategy makes even complicated examples like:

    {with {foo {with {x 1} {fun {y} {foo y}}}} ...}

    work fine.

  3. The only minor difference is that we only make directly named functions (ones that are named in a with with a fun as the named expression) recursive, and other functions not; for example, this:

    {with {foo {with {x 1} {fun {y} {foo y}}}} ...}

    will not make foo recursive.

  4. Yes, having all binders be implicitly recursive means that we can get the same effects with plain values too, for example, evaluating

    {with {x {+ x 1}} ...}

    would result in an infinite loop.

  5. There is only a difference in implementation, since our resulting language achieves recursion with no mutation at all it can be compiled into more efficient code, and in many cases code could be compiled into a machine-code loop.

Question 8b.

Here’s a joke:

Why is “abbreviated” such a long word?

There’s a whole bunch of these gems:

What makes these things funny (to most people)?

  1. They put together contrasting words in a similar context, which makes people laugh.

  2. Because the “dynamic scope” of the reader is used whereas people natually assume lexical scope for human text.

  3. Because they remind people of a complexity in the same style of the Y combinator.

  4. Because they mix the levels of syntax and of meaning.

  5. Because they’re using complex words next to simple words in unexpected ways.

  6. They’re not funny.

(No, it’s not 6.)

Question 8c.

In the Brang language we have implemented both bind and bind*, and both of them have been implemented as syntactic sugar that expands into either nested withs or a multiple-argument function application, and utlimately both of these get expanded into unary function applications. This means that the bindings happen one by one in either case.

However, the resulting binders still behave differently, as demonstrated by this example:

{with {x 1} {bind  {{x 2} {x {* x 10}}} x}}
{with {x 1} {bind* {{x 2} {x {* x 10}}} x}}

How come the results are different when the bindings happen in single steps in either case?

  1. This is a trick question; both of these would evaluate to 10.

  2. This is a trick question; both of these would evaluate to 20.

  3. They are different because the evaluations for the named expressions ultimately happen in in different scopes, making the first one return 10 and the second return 20.

  4. By expanding the binders into a language with just single-argument functions we essentially re-implement dynamic scope, making an unpredictable language where the order of binding generation and function calls happen to produce the expected results.