Lets Read: Structure and Interpretation of Computer Programs
Chapter 2: Part 1
2022-02-22
This is the fourth entry in the Letās Read SICP series.
2. Building Abstractions with Data
Okay we just wrapped up creating abstractions with procedures, now itās time to talk about data!
I canāt say too much about the chapter intro. It mostly just described things that weāre going to learn that which, not having learned them yet, did not mean too much to me.
2.1 Introduction to Data Abstraction
Data abstractions have constructors, which are familiar from OOP land. Itās how you make a thing.
And they also have selectors, like āgettersā, which is how you extract data from the abstraction.
I find myself once again considering functional programming vs.Ā object-oriented programming because to me, these two terms are deeply entrenched in OOP. But this book for the most part seems to avoid discussing either paradigm. Iāve already tempered a lot of my āFunctional good, Object Oriented badā feelings and rhetoric over the years, and this omission makes me wonder how superficial that divide really may be.
2.1.1 Example: Arithmetic Operations for Rational Numbers
Our introduction to data abstractions is rational numbers, aka fractions.
The authors do a good job of showing how the abstraction allows us to separate use of an abstraction from the implementation of an abstraction by not showing us the implementation at all.
Constructor signature:
(make-rational-number <n> <d>)
. Takes an
integer numerator and an integer denominator and returns a rational
number.
Selector signatures:
(numerator <x>)
. Takes a rational number and returns an integer numerator.(denominator <x>)
. Takes a rational number and returns an integer denominator.
This is enough to get started writing procedures for adding, subtracting, multiplying, and dividing rational numbers without ever knowing (or caring) about how the constructor or selectors are implemented.
The implementation is something I do care about though because they mark the appearance of some lisp celebrities.
Constructor1:
define make-rational-number cons)
(define numerator car)
(define denominator cdr) (
2.1.2 Abstraction Barriers
Data abstraction allows you to create abstraction barriers.
Each box in the following diagram represents a barrier between different ālevelsā of the program.
Being a program that uses rational numbers in the problem domain, you
have access to public methods like add-rat
,
sub-rat
, rat-eql?
, etc.
You do not have access to anything below that barrier.
Those public methods have access to the constructor and selector
procedures, make-rat
, numer
, and
denom
. They do not have knowledge of how those methods are
implemented.
The constructor and selectors, however, know that the data is
represented by pairs using cons
, car
,
cdr
.
And those language primitives know how they are implemented in the language.
Abstraction barriers allow us to freely change implementation details as long as we keep the APIs the same.
2.1.3 What Is Meant by Data?
A constructor, some selectors, and a definition.
For example, a pair: for any objects x
and
y
, if z
is (cons x y)
then
(car z)
is x
and (cdr z)
is
y
.
So thatās data.
Then this short section does something kind of unexpected.
It demonstrates an implementation of pair:
define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
(= m 1) y)
((else
(error "Argument not 0 or 1:
( CONS" m))))
dispatch)
define (car z) (z 0))
(define (cdr z) (z 1)) (
ā¦which is not itself unexpected.
What is unexpected is that the authors then tell us:
This use of procedures corresponds to nothing like our intuitive notion of what data should be.
To which I sayā¦ why would you think that?
We just spent the last section making a constructor and selectors for rational numbers out of procedures. How is this any different? I see passing data to procedure, and then returning data from a procedure.
The only thing I see here that is kind of interesting is that I think this might be the first time the authors have shown a closure.
When calling the constructor cons
, you pass two
arguments x
and y
and then return a new
procedure dispatch
that closes over and retains
access to the values of x
and y
.
But they make no mention of that.
They do say that even though this is a āprocedural implementationā of pairs and is a valid implementation, it is not a ārealā data structure. Which I guess is true in the sense that it is not a primitive data structure like a list or a hash or a tuple or something.
Finally:
This example also demonstrates that the ability to manipulate procedures as objects automatically provides the ability to represent compound data. This may seem a curiosity now, but procedural representations of data will play a central role in our programming repertoire. This style of programming is often called message passing, and we will be using it as a basic tool in Chapter 3 when we address the issues of modeling and simulation.
I think my inability to understand why procedural data structures are super special is also preventing me from understanding what message passing is in this context, but I guess Iāll just wait until Chapter 3 to find out more about that!
2.1.4 Extended Exercise: Interval Arithmetic
Interval arithmetic such as when dealing with resistors that, e.g., have a plus or minus 5% tolerance.
This can be represented also as a pair which stores the minimum and the maximum resistance. The example goes on to show that you can have different APIs for the same data (min/max vs.Ā center + width vs.Ā center + %) and that using different formulas can produce different results even though the formulas are equal. (Weird math!)
2.2 Hierarchical Data and the Closure Property
This section introduces box and pointer notation.
Closure is not what you think it is: closure is the property that allows combinations of things to be combined into combinations of things.
I think weāre going to use cons
pairs to make all of the
following data types.
2.2.1 Representing Sequences
All about lists! Filter em, map em, stick em in a stew!
One thing I learned is that schemeās map
procedure takes
a procedure and n number of lists, and then sequentially applies the
procedure to the ith number of each list!
+ '(1 2 3) '(4 5 6) '(7 8 9))
(map ; -> (12 15 18)
2.2.2 Hierarchical Structures
A list comprised of other lists can be thought of as a tree.
Look at the list ((1 2) 3 4)
It can be represented as a tree:
The length of the list is different to the number of leaves on the tree.
define x (cons (list 1 2) (list 3 4)))
(length x) ; -> 3
(; -> 4 (count-leaves x)
count-leaves
introduces basic tree iteration:
define (count-leaves t)
(cond ((null? t) 0)
(not (pair? t) 1)
(else (+ (count-leaves (car t))
(cdr t)))))) (count-leaves (
2.2.3 Sequences as Conventional Interfaces
Okay this gets into the kind of functional, list processing programming that I really like.
The authors introduce two arbitrary procedures. The first sums the
squares of all the odd numbers in a tree. The second describes a
procedure f(n) that produces a list of all of the even
Fibonacci numbers Fib(k) where k < n
.
They implement the procedures in a very imperative way that makes them structurally look quite different from each other.
But when described as signal flows they look like they should be more similar.
So we create a bunch of accumulators, maps, filters, and enumerators, and suddenly everything gets a lot more functional, modular, composable, etc.
Nested Mappings
Okay this is neat, too.
Imagine a situation that would call for a nested for loop. (The given
example is a procedure f(n) that returns all triples (i, j,
i + j) where 1 <= j <= i <= n
, where
i + j
is prime.
So you need to iterate over i
for each
1..n
, and at each step iterate over j
for each
1..i
, and accumulate (i j)
if
i + j
is prime.
In order to create this process, we first create a procedure using our enumerator, accumulator, and map from earlier in this section.
define (make-pairs n)
(
(accumulateappend
nillambda (i)
(map (lambda (j)
(map (list i j))
(1 (- i 1))))
(enumerate-interval 1 n))))
(enumerate-interval
4)
(make-pairs ;; -> ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4))
This accumulate append nil pattern is very common, and is in fact the implementation of flatmap, whom I know from my forays into functional programming2:
define (flatmap proc seq)
(append nil (map proc seq))) (accumulate
They go on to show how flatmap can help us compute all the solutions to the Eight Queens puzzle3.
2.2.4 Example: A Picture Language
This section was good but ultimately disappointing because I thought we were going to be writing an actual graphics program. Instead, the content was purely theoretical, focusing on a closed (as in implements the closure property) procedural data structure called a painter that we can combine and transform in lots of different ways to create mosaics.
It was straightforward enough until it got to how frames are implemented using three vectors (an origin and two edges) and a painter can be applied to a frame using a frame coordinate map. The implications were clear enough: you can trivially flip, invert, distort, and otherwise transform a frame (and thus the picture created by the painter) by setting different origins and edges. But I didnāt understand the implementation details.
Summary
So far, Chapter 2 is overall a little more chill than Chapter 1 was, as far as complicated math goes.
I think the problems with Chapter 1 come from the fact that it was trying to express complicated ideas about procedures as abstraction while using no data abstractions. So if youāre trying to express complicated ideas with nothing but primitive numbers, then youāre probably pretty likely to get fairly fancy with those numbers. Now that weāre dealing with procedural abstractions and data abstractions, our subject matter by itself is complicated enough that we can do some really interesting things without having to resort to complex mathematical formulas and theorems.
Okay, there are three more sections left in Chapter 2. Stay tuned!