SICP

This section covers my notes and exercises of the book Structure and Interpretation of Computer Programs.

How I'm reading the book

While reading I'm taking notes of what I think is interesting. I'm using the programming language Racket with DrRacket instead of Scheme, which is used in the book. On the first line of DrRacket I enter #lang sicp which should help with compatibility.

My reading is from start to finish and doing the exercises on my own unless I get stuck. I'm not using knowledge outside the book to solve the exercises. So my solutions use the knowledge presented in the book until that point.

1. Building Abstractions with Procedures

1.1 The Elements of Programming

A programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Every language has three mechanisms for combining simple ideas to form more complex ideas:

1.1.1 Expressions

This is an expression:

(+ 137 349)

Expressions delimited by parentheses are called combinations. The left most element in the list is called the operator and the other elements are called operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

This convention of placing the operator to the left of the operands is known as prefix notation. One advantage is that it can receive an arbitrary number of arguments. A second advantage is that is straight-forward way to allow combinations to be nested:

(+ (* 3 5) (- 10 6))
; => 19

1.1.2 Naming and the Environment

The ability to associate symbols and later retrieve them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment.

1.1.3 Evaluating Combinations

To evaluate a combination, do the following:

  1. Evaluate the subexpressions of the combination.
  2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

The evaluate primitives (such as 8, + or x) we follow this:

The key point to notice is the role of the environment in determining the meaning of the the symbols in expressions. It's meaningless to speak of the value of an expression such as (+ x 1) without specifying any information about the environment that would provide a meaning for the symbol x (or event for the symbol +).

The evaluation rule above does not handle special forms. Each special form has its own evaluating rule.

1.1.5 The Substitution Model for Procedure Application

The model were we fully expand an expression ir order to evaluate it is called normal-order evaluation:

(sum-of-squares (+ 5 1) (* 5 2))
;(+ (square (+ 5 1)) (square (* 5 2)))
;(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
;(+ (* 6 6) (* 10 10))
;(+ 36 100)
;136

The other model is known as applicative-order evaluation, which is what the interpreter actually uses it:

(sum-of-squares (+ 5 1) (* 5 2))
;(+ (square 6) (square 10))
;(+ (* 6 6) (* 10 10))
;(+ 36 100)
;136

1.1.6 Conditional Expressions and Predicates

predicate is an expression whose value is interpreted as either true or false.

1.1.7 Example: Square Roots by Newton's Method

(define (square x) (* x x))

(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))

(define (improve guess x)
(average guess (/ x guess)))

(define (average x y)
(/ (+ x y) 2))

(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
(sqrt-iter 1.0 x))

(sqrt 9)
; => 3.00009155413138

1.1.8 Procedures as Black-Box Abstractions

Goes on about lexical scoping.

1.2 Procedures and the Processes They Generate

1.2.1 Linear Recursion and Iteration

Linear recursive process:

(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))

Linear iterative process:

(define (factorial n)
(fact-iter 1 1 n))

(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product) (+ counter 1) max-count)))

Consider the first solution. The substitution model reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations. The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with n. Such a process is called a linear recursive process.

By contrast, the second solution does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. In computing n!, the number of steps required grows linearly with n. Such a process is called a linear iterative process.

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we're referring to the syntactic fact that procedure definitions refers to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written.

1.2.2 Tree Recursion

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

(define (fib n)
(fib-iter 1 0 n))

(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(define (count-change amount) (cc amount 5))

(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

1.2.4 Exponentiation

Consider the problem of computing the exponential of a given number. The procedure takes a base b and a positive integer exponent n and computes bn. One way to achieve that is using the recursive definition:

which translate easily to:

(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))

It's a recursive process has O(n) time and O(n) space. The iterative equivalent:

(define (expt b n)
(expt-iter b n 1))

(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))

This version has O(n) time and O(1) space.

One possible optimization is instead of computing b8 as:

b.(b.(b.(b.(b.(b.(b.b))))))

it can be done in three multiplications:

This works for exponents that are powers of 2. Another optimization is:

This can be expressed as:

(define (fast-expt b n)
(cond ((= n 0) 1)
((event? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))

(define (event? n)
(= (remainder n 2) 0))

This has the advantage of being O(log n) in both time and space. This becomes apparent when we observe that computing b2n requires only one more multiplication than computing bn. Therefore, the exponent we can compute doubles with every new multiplication we're allowed.

1.2.5 Greatest Common Divisors

The greatest common divisor (GCD) of two integers is defined to be the largest integer that divides both with no remainder.

Euclid's Algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r. Thus, we can use the equation

GCD(a,b) = GCD(b,r)

to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,

GCD(206,40) = GCD(40,6) = GCD(6,4) = GCD(4,2) = GCD(2,0) = 2

reduces GCD(206,40) to GCD(2,0). It's possible to show that starting with any two positive integers and performing repeated reductions will always eventually produce a pair where the second number is 0. Then the GCD is the other number in the pair.

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

1.3 Formulating Abstractions with Higher-Order Procedures

One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Procedures provide this ability.

Often the same programming pattern will be used with a number of different procedures. To express such patterns as concept, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures as called higher-order procedures.

1.3.1 Procedures as Arguments

Consider the following three procedures:

(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))

(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a)
(sum-cubes (+ a 1) b))))

(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2)))
(pi-sum (+ a 4) b))))

These procedures share a common underlying pattern. In order to find this pattern we can make them as similar as possible, which is already the case. Then the template looks like:

(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))

1.3.2 Constructing Procedures Using lambda

Is the way Scheme uses to define an anonymous procedure:

(lambda (x) (+ x 4))

There is let for creating local variables:

(let ((<var1> <exp1>)
(<var2> <exp2>)
...
(<varn> <expn>))
<body>)

1.3.4 Procedures as Returned Values

The previous examples demonstrate how the ability to pass procedures as arguments significantly enhances the expressive power of our programming language. Even more expressive power can be achieved by creating procedures whose returned values are themselves procedures.

The idea of average damping can be expressed as a procedure:

(define (average-damp f)
(lambda (x) (average x (f x))))

average-damp is a procedure that takes as its argument a procedure f and returns as its value a procedure that when applied to a number x produces the average of x and (f x). For example, applying it to the square procedure produces a procedure whose value at some number x is the average of x and x2. Applying this resulting procedure to 10 returns the average of 10 and 100: 55.

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the "rights and privileges" of first-class elements are:

Lips, unlike other common programming languages, awards procedures full first-class status. This poses challenges for efficient implementation, but the result gain in expressive power is enormous.

2. Building Abstractions with Data

The general technique of 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 is a powerful design methodology called data abstraction. These data abstraction makes programs much easier to design, maintain, and modify.

The use of compound data leads to real increase in the expressive power of our programming language. Consider the idea of forming a "linear combination" ax + by. This can be defined as:

(define (linear-combination a b x y)
(+ (* a x) (* b y)))

But suppose we are not concerned only with numbers. Suppose we would like to express, in procedural terms, the idea that one can form linear combinations whenever addition and multiplications are defined - for rational numbers, complex numbers, polynomials, or whatever. We could express this as a procedure of the form:

(define (linear-combination a b x y)
(add (mul a x) (mul b y)))

where add and mul are not the primitive procedures + and * but rather more complex procedures that will perform the appropriate operations for whatever kinds of data we pass in as the arguments a, b, x, and y. From the perspective of linear-combination it is irrelevant what a, b, x, and y are and even more irrelevant how they might happen to be represented in terms of more primitive data.

2.1 Introduction to Data Abstraction

The basic idea of data abstraction is to structure the programs that are to use compound data objects so that they operate on "abstract data." That is, our programs should use data in such a way as to make no assumptions about the data that are not strictly necessary for performing the task at hand. At the same time, a "concrete" data representation is defined independent of the programs that use the data. The interface between these two parts of our system will be a set of procedures, called selectors and constructors, that implement the abstract data in terms of the concrete representation.

2.1.1 Example: Arithmetic Operations for Rational Numbers

Suppose we want to do arithmetic with rational numbers. We want to be able to add, subtract, multiply, and divide them and to test whether two rational numbers are equal.

Let us begin by assuming that we already have a way of constructing a rational number from a numerator and a denominator. Also assume that, given a rational number, we have a way of extracting (or selecting) its numerator and its denominator. These are defined as procedures:

This is a powerful strategy of synthesis: wishful thinking. We haven't yet said how a rational number is represented, or how these procedures are implemented. Even so, if we have these three procedures, we could then add, subtract, multiply, divide, and test equality by using the following relations:

n1/d1 + n2/d2 = (n1d2 + n2d1)/d1d2

n1/d1 - n2/d2 = (n1d2 - n2d1)/d1d2

n1/d1 . n2/d2 = n1n2 / d1d2

(n1/d1)/(n2/d2) = n1d2/d1n2

n1/d1 = n2/d2 if and only if n1d2 = n2d1

These rules can be expressed as procedures:

(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))

(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))

(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))
Pairs

To enable us to implement the concrete level of our data abstraction, our language provides a compound structure called a pair, which can be constructed with the primitive procedure cons.

(define x (cons 1 2))
(car x)
;=> 1
(cdr x)
;=> 2

Then the rational numbers can be expressed as:

(define make-rat cons)
(define numer car)
(define denom cdr)

in order to display the result we can print the numerator, a slash, and the denominator:

(define (print-rat x)
(newline)
(display (numer x))
(display "/")
(display (denom x)))

This rational number implementation does not reduce rational numbers to lowest terms. This can be fixed by changing make-rat. The gcd procedure can be used to reduce the numerator and the denominator to lowest terms before constructing the pair:

(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))

With these procedures in place we can do some operations:

(print-rat (add-rat (make-rat 2 4) (make-rat 3 8))) ;; 2/4 + 3/8 = 7/8
(print-rat (sub-rat (make-rat 1 1) (make-rat 1 2))) ;; 1/1 - 1/2 = 1/2
(print-rat (mul-rat (make-rat 3 2) (make-rat 5 2))) ;; 3/2 * 5/2 = 15/4
(print-rat (div-rat (make-rat 3 7) (make-rat 4 9))) ;; 3/7 / 4 9 = 27/28
(equal-rat? (make-rat 2 2) (make-rat 1 1)) ;; #t
(equal-rat? (make-rat 2 3) (make-rat 1 1)) ;; #f

Organizing what we have so far:

;; Math Primitives
(define (square x) (* x x))

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

;; Rational numbers: Constructor and selectors
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define numer car)
(define denom cdr)


;; Rational numbers: Operations
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))

(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))

(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))

;; Rational numbers: Printing
(define (print-rat x)
(newline)
(display (numer x))
(display "/")
(display (denom x)))

;; Rational numbers: Usage
(print-rat (add-rat (make-rat 2 4) (make-rat 3 8))) ;; 2/4 + 3/8 = 7/8
(print-rat (sub-rat (make-rat 1 1) (make-rat 1 2))) ;; 1/1 - 1/2 = 1/2
(print-rat (mul-rat (make-rat 3 2) (make-rat 5 2))) ;; 3/2 * 5/2 = 15/4
(print-rat (div-rat (make-rat 3 7) (make-rat 4 9))) ;; 3/7 / 4 9 = 27/28
(equal-rat? (make-rat 2 2) (make-rat 1 1)) ;; #t
(equal-rat? (make-rat 2 3) (make-rat 1 1)) ;; #f

2.2 Hierarchical Data and the Closure Property

Pairs provide a universal building block from which we can construct all sorts of data structures. To combine 1, 2, 3, and 4:

(cons (cons 1 2)
(cons 3 4))

The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the clojure property of cons. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation.

2.2.1 Representing Sequences

One of the useful structures we can build with pairs is a sequence - an ordered collection of data objects.

(cons 1
(cons 2
(cons 3
(cons 4 nil))))

Such sequence of pairs is called a list, and Scheme provides a primitive called list to help in constructing lists.

(define one-through-four (list 1 2 3 4))
; => (1 2 3 4)

(car one-through-four)
; => 1

(cdr one-through-four)
; => (2 3 4)

(cons 10 one-through-four)
; => (10 1 2 3 4)

2.2.2 Hierarchical Structures

The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. These structures are trees.

Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree.

As an example see how we can count the number of leaves:

(define tree (cons (list 1 2) (list 3 4)))

(define (count-leaves x)
(cond ((null? x) 0)
((not (pair? x)) 1)
(else (+ (count-leaves (car x))
(count-leaves (cdr x))))))

(count-leaves tree)
; => 4

2.3.3 Sequences as Conventional Interfaces

The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the "signals" that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages.

(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))

(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))

(define (flatmap proc seq)
(accumulate append nil (map proc seq)))

(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
sequence))

2.3 Symbolic Data

2.3.1 Quotation

Suppose we want to construct the list (a b). We can't accomplish this with (list a b) because this expression constructs a list of the values of a and b rather than the symbols themselves. The single quote symbol (') helps with that:

(define a 1)
(define b 2)
(list a b)
; => (1 2)
(list 'a 'b)
; => (a b)
(list 'a b)
; => (a 2)

2.4 Multiple Representations for Abstract Data

Earlier it was introduced data abstraction, a methodology for structuring systems in such a way that much of a program can be specified independent of the choices involved in implementing the data objects that the program manipulates. For example, the rational number, where it was separated the task of designing a program that uses rational numbers from the task of implementing rational numbers in terms of the computer language's primitive mechanism for constructing compound data. The data-abstraction barriers are powerful tools for controlling complexity.

This kind of data abstraction is not yet powerful enough, because it may not always make sense to speak of "underlying representation" for a data object. There might be more than one useful representation for a data object, and we might like to design systems that can deal with multiple representations. An example is complex numbers, which may be represented in rectangular form and in polar form. Depending of the situation one is more appropriate than the other. It is perfectly plausible to imagine a system in which complex numbers are represented in both ways, and in which the procedures for manipulating complex numbers work with either representation.

To solve this we must construct generic procedures — procedures that can operate on data that may be represented in more than one way.

2.4.1 Representations for Complex Numbers

First, we assume that the operations on complex numbers are implemented in terms of four selectors: real-part, imag-part, magnitude, and angle. Also assume we have two procedures for constructing complex numbers: make-from-real-imag and make-from-mag-ang. The code below shows how to use these procedures, both result in complex numbers that are equal to z.

(make-from-real-imag (real-part z) (imag-part z))
(make-from-mag-ang (magnitude z) (angle z))

Using these constructors and selectors, we can implement arithmetic on complex numbers using the "abstract data" specified by the constructors and selectors, just as we did for rational numbers.

(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))

(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))

If we choose to represent numbers in complex form:

(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
(sqrt (+ (square (real-part z))
(square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))

Using polar form:

(define (real-part z) (* (magnitude z) (cos (angle z))))
(define (imag-part z) (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))
(define (make-from-mag-ang r a) (cons r a))

2.4.2 Tagged data

It's possible to use both representation at the same time, for that we need a way to distinguish if the data is represented in rectangular or polar 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. In order to manipulate tagged data, we will assume that we have procedures type-tag and contents that extract from a data object the tag and the actual content (the polar or rectangular coordinates, in the case of complex number). We will also postulate a procedure attach-tag that takes a tag and contents and produces a tagged data object.

(define (attach-tag type-tag contents)
(cons type-tag contents))

(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum: TYPE-TAG" datum)))

(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum: CONTENTS" datum)))

(define (rectangular? z)
(eq? (type-tag z) 'rectangular))

(define (polar? z) (eq? (type-tag z) 'polar))

With these we can redefine the previous procedures:

; Rectangular
(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
(sqrt (+ (square (real-part-rectangular z))
(square (imag-part-rectangular z)))))
(define (angle-rectangular z)
(atan (imag-part-rectangular z) (real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
(attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
(attach-tag 'rectangular
(cons (* r (cos a)) (* r (sin a)))))

; Polar
(define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z))))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (make-from-real-imag-polar x y)
(attach-tag 'polar
(cons (sqrt (+ (square x) (square y)))
(atan y x))))
(define (make-from-mag-ang-polar r a)
(attach-tag 'polar (cons r a)))

Each generic selector is implemented as procedure that checks the tag of its argument and calls the appropriate procedure for handling data of that type.

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

(define (imag-part z)
(cond ((rectangular? z)
(imag-part-rectangular (contents z)))
((polar? z)
(imag-part-polar (contents z)))
(else (error "Unknown type: IMAG-PART" z))))

(define (magnitude z)
(cond ((rectangular? z)
(magnitude-rectangular (contents z)))
((polar? z)
(magnitude-polar (contents z)))
(else (error "Unknown type: MAGNITUDE" z))))

(define (angle z)
(cond ((rectangular? z)
(angle-rectangular (contents z)))
((polar? z)
(angle-polar (contents z)))
(else (error "Unknown type: ANGLE" z))))

The last part is to choose whether to construct complex numbers using rectangular or polar form. A reasonable choice is to construct rectangular numbers whenever we have a real and imaginary parts and to construct polar numbers whenever we have magnitudes and angles:

(define (make-from-real-imag x y)
(make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
(make-from-mag-ang-polar r a))

We can see this is action:

(real-part (make-from-real-imag 2 3)) ;; 2
(imag-part (make-from-real-imag 2 3)) ;; 3
(magnitude (make-from-real-imag 2 3)) ;; 3.605551275463989
(angle (make-from-real-imag 2 3)) ;; 0.982793723247329
(real-part (make-from-mag-ang 3.605551275463989 0.982793723247329)) ;; 2.0
(imag-part (make-from-mag-ang 3.605551275463989 0.982793723247329)) ;; 3.0

Recap of what we have so far:

;; Math Primitives
(define (square x) (* x x))

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

;; Rational numbers: Constructor and selectors
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define numer car)
(define denom cdr)


;; Rational numbers: Operations
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))

(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))

(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))

(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))

;; Rational numbers: Printing
(define (print-rat x)
(newline)
(display (numer x))
(display "/")
(display (denom x)))

;; Rational numbers: Usage
(print-rat (add-rat (make-rat 2 4) (make-rat 3 8))) ;; 2/4 + 3/8 = 7/8
(print-rat (sub-rat (make-rat 1 1) (make-rat 1 2))) ;; 1/1 - 1/2 = 1/2
(print-rat (mul-rat (make-rat 3 2) (make-rat 5 2))) ;; 3/2 * 5/2 = 15/4
(print-rat (div-rat (make-rat 3 7) (make-rat 4 9))) ;; 3/7 / 4 9 = 27/28
(equal-rat? (make-rat 2 2) (make-rat 1 1)) ;; #t
(equal-rat? (make-rat 2 3) (make-rat 1 1)) ;; #f

;; Tagging System
(define (attach-tag type-tag contents)
(cons type-tag contents))

(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum: TYPE-TAG" datum)))

(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum: CONTENTS" datum)))

;; Tag predicates
(define (rectangular? z)
(eq? (type-tag z) 'rectangular))

(define (polar? z) (eq? (type-tag z) 'polar))

;; Complex Numbers: Operations - Rectangular
(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
(sqrt (+ (square (real-part-rectangular z))
(square (imag-part-rectangular z)))))
(define (angle-rectangular z)
(atan (imag-part-rectangular z) (real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
(attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
(attach-tag 'rectangular
(cons (* r (cos a)) (* r (sin a)))))

;; Complex Numbers: Operations - Polar
(define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z))))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (make-from-real-imag-polar x y)
(attach-tag 'polar
(cons (sqrt (+ (square x) (square y)))
(atan y x))))
(define (make-from-mag-ang-polar r a)
(attach-tag 'polar (cons r a)))

;; Complex Numbers: Selectors
(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))))

(define (imag-part z)
(cond ((rectangular? z)
(imag-part-rectangular (contents z)))
((polar? z)
(imag-part-polar (contents z)))
(else (error "Unknown type: IMAG-PART" z))))

(define (magnitude z)
(cond ((rectangular? z)
(magnitude-rectangular (contents z)))
((polar? z)
(magnitude-polar (contents z)))
(else (error "Unknown type: MAGNITUDE" z))))

(define (angle z)
(cond ((rectangular? z)
(angle-rectangular (contents z)))
((polar? z)
(angle-polar (contents z)))
(else (error "Unknown type: ANGLE" z))))

;; Complex Numbers: Constructors
(define (make-from-real-imag x y)
(make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
(make-from-mag-ang-polar r a))

;; Complex Numbers: Usage
(real-part (make-from-real-imag 2 3)) ;; 2
(imag-part (make-from-real-imag 2 3)) ;; 3
(magnitude (make-from-real-imag 2 3)) ;; 3.605551275463989
(angle (make-from-real-imag 2 3)) ;; 0.982793723247329
(real-part (make-from-mag-ang 3.605551275463989 0.982793723247329)) ;; 2.0
(imag-part (make-from-mag-ang 3.605551275463989 0.982793723247329)) ;; 3.0

2.4.3 Data-Directed Programming and Additivity

The general strategy of checking the type of a datum and calling an appropriate procedure is called dispatching on type. This is a powerful strategy for obtaining modularity in system design. On the other hand, implementing the dispatch as it was done has two significant weaknesses. One weakness is that the generic interface procedures (real-part, imag-part, magnitude, and angle) must know about all the different representations. In case we want to incorporate a new representation for complex numbers into our complex-number system. We would need to identify this new representation with a type, and then add a clause to each of the generic interface procedures to check for the new type and apply the appropriate selector for that representation.

Another weakness of the technique is that even though the individual representation can be designed separately, we must guarantee that no two procedures in the entire system have the same name. The underline issue is that implementing generic interfaces is not additive.

What we need is a means for modularizing the system design even further. This is provided by the programming technique known as data-directed programming. To understand how data-directed programming works, begin with the observation that whenever we deal with a set of generic operations that are common to a set of different types we are, in effect, dealing with a two-dimensional table that contains the possible operations on one axis and the possible types on the other axis.

ProcedurePolarRectangular
real-partreal-part-polarreal-part-rectangular
imag-partimag-part-polarimag-part-rectangular
magnitudemagnitude-polarmagnitude-rectangular
angleangle-polarangle-rectangular

Data-directed programming is the technique of designing programs to work with such a table directly. The interface will be a single procedure that looks up the combination of the operation name and argument type in the table to find the correct procedure to apply, and then applies it to the contents of the argument.

To implement this plan, assume that we have two procedures, put and get, for manipulating the operation-and-type table:

A developer can define a collection of procedures, or a package, and interface these to the rest of the system by adding entries to the table that tell the system how to operate on rectangular number.

(define (install-rectangular-package)
;; internal procedures
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (make-from-real-imag x y) (cons x y))
(define (magnitude z)
(sqrt (+ (square (real-part z))
(square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))

;; interface to the rest of the system
(define (tag x) (attach-tag 'rectangular x))
(put 'real-part '(rectangular) real-part)
(put 'imag-part '(rectangular) imag-part)
(put 'magnitude '(rectangular) magnitude)
(put 'angle '(rectangular) angle)
(put 'make-from-real-imag 'rectangular
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'rectangular
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)

The polar system is analogous:

(define (install-polar-package)
;; internal procedures
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-mag-ang r a) (cons r a))
(define (real-part z) (* (magnitude z) (cos (angle z))))
(define (imag-part z) (* (magnitude z) (sin (angle z))))
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))

;; interface to the rest of the system
(define (tag x) (attach-tag 'polar x))
(put 'real-part '(polar) real-part)
(put 'imag-part '(polar) imag-part)
(put 'magnitude '(polar) magnitude)
(put 'angle '(polar) angle)
(put 'make-from-real-imag 'polar
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'polar
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)

The complex-arithmetic selectors access the table by means of a general "operation" procedure called apply-generic, which applies a generic operation to some arguments. apply-generic looks in the table under the name of the operation and the types of the arguments and applies the resulting procedure if one is present:

(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))
(error "No method for these types: APPLY-GENERIC" (list op type-tags))))))

Then the generic constructors and selectors can be written as:

(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))

(define (make-from-real-imag x y)
((get 'make-from-real-imag 'rectangular) x y))
(define (make-from-mag-ang r a)
((get 'make-from-mag-ang 'polar) r a))
Message passing

The key idea of data-directed programming is to handle generic operations in programs by dealing explicitly with operation-and-type tables. The style of programming used previously organized the required dispatching on type by having each operation take care of its own dispatching. In effect, this decomposes the operation-and-type table into rows, with each generic operation procedure representing a row of the table.

An alternative implementation strategy is to decompose the table into columns and, instead of using "intelligent operations" that dispatch on data types, to work with "intelligent data objects" that dispatch on operation names. We can have a data object, such as a rectangular number, represented as a procedure that takes as input the required operation name and performs the operation indicated. See example:

(define (make-from-real-imag x y)
(define (dispatch op)
(cond ((eq? op 'real-part) x)
((eq? op 'imag-part) y)
((eq? op 'magnitude) (sqrt (+ (square x) (square y))))
((eq? op 'angle) (atan y x))
(else (error "Unknown op: MAKE-FROM-REAL-IMAG" op))))
dispatch)

(define (apply-generic op arg) (arg op))

This style of programming is called message passing. The name comes from the image that a data object is an entity that receives the requested operation name as a "message".

2.4 Systems with Generic Operations

2.5.1 Generic Arithmetic Operations

We want to have a generic procedure add that acts like ordinary primitive addition + on ordinary numbers, like add-rat on rational numbers, and like add-complex on complex numbers. We will attach a type tag to each kind of number and cause the generic procedure to dispatch to an appropriate package according to the data type of its arguments.

The generic arithmetic procedures are defined as follows:

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))

We begin by installing a package for handling ordinary numbers. It will be tagged with scheme-number. Since these operations take two arguments, they are installed in the table keyed by the list (scheme-number scheme-number):

(define (install-scheme-number-package)
(define (tag x) (attach-tag 'scheme-number x))
(put 'add '(scheme-number scheme-number)
(lambda (x y) (tag (+ x y))))
(put 'sub '(scheme-number scheme-number)
(lambda (x y) (tag (- x y))))
(put 'mul '(scheme-number scheme-number)
(lambda (x y) (tag (* x y))))
(put 'div '(scheme-number scheme-number)
(lambda (x y) (tag (/ x y))))
(put 'make 'scheme-number (lambda (x) (tag x)))
'done)

Users of the Scheme-number package will create (tagged) ordinary numbers by means of the procedure:

(define (make-scheme-number n)
((get 'make 'scheme-number) n))

Here's the rational-number package:

(define (install-rational-package)
;; internal procedures
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))

;; interface to rest of the system
(define (tag x) (attach-tag 'rational x))
(put 'add '(rational rational)
(lambda (x y) (tag (add-rat x y))))
(put 'sub '(rational rational)
(lambda (x y) (tag (sub-rat x y))))
(put 'mul '(rational rational)
(lambda (x y) (tag (mul-rat x y))))
(put 'div '(rational rational)
(lambda (x y) (tag (div-rat x y))))
(put 'make 'rational
(lambda (n d) (tag (make-rat n d))))
'done)

(define (make-rational n d)
((get 'make 'rational) n d))

The complex-numbers package:

(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))
(define (make-from-mag-ang r a)
((get 'make-from-mag-ang 'polar) r a))

;; internal procedures
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))

;; interface to rest of the system
(define (tag z) (attach-tag 'complex z))
(put 'add '(complex complex)
(lambda (z1 z2) (tag (add-complex z1 z2))))
(put 'sub '(complex complex)
(lambda (z1 z2) (tag (sub-complex z1 z2))))
(put 'mul '(complex complex)
(lambda (z1 z2) (tag (mul-complex z1 z2))))
(put 'div '(complex complex)
(lambda (z1 z2) (tag (div-complex z1 z2))))
(put 'make-from-real-imag 'complex
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'complex
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)

(define (make-complex-from-real-imag x y)
((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
((get 'make-from-mag-ang 'complex) r a))

Here we're using a two-level tag system. The outer tag (complex) is used to direct the number to the complex package. Once within the complex package, the next tag (rectangular) is used to direct the number to the rectangular package.

2.5.2 Combining Data of Different Types

We were able to define a unified arithmetic system that encompass ordinary numbers, rational numbers, complex numbers, and any other type of numbers we might decide to invent. However, the operations are completely independent. We can't yet perform operations that cross the type boundaries, such as the addition of a complex number to an ordinary number.

One way to handle cross-type operations is to design a different procedure for each possible combination of type for which the operation is valid. For example, we could extend the complex-number package so that it provides a procedure for adding complex numbers to ordinary numbers and installs this in the table using the tag (complex scheme-number):

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

This technique works, but it is cumbersome. With such a system, the cost of introducing a new type is not just the construction of the package procedures for that type but also the construction and installation of the procedures that implement the cross-type operations. This can easily be much more code than is needed to define the operations on the type itself. The method also undermines our ability to combine separate packages additively, or at least to limit the extend to which the implmentors of the individual packages need to take account of other packages.

In the general situation of completely unrelated operations acting on completely unrelated types, implementing explicit cross-type operations, cumbersome though it may be, is the best that one can hope for. Fortunately, often the different data types are not completely independent, and there may be ways by which objects of one type may be viewed as being of another type. This process is called coercion. For example. if we are asked to arithmetically combine an ordinary number with a complex number, we can view the ordinary number as a complex number whose imaginary part is zero. This transforms the problem into combining two complex numbers, which can be handled by the complex-arithmetic package.

In general, we can implement this idea by designing coercion procedures that transform an object of one type into an equivalent object of another type. Here is a typical coercion procedure, which transforms a given ordinary number to a complex number with that real part and zero imaginary part:

(define (scheme-number->complex n)
(make-complex-from-real-imag (contents n) 0))

We install these coercion procedures in a special coercion table, indexed under the names of the two types:

(put-coercion 'scheme-number
'complex
scheme-number->complex)

Generally some of the slots in the table will be empty, because it is not generally possible to coerce an arbitrary data object of each type into all other types. For example, there is no way to coerce an arbitrary complex number to an ordinary number, so there will be no general complex->scheme-number procedure included in the table. Once the coercion table has been set up, we can handle coercion in aa uniform manner by modifying the apply-generic procedure. When asked to apply an operation, we first check whether the operation is defined for the arguments' types, just as before. If so, we dispatch to the procedure found in the operation-and-type table. Otherwise, we try coercion. For simplicity, we consider only the case where there are two arguments. We check the coercion table to see if objects of the first type can be coerced to the second type. If so, we coerce the first argument and try the operation again. If objects of the first type cannot in general be coerced to the second type, we try the coercion the other way around to see if there is a way to coerce the second argument to the type of the first argument. Finally, if there is no known way to coerce either type to the other type, we give up. Here is the procedure:

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

There may be applications where this coercion scheme is not general enough. Even when neither of the objects to be combined can be converted to the type of the other it may still be possible to perform the operation by converting both objects to a third type. In order to deal with such complexity and still preserve modularity in our programs, it is usually necessary to build systems that take advantage of still further structure in the relations among types, as we discuss next.

Hierarchies of types

There is often a more "global" structure in how the different types relate to each other.