EPISODE TRANSCRIPT
Structure and Interpretation of Computer Programs (Harold Abelson & Gerald Jay Sussman)
Automatically transcribed from the episode audio. Some words and names may be inaccurate.
Listen to the episodeDownload textDownload captions
What if I told you that data doesn't actually exist? Oh boy. Starting right out of the gate with that. I mean it. Like the numbers or the photos or even the text messages saved on your phone right now. What if they aren't physical things stored in little microscopic boxes but are actually, you know... active invisible spells just waiting for a command. It sounds totally like science fiction or, I don't know, mysticism. Right. Because we are so conditioned to think of computers as these rigid mechanical factories.
You know, you punch in a number, the gears turn and a predictable widget pops out. Exactly. We treat programming like handing a list of mundane chores to a very fast, very literal filing clerk. Right. A clerk who has no imagination whatsoever. But today, we are going to completely shatter that factory floor. Welcome to the Deep Dive. We are opening up a literal grimoire today. A grimoire. I like that. It really is. It's the 1996 second edition of a legendary MIT textbook. It's called Structure and Interpretation of Computer Programs. Written by Harold Abelson and Gerald J. Sussman with Julie Sussman. Yeah. And if you hang around software engineers, you only have to say two words, and they know exactly what you mean. The Wizard Book. The Wizard Book. And that nickname comes directly from the cover art, which is just iconic in the field. It really is. It features the sorcerer in classic robes, and he's holding a glowing magical sphere. And on the sphere, it says the words Evol and Apply.
Right. And across from him, there's a woman gesturing toward a burst of light containing the Greek letter Lambda. Yeah, which we will definitely get into. But I mean, it doesn't look like a computer science textbook at all. Not at all. It looks like an arcane text on how to bend the fabric of reality. Which is incredibly fitting, really. Because for years, this book was the terrifying, mind -expanding foundation of MIT's entry -level computer science course. Course 6001, right? Exactly. 6 .001. But I think we should make something crystal clear for you listening right now. Yes, please. Whether you are a senior software architect or someone who has literally never written a single line of code in your life, this deep dive is for you. 100%. This is not a coding manual. We are not going to teach you how to build a web app today. Far from it. It's a profound philosophical treatise, really, on how human beings can manage impossible complexity.
It's about organizing thought. Yes. Organizing thought. The overarching theme is actually laid bare right in the foreword, which was written by Alan J. Perlis. And he drops a massive bombshell on the very first page. He does. He states, and I quote, Computer science is not a science, and its significance has little to do with computers. I absolutely love that line. It's so good. But it makes you wonder, if it's not about computers, what is it about? Well, my read on Perlis is that the computer revolution is actually a revolution in human expression. Okay, unpack that. He calls it the emergence of procedural epistemology.
Epistemology being the study of knowledge. Right. Classical mathematics is declarative, right? Yeah. It provides a framework for dealing with what is. Like stating facts. Exactly. It's about true statements. But computation provides a framework for dealing with how to. Ah. So if math is the study of absolute truths, this procedural epistemology is the study of active processes. Yes. You aren't just stating facts anymore. You are conjuring abstract processes that evolve and manipulate information. The book leans so heavily into this metaphor of magic. Like, the programs we write are carefully composed spells. Spells written in esoteric languages directing invisible spirits.
It's so poetic. But Perlis uses another analogy in his preface that really stuck with me. He compares the computer to a violin. Oh, the phonograph versus the violin. That frames the entire philosophy of the book. Right. So he says, imagine a novice who tries a phonograph first. You put the needle down and perfect music plays. It's effortless. Completely effortless. Then that same novice picks up a violin, scrapes the bow across the strings, and it just screeches. It sounds terrible. awful. And the novice immediately declares that the violin is a terrible, inflexible machine that isn't fit for purpose. But the violin isn't inflexible at all. No, it just requires mastery.
A phonograph can only ever play what someone else has already recorded. Right. It's a closed system. Exactly. But a violin, once you master it, can create infinite original music. And most of the software we interact with daily, you know, our social media apps, our operating systems, those are phonographs. They are prepackaged. Completely prepackaged, closed experiences. You can only do what the programmer anticipated you would do. Right. But the programming language itself, the raw tool of computation, that is the violin. And Perlis points out that when we learn to program at this really deep level, we are learning to build evolving organisms. He explicitly contrasts languages here, which is fascinating. Yeah, he says a language like Pascal is for building pyramids. Right, pyramids. Static, imposing, rigid structures where every single block has to be perfectly planned in advance.
But Lisp, which is the language used throughout the wizard book, is for building organisms. Dynamic, fluctuating systems. Yeah, systems made of simpler organisms fitting together, constantly evolving and reacting to things. And that transition, you know, from pyramid builder to organism breeder. That is the core journey of the book. We have to learn to read the sheet music of this masterpiece. And that is exactly what our mission is today. We are going to meticulously go through the core concepts, chapter by chapter. To uncover the secrets of how you build these robust, complex organisms from absolute primitive spells. But, you know, to build an organism, you can't just start with a fully formed... arm or leg. No, you have to understand the cellular biology first.
Right, you need the basic building blocks. Chapter one. The fundamental spells, the active verbs of our magical language. The authors argue that every powerful programming language, no matter how modern or archaic it is, has to provide three basic mechanisms. Okay, let's break those down. First one. First, you need primitive expressions. These are the simplest entities the language cares about. So like basic numbers. Exactly. Basic numbers. That's your raw material. Okay. What's the second mechanism? Then you need means of combination. You have to be able to put those primitive elements together to build compound elements. So basic math operations. Addition, multiplication. Right. And finally, the most important piece of the puzzle, means of abstraction.
Abstraction. That's a heavy word. What does that mean in this context? It means once you've combined things into a complex compound element, you need a way to give it a name and treat it as a single new unit. Ah, okay. So I don't have to keep repeating the long, complex combination. I just use the name. Precisely. Now, the language they use to explore all of this is a dialect of lisp. called Scheme. Scheme. And Lisp is ancient in computing terms. Very ancient. I think only Fortran is older. It was invented by John McCarthy in the late 1950s. That's wild. But it survives because of its radical, fundamental elegance. It really does. Though I have to admit, looking at Lisp code for the first time feels like looking at alien algebra. Oh, it completely departs from customary mathematical convention. Yeah, Lisp uses prefix notation. Which... throws everyone off at first. It totally does, because it means the operator always comes first. Right. Like, if you or I want to add 2 and 3, we write 2, then a plus sign, then 3. But in Lisp, you open a parenthesis, write the plus sign, then the 2, then the 3, and then you close the parenthesis.
It looks strange to our eyes, but the advantages are immediate when you actually start writing real programs. How so? Well, prefix notation accommodates procedures that take any number of arguments without any ambiguity whatsoever. Okay, give me an example. You can write open parenthesis, plus sign, 21, 35, 12, 7, close parenthesis. And the machine just adds them all up. Because the leftmost element inside the parenthesis is always the action. Exactly. And everything that follows is just the stuff being acted upon. It makes sense. But the real power I saw was how perfectly it nests. Yes. The nesting is where it gets incredibly powerful. You can put a combination inside a combination infinitely deep. And that nested structure becomes explicitly drawn out by the parentheses. It's so visual. You can write an expression that means add the result of multiplying 3 and 5 to the result of subtracting 6 from 10.
Right. The parentheses force you to articulate the exact tree structure of that computation. It's literally like Russian nesting dolls of math. That's a perfect analogy. You open the big doll, the addition, and there are two smaller operations inside it. The multiplication and the subtraction. And sitting behind all this nesting, this endless combination, is the heartbeat of the list machine. What the authors call the REPL. R -E -P -L. The Read Evil Printlip. It is the core cycle of the interpreter. Walk me through that cycle. So it reads the expression you typed. That's the R. Okay, reading the text on the screen. Then it evaluates that expression to find its meaning. That's the E. The evaluation part seems like the heavy lifting. It is. Then it prints the result, the P. And then it loops.
It just sits there waiting for you to type something else. Exactly. Now, to give us a mental framework for how this evaluation actually happens under the hood, the book introduces the substitution model of evaluation. The substitution model? Let me see if I have this right, because it feels a lot like middle school algebra. It is very similar. So, if I define a procedure called square that takes a number, let's call it x, and multiplies x by x. Okay, simple enough. Later, I ask the machine to evaluate the square of 5. Under the substitution model, the machine simply takes the text of my procedure. finds the parameter x, and swaps in the number 5. Right. So x times x just literally becomes 5 times 5, which reduces to 25. You've completely captured the essence of it. It's just text replacement. Basically.
To evaluate a complex combination, the machine evaluates all the subexpressions first, and then applies the operator to those evaluated arguments. Okay. And if the operator is a custom procedure you built, like your square function, it literally substitutes the arguments into the body of your procedure. It's just a process of continuous reduction. We're shrinking the equation until there's only one number left. Exactly. But of course, the authors throw a massive curveball early on. Oh, they do. They introduce recursion. Defining a procedure in terms of itself. Which is so trippy. If creating a procedure is like writing a recipe for the machine, recursion feels like writing a line in the recipe that says, now go read this exact recipe again. Yes. My immediate thought was, how does the computer not just spin out of control into an infinite loop and eventually just explode? It's a very common reaction. And the authors use this exact confusion to draw a really crucial distinction.
Between what? Between the syntax of a procedure, which is... just how the text is written on the screen and the shape of the computational process it actually generates in memory. The syntax versus the shape of the process. Right. A procedure might be recursive in its syntax, meaning the code text literally calls its own name. Okay. But the process that unfolds in the machine's memory can be entirely different. Wait, so a recursive syntax doesn't always mean a recursive process? Exactly. We can illustrate this with a classic example from the book, Calculating a Factorial. Ah, factorials. Remind me how that works. So the factorial of 6 is 6 times 5 times 4 times 3 times 2 times 1. If we design this as a recursive process, the machine thinks, to find the factorial of 6, I need to multiply 6 by the factorial of 5. But it doesn't know the factorial of 5 yet. Exactly. I don't know the factorial of 5 yet, so I'll put the multiply by 6 operation on hold. It leaves the trail of brokrums. Yes. It pauses its current task. Saves its place and dives deeper into the rabbit hole.
Now I need the factorial of 4, so put the 5 on hold. And it builds up this massive chain of deferred operations. It dives all the way down to 1. Okay, and then what? Once it hits the bottom, the 1, it has to walk all the way back up that chain, executing all those deferred multiplications. Doing all the math it put on hold. That is a true recursive process. If shape expands as it builds the chain and then shrinks as it calculates the answer. It physically takes up more space. Crucially, yes. It requires an expanding amount of memory to keep track of all those deferred operations. So what's the alternative? How do you calculate a factorial without leaving that massive memory -hogging trail of breadcrumbs?
You use an iterative process. You use state variables. State variables? How does that change the shape? Instead of deferred operations, you keep a running product and a counter. Ah, so like step one, the product is one, the counter is one. Right. Step two, the product is two, the counter is two. Step 3. The product is 6, the counter is 3. You are passing the current complete state to the next step every single time. So the instructions are just multiply the running product by the counter, increase the counter, and call the procedure again. Exactly. Now notice the syntax is still recursive. The procedure is still calling itself by name at the end of every step. Oh, I see.
But the process is iterative. At any given moment, Those two variables contain the entire state of the computation. So if I tripped over the power cord and unplugged the machine halfway through, I wouldn't lose some invisible chain of deferred operations. No, you wouldn't. I could just look at the two numbers written on the screen. Let's say product is 120, counter is 5, plug the machine back in, and resume perfectly from that exact spot. That is the defining feature of an iterative process. It runs in constant memory space. it never expands. That is brilliant.
And one of the really beautiful things about Scheme is that its interpreter is specifically designed to execute these iterative processes without ever running out of memory, no matter how many times the procedure calls itself. Okay, so we have our basic spells. We have numbers, we can name things, we can nest operations, and we can write loops that run forever in constant space. That's a solid foundation. Most people would stop there and say, great, I can write software now. But... The wizard book shifts gears into something called higher order procedures.
And this is where the training wheels completely come off. Up to this point, our spells have only acted on raw materials. Just numbers. Nouns. Right. Yeah. But true abstraction requires more power than that. Often you'll find the exact same pattern of computation used in completely different situations. Give me an example. You might write a loop to sum the integers from 1 to 10. 1 plus 2 plus 3. Exactly. Then later, you write a loop to sum the cubes of the integers from 1 to 10. So 1 cubed plus 2 cubed plus 3 cubed. The structure of the loop is identical.
The addition part is identical. The only thing that changes is the tiny little action you perform on the number right before you add it to the pile. Right. In many conventional languages, you'd be forced to write two completely separate procedures for that. Lots of repeated code. But not in LISP. Not in LISP. In LISP, procedures are first -class citizens. First -class citizens, meaning what exactly? They have the exact same rights and privileges as numbers do. Meaning I can pass a verb into another verb. I don't just hand the machine a number. I can hand the machine a tool. Yes. You can define a general sum procedure. It takes the starting number, the ending number, and it takes a third argument, a procedure that tells it what to do to each term. So I can pass my cube procedure directly into the sum procedure as an argument. It's like, imagine a factory. Instead of giving a factory worker a pile of wood and telling them to build a chair, you hand them a pile of wood and you also hand them a custom built saw and you say, use whatever saw I hand you on this wood. That's a great way to visualize it. And then the next day you hand them the same wood, but a drill instead of a saw. The factor worker, which is our sum procedure, doesn't need to know how the tool works. They just need to know they have to apply it. The flexibility is just staggering.
You can even write procedures whose entire job is to manufacture and return brand new procedures. We are totally blurring the traditional line between active processes and passive data. A procedure is no longer just a rigid rule for manipulating data. It can be tossed around, passed as an argument, and returned as a result. Just like a simple number. Which perfectly sets up the most mind -bending transition in the book. Chapter two. Yes. Moving on from procedures to data. Because if procedures are the active verbs of our language and we can pass verbs around like nouns, what are the nouns? What actually is data? This introduces the concept of the illusion of data. In our journey from basic cells to complex organisms, we've mastered processes. Now we must tackle compound data. Because the real world isn't modeled with isolated numbers. No, we need to represent complex phenomena with multiple interconnected parts. And the authors use rational numbers fractions as their prime example here.
Because a fraction intrinsically has two parts. A numerator and a denominator. They are glued together. To manage this complexity, they introduce the principle of data abstraction. Okay, data abstraction. The goal is to build a wall, an abstraction barrier, between how a compound data object is used and how it is physically constructed under the hood. It reminds me of a corporate org chart, honestly. Esso. Imagine the CEO of the math department wants to add two fractions together. The CEO shouldn't be digging around in the basement trying to figure out if the numerator is stored in filing cabinet A or written on a sticky note on someone's desk. Right. The CEO shouldn't care about those details. The CEO just wants to say, give me the numerator. Exactly.
So we build a constructor procedure. Let's call it make rat, which takes two numbers and glues them together into a rational number. OK. And we build selector procedures, numera and denum, which. Extract those pieces. And the CEO only ever talks to Numer and Denim. Right. The CEO's high -level addition procedure uses those selectors, does the math, and uses MakeRat to output the new fraction. And the beauty of this is, if the IT department goes into the basement a year later and completely changes how fractions are stored in the computer's memory. The CEO doesn't have to change a single line of their high -level addition code. Deferring decisions about data representation until the last possible moment preserves maximum flexibility in your system architecture. It's so clean. But then the authors push this concept to an extreme that completely challenges our fundamental understanding of computation.
They ask a seemingly simple question. What is meant by data? I remember reading this section and literally putting the book down to stare at the wall. It has that effect. Because their answer is that we don't actually need underlying data structures to create data. They define data purely by its behavior. But how is that physically possible? I mean, if I have a fraction 1 over 2, those numbers 1 and 2 have to live somewhere in the machine, right? You would think so. If you don't have a physical data structure, like a physical box in memory, how does the pair even exist? Well, in Lisp, the primitive glue used to pair two things together is called cons, C.
Okay, cons. You cons one, two together. Then you extract the first part with a command called car, C -A -R, and the second part with C -D -R -C -D -R. Weird names, but okay. They are historical artifacts from early hardware. Normally, we imagine cons allocating a tiny physical box in memory with two compartments. Right, a literal container. But the authors demonstrate the procedural representation of pairs. They show that cons, car, and CDR can be implemented using nothing but functions. Okay, you have to walk me through the mechanics of that. How does a function act as a pair of numbers?
Imagine cons doesn't build a box at all. When you call cons and hand it the numbers 1 and 2, it doesn't store them in memory compartments. What does it do? Instead, it manufactures and returns... A brand new procedure. A verb. A verb. And inside the internal scope of this new verb, those numbers one and two are trapped. Trapped. They're suspended in the environment of that function. This new procedure just sits there, completely dormant, waiting for you to interact with it. It's just waiting for a command. Exactly.
When you want the first number, you use car. But car isn't reaching into a physical box. Car is actually sending a message to this dormant procedure. Oh, wow. It sends a message saying, give me your first item. The doorman procedure wakes up, hears the message, and replies with the one. And if you send it the CDR message. It replies with the two. That is unbelievable. The data isn't a passive container at all. The data is an active, intelligent entity that reacts to messages. This is known as message passing. And the abstraction barrier is so flawless that the high -level math program adding those fractions literally cannot tell if the pair it's interacting with is a physical block of memory or a cleverly disguised function intercepting messages. It destroys the boundary between procedure and data.
Nouns are just verbs waiting to be activated. It's all just processes all the way down. Indeed. So, okay, once we have this magical cons glue, whether it's made of boxes or functions, what do we actually build with it? We leverage a mathematical property called closure. Closure. And we should be careful here. This is mathematical closure, not the lexical closures we just touched on, where a function traps variables in its scope. Right. Different kind of closure. Mathematical closure means that when you combine two things using an operation, the result can be combined again using that exact same operation. Like addition.
If I add two and three, the result is five. And five is still a number. I can immediately feed five back into another addition operation. The system doesn't break. Exactly. Because cons satisfies the closure property, we don't just have to glue two raw numbers together. We can take a pair and glue it to another pair. Okay. And then glue that resulting structure to a third pair. We can build sequences, linked lists, deeply branching trees. We're moving from single cells to complex tissues now. And we can build higher order procedures to operate on these massive structures uniformly.
Like what? We can map a function across every single leaf of a giant tree or filter a list based on a specific condition or accumulate all the values into a single result. The book visualizes this beautifully with a picture language. Oh, that's a wonderful section. They show how you can define a basic painter, which is just a procedure that draws lines inside a frame. Right. But because of Clojure, you can write an operation that takes a painter. scales it down to half size, and places it next to a copy of itself. And the output of that operation is not just raw pixels on a screen.
It is a new, more complex painter. Which means you can feed it right back into the same scaling operation. You can take the two -image painter, shrink it, and place it next to itself to make four. Then 16. You can add rotations. The authors show how you can recreate those mind -bending MC Escher drawings. Yes, like the one where the fish interlock and shrink infinitely toward the center of the page. And you do it using just a handful of perfectly closed operations. Infinite complexity arising from very simple rules. It is a stunning demonstration of abstract modeling.
But, you know, we've built these beautiful, hierarchical, infinitely complex structures. But there is a glaring limitation to everything we've done so far. There is. The Escher drawings are frozen. They don't move. They are completely timeless. In the functional programming we've been doing so far, if you evaluate a mathematical expression, it always yields the exact same result, regardless of when you ask. But the real world isn't static. No. The real world changes over time. If we want our computational organisms to model a dynamic world, we have to allow our programs to change.
We have to introduce the concept of state. Chapter 3. State. Meaning an object has state if its behavior is influenced by its own history. To achieve this, the author's hand is a dangerous new spell. Assignment. The set command. S -E -T exclamation point. Which is a great visual warning sign in the code. It really is. We are finally giving our objects local memory. Consider modeling a bank account. Without assignment, an account is just a static number. Okay. If you have an account with $100 and you evaluate a withdrawal of $10, a purely functional program doesn't change the account. What does it do?
It takes the $100, subtracts $10, and returns a brand new, completely separate entity representing $90. But the original $100 account... Still exists, perfectly intact in the mathematical ether. It's like snapping a photograph of the account at different moments, but the account itself isn't a living thing. Right. But with Set... We can change the value of the balance variable in place. We can tell the machine, update the balance to be whatever the balance used to be, minus 10. And the account now remembers its new balance. It creates a much more intuitive model of the real world. But the cost is devastating, isn't it? It is. By introducing set, we permanently lose. a mathematical property called referential transparency. Let's ground that term. What does referential transparency actually mean for the programmer typing at the keyboard? It means you can substitute a procedure call with its calculated value without changing how the program behaves.
Okay, give me an example. In our old, timeless world, if you evaluate square 5, it is always 25. You could literally go through your code, erase square 5, write 25 in pencil, and the program would run identically. But with our new bank account, that's impossible. Completely impossible. If I run withdraw 10, the result depends on time. The first time I run it, it might return 90. If I run the exact same line of code a second time, it returns 80. Because the underlying variables are mutating. I can't replace the code with a fixed number. We are no longer doing pure mathematics.
We have let the demon of time into our machine. We broke the x -ray machine. We can't just trace the code on a piece of paper easily anymore using the substitution model. So how do the authors... Fix our mental model because substitution is dead. They replace substitution with a much heavier framework, the environment model of evaluation. I remember this requiring a lot of physical drawing of boxes and arrows on paper to understand. It requires visualizing environments, which are sequences of frames. Frame. Think of a frame as a secure physical box in the computer's memory.
Inside this box is a ledger that holds the associations between variable names and their current. mutable values. So when I call my bank account procedure, the machine doesn't just substitute text anymore. No. It creates a new sealed box, a new frame. Inside that box, it writes down balance equals 100. Exactly. And the withdraw procedure lives inside this specific environment. So when it uses set, it reaches into its specific box and crosses out the 100 and writes 90. And because that frame is encapsulated, no other part of the massive program can accidentally see or mutate that specific balance variable. It gives us true modularity. But modularity with state leads us into a terrifying thicket. It really does. Because in the real world, things don't happen one by one in a neat, orderly line. Things happen simultaneously.
Concurrency. If we model the world with independent objects that have internal state, What happens when multiple processes try to interact with the exact same object at the exact same moment? The classic race condition. Imagine you and I share a joint built account with $100. I go to an ATM in New York and you go to an ATM in London. At the exact same millisecond, we both hit the button to withdraw $10. If the timing is perfectly misaligned, the consequences are disastrous. Walk me through the disaster. The New York ATM reads the balance. 100. A millisecond later, before New York updates anything, the London ATM reads the balance. 100. Okay, so New York calculates the new balance as 90, and London calculates the new balance as 90. New York writes 90 into the shared frame. A microsecond later, London overwrites that 90 with its own 90. Oh, wow. So we collectively withdrew $20, but the bank's internal state only reflects a $10 withdrawal.
Free money for us, bad news for the bank. The state variable has been corrupted by time. To solve this, you have to introduce incredibly tedious traffic control mechanisms. You hear programmers talk about mutexes. Mutually exclusive locks. Right. It's like the physical key attached to a giant hubcap for a gas station bathroom. That's a good visual. If the New York ATM has the key, it locks the bathroom door. It goes in, reads the balance, does the math, writes the new balance, walks out, and hands the key to London. But managing those locks across thousands of interacting processes, ensuring processes don't freeze while waiting for a key, is notoriously difficult. It introduces immense complexity.
Which is why I was so struck by the author's alternative. Yes. After spending pages showing how complex time and state are, they introduce a paradigm shift. They ask, what if we just didn't use time? They introduce streams. This felt like stepping completely outside of reality. How do streams work? A stream is a data structure that represents the entire history of a variable past, present, and future as a single continuous mathematical list. Okay, wait. Instead of updating a single balanced variable step -by -step using assignments, a stream models the bank account as an unbroken sequence of balances. Yes. But how can a computer store the future? A bank account could theoretically have an infinite number of transactions. If I ask the computer to build an infinite list, it will instantly run out of memory and crash. It avoids crashing through the magic of delayed evaluation. Delayed evaluation. A stream looks and feels exactly like the list we built earlier, but it doesn't compute all its elements at once.
When you create a stream, it computes the first element and then packages the rest of the computation into a func. Let's ground func. What is it mechanically? A func is simply a procedure with no arguments that hasn't been called yet. It's a promise. Exactly. It's a promise. The stream says, here is your first balance, and here is a sealed envelope. Inside the envelope are the instructions to calculate the next balance, but do not open it until you actually need it. It's extremely lazy evaluation. It only works when forced. Exactly. Because of this laziness, you can write programs that manipulate infinite series. You can write a stream that represents all the prime numbers in the universe.
And the machine doesn't crash? No. Because it only calculates the very first prime number two and hands you an envelope containing the recipe for finding the next one. And then? You ask for the next prime, it opens the envelope, finds the three, and hands you a new envelope. It turns the crank exactly one time. But how does this save us from the horrors of the race condition at the APM? Because there is no set. Nothing is ever being overwritten or mutated. The stream of bank balances is just a pure mathematical function of the stream of withdrawal requests.
We have recovered referential transparency. Yes. We've completely bypassed time. Time is no longer a sequence of mutating variables that we have to lock and protect. Time is just treated as another spatial dimension laid out completely flat like a strip of film. We can look at the whole history at once. It's a God's eye view of computation. But the authors don't stop at giving us a God's eye view. They take us to the logical extreme of procedural epistemology. They show us how to become gods ourselves. Chapter 4. This takes us into the realm of metalinguistic abstraction. Metalinguistic. We've bent time.
We've turned data into active procedures. But all of this has been within the confines of the scheme language. What if the language itself isn't suited to our problem? The authors argue that the most fundamental idea in programming is that the evaluator, the complex software that reads your code and figures out what it means, is just another program. An evaluator is just an interpreter. And they are saying we can write a Lisp interpreter using Lisp code to run Lisp programs. It is called a metacircular evaluator. And its core mechanism is a beautiful endless cycle between two procedures, evil and apply.
The two words on the sorcerer's sphere from the book's cover. The yin and yang of computation. Okay, how do they interact? Evil's job is to take a raw expression and the current environment and reduce it to a procedure and a set of arguments. It preps everything. Right. It then hands those over to Apply. Apply takes that procedure, strips away the abstraction barrier, and reduces it to a new, simpler set of expressions. And what does it do with those? It hands those new expressions back to Evil. Evil to apply, apply to evil, cycling downward, unpacking the Russian nesting dolls until it hits the absolute primitive bedrock basic numbers and built -in hardware math. The philosophical implication is what Alan Turing proved decades ago. The concept of a universal machine. A universal machine. Our evaluator is a program, but it acts as a machine. If we feed this evaluator a set of rules describing a different programming language, our evaluator configures itself to emulate that other language. It is a master blueprint that can fold itself into any machine you can imagine. Exactly. But my immediate pushback when reading this was, why?
Why go to the immense trouble of building a scheme evaluator inside scheme? I already have scheme. If your goal is just to run standard scheme, it is redundant. But the power of metalinguistic abstraction is linguistic experimentation. If you own the evaluator, you are no longer bound by the rules of the language designers. You can change the fundamental laws of physics of your universe. We can invent entirely new programming paradigms. The book demonstrates this by tweaking the evaluator to perform lazy evaluation globally.
Like the streams we just talked about. Right. In standard scheme, arguments are evaluated eagerly before being passed to a function. But with a few changes to our evil procedure, we can force the language to wrap every single argument in a thunk, a delayed promise. So instead of streams being this special, weird data structure we have to build manually, the entire language becomes lazy by default. We've invented a normal order language. But they push it even further. They introduce a language extension called non -deterministic computing. Using an operator called AM. A -M -B. The AM operator. I have to say, this was the moment my brain officially melted. It stands for ambiguous. And it is a phenomenal paradigm shift. The AM operator essentially implements the multiverse theory of quantum mechanics into your code. It really does. You give it a set of choices. For example, you say X is the AM of 1, 2, and 3. Normal language would throw an error. Or maybe just pick the first one. But the AM evaluator doesn't pick. No. It literally splits the execution into parallel realities.
It explores the universe where X is 1, the universe where X is 2, and the universe where X is 3 simultaneously. And you combine this branching multiverse with constraints. You assert that a certain condition must be true in a valid universe. The book uses logic puzzles to show this, like the multiple dwelling problem. Oh, that's a classic. Five people live on five different floors of an apartment. And you have a list of arbitrary rules. Baker doesn't live on the top floor. Cooper doesn't live on the bottom floor. Fletcher isn't adjacent to Smith. In a normal language, you would have to write massive, complex, nested loops to test every single combination. But with AM, you don't write the search algorithm at all. You simply state the choices. Each person lives on an AM of floors one through five. And then you list the constraints. And the language does the searching.
If the evaluator explores a universe where Baker is on the top floor. It hits your constraint, realizes this reality is invalid, and that universe dies. But here's the critical part. How does it keep searching without losing its mind? Right. How does it track all these dead universes? It uses continuations. Continuation. A continuation is essentially a highly advanced save state. Every time the AM operator faces a choice, the evaluator takes a complete snapshot of the entire program state. and saves it. Okay. When a constraint fails and a universe dies, the evaluator simply backtracks. It hits load game on the most recent save state, rewinds time, and takes the next available fork in the road. It automatically collapses the multiverse until it finds the one reality where all constraints are satisfied and it prints the answer. You just described the rules of the puzzle and the language solves it.
It feels like pure magic. They conclude this metalinguistic journey with an even more radical departure. logic programming. We abandon the imperative how to computing entirely and return to declarative what is knowledge. We build an engine where we just declare relationships. We tell it John is a father of Mary and Mary is the mother of Susan. Then we ask who is the grandfather of Susan. And the engine uses mathematical logic, pattern matching, and deduction to figure out the answer. We have traveled from simple numbers to state -driven objects to lazy streams to multiverses to automated logic engines. But this raises the ultimate grounding question. Yes, it does. All these infinite multiverses, these deferred promises, these environments, they are beautiful abstractions.
But eventually, these abstract thoughts have to run on physical atoms. They have to hit a processor made of silicon and copper wire. Which brings us to the final descent of the book, stripping away the magic to find the mechanics. Chapter 5 explores computing with register machines. We drop out of the clouds of philosophy and hit the bare metal. We are no longer talking about environments or infinite timelines. We are talking about physical boxes. A register machine is a model of a computer at the hardware level. What are the components? The boxes are registers' tiny physical memory banks that hold sequences of bits. Okay, memory banks. The data paths are the physical wires connecting these registers, allowing bits to flow from one box to another.
And how do they know when to flow? The controllers are the physical sequences of buttons that dictate which wires are active at any given microsecond. The authors show us how to build a theoretical machine to compute the greatest common divisor, the GCD, of two numbers. And it is breathtakingly granular. You define register A, register B, and a temporary register T. You literally write out the step -by -step controller sequences. The controller checks a physical sensor to see if register B is zero. If the sensor is triggered, it opens a gate to route the contents of register A to the output. And if it's not zero? If the sensor is not triggered, it calculates the remainder.
opens a gate to move B into A, opens another gate to move the remainder into B, and loops back to the start. It just switches opening and closing. It's so mechanical. But reading this, I hit a massive intellectual roadblock. What was it? It bridges all the way back to our very first discussion about recursion. Ah, the problem of recursion on finite hardware. Exactly. If a register machine only has a fixed physical set of boxes, let's say, 10 registers soldered onto a motherboard, how on earth does it compute a recursive process? We established that a recursive process, like calculating a complex factorial or traversing a giant tree, builds up an expanding chain of deferred operations. It needs an exponentially growing amount of memory to remember its past states. How can a machine with only 10 physical boxes remember an infinitely deep recursive chain?
This is the moment the hardware magic is revealed. To execute recursion, the physical machine relies on one critical hardware component. The stack. The stack. The stack is what provides the illusion of infinite memory. How does it work? It is a specialized memory structure that operates on a last -in, first -out principle. Think of a physical stack of heavy plates at a buffet. Right, the ones that are pushed down into a spring. You push a new plate onto the top of the pile, pushing the others down. When you need a plate, you pop the top one off. So how does the register machine use this to solve recursion? When the machine is calculating a factorial and realizes it needs to dive into a recursive subproblem, it knows it can't just overwrite its current registers. It needs those specific values later to finish the math. So before it dives down the rabbit hole, it saves the current contents of its registers by physically pushing them onto the top of the stack. It sets its current reality aside. It safely packs its bags. Having secured its state on the stack, It is now free to overwrite its main registers to solve the smaller subproblem.
It dives deeper. Pushing new states onto the stack every time it recurses. Okay, so it gets to the bottom, solves the base case. Then what? It needs to resume its previous work. So it pops the top values off the stack, loading them back into the main registers. Restoring its previous state perfectly. It restores, does the deferred multiplication, pops the next state, restores, multiplies, all the way back to the surface. The stack is the physical bridge that allows finite silicon hardware to execute infinitely deep abstract recursive processes. It's the secret sauce that makes the math possible in the real world. And then for the grand finale of the entire book, the authors pull off an incredible synthesis.
The explicit control evaluator. They literally take the metacircular evaluator we built in Chapter 4, that massive Lisp -in -List program with its eval -apply cycle and its complex environment frames, and they translate the entire thing into the granular register machine instructions of Chapter 5. They bridge the gap between high -level Lisp and raw machine code. They design a physical register machine whose sole dedicated purpose is to read, evaluate, and execute LISP programs. They cast the abstract evaluator into silicon. And as they do this, they clarify the fundamental difference between an interpreter and a compiler, which I found fascinating. The explicit control evaluator we just described is an interpreter, right? An interpreter traverses your source code structure, analyzing it and executing it on the fly, line by line. It's interactive. If you type a command into the REPL, the interpreter executes it instantly. But the drawback is that the interpreter has to figure out the syntax every single time?
Yes. If you have a loop that runs a million times, the interpreter re -analyzes the structure of that loop a million times. It's flexible, but it's slow. A compiler, on the other hand, is a translator. It takes your entire high -level Lisp program and analyzes it fully before anything runs. It translates the abstract... abstractions directly into a highly optimized raw sequence of machine instructions. It does all the heavy lifting of figuring out the environments and the variable lookups ahead of time. Once compiled, the program runs incredibly fast because it's just pure native machine code. And modern computing ecosystems rely on both, right? We interpret while we are actively developing, experimenting, and debugging because we need that interactive REPL. And we compile when we're ready to deploy the software and need raw, unadulterated performance.
So let's step back and look at the epic descent we've just made. It's been quite a journey. We started in chapter one with the magical fundamental spells of computation, learning how to combine primitive procedures and write recursive processes. In chapter two, we realized that data itself is an illusion, constructed from those very same procedural spells using message passing. In Chapter 3, we grappled with the curse of time, state, and concurrency, and explored how lazy streams can map infinite time to flat space. In Chapter 4, we learned to rewrite the laws of the universe by building our own evaluators and multiverses.
And finally, in Chapter 5, we stripped away the magic to find the cold, hard clockwork of the register machine and the stack beneath it all. It is a remarkable, exhausting intellectual journey. But it brings us perfectly full circle to Alan Perlis' Forward. We didn't just learn the syntax of a 1950s programming language today. We learned a procedural epistemology. We learned how to manage impossible complexity by building abstraction barriers and defining conventional interfaces. We learned how to build Perlis' evolving organisms rather than static pyramids. If you can internalize these concepts, it permanently changes how you approach complex problems in your everyday life.
Whether you are organizing a massive corporate structure, modeling a financial system, or just trying to understand human language. You start seeing abstraction barriers and evaluation loops everywhere. It provides vocabulary for describing complex systems of any kind. Which leaves me with one final, deeply provocative thought for you, the listener, to mull over as we end this deep dive. Lay it on us. Throughout this entire journey, we've seen a recurring pattern. As systems become sufficiently complex, the rigid lines we draw to make ourselves comfortable begin to blur and dissolve. Yes, they do. Data becomes procedures waiting for a message. Procedures become data to be passed around as arguments.
Our metacircular evaluator is just a program written in text, yet it acts as a machine. And the hardware register machine itself is just a physical evaluator, casting those same logical rules into copper and silicon. So, if an evaluator is just a program, And hardware is just an evaluator made of sand and wire. Where exactly does the software end and the machine begin? That blur is the ultimate truth of computation. Is the computer even a real physical thing, or is it just the lowest level of language we happen to be speaking today? Maybe the cold mechanical factory floor was the illusion all along. Thank you for joining us on this deep drive into the architecture of thought itself.