Reading Time: 7 minutes

I recently took Dave Beazley’s week-long course on The Structure and Interpretation of Computer Programs. In this series, I’ll share memorable insights from the course (here’s where you can see all the posts so far).

The first two chapters of SICP emphasize the idea that all modular programming amounts to substitution. We substitute placeholder names for the values that we pass into functions and then run the code with those values.

In this post, we’ll turn to the third chapter of the book, which introduces mutable state: the ability to change the value of an existing variable.

We can do that in scheme with the set! operation:

Once we add mutable state, the substitution model we have used so far no longer works.

What changes when we add mutable state to our programs?

 Mutability Change #1: Rather than rely on substitution of passed-in variables, we must introduce the idea of scopes.

Suppose we want to build an interpreter in Python to evaluate and execute scheme code. We’d want it to evaluate typical Scheme expressions like these:

We write essentially a giant conditional for the evaluation and application of basic syntax (that link will show you the whole interpreter, and I’ll only inline the code directly relevant to our discussion here).

We want programmers to be able to create and execute procedures. We create a small class to represent the parts of a procedure, and we create an instance of it to represent each procedure in the code:

For every expression in the procedure, we take the parameters (the names that represent passed-in values in a function’s definition) and the arguments (the values passed in for those names when the function is called), zip them together, and then, on line 10, call the substitute method, which lives at the top level of our interpreter and looks like this:

It’s recursively substituting values for names before returning the fully substituted expression.

When it’s time to add scope, this goes away, and we must re-implement our interpreter to keep track of environments (again, full interpreter at link).

Our substitute method goes away. Now, each time we find ourself within the scope of a new procedure, we need to keep track of the environment at the time that the procedure was created, and additionally keep track of a new environment for the scope of this specific procedure.

For nested expressions, our nested environments are recursively passed through, first to seval (which evaluates expressions), then back into a new environment if evaluation reveals another procedure.

A quick note: You’ll notice on line 17 that we’re slapping our new local env on top of a copy of the existing environment, and for a huge environment that will be really space inefficient. We’ve talked on this blog before about a similar situation: tracking nested transactions in an implementation of an in-memory database. If this were a real interpreter and not a toy for learning purposes, I might turn to a solution like that one. Note that the nested scopes wouldn’t face that annoying deletion snafu we faced with the database: local scopes can overwrite the values of variables from broader scopes, but they don’t delete them.

 Mutability Change #2: “is” and “equals”.

The question of “is” (value equality) versus “equals” (reference equality) is only a problem when you introduce mutability. If created variables cannot be changed, it doesn’t matter if objects have the same reference or not. Their values are not going to change. So if they’re initialized at the same value, they might as well be the same.

This is why Swift has an identity operator === that you can use for classes, but not for structs. Structs don’t change after they are created and are always uniquely referenced, so to equate them we can only implement the equality operator ==, which does value equality for primitives and is intended to be used for value equality in compound objects, too.

 Mutability Change #3: Order matters.

Results only depend on the sequence of operations when variables can be reassigned. Before that, things can happen in any order, or concurrently, and the result is the same. “Stateless” functions (kind of a misnomer, the state is passed in, it’s not completely absent) make sense in cases of concurrent or asynchronous calls for exactly this reason.

When we mix state and potential concurrency, we can have the same piece of data getting modified at the same time in two different ways. Programmers usually resolve this with various types of mutex lock that prevent changes to data that the program thinks is currently being changed somewhere else.

Can we have state without reassignment or mutability?

Sort of. Suppose we have two operations: one that counts up, and one that counts down.

We want to run these two operations concurrently.

What if we were to implement a queue, shove operations from each of these functions onto that queue, and then pop them off and execute them one by one?

Our queue might look like this:

And then instead of executing each operation as it’s created, we put it on a queue. We define a run method to pop things off the queue and execute them in order:

What have we done here? We have delayed our procedures’ execution. Scheme has keywords delay and force to do this explicitly in programs as well.

We can take this concept even further with something like streams. Streams in scheme function much like a list, with an important difference: the car (first element) of the stream is evaluated, but the cdr (rest of it) is not.

From Dave:

“Stream processing lets us model systems that have state without ever using assignment or mutable data.”

Because all but the first element is not evaluated, we can even create infinite streams. These streams reference themselves in their cdrs, and that’s perfectly allowed.

If you try to do this with an ordinary pair, the Scheme interpreter will not let you, insisting that you have referenced a value before assigning it.

In the next post, we’ll talk more about delayed evaluation—specifically, about the implementation details of building an interpreter for a Scheme like-language that defaults to lazy evaluation instead of eager evaluation.

If you liked this piece, you might also like:

The Leveling Up Series

The Crafting Interpreters Series (which includes some examples of techniques from the leveling up series)

The Techtivism Series (when I finish the listening series and get around to publishing the techtivism series)