Sample Midterm 4

Write an add-between function that takes a list and an item, and produces the elements of the list with the item between each two elements. Here are some tests:

1. Write a higher-order flip function that consumes a binary function of any type, and returns a similar function that uses it’s arguments in reverse. For example (flip cons) is a function that takes a list and an item and conses the item onto the list.
   Tests:

   (define snoc (flip cons)) (test (snoc '(2 3) 1) => '(1 2 3)) (test ((flip -) 1 2) => 1)

   Again, remember to write a proper type declaration and a brief purpose statement.
   Note: In general you need to use lambda: to create functions in typed scheme, but you can ignore this and just use plain lambda here.
2. Using flip from the first part of this question, and curry and map that we’ve seen in class, we can define the following function in a “point-free style” (similar to what we’ve seen in Lecture #9):

   (define foo ((currify map) ((currify (flip -)) 5)))

   Describe what this function is doing.
   (Note: this is a real function! We’re defining it using “point-free style”, which means that we’re combining other functions to create a new function with no explicit lambda, but it is still a function.)
   Do this in three ways:
   • Write the type of this function.
   • A (brief!) description of what it is doing in plain English.
   • Some tests that clearly demonstrate what it is doing.
   Reminder — the following is the definition of our currify from class, and the type of simple uses of map.

   (: currify : (All (A B C) ((A B -> C) -> (A -> (B -> C))))) ;; convert a double-argument function to a curried one (define (currify f) (lambda (x) (lambda (y) (f x y)))) (: map : (All (A B) ((A -> B) (Listof A) -> (Listof B))))

As we’ve seen in class, it is easy to change our parser to parse fully parenthesized infix expressions. Here is a new grammar modified this way:

Huge hint: an easy solution involves two nested withs, with bindings for + and for call.
(And rememebr – this is a FLANG expression, not Scheme code.)

1. (blank +)
2. (sqrt blank) ; hint: you do not need a calculator for this
3. (car (map (blank) ’(660)))
4. (if blank (blank) blank)
5. ((lambda (blank blank) (+ blank blank)) 330 330) ; careful!

Note: for this question refer to the FLANG-ENV interpreter — the FLANG implementation that uses environments.

In our implementation of FLANG using environments, the closures that we create close over the whole environment at the point of evaluating a fun expression. However, in many cases there is no need to close over the whole environment — only over identifiers that appear free in the body of the function. For example, when we get to evaluate the fun form in:

We can implement this by introducing a new preprocessing step into the evaluator, which translates all Fun expressions into annotated AFun expressions — those will be just like Fun, except that they will have an extra field that will keep the list of free identifiers in the body. Then, when we get to evaluation, we can make AFun forms evaluate to FunV closures holding only the relevant bindings. In this question, you will implement this annotation step.

The new FLANG type definition is:

Your annotator function should look like this:

Hint: in question 5 of the second sample midterm there is a definition of a free-vars function — this is doing something very similar to what you need here: you should use it as a helper function.

Note: because of the hack of adding AFun to the existing AST definition, the annotator will need to also have a case for an AFun input. However, then should never happen, so you can make that case just thrown an “internal error”.

In this question you will implement the evaluation part of the last question. To do this, we first change the run function to annotate the code before it is evaluated:

Then, you need to:

• start with the eval definition from the FLANG-ENV interpreter,
• change the Fun fragment to throw an internal error, because the result of the annotator should never have any Funs,
• write the new case for AFun.

While you’re at it, further optimize the portion of the environment that is closed over by not keeping duplicate identifiers. For example, when this code:

It will be easier to do this if you write a small utility function to do the filtering. (Note: if you know about filter — it could have been used, but when you scan the list you need to remember bindings that you’re scanning (to remove duplicates), and if you use filter then you won’t be able to do that — in any case, the environment in question is not kept as a list...)

1. Using our annotator step in the last two questions, you can make the following observation: if all functions in a program don’t close over any identifiers, then the program will run the same whether the interpreter uses dynamic or lexical scope.
   • How does that fit with the fact that dynamic scope gives us recursive calls “for free”?
   • Actually, this is too restrictive — demonstrate this with some program that runs the same on either scope, but not all AFuns are completely free of identifiers they close over. (This hints at some possible optimizations that we’re not doing, but these optimizations are dynamic in nature.)
2. In this code from the ALGAE2 solution:

   (: And : (Listof ALGAE) -> ALGAE) ;; Translates `{and E ...}' syntax to core Algae. (define (And exprs) (cond [(null? exprs) (Bool #t)] [(null? (rest exprs)) (first exprs)] [else (If (car exprs) (And (cdr exprs)) (Bool #f))]))

   it looks like the second case is not really needed. Explain why this is not true. Hint: removing it still makes and evaluate to the same result when taken as a boolean, but destroying a certain feature of the language. (Removing the second case will still leave and as a form that returns the same boolean answers when used with booleans — it is some other feature that is destroyed.)
   To demonstrate this, write some Scheme code using and, which would run differently if and was implemented in a way such that

   (and E1 E2) translates to (if E1 (if E2 #t #f) #f)

   or equivalently, if

   (and E) translates to (if E #t #f)

3. In question 1a of Assignment #2 we specified a restricted set of expressions that evaluate to S-expression values. Is there any reason for not including things like car — so expressions like

   (cons (car (list 1)) (cdr (list 1)))

   are not included in the language? Well, yes, of course. Explain it.
4. We’ve seen this in class:

   (rewrite (protect f) => (lambda (x) (f x))) (define (make-recursive f) ((lambda (x) (x x)) (lambda (x) (f (protect (x x))))))

   Why did we need to define protect as a “rewrite rule” rather than a plain function?

As we have seen, in the Schlac language we can represent pretty much anything that we can in “normal” programming languages. The main issue is choosing an appropriate encoding that satisfies the required properties (e.g., cons returning a value that contains its two inputs, and null being a value that null? can distinguish from all other pairs).

We’ve seen two different encodings for natural numbers — but we didn’t see an encoding for integers yet. In this question, you’ll fill up this hole.

A pretty obvious and convenient representation for integers is using pairs: represent an integer as a pair of a boolean and a natural number, where (cons #t N) stands for N and (cons #f N) for -N. (Note that this means that we have two different representations for 0, but that should not be a problem as long as your code treats both as 0.)

Using this, we essentially get a new “type” of values, with its own set of operations. In other words, using natural-number operations on integers encoded this way is not going to work.

We define a tiny library of operations for these integers, using an i: prefix to distinguish integer operations:

So the only problem is now defining an integer addition operation, i:+. Consider that the result of (sub1 n) is 0 when n is 0, and therefore (- n m) is 0 if m is bigger than or equal to n. Using this idea, we can implement a utility -- function that subtracts two natural numbers and returns the resulting integer result.

The last piece that is missing now is i:+, and this should be relatively easy. Complete its definition. (Note: you can assume that everything that we defined in class is given.)