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 |

(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.

(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))We also discussed the

(define y x)

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

here, y evaluates to (3 2)

(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

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

set-car! x v

x)

(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.

mk-array: Num -> Array ;; (mk-array k) makes an array indexed from 0 to k-1We 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.

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

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)))))

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)It's crucial that the recursive call in fib is to fastfib-helper and not fib or fastfib. Why?

(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)))

(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