* Lecture 2B Compound Data
https://youtu.be/DrFkf-T-6Co

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

#+BEGIN_SRC scheme
  (define (+rat x y)
    (make-rat
     (+ (* (numer x)(denom y))
	(* (numer y)(denom x)))
     (* (denom x) (denom y))))
#+END_SRC

no problem at all, if we have these 'clouds'

we can also implement the product of 2 rats
#+BEGIN_SRC scheme
  (define (*rat x y)
    (make-rat
     (* (numer x) (numer y))
     (* (denom x) (denom y))))
#+END_SRC

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'

#+BEGIN_SRC scheme
  (define (make-rat n d)
    (cons n d))
  (define (numer x) (car x))
  (define (denom x) (cdr x))
#+END_SRC

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

#+BEGIN_SRC scheme
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g)
	    (/ d g))))
#+END_SRC

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

#+BEGIN_SRC scheme
  (define (make-vector x y) (cons x y))	;; constructor
  (define (xcor p) (car p))		;; selector
  (define (ycor p) (cdr p))		;; selector
#+END_SRC

given points in a plane, we might want to use them to build
something. we might want to talk about line segments connecting
points.

#+BEGIN_SRC scheme
  (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)))))
#+END_SRC

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

#+BEGIN_SRC scheme
  (define (cons a b)
    (lambda (pick)
      (cond ((= pick 1) a)
	    ((= pick 2) b))))
  (define (car x) (x 1))
  (define (cdr x) (x 2))
#+END_SRC

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