👩‍💻 chrismanbrown.gitlab.io

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.

« previous | index


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:

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.

diagram

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!

(map + '(1 2 3) '(4 5 6) '(7 8 9))
; -> (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:

diagram

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
(count-leaves x) ; -> 4

count-leaves introduces basic tree iteration:

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

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.

diagram

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)
  (accumulate
    append
    nil
    (map (lambda (i)
      (map (lambda (j)
        (list i j))
        (enumerate-interval 1 (- i 1))))
      (enumerate-interval 1 n))))

(make-pairs 4)
;; -> ((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)
  (accumulate append nil (map proc seq)))

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!