# Sample Midterm 4Date: Monday, October 7th

 Name:

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

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

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

Write a Racket function called subseq? that accepts two lists, and determines whether the first one is a sub-sequence of the second. A list L1 is a sub-sequence of a list L2 if and only if the members of L1 all apear in L2 in the same order, possibly with other values in between them.

Examples (as test cases) — all of these are true:

 ```(test (subseq? '() '(1 2 3))) (test (subseq? '(1 2 3) '(1 2 3))) (test (subseq? '(1 2 3) '(0 1 0 2 0 3 0))) (test (subseq? '(1 2 3) '(1 1 2 2 3 3))) (test (subseq? '(1 1 2 3) '(1 1 11 2 3))) (test (not (subseq? '(1 1 2 3) '(1 2 3)))) (test (not (subseq? '(1 1 2 3) '(1 2 1 3))))```
Remember to write a proper type and purpose statement for the function.

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

In class we have seen the currify higher-order function that converts a function of two inputs to a single-argument function that returns a single-argument function.

Here is the code and some examples:

 ```(: 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)))) (define plus (currify +)) (test 3 ((plus 1) 2)) (test 3 (((currify +) 1) 2)) (test '(2 3 4) (map (plus 1) '(1 2 3)))```

Write a similar higher-order function, currify3, that converts three-argument functions into a three-staged curried function. Again, don’t forget a proper type and purpose statement.

Obviously, this not the only way of currying a three argument function. Instead of a three-level curried function, we could have used a two level function. There are two ways to do that: write the type definitions for these two options. (Just the type, not the code.)

## Question 3: BNF Grammar 15 pts

Write a BNF grammar for the language of palindromes over A, B, and C. Make sure that your grammar can derive palindromes of both even and odd lengths. For example, your grammar should be able to derive all of these: ABCCBA, ABCBA, C, CCCC. For this, we consider a palindrome as an actual word — so the empty string should not be in the language.

## Question 4: Fill in the blanks 15 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. (first ’blank)
2. ((blank) "2")
3. ((car (blank)))
4. (or (blank) (+ 1 "2"))
5. (let ([blank (blank)]) (+ blank 330))

## Question 5: Structural Recursion with ASTs 20 pts

In class, we have defined a “closed” expression as one that does not have any free identifiers. This is a property that is usually necessary for correct programs in a lexically scoped language, and it is one that can be checked statically, without running the code. For example, if we take care to check that the original program that is fed to our substitution-based evaluator is closed, then we avoid the obvious bug that we have talked about when it is made to do lazy evaluation.

Write such a predicate, closed?, that takes in a FLANG syntax value and determines whether it is closed. (Use the FLANG evaluator for the type definition.)

Here are a few test cases to help:

 ```(test (closed? (parse "{+ 1 2}"))) (test (closed? (parse "{with {x 5} {+ 1 2}}"))) (test (closed? (parse "{fun {x} {+ 1 x}}"))) (test (closed? (parse "{with {x 1} {with {y x} {+ x y}}}"))) (test (not (closed? (parse "{+ 1 x}")))) (test (not (closed? (parse "{with {x x} {+ 1 x}}"))))```

Implementation hint: write a helper function that uses an additional arguments holding a list of the currently known-to-be bound identifiers. This helper should do most of the work, and closed? is actually a simple wrapper that calls it. (You need to write a proper type for the helper function too.)

## Question 6: Extending the FLANG Language 20 pts

As we have seen, the semantics of call, like the semantics of with, are eager: the argument is evaluated before the substitution happens. We want to extend the substitution-based FLANG evaluator (FLANG) with a lcall construct that is similar to call except that it is lazy. (Important: do not use the environment-based evaluator for this!)

As usual, this requires a few changes to the code.

• Extend the BNF:  ``` ::= ...same... | { lcall }```
• The AST type definition:  ```(define-type FLANG ;; ...same... [LCall FLANG FLANG])```
• The parser:  ```(: parse-sexpr : Sexpr -> FLANG) (define (parse-sexpr sexpr) (match sexpr ...same... [(list 'call fun arg) (Call (parse-sexpr fun) (parse-sexpr arg))] [(list 'lcall fun arg) (LCall (parse-sexpr fun) (parse-sexpr arg))] ...same...))```
• And the substitution function:  ```(: subst : FLANG Symbol FLANG -> FLANG) (define (subst expr from to) (cases expr ...same... [(Call l r) (Call (subst l from to) (subst r from to))] [(LCall l r) (LCall (subst l from to) (subst r from to))] ...same...))```

The main work is the new semantics: the definition and the corresponding eval definition. Begin with the new evaluation rule for lcall expressions, and then extend eval to implement this rule for instances of LCall. For both of these, you don’t need to copy the existing set of rules and the eval code — write only the new rule, and the new LCall clause for eval.

## Question 7: Schlac 15 pts

In our encoding of Church numerals, we have defined the zero? predicate as follows:

 `(define zero? (lambda (n) (n (lambda (x) #f) #t)))`

As we know, if n is a function that encodes a number N, then it applies its first argument over its second argument N times. Since this is exactly what this definition of zero? does, an important question is whether it is fast or not. In other words, if it is used with a very large number, say 1000000, would we need a huge number of evaluation steps to compute (zero? 1000000)?

Show that this is not the case, and that zero? would still require only the same (small) number of steps to return #f when given a big number. Do this by starting from (zero? 4) and showing how it reduces to #f. (You can use either (lambda (f x) (f (f (f (f x))))) or (add1 3) as the definition of 4.)

## Question 8: Language Features 12 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 question 5 we’ve said that being closed is usually a necessary property for programs in a lexicaly scoped language. Why is it not needed always?
1. This is because there are some languages with an odd evaluation regimen, more than just dynamic-scope. For example, stack-based evaluation has a different notion of scope.
2. The disclaimer was made only for theoretical language definitions, if we consider only the formal evaluation rules. For actual implementations we only need this property.
3. As long as we’re dealing with a “pure evaluator”, where there is no compilation that optimizes binding references (eg, with de-bruijn indexes), we might have a free occurrence of an identifier in a part of the code that is not reached at runtime.
4. This is only relevant in a lazy substitution-based language, were the requirement for a closed program is not needed because of the bug that exposed our incomplete subst definition.
2. Write a test case for the extended eval for our language with lcall. More than just testing the code, it should demonstrate that lcall is actually a lazy kind of function call. In other words, if you’d change lcall to a call in this test, it should fail.
Note: this is not a multiple-choice question; but the answer can (and should) be a relatively short test.
3. We have introduced the Y combinator in the context of racket, which uses an environment based evaluation. Will it behave in the same way in a language that uses substitution as our the original FLANG?
1. No, because the switch from a substitution based evaluator to one that is based on environments (or substitution caches) has also changed the semantics of our language to a dynamically scoped one, and that would break the Y combinator definition.
2. In theory, it would behave in the same way, but in practice it is going to be hard to use because the protection that we needed to use to avoid an infinite loop will need to be much more verbose and evaluating it will be much slower.
3. Yes, of course, since an environment-based evaluator should have the same semantics as a substitution based one.
4. It would behave the same only if the language is implemented as an interpreter. However, if it is compiled, then the generated code for both evaluation strategies would be different, resulting in a different behavior.
4. There is no question 8d.