[SICP-ch2] Building Abstractions with Data

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

(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

(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

;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

(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.

(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

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

(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

(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

(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

(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

(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

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

(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