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