[SICP-ch2] Building Abstractions with Data

Posted on | In |

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

  1. assume the constructor and selectors are available
1

numer , denom , make-rat
  1. 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))))
  1. 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:

  1. some collection of selectors and constructors
  2. 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

  1. arithmetic on polynomials
  2. representation of polynomials
  3. arithmetic on term list
  4. 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