MidtermDate:   Sunday, October 28th

Administrative

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

QuestionGrade 
(1) Higher Order Racket Programming /20
(2) Nothing /0
(3) Fill in the blanks /15
(4) BNF Grammar /16
(5) Structural Recursion with ASTs /20
(6) Extending the FLANG Language /22
(7) Schlac /17
(8) Language Features /20
Total /130

Question 1. Higher Order Racket Programming20 pts

You are now familiar with the fold functions (i.e., foldl and foldr). We can also define an analogous inversed version of a fold, an unfold function that implements a kind of a “generator loop”:

(define (unfold done? seed->value next seed)
  (if (done? seed)
    '()
    (cons (seed->value seed)
          (unfold done? seed->value next (next seed)))))

Here are two usage examples, given as test expressions:

(test (unfold null? first rest '(a b c d e))
      => '(a b c d e))
(test (unfold zero? add1 sub1 6)
      => '(7 6 5 4 3 2))

Question 1a. Type

Your first task is to provide a (polymorphic) type for unfold.

[Note that this should be a proper type in that it results in a function that is as useful as possible. For example, you could say that map has a type of

(: map : (All (A) (A -> A) (Listof A) -> (Listof A)))

but this type unnecessarily restricts the type to use a single type in both sides of the mapped function, and we want to be able to call it with, for example, string-length and a list of strings.

Question 1b. Using unfold

Implement a pairs function that takes in a list and returns a list of all consecutive pairs from the input lists. Some examples demonstrates this better (again, given as tests):

(test (pairs '(a b c d)) => '((a b) (b c) (c d)))
(test (pairs '(1 2)) => '((1 2)))
(test (pairs '(#f)) => '())

Remember to specify a proper (polymorphic) type and purpose statement. To keep it simple, you can assume that the input list is never empty.

Question 2. Nothing0 pts

(There was question 2…)

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

b. ((blank + 1) * (blank + 1))

c. (foldr / 1 blank)
  ;; note that the arguments of `foldr` are the (two-argument)
  ;; function, the initial value, and the list to process (the
  ;; first argument to the two-argument function is the value from
  ;; the list, but (hint) that's not important)

d. (cond [blank  (blank)]
        [(blank) blank]
        [else    330])

e. (let ([blank (let ([blink blank]) blink)]) blank)

Question 4. BNF Grammar16 pts

Your friend Nancy Negative is arguing with you about having tail calls implemented in Javascript. Like many other JS-ers, she is worried about people getting confused with calls, not knowing which calls would be- and which calls wouldn’t be tail calls. In an attempt to demonstrate that distinguishing the two is simple, you remember that it is something that can be done statically, based on just how the code looks like.

To make this point a bit more organized, we start with a very simplified grammar for a very watered down version of Javascript:

<JS-PROG> ::= <JS-STMT>; ...

<JS-STMT> ::= function <id> ( <id>, ... ) { <JS-STMT> ... <JS-STMT> };
            | <JS-EXPR>;
            | if ( <JS-EXPR> ) <JS-STMT> else <JS-STMT>
            | return <JS-EXPR>;

<JS-EXPR> ::= <id>
            | <num>
            | <str>
            | <JS-EXPR> + <JS-EXPR>
            | <JS-EXPR> < <JS-EXPR>
            | <JS-EXPR> ( <JS-EXPR>, ... )

This is a rough BNF, but we can ignore its minor problems, ambiguities, etc, as well as the fact that it’s simplified to a ridiculously small version. Note that the { } in the body of a function is intended to ensure that there is at least one statement in the body (unlike real JS), and that it has a semicolon after it to make it more uniform.

To make the point that we can syntactically distinguish tail calls, you need to change the function syntax so that tail positions must use a return-tail keyword. For example, these would all be valid functions in the modified language:

function foo1(x) {
  print(x);
  return-tail 123;
}
function foo2(x) {
  return-tail 123;
}
function foo3(x) {
  return 987;                    <-- doesn't make sense, but still valid
  return-tail 123;
}
function foo4(x) {
  if (x < 10) return 999; else print("hey!");
  return-tail 123;
}
function foo4(x) {
  if (x < 10) return 999; else print("hey!");
  if (x < 10) return-tail 999; else return-tail print("hey!");
}

And these will not be valid:

function bogus1(x) {
  print(x);                      <-- must use `return-tail` in the end
}
function bogus1(x) {
  return-tail print(x);          <-- can't use it in the middle
  return-tail 123;
}

You need to write the BNF for this variant of the language. You need to do two things for this:

Question 4a.

Change one line in the <JS-STMT> — write only the changed line.

Question 4b.

Write a <JS-TAIL> that would be used in tail positions.

Question 5. Structural Recursion with ASTs20 pts

As you know from experience, there are always cases where you write a function which one of its arguments is not being used. We define an unused function argument as an argument identifier that does not occur free within its scope — the body expression of the function. For instance, in the following FLANG expression:

{call {fun {x} {fun {y} y}} x}

the formal parameter x is unused.

Most progammers (in many languages) use a common convention of using _ as a formal parameter when it is unused. We want to implement an automatic transformation that takes in a FLANG expression (an AST value), and converts it to have _s for all unused arguments.

We will work with the usual type definition for the FLANG syntax:

(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])

To make things simpler, we do this in two functions:

Question 5a. (is-free? id expr)

Implement an is-free? (recursive) predicate that takes in an identifier (a Symbol), and a FLANG expression, and determines whether that identifier appears free in the given expression. Here is a skeleton to use:

(: is-free? : Symbol FLANG -> Boolean)
;; determines whether id appears free in expr
(define (is-free? id expr)
  (cases expr
    ...fill-in...
    ))

A few tests that demonstrate how this works — note that we’re using parse in these tests to have a familiar syntax instead of writing AST constructors:

(test (is-free? 'x (parse "{+ x y}")))
(test (not (is-free? 'x (parse "{fun {x} {+ x y}}"))))
(test (is-free? 'y (parse "{fun {x} {+ x y}}")))
(test (not (is-free? 'x (parse "{fun {y} {fun {x} {+ x y}}}"))))
(test (not (is-free? 'x (parse "{+ 1 2}"))))

Question 5b. (unused->underline expr)

This function should take in a FLANG expression, and convert all unused fun arguments to _s. It should use is-free? above. Note that again, you should work with a cases and cover all of the FLANG variants.

(The same should be done for unused with bindings, but ignore them to simplify things.)

Question 6. Extending the FLANG Language22 pts

We want to extend the FLANG language with a useful construct for handling errors. At the end of this, we will have a new try-else form, which looks as follows:

{try-else expr1
          expr2}

with the semantics of evaluating expr1, and if that evaluation encountered an error, then it would evaluate and return the result of expr2. If no error was encountered, we would get the value of expr1, and if an error was encountered in both, then it would still result in that error.

Some examples for clarifying this:

(test (run "{try-else {+ 1 2}
                      {* 3 4}}")
      => 3)
(test (run "{try-else {+ 1 x}
                      {* 3 4}}")
      => 12)
(test (run "{try-else {+ 1 x}
                      {* 3 y}}")
      =error> "unbound identifier")
(test (run "{try-else {+ 1 {fun {x} x}}
                      {* 3 4}}")
      => 12)
(test (run "{try-else {call 1 2}
                      {* 3 4}}")
      => 12)
(test (run "{try-else {call 1 2}
                      {* x 4}}")
      =error> "unbound identifier") ; note: returns the `else` branch error

Note that we’re not using a division-by-zero, since our code does not detect that, so it’s not an error that we will handle. (We could, but that would mean more code, and we try to keep things simple.)

To implement this, there are the usual things, which you don’t need to handle:

Then, we need to handle error values — for this, we extend the set of runtime values:

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

The next step, is to return this value instead of throwing an error where appropriate. There are three error uses in our code, and we list them here so you don’t need to do them either:

  1. lookup has

    (error 'lookup "no binding for ~s" name)

    which would change to

    (ErrV (format "no binding for ~s" name))

    (Note that format is the Racket tool that formats a string and returns it.)

  2. Similarly, in NumV->number the error changes to:

    (ErrV (format "expected a number, got: ~s" val))
  3. The last use is in run, but since that complains about any non-number result, we don’t need to change it and let it complain about ErrV results (the message content will be visible in its printout).

There is also another one in the Call branch, which you’ll deal with below.

Now, the interesting part is handling these error values. The thing is that if we have an expression that involves evaluating subexpressions, we want to stop and return an error value as soon as we encounter one. The first place that should change is arith-op. The problem is first seen by the fact that we can not rely on NumV->Number to throw an error and abort the computation — instead, we need to test it explicitly. We use a small utility:

(: is-error? : VAL -> Boolean)
;; is the given VAL an ErrV?
(define (is-error? val)
  (cases val
    [(ErrV msg) #t]
    [else      #f]))

And using this, we can revise arith-op. Again, you still don’t need to do this — here is the revised version:

(define (arith-op op val1 val2)
  (cond [(is-error? val1) val1]
        [(is-error? val2) val2]
        [else (NumV (op (NumV->number val1) (NumV->number val2)))]))

And now, at long last, we get to the three parts that you need to write:

Question 6a. Revise the With evaluation fragment

The current evaluation fragment for With

[(With bound-id named-expr bound-body)
(eval bound-body
      (Extend bound-id (eval named-expr env) env))]

should be revised so that if the evaluation of the named-expr is an error, it should be returned without evaluating the body.

Question 6b. Revise the Call evaluation fragment

Similarly, you need to revise the Call evaluation rule:

[(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))]
    [else (error 'eval "`call' expects a function, got: ~s"
                        fval)]))]

In addition to handling error values, make sure that you also change the error to return an ErrV.

Question 6c. Handle TryElse expression

Finally, we get to the main meat of the problem: handle TryElse expressions. This is a new evaluation rule that you need to implement.

[(TryElse main-expr else-expr)
...fill-in...
]

Question 7. Schlac17 pts

In class, we have seen informally that the church-encoded numeral N can also function as functional “to the power of N” combinator. For example (using ^ as a functional power operator and . as a compose operator):

(0 f) = f^0  = identity
(1 f) = f    = f^1
(2 f) = f.f  = f^2
(3 f) = f.f.f = f^3

Write a formal inductive proof that for every natural number N its encoded form is indeed a function that takes in a function F and returns F^N.

Reminder, we defined encoded natural numbers using these definitions:

(define 0 (lambda (f x) x))
(define add1 (lambda (n) (lambda (f x) (f (n f x)))))

Note that your answer should be a straightforward induction: do the base case of 0, then assuming that it is true for the encoding of N, show that it works for the encoding of N+1. In both of these you will need to show how expressions reduce in Schlac (as we did in class) — make sure you show all steps in these reductions.

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

We define “homological” to mean a word that describes itself. Examples of homological words include “short”, “pentasyllabic”, and “english”. Next, define “heterological” to mean a word that does not describe itself — examples of these words include “long”, “monosyllabic”, “hebrew”, and “hyphenated”.

Is “heterological” a heterological word?

  1. The question doesn’t make sense, since the subject here are words in a natural language, and therefore they are inherently ambiguous.

  2. It can go both ways, since these are artificial definitions that we decided to make, they are open to interpretation, and therefore we can define “heterological” as either one.

  3. It’s a paradox, so its neither.

  4. The problem in this question is in the implicit assumption that a word is either homological or heterological, but “heterological” paradoxically demonstrates that some words are neither.

  5. It must be, since otherwise heterological would describe itself which would lead to a contradiction.

Question 8b.

The #lang pl language allows a test form to be used only as a toplevel expression. Is there any significant restriction over test expressions (and the testing framework) as a result?

  1. There is the obvious built-in restriction of not being able to use test anywhere that is not the toplevel, nothing important beyond that.

  2. If it can only appear at the toplevel, it cannot be compiled efficiently since it cannot appear in functions.

  3. There is no restriction that we see in our language so far, but it will lead to future problems if we wish to extend the language with high-level abstractions such as packages, namespaces, or classes.

  4. Having a toplevel-only test expression means that it cannot support common testing tools like setup/teardown code that are essential for testing code with side-effects.

  5. An important limitation on our testing framework is that we cannot abstract over tests, like having them in functions and/or loops, to do things like fuzzy testing of random inputs, or like composing higher level tests that are executed as a combination of actual tests.

Question 8c.

Say that we change the syntax of call expressions in our Flang language to allow only an identifier as the function expression:

  <FLANG> ::= ...
            | { call <id> <FLANG> }

What kind of a language do we get?

  1. We get a language that supports higher order functions, but we lose first-class functions.

  2. We get the same language, since we can translate calls with non-identifier expressions into calls with them in a simple and uniform way.

  3. We get a more efficient (and therefore faster) language since it is easier to type-check and to compile aggresively.

  4. If call expressions must use an identifier as the function to call, the Y combinator is impossible to implement and therefore recursion is impossible.

  5. We get a language that must either be dynamically scoped; or if we insist on lexical scope, we would lose the ability to do recursive calls and get a “boring” language without infinite computations.

Question 8d.

What is the meaning of (lambda (x x) x) as a number in Schlac? In other words, what would the following schlac test expression return:

(->nat (lambda (x x) x))
  1. It is a function and not a number and therefore we will get some nonsensical result.

  2. This expression will throw a syntax error because of the duplicate argument names, and therefore there is no actual answer (and no meaning).

  3. It is a (curried) function that returns its first argument and ignore the second, and therefore we will get 0.

  4. It is a (curried) function that returns its second argument and ignore the first, and therefore we will get 0.

  5. It is a (curried) function that returns its first argument and ignore the second, and therefore it is not an encoded number and we will get some nonsensical result.