;;Tuesday:
;; Abstraction:
;;Admin
;; TA's doing homework
Tu 6:30-800 306 Soda
Mon 5-630 TBA
;;
;; Group exam
;;
;;
;;Done with describing processes ---
;; Next, how represent data
;;
;;Abstraction:
;;------------
;;Example: Counting cards.
;; a card is a word of rank and suit
;; a hand is a sentence of cards
;; Assume that we are writing a very large
;; games program. One of the tasks (in particular):
;; get the total value of a hand:
; first version -- no data abstraction
(define (total-hand hand)
(if (empty? hand)
0
(+ (butlast (last hand))
(total-hand (butlast hand)) )))
(total-hand '(3h 10c 4d))
;; Why bad?
;; Firstly, not obvious what is going on
;; If I wanted to change the proc to select
;; elements from a hand from the beginning,
;; it is not obvious where I would have to make
;; the changes. (Multiply this by 1000 for a
;; really complex program!)
;; How fix? Selectors for data
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; second version -- add selectors
(define card-rank butlast)
(define card-suit last)
(define one-card last)
(define remaining-cards butlast)
(define empty-hand? empty?)
(define (total-hand hand)
(if (empty-hand? hand)
0
(+ (card-rank (one-card hand))
(total-hand (remaining-cards hand)) )))
(total-hand '(3h 10c 4d))
;; Better (more readable), but still not perfect:
;; I select elements of a hand abstractly, but
;; I have to construct them concretely.
;;
;; If I decide that I would like the suit to come
;; before the rank of a card, I'd have to change
;; every instance of a card.
;; How fix? Constructors!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; third version -- add constructors
(define (make-card rank suit)
(word rank (first suit)) )
(define make-hand se)
(total-hand (make-hand (make-card 3 'heart)
(make-card 10 'club)
(make-card 4 'diamond) ))
(total-hand '(3h 10c 4d)) ;; Data Abstraction Violation!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; What have we got? An INTERFACE to the card and
;; hand abstractions.
;;
;;
;; What does this give me? Using the selectors and
;; costructors, I can operate on cards and hands
;; without actually knowing what they look like
;; internally.
;;
;;
;; Who cares? Well, 2 big benefits to this:
;; 1. I can change the underlying implementation
;; without having to re-look at the procs that
;; use the abstraction. (Provided that the
;; interface hasn't changed)
;; 2. I can hide details that I don't want to be
;; dealing with under the abstraction barrier!
;; Example: A system with no words:
(define (make-card rank suit)
(cond ((equal? suit 'heart) rank)
((equal? suit 'spade) (+ rank 13))
((equal? suit 'diamond) (+ rank 26))
((equal? suit 'club) (+ rank 39))
(else (error "say what?")) ))
(define (card-rank card)
(remainder card 13))
(define (card-suit card)
(nth (quotient card 13) '(heart spade diamond club)))
;; Still don't buy it??
;;
;; Well, think back to the product function from Monday:
;; We had two versions: the one with helpers, and the one
;; written in lambdas:
;; Here's the final version:
;; Notice how hard it is to figure out what is going on!
;; (Especially if you tried to write it!)
(define (product se1 se2)
(every (lambda (x)
(every (lambda (y)
(word x '- y))
se2))
se1))
(product '(a b c) '(1 2 3))
;; Our second version is much better (from an
;; abstraction point of view). We have hidden
;; some of the detail of the original in the
;; function-abstraction 'prepend-every': we
;; don't care how it works, as long as it returns
;; the right answer.
(define (prepend-every wd sent)
(every (lambda (y) (word wd '- y)) sent))
(define (product se1 se2)
(every (lambda (x) (prepend-every x se2))
se1))
(product '(a b c) '(1 2 3))
;;
;;
;; From now on, use abstraction as possible!
;;
;;
;; Tu 630-800 306 Soda
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; How does scheme aggregate stuff?
;;;
;;Abstract Data Type: Cons Pairs
;; Interface:
;; Constructor:
;; (cons x y) ; 0(1)
;; Selectors:
;; (pair x) ; returns #t if x is a pair 0(1)
;; (car p) ; returns the first element of the pair O(1)
;; (cdr p) ; returns the second element of the pair 0(1)
;; The above is what an interface to one of your ADTs should
;; look like!
(define p (cons 1 2))
p ;; check this out!
(car p)
(cdr p)
;; Pairs can be nested
(define q (cons (cons 1 2) (cons 3 4)))
q
(cdr (car q)) ;; (cdar q)
(car (cdr q)) ;; (cadr q)
;; You can do anything (!) with pairs.
;; Example: ADT lists (sequences)
;;
;; Interface:
;; Constructors:
;; (list a b c) ; Makes a list of a, b, and c 0(N)
;; (cons a lst) ; Makes a new list where the first
;; ; element is 1 and the rest are the
;; ; elements of lst
;; Selectors:
;; (car lst) ; Returns the first element 0(1)
;; (cdr lst) ; Returns the same list with the
;; ; first element removed.
;; (empty? lst) ; Returns #t if lst has no elements 0(1)
(define l (list 1 2 3))
(car l)
(cdr l)
(cdr (cdr l))
;; Lists look just like sentences!! (Not quite...)
(define l2 (cons 0 l))
(define l3 (list l2 l2))
(define l4 (cons l2 l3))
l2
l3
l4
(car l2)
(car l3)
(car l4)
;; The empty list:
(cdr (list 1))
;; Actually is a list and can be used as an element of
;; another list
(list)
(list (list))
(list (list) (list (list)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Implementation of lists:
;; box and pointer
;; cons -> makes one pair
;; list -> makes a backbone, one pair for each element
;;
;; Wednesday
;;
;; Office hours today --> not Thursday
;; No videotaping!
;;
;;
;; On the Agenda:
;;
;; 1. More with boxes and pointers
;; 2. Implementation of pairs
;; 3. Respect the abstaction: points/segment
;; 4. Recursion over lists
;; Three ways of thinking about pairs and lists:
;; 1. Box and pointer
;; 2. cons/list construction
;; 3. Scheme representation
;; 4. Tree representation
;;
;; You should be able to convert from one to another!
;; Example:
;; Constructive point of view:
(define l1 (cons 0 1))
(define l2 (cons 2 3))
(define l3 (cons l1 l2))
(define l4 (list l1 l2))
(define l5 (list l1 (list l4) l4))
(list)
(list (list))
(list (list) (list (list)))
;; Box-and-pointer point of view:
;; list -> box-and-pointer
;; list: makes a backbone of each element
;; cons: 1 new pair: car is first arg, cdr is second
(list 'a 'b' c)
(list (list 1 2) 'b 'c)
(list (list 1 2 3))
;; box-and-pointer -> list
;; How can you tell if an arbitrary structure is
;; a list??
;; Our first recursive definition!!
;; x is a list iff
;; x is the empty list (base case) OR
;; (cdr x) is a list (recursive case)
;; If it is a list, find the backbone then recursively
;; figure out the elements.
;; To scheme representation:
;; Rules:
;; Given a data structure (of pairs):
;; If it is a list, <-- How can you tell??
;; Print '(', elements (recursively), ')'
;; Otherwise, use dot notation
;; scheme rep -> lists
;; most often, an open paren means 'down a level'
;; and a close paren means close the list and go
;; up a level.
'(0 (1 ((2) 3)))
'( () (()()) )
;; Be able to move from one representation to another!
;; Monday 630-800 306 Soda
;; Jeff, Ilya
;; 2. Do pairs have to be primitive??
;;
;; No! They are an ADT, so
;; What are their essential characteristics?
;; For all x, (equal? (car (cons x y)) x) must be true
;; For all y, (equal? (cdr (cons x y)) y) must be true
;; Sure, you can use an array to make sure this is true,
;; but why not be clever and use procedures!
;;
;; Alternative implementation of pairs as functions
(define (cons x y)
(lambda (which)
(cond ((equal? which 'car) x)
((equal? which 'cdr) y)
(else (error "Bad message to CONS" which)) )))
(define (car pair)
(pair 'car))
(define (cdr pair)
(pair 'cdr))
(define x 3)
(define y 4)
(cons x y)
(car (cons x y))
(cdr (cons x y))
;; Not done this way for efficienty reasons, but neat
;; that it _can_ be done!
;; R E L O A D scheme!!
;; 3:
;; Respect
;; Thy
;; Abstraction
;;
(define (make-point x y) (cons x y))
(define (get-x p) (car p))
(define get-y cdr)
;; 1. What is the difference?
(define p1 (make-point 1 2))
(se (get-x p1) (get-y p1))
;;
;; Alright, how about rectangles:
;;
;; Version 1:
(define (make-rec x1 y1 x2 y2)
(list x1 y1 x2 y2))
(define get-x1 car)
(define get-y1 cadr)
(define get-x2 caddr)
(define get-y2 cadddr)
(make-rec 1 2 3 4)
;; Why is this wrong?
;; We've got points -- so use them:
(define (make-rec x1 y1 x2 y2)
(cons (make-point x1 y1)
(make-point x2 y2)))
(define (get-x1 p)
(get-x (car p)))
(define (get-y1 p)
(get-y (car p)))
(get-x1 (make-rec 1 2 3 4))
;;
;; Better than first, but still not perfect
;; Why??
;; Respect the point abstraction -- not just
;; with constructors and selectors, but with
;; usage, also:
(define (make-rec p1 p2)
(cons p1 p2))
(define get-p1 car)
(define get-p2 cdr)
(get-x (get-p2 (make-rec (make-point 1 2)
(make-point 3 4))))
(define (tri p1 p2 p3)
(list p1 p2 p3))
(define (get-p2 t)
(cadr t))
;;
;; Little more wordy, but conceptually more pure
;;
;; Box and pointer of rectangle:
;; think of it like a pair pointing to two objects
;; rather than three pairs pointing to 4 numbers.
;; 4. Recursion over lists:
;;
;; Exaggerate
;;
(define double (lambda (x) (* 2 x)))
(define (exaggerate sent)
(cond ((empty? sent) (se))
((number? (first sent)) (se (double (first sent))
(exaggerate (bf sent))))
(else (se (first sent) (exaggerate (bf sent))))))
(exaggerate '(i gained 15 pounds of muscle last year))
;;
;; How bout for lists?
;;
(define (exaggerate lst)
(cond ((null? lst) (se))
((number? (car lst)) (cons (double (car lst))
(exaggerate (cdr lst))))
(else (cons (car lst) (exaggerate (cdr lst))))))
(exaggerate '(I gained 15 pounds of muscle last year))
;;
;; What are we missing??
;; Lists can be nested:
(exaggerate
'(I gained 15 pounds of muscle
(and lost 10 pounds of fat)
last year))
;; deep-exaggerate
(define (deep-exaggerate lst)
(cond ((null? lst) (se))
((list? (car lst)) (cons (deep-exaggerate (car lst))
(deep-exaggerate (cdr lst))))
((number? (car lst)) (cons (double (car lst))
(deep-exaggerate (cdr lst))))
(else (cons (car lst) (deep-exaggerate (cdr lst))))))
(deep-exaggerate
'(I gained 15 pounds of muscle
(and lost 10 pounds of fat)
last year))