SICP-ch2 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 , make-rat
|
- use them to express rational operation
1 2 3 4 | (define (add-rat x y) (make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) |
- implement representation
1 2 3 | (define (make-rat 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 ( add-1 n ) ( lambda ( f )( lambda ( x ) ( f ( ( n f ) x ) )))) ;从0开始,每多一个f就+1 ( define ( church-to-int 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, last-pair, 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 signal-processing 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 signal-flow 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 | (make-from-real-imag (real-part z) (imag-part z)) (make-from-mag-ang (magnitude z) (angle z)) |
selectors
rectangular representation & polar representation
1
| real-part,imag-part,magnitude,angle
|
implement arithmetic on complex numbers
1
| add-complex, sub-complex, mul-complex, div-complex
|
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 (make-from-real-imag-rectangular x y) (attach-tag 'rectangular (cons x y))) |
Make sure names do not conflict: Append the suffix -rectangular
1
| (define (real-part-rectangular 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 (real-part z) (cond ((rectangular? z) (real-part-rectangular (contents z))) ((polar? z) (real-part-polar (contents z))) (else (error "Unknown type: REAL-PART" z)))) |
Generic Constructor
1 2 | (define (make-from-real-imag x y) (make-from-real-imag-rectangular 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 Data-Directed 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
Data-directed programming
- dealing with a two-dimensional 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 (install-rectangular-package) ;; internal procedures (define (real-part z) (car z)) (define (make-from-real-imag x y) (cons x y)) ;; interface to the rest of the system (define (tag x) (attach-tag 'rectangular x)) (put 'real-part '(rectangular) real-part) (put 'make-from-real-imag 'rectangular (lambda (x y) (tag (make-from-real-imag x y)))) 'done) |
Generic Selectors
1 2 3 4 5 6 7 8 9 | (define (apply-generic op . args) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc ;apply arguments to procedure (apply proc (map contents args)) (error "No method for these types: APPLY-GENERIC" (list op type-tags)))))) |
1
| (define (real-part z) (apply-generic 'real-part z))
|
Generic Constructors
1 2 | (define (make-from-real-imag x y) ((get 'make-from-real-imag 'rectangular) x y)) |
Interface ( generic selectors )
Previous | Data-directed |
---|---|
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 (make-from-real-imag x y) (define (dispatch op) (cond ((eq? op 'real-part) x) (else (error "Unknown op: MAKE-FROM-REAL-IMAG" op)))) ;return procedure dispatch) |
Selector
1
| (define (apply-generic op arg) (arg op))
|
2.5 Systems with Generic Operations
use data-directed techniques to construct a package of arithmetic operations
2.5.1 Generic Arithmetic Operations
generic arithmetic procedures
1
| (define (add x y) (apply-generic 'add x y))
|
install packages
1 2 3 4 5 6 7 8 9 10 11 12 13 | (define (install-complex-package) ;; imported procedures from rectangular and polar packages (define (make-from-real-imag x y) ((get 'make-from-real-imag 'rectangular) x y)) ;; internal procedures (define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) ;; interface to rest of the system (define (tag z) (attach-tag 'complex z)) (put 'make-from-real-imag 'complex (lambda (x y) (tag (make-from-real-imag x y)))) 'done) |
constructor
1 2 | (define (make-complex-from-real-imag x y) ((get 'make-from-real-imag 'complex) x y)) |
two-level 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 cross-type 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 (add-complex-to-schemenum z x) (make-from-real-imag (+ (real-part z) x) (imag-part z))) (put 'add '(complex scheme-number) (lambda (z x) (tag (add-complex-to-schemenum 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 (scheme-number->complex n) (make-complex-from-real-imag (contents n) 0)) |
install in coercion table
1 2 3 | (put-coercion 'scheme-number 'complex scheme-number->complex) |
apply-generic
- 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 (apply-generic op . args) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (apply proc (map contents args)) (if (= (length args) 2) (let ((type1 (car type-tags)) (type2 (cadr type-tags)) (a1 (car args)) (a2 (cadr args))) (let ((t1->t2 (get-coercion type1 type2)) (t2->t1 (get-coercion type2 type1))) (cond (t1->t2 (apply-generic op (t1->t2 a1) a2)) (t2->t1 (apply-generic op a1 (t2->t1 a2))) (else (error "No method for these types" (list op type-tags)))))) (error "No method for these types" (list op type-tags))))))) |
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
apply-generic
- 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
- multiple-supertypes
- means that there is no unique way to “raise” a type in the hierarchy