Recitation 9

Today's Idea: A Safer Data Abstraction
(And on the way, some stuff about equality and let)

A Spectrum of Equalities

A tricky business
-- notion of equality is hard anyway
-- in Scheme, three equality ops
-- underdefined to allow implementation freedom
-- so can't predict the result of some equality tests!

Three equality ops
-- eq? is the finest
-- equal? is the coarsest
-- eqv? is in between

equal?
-- often called "structural equality"
-- recursively compares the contents of structures, and finally compares primitives with eqv?
-- generally, two values are equal? if they print the same
-- may fail to terminate if arguments are cyclic structures
-- can't really tell if two values are equivalent: eg (lambda (x) x) and (lambda (y) y) may not be equal?

eq?
-- tells if two cons cell values are the same cell
-- behaviour on primitives is undefined (but always returns true or false, and if it returns true, eqv? would also)

eqv?
-- like eq?, but gives expected behaviour on primitives (eg, (eqv? 2 2) is true)

Warmup Exercises

(eq? (list) (list))
(equal? (list) (list))
(eq? (cons 1 null) (cons 1 null))
(equal? (cons 1 null) (cons 1 null))
(define x (cons 1 null))
(eq? x x)

(define q (list 2 3))
(define p (cons 1 q))
(define r (list 1 2 3))
(eq? q (cdr p))
(eq? q (cdr r))

(let ((x 1)) x)
(define x 3)
(let ((x 1) (y x)) (+ x y))
(let* ((x 1) (y x)) (+ x y))

We talked about how let desugars to lambda, and how let* is a shorthand for a nested let. Let binds its variables "in parallel".

A Data Abstraction

From last time:

(define set-tag 'set)
(define list2set (lambda (r)(cons set-tag r)))
(define set2list (lambda (r)
(if (and (pair? r)
           (equal? (car r) set-tag))
      (cdr r)
      (error "not a set"))))
(define empty-set (list2set null))
(define is-member (lambda (set elt)
(pair? (member elt (set2list set)))))
(define insert (lambda (set elt)
(if (is-member set elt)
      set
      (list2set
       (cons elt (set2list set))))))
(define delete (lambda (set elt)
(list2set (remove elt (set2list set)))))

A Safer Data Abstraction

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

We discussed how this worked and how it prevents violation of the abstraction barrier.
The key idea is that the tag is now made from a cons cell, and any subsequent cons cell must be different from it. The names set-tag, list2set, etc are not visible outside the let expression, so the client can't use them to make a representation value.

However, the abstraction isn't foolproof. Can you figure out how to violate it?

Definitions used

(define (accumulate f base p)
    (cond
      ((null? p) base)
      (else (f (car p) (accumulate f base (cdr p))))))

(define (remove e p)
    (cond ((null? p) '())
          ((equal? e (car p))(cdr p))
          (else (cons (car p)
                      (remove e (cdr p))))))

Definitions Developed

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

Daniel Jackson
October 6, 1999