Recitation 13

Message Passing

Our introduction to object-oriented programming begun with constructing data abstractions that hide their representation and use message symbols to select a procedure.

(define (make-counter)
(let ((val 0))
    (lambda (msg)
      (cond ((eq? msg 'up) (set! val (+ val 1)))
            ((eq? msg 'down) (set! val (- val 1)))
            ((eq? msg 'show) (display val) (newline))))))

(define c (make-counter))
(c 'up)
(c 'up)
(c 'show)

Note the safe encapsulation of the rep of the counter. Also note how, unlike fastfib2, there's a separate instance of the rep for each counter.

Here's another data abstraction in this style. It's a bit more interesting than the counter, because its operations have arguments. Note how the result of "passing a message" is now a procedure to be applied. This allows us to handle arbitrary numbers of arguments. The constructor also has arguments; these are for initializing the object.

(define (make-stock name initial)
(let ((val initial))
    (lambda (msg)
      (cond ((eq? msg 'move) (lambda (amt) (set! val (+ val amt))))
                ((eq? msg 'show) (lambda ()
                               (display name)
                               (display "@")
                               (display val)
                               (newline)))))))

(define s (make-stock "intel" 65))
((s 'move) 10)
((s 'show))
((s 'move) 10)
((s 'show))

(define t (make-stock "aol" 115))
((t 'move) -5)
((t 'show))

And now, finally, here's a data abstraction that represents a stock portfolio. This introduces us to the idea of the "has-a" relationship between objects: each portfolio has some stocks. Note that sending a message to a stock object can now cause the result of sending a message to a portfolio to be different!

(define (make-portfolio name)
(let ((stocks '()))
    (lambda (msg)
      (cond ((eq? msg 'buy) (lambda (stock num)
                              (set! stocks
                                    (cons (cons num stock) stocks))))
            ((eq? msg 'show) (lambda ()
                               (display name)
                               (display " contains ")
                               (newline)
                               (map (lambda (c)
                                      (display (car c))
                                      (display "x")
                                      (((cdr c) 'show) ))
                                    stocks)
                               (newline)))))))

(define p (make-portfolio "my portfolio"))
((p 'buy) s 100)
((p 'buy) t 100)
((p 'show))
((s 'move) 10)
((p 'show))

An Even Faster Fibonnacci

Recall our Fib procedure from Recitation 10. We had to pass the memoization pad (the array of computed results) around. Now that we understand the environment model we can do something cleaner: we can encapsulate the pad inside the procedure. Moreover, results are now remembered across uses.

Old code:

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

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

New code:

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

We drew the environment model for fastfib2 and its invocation. For the let expressions, we didn't bother to desugar to lambda -- we just hung a frame.

This procedure has an interesting property. Although it uses mutation, it appears to its client to be entirely free of side effects. Aside from the dramatic improvement in performance, there's no way the client can tell that inside the procedure mutation is being used.

It will break if presented with an argument greater than 1000, of course. Not exactly high quality software engineering here :-)

Back to sets

Exercise for you: can you rewrite our set example in object oriented style so that it now encapsulates the rep properly?

Here's our old version:

(define set-adt
(let ((set-tag (list '())))
    (let ((list2set (lambda (r)(cons set-tag r)))
          (set2list (lambda (r)
                      (if (and (pair? r)
                               (eq? (car r) set-tag))
                          (cdr r)
                          (error "not a set")))))
      (let ((empty-set (list2set null))
            (is-member (lambda (set elt)
                         (pair? (member elt (set2list set)))))
            (insert (lambda (set elt)
                      (if (is-member set elt)
                          set
                          (list2set (cons elt (set2list set))))))
            (delete (lambda (set elt)
                      (list2set (remove elt (set2list set))))))
        (list empty-set is-member insert delete)))))
(define empty-set (car set-adt))
(define is-member (cadr set-adt))
(define insert (caddr set-adt))
(define delete (cadddr set-adt))

Definitions used

"Arrays" from Recitation 10:

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

Daniel Jackson
October 20, 1999