lecture.org 6.4 KB
Lecture 2B Compound Data
so far we've been talking about procedures
-
primitive things
-
means of combination
-
means of abstraction
we've seen general methods for computing things
the Crucial idea:
!! We are building a layered system
abstraction boundaries, ie
sqrt ;; above the abstraction layer
/---------------\ ;; abstraction layer
good-enuf? ;; hidden parts
divorce the task of building things from the task of building their parts.
now we will look at the same thing in terms of data
-
primitive data
-
glue for combining
-
methodology for abstraction
all of which we will do by building layers of abstraction.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' the system we will be considering is rational numbers: how to add, mul, sub, div fractions
we dont have a system for rational numbers
scheme gives us a system for numbers, but not a number for a numerator and a denominator
we will enable this by using the technique of
!! WISHFUL THINKING
we will imagine we have these procedures
(make-rat n d) ;; -----> returns some 'cloud' containing n and d (numer **cloud**) ;; -> takes in one of those 'clouds' and returns numerator (denom **cloud**) ;; -> takes in one of those 'clouds' and returns denominator
how 'cloud' is made is not our problem: we dont want to know
being able to leverage a 'cloud' though will give us the ability to work
(define (+rat x y)
(make-rat
(+ (* (numer x)(denom y))
(* (numer y)(denom x)))
(* (denom x) (denom y))))
no problem at all, if we have these 'clouds'
we can also implement the product of 2 rats
(define (*rat x y)
(make-rat
(* (numer x) (numer y))
(* (denom x) (denom y))))
we assumed by wishful thinking that we had a data object
we assumed we had a way to make one, a "constructor"
-
make-rat
we assumed we had ways to get things out, "selectors"
-
denom
-
numer
without abstractions: more importantly thon confusing our programming, we might confuse our mind
–> break
we need a glue for data objects. lisp provides the glue via
LIST STRUCTURE via PAIRS
'cons' taking two args and returning a pair 'car' selecting the first part of a pair 'cdr' selecting the second part of a pair
there is a "box and pointer" notation which i wont try to draw in ascii art here today
with these data glue primitives, we can easily define the 'clouds'
(define (make-rat n d)
(cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
for
1 1 --- + --- 2 4
(define a (make-rat 1 2)) (define b (make-rat 1 4)) (define ans (+rat a b)) (numer ans) ;; 6 (denom ans) ;; 8
our implementation does not reduce to lowest terms
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g)
(/ d g))))
DATA ABSTRACTION:
we have *rat, +rat, etc !!the use of data ------------------------------------------- abstraction layer: make-rat/numer/denom ------------------------------------------- implemented via pairs !!the representation of data
ableson said "bs" O_O
why bother with data abstraction?
goes back to the sorceress' power over a spirit if she has its name
when programming, we are forced to make decisions. in general, for flexibility, we'd like to never make a decision until we absolutely have to. there's a fine line between deferring decisions and outright procrastination. we'd like to make progress and also never be bound by the consequences of our decisions. data abstraction allows this. we used wishful thinking. WE GAVE A NAME TO THE DECISION. then we continued as if decisions had been made. sometimes the decision never has to be made.
!! GJS: "there's a good part of computer science that's a lot like magic. theres a bad part that's a lot like religion"
—> break
its not so great that we can do rational arithmetic. it is great that we can use these as building blocks for something more complex
imagine points in a plane, like the point p(1,2)
we can make a system for representing points in a plane
(define (make-vector x y) (cons x y)) ;; constructor (define (xcor p) (car p)) ;; selector (define (ycor p) (cdr p)) ;; selector
given points in a plane, we might want to use them to build something. we might want to talk about line segments connecting points.
(define (make-seg p q) (cons p q))
(define (seg-start s) (car s))
(define (seg-end s) (cdr s))
(define (midpoint s)
(let ((a (seg-start s))
(b (seg-end s)))
(make-vector
(average (xcor a) (xcor b))
(average (ycor a) (ycor b)))))
(define (length s)
(let
((dx (- (xcor (seg-end s))
(xcor (seg-start s))))
(dy (- (ycor (seg-end s))
(ycor (seg-start s)))))
(sqrt (+ (square dx)
(square dy)))))
here we have built a LAYERED SYSTEM
SEGMENTS ----------------------------\ abstraction layer make-seg/seg-start/seg-end ----------------------------------------------- VECTORS ----------------------------\ abstraction layer make-vector/xcor/ycor ----------------------------------------------- PAIRS
this grows quite naturally bc pairs can themselves point to other pairs etc
one of abelson's fav words: !! CLOSURE when you put things together, you can then put those things together, like pairs of pairs
—> break
"its always harder in computer science to talk about what something means than to go off and do it"
with
-
make-rat
-
numer
-
denom
we have abstract data
it fulfills a contract:
IF x = (make-rat n d)
THEN
(numer x) n
--------- = ---
(denom x) d
abelson: "let me do something that i think is really going to terrify you"
AXIOM FOR PAIRS:
FOR ANY x AND y
(car (cons x y)) IS x
(cdr (cons x y)) IS y
what might we build pairs from? whats below the pair abstraction?? abelson says pairs can be built from nothing at all, pure abstraction
(define (cons a b)
(lambda (pick)
(cond ((= pick 1) a)
((= pick 2) b))))
(define (car x) (x 1))
(define (cdr x) (x 2))
there are no data objects! only procedures! it's built out of air
we dont need data at all to build data abstractions
ONCE AGAIN we blur the line between data and procedure