## 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