Microsquishy vs. Mashmatica

Mashmatica has profiled their entire product and found that one particular function runs very slowly. Their CEO hired a hacker from Microsquishy to "optimize" the function. However, the CEO does not trust hackers from places like Microsquishy because he knows that, while they make his code faster, they are just as likely to introduce a bug. Furthermore, the CEO knows that the Microsquishy hackers will only use small test cases to determine whether the code is faster. The CEO of Mashmatica is concerned that the code runs fast for large test cases.

Knowing that you have survived the dreaded CS212 course, the CEO of Mashmatica has hired you to double check the Microsquishy hacker's code...

The important function's definition used to look like this:

(define (f f1 f2 x)
  (map f1 (map f2 x)))

where as usual, map is defined as:

(define (map g y)
  (if (null? y)
    empty
    (cons (g (head y))
          (map g (tail y)))))

It turns out that f is called in many places but the CEO of Mashmatica claims that all the calls pass in two pure functions and a proper list of integers. The functions are pure in that they always takes integers as arguments, and produce integers as results without performing any side effects, errors, or I/O. Also, the two functions always take constant time.

The Microsquishy hacker replaced the above definition for f with the new defintion:

(define (new-f f1 f2 x)
  (map (lambda (i) (f1 (f2 i))) x))

1. Is the new definition (new-f) asymptotically faster than the old definition (f)? Justify your answer.
   
   
   
   
   
2. Using the substitution model and induction, prove that for all pure functions g1 and g2 and all lists of integers '(i1 i2 ... in):

   (f g1 g2 '(i1 i2 ... in)) = (new-f g1 g2 '(i1 i2 ... in))

   
   
   
   
   
3. Suppose the CEO of Mashmatica is wrong and that there may be a call to f which passes in impure functions (i.e., functions that perform some side effect, don't terminate, or have errors.) Under these new assumptions, give an example call which shows that new-f is not equivalent to f.
   
   
   
   
   

Solution

Return to CS 212 Final - Spring 1998