Recitation 10

Today's idea: Memoization, An Application of Mutation

Administrivia
-- I'm away next Wednesday and Friday (invited lecture at Automated Softw Eng Conference)
-- You should choose another recitation; please spread yourselves around!

Section #	Time	Room	Instructor	Tutor
1	10:00	13-4101	Randy Davis	Jim Waldrop
2	11:00	13-4101	Randy Davis	Kyle Ingols
3	10:00	36-155	Daniel Jackson	Jim Waldrop/Mike Phillips
4	11:00	36-156	Daniel Jackson	Robbin Chapman
5	11:00	26-204	Tony Eng	Robbin Chapman/Kyle Ingols
6	12:00	26-204	Tony Eng	Aileen Tang
7	1:00	26-204	Leslie Kaelbling	Mieszko Lis
8	2:00	26-210	Leslie Kaelbling	Mike Phillips
9	12:00	36-153	Tomas Lozano-Perez	Aileen Tang/Mieszko Lis

Recitation Problem

(define (make-cycle x)
(set-cdr! (last-pair x) x)
x
)

(define (last-pair x)
(if (null? (cdr x)) x (last-pair (cdr x))))

Draw a BPD for the value of z after

(define z (make-cycle (list 'a 'b 'c)))

What happens when we evaluate (last-pair z)?

We discussed the cycle that arises in z, and noted the new form that the first define takes. Its a double shorthand: first, for a lambda as we've seen many times before, and second for a begin expression.

Cell Mutations

We reviewed the cons cell mutating procedures set-car! and set-cdr! introduced in lecture yesterday. The essential idea is that

(set-car! c v)

changes the cell c so that it's cdr is subsequently v.

I pointed out some possible confusions:
-- c does not name a different cell after; the procedure changes the cell that is named c
-- no new cells are created; only cons does that
-- no change is made to v

We sometimes say sloppily "(set-cdr! c ..) changes the cdr of c", but that's ambiguous. Suppose someone told you "Jane got fed up with her husband Bob, so she changed him". Does that mean that Jane got a new husband, or that she somehow made Bob a better person? Similarly, you might get confused about set-cdr!, but remember it always which object is the cdr, and doesn't change the object itself.

We played around with some examples, and saw "aliasing": when a change appears unexpectedly because two names refer to the same object.

(define x (list 1 2))
(define y x)
here, y evaluates to (1 2)
(set-car! x 3)
here, y evaluates to (3 2)

We also discussed the begin special form:

(begin e1 ... en)

evaluates each expression e1 ... en in turn, and returns as its value the value of the final expression. Until now, we've had no use for such a form, since all expressions were executed for their values. Now we have expressions executed for their effect, so we'll do things like

(begin
set-car! x v
x)

which applies set-car! to x then returns x itself. Note that the value of (set-car! ...) and (set-cdr! ...) is not defined.

Bad Fibonnacci

We looked at a really bad implementation of the Fibonnacci function:

(define (fib k)
(cond ((= 0 k) 0)
((= 1 k) 1)
(else (+ (fib (- k 1)) (fib (- k 2))))))

I pointed out that the ratio (fib i) / (fib (- i 1) tends to the golden ratio as i grows. I told you about nice properties of the A-series of paper in Europe and asked you to find out what nice propery American letter size paper has.

We played with this function and noticed that when k reaches about 28, (fib k) starts to take a long time. We left (fib 40) running while we did an exercise, and it hadn't terminated after 15 minutes. One of you pointed out that because each application of the function spawns two further applications, the number of applications in total will grow exponentially! And in fact, we noticed that (fib 27) took about twice as long as (fib 26).

I drew a picture on the board (it's in SICP too) showing how this implementation wastes computation by computing the same Fibonnacci number repeatedly.

Another ADT: Arrays

As an exercise, you implemented a fixed size array with the following operations:

mk-array: Num -> Array            ;; (mk-array k) makes an array indexed from 0 to k-1
set: Num, Any, Array -> undef   ;; (set a i v) makes v the element of array a with index i
get: Num, Array -> Any              ;; (get a i) returns the element of array a with index i

We assumed that there are no out-of-bound accesses. A special tag 'no-elt can be used when initializing the array, so get will return this symbol if there has not been a set operation at that index.

Here's an implementation:

(define (mk-array n)
(if (= n 0)
      '()
      (cons 'no-elt (mk-array (- n 1)))))
(define (get k t)
(cond ((null? t) (error "out of bounds access"))
        ((< k 0)   (error "out of bounds access"))
        ((= k 0)   (car t))
        (else      (get (- k 1) (cdr t)))))
(define (set k v t)
(cond ((null? t) (error "out of bounds access"))
        ((< k 0)   (error "out of bounds access"))
        ((= k 0)   (set-car! t v))
        (else      (set (- k 1) v (cdr t)))))

Better Fibonnacci Implementation

We then used the technique called memoization to improve our Fib function. The key idea is to keep a "memo" of results previously computed, in an array. Instead of computing afresh, we first look up the number in an array to see if its Fibonnacci number has been previously computed.

As we saw by playing with the new implementation, the speed improvement is dramatic. (fastfib 40) is instantaneous, and (fastfib 400) takes only a couple of seconds.

We discussed how our array implementation isn't random access, but we noted that in this case that's only a small effect compared to the change in overall structure of the algorithm.

I left you to ponder why mutation is really needed here, and why we couldn't achieve memoization easily without it.

(define (fastfib k)
(let ((t (mk-array (+ 1 k))))
    (fastfib-helper k t)))
(define (fastfib-helper k t)
(let ((fib (lambda (k)
               (cond ((= 0 k) 0)
                     ((= 1 k) 1)
                     (else (+ (fastfib-helper (- k 1) t)
                              (fastfib-helper (- k 2) t))))))
        (result (get k t)))
    (if (eq? result 'no-elt)
        (let ((f (fib k)))
          (begin (set k f t) f))
        result)))

It's crucial that the recursive call in fib is to fastfib-helper and not fib or fastfib. Why?

Definitions

(define (fib k)
(cond ((= 0 k) 0)
((= 1 k) 1)
(else (+ (fib (- k 1)) (fib (- k 2))))))

(define (golden-ratio i) (exact->inexact (/ (fib (+ i 1)) (fib i))))

(define (mk-array n)
(if (= n 0)
'()
(cons 'no-elt (mk-array (- n 1)))))

(define (get k t)
(cond ((null? t) (error "out of bounds access"))
        ((< k 0)   (error "out of bounds access"))
        ((= k 0)   (car t))
        (else      (get (- k 1) (cdr t)))))

(define (set k v t)
(cond ((null? t) (error "out of bounds access"))
        ((< k 0)   (error "out of bounds access"))
        ((= k 0)   (set-car! t v))
        (else      (set (- k 1) v (cdr t)))))

(define (fastfib k)
(let ((t (mk-array (+ 1 k))))
(fastfib-helper k t)))

(define (fastfib-helper k t)
(let ((fib (lambda (k)
               (cond ((= 0 k) 0)
                     ((= 1 k) 1)
                     (else (+ (fastfib-helper (- k 1) t)
                              (fastfib-helper (- k 2) t))))))
        (result (get k t)))
    (if (eq? result 'no-elt)
        (let ((f (fib k)))
          (begin (set k f t) f))
        result)))

Daniel Jackson
October 8, 1999