SICPch2 Building Abstractions with Data
building abstractions by forming compound data
Intro
 2.1 data abstraction erect abstraction barriers
 2.2 data == procedures, sequences, closure, conventional interface
 2.3 symbols as elementary data
 2.4 generic operations, data directed programming, additivity
 2.5 implement a package
2.1 Introduction to Data Abstraction
Data abstraction
 isolating
 ( the parts of a program that deal with how data objects are represented )
 from
 ( the parts of a program that deal with how data objects are used )
Construct abstract data
 use constructors, selectors as interface
2.1.1 Example: Arithmetic Operations for Rational Numbers
 assume the constructor and selectors are available
1
 numer , denom , makerat

 use them to express rational operation
1 2 3 4  (define (addrat x y) (makerat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) 
 implement representation
1 2 3  (define (makerat n d) (cons n d)) (define (numer x) (car x)) (define (denom x) (cdr x)) 
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
DEF:
 some collection of selectors and constructors
 together with specified conditions for the representation
Example

Pairs z = ( x, y )

selector: car, cdr

constructor: cons

condition: if z = ( x, y ) => ( car z ) = x && ( cdr z ) = y
1 2 3 4 5 6 7 8 9  (define (cons x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y) (else (error "Argument not 0 or 1: CONS" m)))) ;message passing: data representation returns procedure dispatch) (define (car z) (z 0)) (define (cdr z) (z 1)) 
Exercise 2.6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  ;2.6 ;church numerals DEF ( define zero ( lambda ( f ) ( lambda ( x ) x ) ) ) ( define ( add1 n ) ( lambda ( f )( lambda ( x ) ( f ( ( n f ) x ) )))) ;从0开始，每多一个f就+1 ( define ( churchtoint ch ) ( ( ch ( lambda ( n ) ( + n 1 ) ) ) 0 ) ) ( define one ( lambda ( f ) ( lambda ( x ) ( f x ) ) ) ) ( define two ( lambda ( f ) ( lambda ( x ) ( f ( f x ) ) ) ) ) ;a,b: function of zero, one, two... ;b以x为参数经过b次apply f ;a以x经过b次apply后的结果为参数(( b f ) x )，在此基础上再apply f a次 ( define ( add a b ) ( lambda ( f ) ( lambda ( x ) ( ( a f ) ( ( b f ) x ) ) ) ) ) ;调用 ( define ( square x ) ( * x x )) ; f = square x = 2 ( ( two square ) 2 ) 
2.2 Hierarchical Data and the Closure Property
closure property of cons ( an operation )
 The ability to create pairs whose elements are pairs
 Closure is the key to create hierarchical structures
2.2.1 Representing Sequences
The entire sequence is constructed by nested cons operations
1 2 3 4  (cons 1 (cons 2 (cons 3 (cons 4 nil)))) 
Provides a primitive
1
 (list ⟨ a 1 ⟩ ⟨ a 2 ⟩ . . . ⟨ a n ⟩ )

Operations
1
 ref, length, append, lastpair, reverse

Mapping over list
 Establish an abstraction barrier that
 isolates
 the implementation of procedures that transform lists
 from
 the details of how the elements of the list are extracted and combined.
1 2 3 4 5  (define (map proc items) (if (null? items) nil (cons (proc (car items)) (map proc (cdr items))))) 
2.2.2 Hierarchical Structures
Tree
 sequences whose elements are sequences
 Recursion is a natural tool for dealing with tree structures
2.2.3 Sequences as Conventional Interfaces
Conventional Interface
 permits us to combine processing modules
Signal Processing
A signalprocessing engineer would find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages, each of which implements part of the program plan.
Organizing programs so as to reflect the signalflow structure
 concentrate on the “signals”
 represent these signals as lists
 use list operations to implement the processing
 helps us make program designs that are modular
 connecting the components in flexible ways
Nested Mappings
1 2  (define (flatmap proc seq) (accumulate append nil (map proc seq))) 
2.3 Symbolic Data
Issue arise
 words and sentences may be regarded either as semantic entities ( meaning ) or as syntactic entities ( characters )
Using quotation mark
1 2  (list 'a 'b) (a b) 
manipulating symbols
1
 eq?, memq

2.4 Multiple Representations for Abstract Data
cope with data that may be represented in different ways by different parts of a program
Data Abstraction
 separate the task of designing a program that uses rational numbers from the task of implementing rational numbers
 an application of the “principle of least commitment”
Abstraction Barrier
 formed by the selectors and constructors
 permits us to defer to the last possible moment the choice of a concrete representation
 thus retain maximum flexibility
2.4.1 Representations for Complex Numbers
constructors
1 2  (makefromrealimag (realpart z) (imagpart z)) (makefrommagang (magnitude z) (angle z)) 
selectors
rectangular representation & polar representation
1
 realpart,imagpart,magnitude,angle

implement arithmetic on complex numbers
1
 addcomplex, subcomplex, mulcomplex, divcomplex

implement 2 representations of complex number
1
 分别用直角和极坐标来实现4个selector和2个constructor

2.4.2 Tagged data
If both representations are included in a single system, we will need some way to distinguish data in polar form from data in rectangular form.
A straightforward way to accomplish this distinction is to include a type tag —the symbol rectangular or polar —as part of each complex number.
1 2  (define (makefromrealimagrectangular x y) (attachtag 'rectangular (cons x y))) 
Make sure names do not conflict: Append the suffix rectangular
1
 (define (realpartrectangular z) (car z))

Generic selector
 Dispatch: checks the tag and calls the appropriate procedure of that type.
 because the selectors are generic, operation ( add, mul ) are unchanged
1 2 3 4 5 6  (define (realpart z) (cond ((rectangular? z) (realpartrectangular (contents z))) ((polar? z) (realpartpolar (contents z))) (else (error "Unknown type: REALPART" z)))) 
Generic Constructor
1 2  (define (makefromrealimag x y) (makefromrealimagrectangular x y)) 
General mechanism for interfacing the separate representations
 stripping off and attaching tags as data objects are passed from level to level
2.4.3 DataDirected Programming and Additivity
Two weaknesses of dispatching above
 generic interface procedures must know about all the different representations
 must guarantee that no two procedures in the entire system have the same name
Additive
 design the individual packages separately and
 combine them to produce a generic system
Datadirected programming
 dealing with a twodimensional table
 the possible operations on one axis and the possible types on the other axisss
Manipulate table
1 2  (put ⟨ op ⟩ ⟨ type ⟩ ⟨ item ⟩ ) (get ⟨ op ⟩ ⟨ type ⟩ ) 
Defines a package
Interfaces these by adding entries to the table
1 2 3 4 5 6 7 8 9 10 11 12  (define (installrectangularpackage) ;; internal procedures (define (realpart z) (car z)) (define (makefromrealimag x y) (cons x y)) ;; interface to the rest of the system (define (tag x) (attachtag 'rectangular x)) (put 'realpart '(rectangular) realpart) (put 'makefromrealimag 'rectangular (lambda (x y) (tag (makefromrealimag x y)))) 'done) 
Generic Selectors
1 2 3 4 5 6 7 8 9  (define (applygeneric op . args) (let ((typetags (map typetag args))) (let ((proc (get op typetags))) (if proc ;apply arguments to procedure (apply proc (map contents args)) (error "No method for these types: APPLYGENERIC" (list op typetags)))))) 
1
 (define (realpart z) (applygeneric 'realpart z))

Generic Constructors
1 2  (define (makefromrealimag x y) ((get 'makefromrealimag 'rectangular) x y)) 
Interface ( generic selectors )
Previous  Datadirected 

a set of procedures  single procedure 
explicit dispatch  looks up 
name conflicts  internal 
change if a new representation is added  doesn’t change 
Centralized selectors  Decentralized 
Message passing
Data object receives the requested operation name as a “message.”
Instead of using “intelligent operations” that dispatch on data types
work with “intelligent data objects” that dispatch on operation names.
Represent data object as a procedure
 takes as input the required operation name
 performs the operation indicated
Constructor
1 2 3 4 5 6  (define (makefromrealimag x y) (define (dispatch op) (cond ((eq? op 'realpart) x) (else (error "Unknown op: MAKEFROMREALIMAG" op)))) ;return procedure dispatch) 
Selector
1
 (define (applygeneric op arg) (arg op))

2.5 Systems with Generic Operations
use datadirected techniques to construct a package of arithmetic operations
2.5.1 Generic Arithmetic Operations
generic arithmetic procedures
1
 (define (add x y) (applygeneric 'add x y))

install packages
1 2 3 4 5 6 7 8 9 10 11 12 13  (define (installcomplexpackage) ;; imported procedures from rectangular and polar packages (define (makefromrealimag x y) ((get 'makefromrealimag 'rectangular) x y)) ;; internal procedures (define (addcomplex z1 z2) (makefromrealimag (+ (realpart z1) (realpart z2)) (+ (imagpart z1) (imagpart z2)))) ;; interface to rest of the system (define (tag z) (attachtag 'complex z)) (put 'makefromrealimag 'complex (lambda (x y) (tag (makefromrealimag x y)))) 'done) 
constructor
1 2  (define (makecomplexfromrealimag x y) ((get 'makefromrealimag 'complex) x y)) 
twolevel tag system
2.5.3 Example: Symbolic Algebra
implement polynomial package
 arithmetic on polynomials
 representation of polynomials
 arithmetic on term list
 representation of term list
Data Directed Recursion
 using generic operation ( ADD ) inside each package
Hierarchy of types in symbolic data
 recursive data abstraction
 neither of these types is above the other naturally
 difficult to control coercion
2.5.2 Combining Data of Different Types
Define crosstype operations
One way: design a different procedure for each possible combination of types
1 2 3 4 5  ;; to be included in the complex package (define (addcomplextoschemenum z x) (makefromrealimag (+ (realpart z) x) (imagpart z))) (put 'add '(complex schemenumber) (lambda (z x) (tag (addcomplextoschemenum z x)))) 
Cumbersome
 more code is needed
 individual packages need to take account of other packages ( not additive )
Coercion
 objects of one type may be viewed as being of another type
coercion procedure
1 2  (define (schemenumber>complex n) (makecomplexfromrealimag (contents n) 0)) 
install in coercion table
1 2 3  (putcoercion 'schemenumber 'complex schemenumber>complex) 
applygeneric
 check the coercion table to see
 if objects of the first type can be coerced to the second type or
 if there is a way to coerce the second argument to the type of the first argument
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  (define (applygeneric op . args) (let ((typetags (map typetag args))) (let ((proc (get op typetags))) (if proc (apply proc (map contents args)) (if (= (length args) 2) (let ((type1 (car typetags)) (type2 (cadr typetags)) (a1 (car args)) (a2 (cadr args))) (let ((t1>t2 (getcoercion type1 type2)) (t2>t1 (getcoercion type2 type1))) (cond (t1>t2 (applygeneric op (t1>t2 a1) a2)) (t2>t1 (applygeneric op a1 (t2>t1 a2))) (else (error "No method for these types" (list op typetags)))))) (error "No method for these types" (list op typetags))))))) 
Advantage
 need to write only one procedure for each pair of types rather than a different procedure for each collection of types and each generic operation.
Not General Enough
 can’t converting both objects to a third type.
Hierarchies of types
applygeneric
 raise the object to its super type
 until we either find a level at which the desired operation can be performed
 or hit the top
Inadequates
 multiplesupertypes
 means that there is no unique way to “raise” a type in the hierarchy