recitation 11: tagged data

===========================================================

* what is tagged data?
  - attach a symbol to all nontrivial data (convention)
  - always check the symbol before operating on the data

* ADT: abstract data types

* why use tagged data?
  - data-directed programming: "dispatch on type"
    contract still satisfied, data abstraction still valid
  - operations strip the tags, operate & reattach the tag
    input & return types are tagged data!
  - defensive programming: fail gracefully when given 
    bad arguments (type checking)
  - allow future extension

* common errors:
  - calling a function on the wrong type of data
  - mis-interpreting what a value represents,
    making an incorrect assumption about the data
  - changing one part of a program and not another 
    (common when you have multiple programmers)
* garbage return value is often worse than an error, why?
  - we think we got an okay answer (but send our mars
    rover to its death because of an inches/cm error)
  - we get an error later in the program and blame the
    wrong piece of code/programmer (if I had a dollar
    for every time a student said "the given code has a 
    bug" or "I found a bug in scheme"... )
* avoiding errors:
  - make sure its a pair before you grab its tag
  - use the else branch only for errors not as the last case
  - be paranoid, check tags not only in dispatch procedure
    but also in accessor or operation procedures

===========================================================

Notions of Equality

eq?     the most discriminating test of equality.  If eq? can't tell
        the difference between two things, then nothing else in Scheme
        can either.  Pairs are eq? only if they share the same box and
        pointer structure. Don't use eq? for numbers.

=       works only on numbers.  It generates errors for non-numbers.

eqv?    "the usual" test for equality of atomic items. 
        It uses eq? for symbols and booleans, = for numbers, 
        string=?  for strings, and eq? for pairs (will return
        true only if both items share the same box & pointer structure).
        For procedures it isn't well defined.

equal?  tests "whether they print the same". It uses eqv? for
        everything except pairs. It recurses on the car and cdr.

Let's write equal?:
(define (equal? item1 item2)
   (cond ((null? item1) (null? item2))
         ((null? item2) #f)
         ((and (not (pair? item1)) (not (pair? item2)))
             (eqv? item1 item2))
         ((or (not (pair? item1)) (not (pair? item2)))
             #f)
         (else (and (equal? (car item1) (car item2))
                    (equal? (cdr item1) (cdr item2))))))

===========================================================

ROYAL EVALUATOR (approved by the Queen of England)

* build an "evaluator" for simple scheme-like expressions!
* "coercion" / "casting" to change type of object

(define a (make-sum (make-ounces 5) (make-ounces 8)))
a  ->  (+ (5 ounces) (8 ounces))
(royal-eval a)  ->  (13 ounces)

(define b (make-sum (make-pounds 1) (make-ounces 8)))
b  ->  (+ (1 pounds) (8 ounces))
(royal-eval b)  ->  (24 ounces)

(define c (make-mul (make-inches 4) (make-inches 3)))
c  ->  (* (4 inches) (3 inches))
(royal-eval c)  ->  (12 square-inches)

(define d (make-div (make-pounds 5) (make-mul (make-inches 1) (make-inches 1))))
d  ->   (/ (5 pounds) (* (1 inches) (1 inches)))
(royal-eval d)  ->  (5 psi)

(define e (make-div (make-stones 8) (make-mul (make-feet 2) (make-inches 3))))
e  ->   (/ (8 stones) (* (2 feet) (3 inches)))
(royal-eval e)  ->  (1.5555555555555556 psi)

===========================================================

;; WEIGHT
(define (make-ounces x) (list x 'ounces))
(define (make-pounds x) (list x 'pounds))
(define (make-stones x) (list x 'stones))
(define (ounces? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'ounces)))
(define (pounds? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'pounds)))
(define (stones? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'stones)))
(define (get-ounces x) (if (ounces? x) (car x) (error "not an ounces object")))
(define (get-pounds x) (if (pounds? x) (car x) (error "not an pounds object")))
(define (get-stones x) (if (stones? x) (car x) (error "not an stones object")))
(define (weight? x) (or (ounces? x) (pounds? x) (stones? x)))

;; LENGTH
(define (make-inches x) (list x 'inches))
(define (make-feet x) (list x 'feet))
(define (inches? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'inches)))
(define (feet? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'feet)))
(define (get-inches x) (if (inches? x) (car x) (error "not an inches object")))
(define (get-feet x) (if (feet? x) (car x) (error "not an feet object")))
(define (length? x) (or (inches? x) (feet? x)))

;; AREA
(define (make-square-inches x) (list x 'square-inches))
(define (square-inches? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'square-inches)))
(define (get-square-inches x) (if (square-inches? x) (car x) (error "not a square-inches object")))
(define (area? x) (or (square-inches? x)))

;; PRESSURE
(define (make-psi x) (list x 'psi))
(define (psi? x) (and (pair? x) (pair? (cdr x)) (eq? (cadr x) 'psi)))
(define (get-psi x) (if (psi? x) (car x) (error "not an psi object")))
(define (pressure? x) (or (psi? x)))

;; SUM, MUL, DIV
(define (make-sum x y) (list '+ x y))
(define (sum-exp? x) (and (pair? x) (eq? (car x) '+)))
(define (sum-arg-1 x) (if (sum-exp? x) (cadr x) (error "not a sum object")))
(define (sum-arg-2 x) (if (sum-exp? x) (caddr x) (error "not a sum object")))
(define (make-mul x y) (list '* x y))
(define (mul-exp? x) (and (pair? x) (eq? (car x) '*)))
(define (mul-arg-1 x) (if (mul-exp? x) (cadr x) (error "not a mul object")))
(define (mul-arg-2 x) (if (mul-exp? x) (caddr x) (error "not a mul object")))
(define (make-div x y) (list '/ x y))
(define (div-exp? x) (and (pair? x) (eq? (car x) '/)))
(define (div-arg-1 x) (if (div-exp? x) (cadr x) (error "not a div object")))
(define (div-arg-2 x) (if (div-exp? x) (caddr x) (error "not a div object")))

===========================================================

(define (royal-eval exp)
  (cond
   ((simple-unit? exp) exp)
   ((sum-exp? exp) (royal-add (royal-eval (sum-arg-1 exp))
			      (royal-eval (sum-arg-2 exp))))
   ((mul-exp? exp) (royal-mul (royal-eval (mul-arg-1 exp))
			      (royal-eval (mul-arg-2 exp))))
   ((div-exp? exp) (royal-div (royal-eval (div-arg-1 exp))
			      (royal-eval (div-arg-2 exp))))
   (else (error "don't know how to deal with this expression"))))

===========================================================

(define (simple-unit? x) (or (weight? x) (length? x) (area? x) (pressure? x))

(define (royal-add x y)
  (cond ((and (weight? x) (weight? y))
	 (make-ounces (+ (get-ounces (weight-to-ounces x))
			 (get-ounces (weight-to-ounces y)))))
	((and (length? x) (length? y))
	 (make-inches (+ (get-inches (length-to-inches x))
			 (get-inches (length-to-inches y)))))
	(else (error "can't add these units"))))

(define (royal-mul x y)
  (cond	((and (length? x) (length? y))
	 (make-square-inches (* (get-inches (length-to-inches x))
				(get-inches (length-to-inches y)))))
	(else (error "can't mul these units"))))

(define (royal-div x y)
  (cond	((and (weight? x) (area? y))	 
	 (make-psi (/ (/ (get-ounces (weight-to-ounces x)) 16)
		      (get-square-inches y))))
	(else (error "can't div these units"))))

(define (weight-to-ounces x)
  (cond ((ounces? x) x)
	((pounds? x) (make-ounces (* 16 (get-pounds x))))
	((stones? x) (weight-to-ounces (make-pounds (* 14 (get-stones x)))))
	((weight? x) (error "don't know conversion for this weight"))
	(else (error "this isn't a weight"))))

(define (length-to-inches x)
  (cond ((inches? x) x)
	((feet? x) (make-inches (* 12 (get-feet x))))
	((weight? x) (error "don't know conversion for this length"))
	(else (error "this isn't a length"))))

===========================================================

* It's annoying that:
  (royal-eval (make-sum (make-pounds 1) (make-pounds 2))) 
           -> (48 ounces)
  We probably want the answer in pounds.  

  And this:
  (royal-eval (make-sum (make-pounds 7) (make-ounces 6)))
           -> (118 ounces)
  would be easier to read as: (7 pounds 6 ounces)

  How could you redesign the system to do this?

* It's annoying that we had to add types for squared-inches and
  pounds-per-square-inch.  Can we redesign this system to do something
  more general?

  One Idea: Instead of just a symbol as a tag & type, we could have a
  collection of units as a type.  For example:

  (5 (compound-type (pounds) (inch inch)))  =  5 pounds per square inch
  (27 (compound-type (miles) (hour))) = 27 miles per hour
  etc.

===========================================================