Review

• Generative recursion,
• local,
• Objects,
• Higher-Order Functions (That is, functions which take or return functions as arguments.)
• Tail-recursion; in particular, accumulator-style recursion
• The use of begin and set!
• Loop constructs: while-fn

• Write the function add-fun, which takes two functions f,g and returns a new function f+g, defined as: (f+g)(x) = f(x) + g(x).
• Do the same as above, except instead of using addition, combine f,g with (a) multiplication, (b) exponentiation, (c) >, (d) max, and (e) mod (i.e. remainder). Hint: write one function which you call five times, not five separate functions.
• Write a function auto-factory which creates car objects. A car object has an internal concept of its speed, and understands the following messages:
  • 'cruise with a number. The number corresponds to a speed, and the car returns either 'speeding-up or 'slowing-down in response to the 'cruise message.
  • 'light with the symbol 'green or 'red. The car returns either 'slamming-on-brake or 'maintaining-speed depending on the situation. The car's speed should be zero after a red light, and note that a parked car doesn't need to brake.
  Both messages cause the car's speed to change. Be sure that you can make two different car-objects, which are independent of each other.
• Bonus: modify the above problem so that each car has its own unique serial number upon creation. You can add the message 'get-id (and a dummy argument) to have it return its serial number. The first created car should have serial number 1, then next 2, etc.
• Consider the function num-occurrences, which takes a list and l symbol s, and returns how many times s occurs in l.
  Implement this function using (1) natural recursion, (2) accumulator-style recursion, and (3) while-fn and set!.

Memoization (optional)

(define fib
  (lambda (n)
    (if (< n 2)
        1
        (+ (fib (- n 1)) (fib (- n 2))))))

(define counter 0)
(define instrumentize
  (lambda (f)
    (lambda (n)
       (begin (set! counter (add1 counter))
              (f n)))))
(define call
  (lambda (f n)
     (begin (set! counter 0)
            (f n)
            counter)))

(set! fib (instrumentize fib))
(call fib 5)
(call fib 20)
(call fib 30)

We saw one solution to this predicament in the homework, using two accumulators. This worked fine for fib, but not all functions can be patched in that same way. (Besides, calling (fib 30) twice in a row takes twice as long as it would if computers were smart.) What is a general approach we can take?

Yes, memoization! MemoiWhation, you ask? The idea is simple: every time you compute a result, write down the answer. Later, when you are asked to compute something, before doing the "real" work, first check whether you've solved this exact problem before.

Association Lists

A common idea in Scheme programs is that of an association list, which is just a list of ``key/entry'' pairs. For example, a program might keep a list which associates month-symbols with their numeric counterparts:

(('jan 1) ('Jan 1) ('feb 2) ('Feb 2) ... )

Now, back to memoization: write a function fib-memo which has a persistent local variable prev-results, an association list of argument/result pairs.

If you instrumentize this version of fib, how many calls are made for (call fib-memo 20)? How about for (call fib-memo 19)?