# Recitation 8

Today's Idea: Data abstraction and tags

### Recitation Question

You are given two tagged ADTs for points which include the following
operations:

(define (make-polar-point r theta) ...)
(define (polar-point? pt) ...)
(define (make-cartesian-point x y) ...)
(define (cartesian-point? pt) ...)

; answer the distance between two cartesian points
; type: CartesianPoint,CartesianPoint -> number
(define (cart-distance CartPt1 CartPt2) ...)

; convert coordinates
; type: PolarPoint -> CartesianPoint
(define (polar2cartesian PolarPt) ...)

Assume that none of the above functions have internal tag checks.
Use good defensive programming techniques to implement the function

; Point = PolarPoint | CartesianPoint
; type: Point, Point -> number
(define (point-distance pt1 pt2) ...)

### Solution

(define (cart-if-needed p)
(cond
((cartesian-point? p) p)
((polar-point? p) (polar2cartesian p))
(else (error "unknown type: " p))))

(define (point-distance p1 p2)
(cart-distance (cart-if-needed p1) (cart-if-needed p2)))

### Basic Idea of Data Abstraction

Abstract types
-- not limited to built-in types such as numbers and strings
-- can add "user-defined types"
-- these have ops just like the built-ins
-- and hidden representation

Clients and implementors
-- client: uses the abstract type (ie, writes code that calls its operations)
-- implementor: builds the abstract type (ie, writes the code of the operations)
-- contract between them called the spec

Representation choices
-- same abstract type can be represented many ways
-- eg, set as list, tree, vector

Rep independence
-- client need not know how type is represented
-- in fact, client SHOULD not know

Why rep independence?
-- client code neater and simpler
-- no need to change client when rep changes
-- implementor can make type very efficient

### Example of Data Abstraction

Set
-- collection of elements
-- no order
-- each element in or not: no count

Using set:

(define s (insert empty-set 'a))
(define t (insert empty-set 'b))
(define u (union s t))
(define v (difference u t))
(is-member s 'a)
> #f
(is-member s 'b)
> #t
(is-member v 'a)
> #t

Look Ma! No rep!

Obvious rep
-- as list of elements without duplicates
-- like we did in last recitation

Sample operation:

(define insert cons)
(define is-member member)
What's wrong with this?
-- Might apply set operation to non-set
-- Hard to see which expressions make sets, which make lists

### Using Tags

Use of tags
-- defensive programming: prevents application to non-sets
-- shows up and down from list to set and vice versa

Tagging code

(define set-tag 'set)

(define (list2set r)
(cons set-tag r))

(define (set2list r)
(if (and (pair? r)
(equal? (car r) set-tag))
(cdr r)
(error "not a set")))

Types
-- list2set : list<a> -> set<a>
-- set2list : set<a> -> list<a>

Sample operation

(define (delete set elt)
(list2set (remove elt (set2list set))))
Exercises:
-- write the insert method, using is-member
-- write union using insert, using accumulate and insert
-- write symmetric-difference, using only set operations

Inside and outside
-- Which ops access the rep?
-- the ones that call set2list
-- Sym diff is outside, the rest are inside

Why inside? Why outside?

### 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-tag 'set)

(define (list2set r)
(cons set-tag r))

(define (set2list r)
(if (and (pair? r)
(equal? (car r) set-tag))
(cdr r)
(error "not a set")))

(define empty-set (list2set null))

(define (is-member set elt)
(pair? (member elt (set2list set))))

(define (insert set elt)
(if (is-member set elt)
set
(list2set
(cons elt (set2list set)))))

(define (delete set elt)
(list2set (remove elt (set2list set))))

(define (union s1 s2)
(accumulate
(lambda (elt s) (insert s elt))
s1 (set2list s2)))

(define (difference s1 s2)
(accumulate
(lambda (elt s) (delete s elt))
s1 (set2list s2)))

(define (sym-diff s1 s2)
(union (difference s1 s2)
(difference s2 s1)))

(define s (insert empty-set 'a))
(define t (insert empty-set 'b))
(define u (union s t))
(define v (difference u t))

Daniel Jackson
Sept 30, 1999