notes.org 8.6 KB
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)
1
(cdr x)
2
–> 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)))))