Optimization

You have been contracted to develop a compiler for the complete Scheme language, including side effects. Your employer, Microsquishy, asks that you include a set of "optimizations". However, judging from the number of bugs in their products, you feel that it is important to make sure that Microsquishy's proposed optimizations preserve the semantics of Scheme.

The list of potential optimizations is presented below in the form E   E' where E and E' range over Scheme expressions. You may assume that if the optimization introduces a new variable in E', then that variable is "fresh" - that is, the variable is different from all other variables in the program.

Determine whether each potential optimization preserves the input/output behavior for all Scheme programs. If the optimization preserves the input/output behavior, write "OK". If the optimization does not preserve input/output behavior, write "NOT OK" and give an example program which behaves differently from the "optimized" version.

1. (* 1 E)  E
   
   
   
   
   
2. (* 0 E)  0
   
   
   
   
   
3. (* 2 E)   (let ((x E)) (+ x x))
   
   
   
   
   
4. (if E₁ E₂ E₃)  E₁
   
   
   
   
   
5. (if E₁ E₂ E₃)  E₂
   
   
   
   
   
6. (let ((x E1)) E2)  ((lambda (x) E2) E1)
   
   
   
   
   
7. (method (x) (begin (set! x E) x))   (lambda (x) E)
   
   
   
   
   

Solution

Return to CS 212 Prelim 2 - Spring 1998