Midterm

Define a precedes function that consumes two values and a list, and determines whether the first value appears before the second value in the list. The result should be true if and only if this is the case, and false otherwise. Here are a few test cases to demonstrate how this function works:

Hints:

• “true” in Scheme is any value other than #f.
• (member x l) returns #f if x does not appear in l, but if it does then the result is the tail of the list l that begins with x.

Write a commutative function that accepts a binary function and returns one that is guaranteed to be commutative. Obviously, it is undecidable whether a given function is commutative or not for all possible inputs — but we can take the approach of providing a guarantee for all actual uses of the function by calling the input function twice and throwing an error if the two results are not equal. Here are two tests that demonstrate how this is used:

Note: the resulting function will have to be twice slower than the input function, but don’t make it even slower than that!

There’s a known puzzle about a man trying to cross a river with a sheep, a wolf, and a head of lettuce — using a boat that can only hold him and one more item. As the puzzle goes, he must not leave the wolf alone with the sheep or the sheep alone with the lettuce. In this question you will write a grammar that can be used to describe an attempt to solve this puzzle. Here is how a valid solution looks like in this syntax:

There are different ways in which this grammar can be written. One extreme would be a grammar that has exactly the above, forcing all well-formed programs to be exactly this solution — but that doesn’t leave any place for mistakes. A saner option would be something like:

Write a BNF that is a little more strict: a possible solution is one that is enclosed in begin...end tokens, with an odd number of moves in between, where the first and the last moves go from the left side to the right, and the moves properly alternate directions.

(Note that this still leaves some nonsensical options, like taking the sheep three times from the left to the right. It is possible to make a syntax that accounts for the contents of each side too, and it is even possible to make the grammar specify all correct solutions. However, these alternatives will be more verbose.)

1. (* blank)
2. (* (blank) (*))
3. (second (map blank (list blank (blank blank))))
4. (and (blank) blank)
5. ((lambda (x y) (x y y)) (lambda (x y) (blank x y)) (lambda (x y) (x x y)))

Write a normalize function that takes in a FLANG and a list of symbols and returns a new FLANG that uses these identifiers in sequence from left to right for all of the bound input names. Use the substitution-based FLANG evaluator for this. For simplicity, you can assume that the list of symbols has enough elements, and that the input expression is closed (has no free identifiers).

For example (using parse for the expected output):

Note that you’ll need to define a helper function that returns two values: the normalized FLANG expression, and the list of leftover symbols. Use this declaration:

Hint: since you’re using FLANG, you have subst — using it will make the solution very easy.

A relatively recent dialect of Lisp is “newLISP_®”; its most obvious feature is that it is a dynamically-scoped “interpreted” language — and this is considered a feature (though you won’t find it listed on the front page). Regardless of whether this is a good idea or not, we can play with a feature that is central to it: first-class environments.

The idea of the extension that we’re going to implement is that at any point you can grab the current environment (as a new kind of value), and later on you can use it for some computation. Note that we will be extending the environment-based FLANG-ENV code which is lexically scoped, but the extension itself will make the language have dynamic-scope properties.

Our extension will involve two new expressions:

Here’s an example that should demonstrate this:

To implement this, we begin with an extension of the AST:

The last thing to do is to implement the evaluation fragments for the two new expressions. Do that.

1. Our commutative function (from the first question) relies on a certain property of the input function to preserve its meaning. Which of the following functions does preserve its semantics when fed into commutative? In other words, for which of these functions can you say that (commutative F) is the same as F (modulo its runtime):
   1. (lambda (x y) (printf "adding ~s+~s\n" x y) (+ x y))
   2. (lambda (x y) (* (+ x y) (read-number)))
      (where read-number reads a number from the user)
   3. (lambda (x y) (* (+ x y) ((lambda (x) (x x)) (lambda (x) (x x)))))
   4. (lambda (x y) (* (+ x y) (error "poof!")))
2. Why do we need to assume that the input to normalize (from question number 5) is closed (has no free occurrences)?
   1. Because code that is not closed cannot be evaluated, therefore normalizing it is not necessary.
   2. Because doing that means that normalization does not preserve the semantics of the original code — we will get a dynamically scoped language.
   3. Because doing such normalization can lead to capturing identifiers, for example, if we rename a binding instance to x and its scope had a free x.
   4. Because doing such normalization can lead to capturing identifiers, which could be avoided at the cost of a more complex implementation which will avoid using them.
   5. Because our language is strict, otherwise there is no problem with free identifiers as long as we don’t need them for an expression.
   6. Because bound and free occurrences of identifiers have different semantics in a strict language.
3. Explain why the get-scope and with-scope forms defeat any compilation attempts. (In the sense of using de-Bruijn indexes.)
   1. As can be seen in the examples, we can write code with references to identifiers that are not in the current lexical scope, therefore we get dynamic scope and we cannot compile code.
   2. Since we mimic a feature of a dynamically scoped language, attempts to compile the code can get the compiler into an infinite loop.
   3. It is impossible to compile the code only because we implement a dynamic-scope feature on top of a lexically scoped language. If we had only dynamic scopes to begin with, we could use the same compilation strategy that was discussed in class.
   4. The claim is wrong: compilation is still as possible as it is in FLANG without our extension.
4. Write an expression — if possible — that we can use to learn whether a Schlac-like implementation is dynamically scoped or statically scoped. Explain if impossible.
   1. ((lambda (x) (x x)) (lambda (x) (x x)))
      if the language is dynamically scoped, this will throw an “unbound identifier x” error
   2. (define x 4)
      (define (return-x) x)
      (let ([x 5]) (return-x))
      if the language is dynamically scoped, we’d get 5, otherwise the result is 4.
   3. It is impossible to tell whether it uses dynamic scope or lexical scope, because define in the language cannot be used for recursive functions anyway.
   4. It is impossible to tell whether it uses dynamic scope or lexical scope, because the language is lazy.
   5. It is impossible to tell whether it uses dynamic scope or lexical scope, because the language is implicitly curried.
   6. ((lambda (x y) x) 5 6)
      if the language is dynamically scoped, this will throw an “unbound identifier x” error

In class we have seen two ways to define not for our lambda encoding of booleans:

We will show this now formally as follows: take both definition as a function from two-argument-numeric-functions (Number Number -> Number) to two-argument-numeric-functions functions and see that they produce different output functions for the same input. We only need one counter-example, so we’ll use + as our two-argument-numeric-function and show that (not1 +) and (not2 +) return two different two-argument-numeric-function.

First, begin with (not2 +) — to see what it means, we’ll apply it to two arbitrary encoded church numerals, and reduce things from there:

The second step is to do the same with (not1 +):

[This question is optional, of course. Feel free to write more details, give a single word reply for each item, or completely ignore it if you’re not interested.]

Exam:

• Did you have any issues with this application?
• On a scale of 0=“trivial” to 10=“impossible”, how hard was this exam?
• On a scale of 0=“fell asleep” to 10=“fascinating”, how interesting was this exam?
• Any other comments on the exam?

Class:

• How well do you follow the material? (0=“what material?” 10=“I already read the whole book, twice”.)
• Is it going too slow or too fast? (0=“we could have done what we did in a week”, 10=“it’s fast enough to feel the Doppler effect”.)
• Is it boring? (0=“it’s so boring that I usually fall asleep”, 10=“I love it, can we have 6-hour classes four times a week?”)

Homeworks:

• Are there too little homeworks or too many? (0=“I want more homework, I need more of teh codes”, 10=“I sleep 20m per night on weekends — I want a break!”)
• Are the homeworks too easy or too hard? (0=“I just slam the keyboard randomly for 15 minutes and it works”, 10=“I put ice packs on my head to avoid damage from my inflated brain”)

Any other general comments?