# Sample Midterm 3Date: Monday, October 7th

 Name:

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

 Question Grade (1) Racket Programming, Part 1 /14 (2) Racket Programming, Part 2 /12 (3) BNF Grammar /15 (4) Fill in the blanks /20 (5) Structural Recursion with ASTs /18 (6) Extending the FLANG Language /18 (7) Schlac /16 (8) Language Features /18 Total /131

## Question 1: Racket Programming, Part 1 14 pts

Two common ways to combine elements in a list into a single value are foldl and foldr. For example:

 ```-> (foldl list 0 '(1 2 3 4)) '(4 (3 (2 (1 0)))) -> (foldr list 0 '(1 2 3 4)) '(1 (2 (3 (4 0))))```
Implement a new kind of binary fold called fold-pairs which works by combining every two consecutive elements (and if there’s a single leftover, leave it as is), then repeat this until we get a list with just one element which is the final result. Note that this requires having a non-empty list as the initial input, which means that there’s no need to get an "initial value" input.

Do this in two steps. In the first step, define a map-pairs function that does the pair scan and produces a list of results. Here are a few tests to demonstrate how it works:

 ```(test (map-pairs list '(1 2 3 4 5 6)) => '((1 2) (3 4) (5 6))) (test (map-pairs list '(1 2 3 4 5)) => '((1 2) (3 4) 5)) (test (map-pairs list '(1 2)) => '((1 2))) (test (map-pairs list '(1)) => '(1)) (test (map-pairs list '()) =error> "empty list") (test (map-pairs + '(1 2 3 4 5 6)) => '(3 7 11)) (test (map-pairs + '(1 2 3 4 5)) => '(3 7 5)) (test (map-pairs + '(1 2)) => '(3)) (test (map-pairs + '(1)) => '(1))```

Remember to write a good type declaration and a purpose statement.

(Negative hint: you cannot implement this function using map!)

## Question 2: Racket Programming, Part 2 12 pts

For the second test you need to define the fold-pairs folding function.

Define a fold-pairs which applies the above repeatedly until a single element is left, and returns that value.

Examples:

 ```(test (fold-pairs + '(1 2 3 4 5 6)) => 21) (test (fold-pairs list '(1 2)) => '(1 2)) (test (fold-pairs list '(1 2 3 4)) => '((1 2) (3 4))) (test (fold-pairs list '(1 2 3 4 5 6)) => '(((1 2) (3 4)) (5 6))) (test (fold-pairs list '(1 2 3 4 5)) => '(((1 2) (3 4)) 5)) (test (fold-pairs list '(1)) => 1) (test (fold-pairs list '()) =error> "empty list")```

Note that a proper type for this will be tricky, so you can skip it, and instead describe things more accurately in the purpose statement.

## Question 3: BNF Grammar 15 pts

In class, we have seen a BNF for an infix syntax of the four basic arithmetical expressions, which properly makes multiplication and division have higher precedence, each level of operators is left-associative and we also had parenthesis grouping:

 ``` ::= + | - | ::= * | / | ::= | ( )```

Extend this syntax in two ways:

• Add an exponent "^" operator that is higher precedence than the other four (but not higher than parenthesis).
• Add a unary prefix "-" or "+" that is even higher than "^" (but still not higher than parenthesis, of course).

The resulting language would accept expressions like

 ```-( 1 + -2 * 3 ^ +4 ) -+--+-4 <--- many unary prefix operators```
(The spaces in the above are just for readability, since we don’t specify them in the syntax.)

## Question 4: Fill in the blanks 20 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.)
The language is always the #lang pl that you’ve used so far. Unless explicitly specified, you do not need to write types for the definitions, and assume no mutation is allowed.

Do this for the following expressions.
1. (* blank (+(*)(*)))
2. (/ blank 12345)
Hint: you do not need a calculator for this
3. ((lambda () (blank)))
4. (Y blank)
This is assuming our definition of Y for Racket that we’ve seen in class:
 ```(define (Y f) ((lambda (x) (x x)) (lambda (x) (f (lambda (y) ((x x) y))))))```
Hint: this is way easier than it looks!
Reminder: let* works as a shorthand for a bunch of nested single-identifier binding let forms

## Question 5: Structural Recursion with ASTs 18 pts

Implement a shadowed-identifiers function that consumes an AST syntax for FLANG (an input of type FLANG), and returns a list of all identifiers (a list of symbols) that are "shadowed" anywhere in the code. An identifier is shadowed if in its scope there is some arbitrarily nested scope with the same name. A few examples:

 ```(: shadowed* : String -> (Listof Symbol)) ;; a utility for the tests below (define (shadowed* str) (shadowed-identifiers (parse str))) (test (shadowed* "{with {x 1} {with {x 1} 1}}") => '(x)) (test (shadowed* "{with {x 1} {fun {x} x}}") => '(x)) (test (shadowed* "{with {x 1} {with {x 1} {fun {x} x}}}") => '(x)) (test (shadowed* "{with {x 1} {with {y 1} {fun {x} x}}}") => '(x)) (test (shadowed* "{with {x 1} {with {y 1} {fun {y} x}}}") => '(y)) (test (shadowed* "1") => '()) (test (shadowed* "{+ 1 2}") => '()) (test (shadowed* "{+ x y}") => '())```

For reference, here is the definition of FLANG:

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

Note: you don’t need to worry about the order of symbols and repeating ones. This would be addressed using a predicate that compares two lists as sets, which you don’t need for this question.

## Question 6: Extending the FLANG Language 18 pts

We want to extend the FLANG langugae with a new feature called upref. This will be a new special form that has an identifier, and it will evaluate to the value of the second binding of that identifer in the runtime environment. Again, we use a few tests to demonstrate this extension:

 ```(test (run "{upref x}") =error> "...") (test (run "{with {x 1} {upref x}}") =error> "...") (test (run "{with {x 1} {with {x 2} {upref x}}}") => 1) (test (run "{with {x 1} {with {f {fun {x} {upref x}}} {call f 2}}}") => 1) (test (run "{with {x 1} {with {f {fun {x} {upref x}}} {with {x 3} {call f 2}}}}") => 1)```

To implement this on top of the FLANG langugae that uses environments, we need to:

• Extend the BNF:  ``` ::= ...same... | { upref }```
• The AST type definition:  ```(define-type FLANG ;; ...same... [Upref Symbol])```
• And the parser:  ```(: parse-sexpr : Sexpr -> FLANG) ;; to convert s-expressions into FLANGs (define (parse-sexpr sexpr) (match sexpr ;; ...same... [(list 'upref (symbol: name)) (Upref name)] [else (error 'parse-sexpr "bad syntax in ~s" sexpr)]))```

The main step is extending eval to handle these expressions:

 ```(: eval : FLANG ENV -> VAL) ;; evaluates FLANG expressions by reducing them to values (define (eval expr env) (cases expr ...same... [(Upref name) ???]))```
Your job is to do so. You don’t need to copy any code, it’s enough to specify just the expression that should be written in the place marked with "???". It is best to do this using a new helper function — and you need to write the code for this function as well (including its type and a clear purpose statement).

## Question 7: Schlac 16 pts

The standard way to encode booleans that we have seen in class is as two selector functions:

 ```(define #t (lambda (x y) x)) (define #f (lambda (x y) y))```

As usual, that’s not the only way you could encode them. We could, for example, try to do a more C-style encoding and use 0 for false, and any number bigger than 0 for true:

 ```(define #f 0) ; note: it's actually the same as what we had! (define #t 1) ; or 2, or 3, etc```

This change will obviously require changing other aspects of booleans, and the most basic function that we need to deal with is if. Write its new definition:

 ```(define if (lambda (cond then else) ...fill-in...))```

## Question 8: Language Features 18 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.)

1. In the FLANG extension that we have implemented above we added a new kind of an "upref" identifier reference. An important issue is whether our language is still one that can be compiled or not. Can it?
1. No, the fact that we can do this kind of upref dynamically at runtime means that we get a dynamically scoped language, and as we have discussed in class, such langugaes cannot be compiled. (Since the "offset" of a variable reference cannot be determined before running the code.)
2. Almost, but no. Since all of the references are visible in the source code, we can still tell which binding is referenced at each upvar expression — but this works only if our language is not extended to have a conditional expression like if. Such an expression means that we can have code that goes an arbitrary number of levels at runtime, so we cannot tell statically which binding it refers to.
3. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. Even if we have a conditional if form added to the language we can see the lexical structure of the code since an upref expression returns a value, which means that we cannot do two (or more) uprefs somehow.
4. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. If we have a conditional ‘if’ form added to the language we will need to use a lazy evaluation strategy anyway, and that means that we don’t get expressions with a dynamically determined scope.
2. In the last midterm exam we’ve had this "blank" question:
 `(* 330 (length (cons blank blank)))`
and a solution that was given to it was:
 `(define blank (list 1))`
In the review session, I mentioned the fact that typing this might be tricky. To see this, you need to be aware of the type of cons:
 `(: cons : (All (A) (A (Listof A) -> (Listof A))))`
Which of the following types can be used for this blank definition to work?
1. Any
2. (Listof Any)
3. (Listof Number)
4. (All (A) (Listof A))
5. (List Number)
6. Number
There are exactly three of these that can work, and three that will not. You need to list all three.
3. Joe implemented a Flang evaluator similar to ours in an imperative language, whose name begins with "J". (This question is based on a true story from a past semester. The names have been changed to protect the innocent.)
As common for such programmers, he made the mistake of making environment extension modify via mutation of the environment. Write a simple Flang program that demonstrates that his implementation is wrong.
Note: you need to find such an example yourself, no multiple choices here. (But it is easy to do this.)
4. We’ve seen in class that if we write (list (foo)) in Racket, then the foo call is not a tail call. Intuitively, this is because there is still work to be done with the return value (wrap it in a list). What if we do something like this:
 `((lambda (x) x) (foo))`
— would the foo call be a tail call now?
1. Yes, it would be a tail call. This is because dynamic scope means that there are no closures, so the lambda expression basically evaluates to just the code with no environment to hold on to the value of x. This means that when it is applied, we get just the value of the foo call, and there is no need to do something with that when we get an answer.
2. No, it still would not be a tail call. This is because Racket is a strict language, and therefore no matter which function is called, we still need to evaluate the argument and only then apply the anonymous function onto the resulting value.
3. Yes, it would be a tail-call now. Racket’s compiler performs optimizations like reducing an immediate ((lambda (x) ...) ...) to avoid runtime work on generating a closure that is immediately applied, and therefore the code that the whole expression compiles to is essentially just (foo), and that obviously has the semantics of a tail call (since there is no context).
4. No, it still would not not be a tail call. This is because we have a language with first-class functions, and the only way to optimize away such calls of unknown functions is by a complete lexical analysis of calls, one that can be performed only on a more restricted language, one with just first-order functions.