(jordyn sicp)

ch 1 recap:

used primitive data (numbers) and primitive operations (arithmetic)
combined procedures to form compound procedures through
- composition
- conditionals
- use of parameters
saw that proocedures can be regarded as a pattern for local
evolution of a process
classified, reasoned about, performed simple algorithmic analyses
of common patterns for processes embodied in procedures
saw thath higher-order procedures empower us by allawing us to
manipulate and reason about general methods of computation

this is much of the essence of programming

now, we will approach complex data.

programs typically model complex phenomena, and often, "we construct
computational objocts that have seweral parts in ordor to model
real-world phenomena that have several aspects"

in ch 1 we made compound procedures. in ch2 we will use compound data

neat!

coming up:

compound data object: data "glued together"
data abstraction: isolating the parts of a program that deal
with how data is represented from the parts that deal with how
data is used
abstraction barriers: shielding a process from the more
primitive details it deals with

!! the distinction between data and procedure continues to blur at a
breakneck pace

closure: the glue for combining data works with primitive as
well as compound data
conventional interfaces: combining program modules in a
mix-n-match fashion with compound data
symbolic expressions: data whose elements can be arbitrary
symbols
generic operations: operations that can handle many kinds of
data
data-directed programming: a technique that allows individual
data representations to be combined in isolation and combined
additively
additively: combining data representations without modification

2.1 Introduction to Data Abstraction

data abstraction: isolating how a compound data object is used
from the details of how it's constructed
selectors and constructors: the interface between a concrete
data object and its abstract operations

2.1.1 Example: Arithmetic Operations for Rational Numbers

suppose…we want to do arithmetic with rational numbers

we want to add, subtract, multiply, divide, and test for equality

let's assume the selectors and constructors are available as
procedures:

(make-rat ⟨n⟩ ⟨d⟩): returns rational number with numerator n and
denominator d
(numer ⟨x⟩): returns numerator of rational number x
(denom ⟨x⟩): returns denominator of rational number x

we can happily use wishful thinking here. these procedures do not
exist, but we can pretend they do and build a suite of funtionality:

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))
(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))
(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

we have operations based on the selector and constructor procedures

numer
denom
make-rat

but these don't exist yet. we need a way to glue together two numbers
to make a rational number

pairs

pair: a compound structure provided by lisp

pairs can be constructed with the primitive procedure cons
given a pair, we can extract the elements with car and cdr

(define x (cons 1 2))
(car x)

(cdr x)

–> a note on terminology

cons is short for "construct"

the other two harken back to the IBM 704 implementation of lisp. the
machcine had an addressing scheme that had references to the "address"
and "decrement" parts of a memory location.

car is short for "Contents of Address part of Register"
cdr is short for "Contents of Decrement part of Register"

cdr is pronounced "could-er"

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z)) ; 1
(car (cdr z)) ; 3

!! the single compound primitive pair, implemented by the procedures
cons, car, cdr, is the only glue we need

list-structured data: data objects built by pairs

TODO representing rational numbers

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

including a tostr method, we can use our new procedures for great fun

(define one-half (make-rat 1 2))
(print-rat one-half)

(define one-third (make-rat 1 3))
(print-rat (add-rat one-half one-third))

this does not reduce the terms. we can do this if we have a gcd like
back in 1.2.5

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

2.1.2 Abstraction Barriers

there are abstraction barriers here

-–—|programs that use rational nums|--–—

rational numbers in problem domain

-------–—|add-rat sub-rat … |-------–—

rational numbers as numers and denoms

-------–—|make-rat numer denom|-------–—

rational numbers as pairs

-----------–—|cons car cdr|-----------–—

however pairs are implemented

these abstraction barriers isolate the various levels of the system.
at each level, the barrier separates the programs above from the
programs below that implement the abstractions.
the procedures at each level are the interfaces that define the
abstraction barriers and connect the different levels.

changing from one representation to another should have minimal
(none??!!) effects on the levels above.

2.1.3 What is Meant by Data?

what is data, man?

considering make-rat, for any int n and any nonzero int d, if x is
(make-rat n d), this is true:

 (numer x)       n
-----------  =  ---
 (denom x)       d

data is defined by some collection of selectors and constructors with
specified conditions that the procedures must fulfil in order to be
valid.

this pount of view can define high level data objects such as rats but
also low level objects like pairs.

the condition pair operations satisfy:

if z is (cons x y)
(car z) is x
(cdr z) is y

we could implement pairs with no data structures, only procedures

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "argument not 0 or 1 -- CONS" m))))
  dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

this is an obscure but valid way to implement pairs.

"procedural representations of data will play a central role in our
programming repertoire."

message passing: this style of programming

will visit this in ch 3 re the issues of modeling and simulation

2.1.4 Extended Exercise: Interval Arithmetic

Alyssa P. Hacker is building some cool shit

the system will give ability to manipulate inexact quantites with
known precision, such as with resistors.

calculate parallel resistance:

           1
Rp = -------------
      1/R1 + 1/R2

alyssa postulates the existance of an abstract obj known as an
"interval" with an upper and lower bound

she presumes that given the endpoints of an interval, she can
construct an interval with make-interval

she writes a procedure for adding two intervals:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

she also has a procedure for the product:

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

and the reciprocal, for division

(define (div-interval x y)
  (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))