## 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. use them to express rational operation
1. implement representation

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

Exercise 2.6

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

Provides a primitive

Operations

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.

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

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

manipulating symbols

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

selectors

rectangular representation & polar representation

implement arithmetic on complex numbers

implement 2 representations of complex number

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.

Make sure names do not conflict: Append the suffix -rectangular

Generic selector

• Dispatch: checks the tag and calls the appropriate procedure of that type.
• because the selectors are generic, operation ( add, mul ) are unchanged

Generic Constructor

General mechanism for interfacing the separate representations

• stripping off and attaching tags as data objects are passed from level to level

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

• 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

Defines a package

Interfaces these by adding entries to the table

Generic Selectors

Generic Constructors

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

Selector

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

install packages

constructor

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

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

install in coercion table

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

• 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