# Recitation 9

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

### A Spectrum of Equalities

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

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

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