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

Constructor^{1}:

```
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 programming^{2}:

```
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 puzzle^{3}.

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