The nesting doll

The parser from the last chapter turned a string into a tree of tuples, and five lines of recursion walked the tree and got eleven. That formula held only numbers and operators. A program holds more: names defined somewhere above, functions that call themselves, functions that are born inside other functions and carry off their variables. The tree of such a program is walked by recursion too, but on the way we have to decide where the values of names are kept, what happens during a call, and why a function remembers the place where it was made. A program that answers these questions and executes the tree is called an interpreter, and that is what we are going to write.

The chapter is built like a set of nesting dolls, a Russian matryoshka. The outer doll is Python. Inside it runs our Lisp interpreter. In that Lisp we will write another Lisp interpreter, and inside it we will run a small program, the factorial. Python isn’t the biggest doll either: its bytecode is executed by a program written in C, as we saw in Chapter 33, and that program’s machine instructions by the processor of Chapter 32. Each doll runs the one inside it and knows nothing about the one outside.

We will interpret Lisp rather than Python, and the reason is the parentheses. In the museum of languages we saw that a Lisp program is a ready-made tree: there is almost nothing to parse, so all our attention can go to meaning. And it all started with a paper whose interpreter nobody meant to run.

MIT, 1958–1960. A function for reading

We will follow Russell’s path, only in Python and not by hand. Then we will do what McCarthy started with and write eval in Lisp itself.

The first doll: reading

A Lisp program is nested parentheses with words and numbers inside. Its lexer fits in one line: put spaces around every parenthesis and split the text on spaces. The parser is recursive: on an opening parenthesis, read expressions until a closing one turns up and gather them into a list; anything else is a single word, a number or a name.

Press “Steps”: parse calls itself at every opening parenthesis and returns at the closing one, so the stack of calls mirrors the nesting of the parentheses. The tree is made of ordinary Python lists: ['+', 1, ['*', 2, 3]]. Numbers became numbers, while names, even + and define, stayed strings. An expression of this kind, either an atom or a list of such expressions, is called an S-expression, short for symbolic expression; these are the symbolic expressions in the title of McCarthy’s paper.

Compare it with the parser of Chapter 50. That grammar had several levels so that multiplication would bind tighter than addition. Here we have one function of a dozen-odd lines and no precedence at all. None is needed, because the parentheses have already settled every question of precedence: (+ 1 (* 2 3)) can’t be read two ways. The parentheses are the price Lisp pays for so short a parser.

The second doll: evaluating the tree

The rule for evaluating such a tree fits in three lines, and it holds all of Lisp except the special cases. A name: look up in a table what stands behind it. A number: it is its own value. A list: evaluate all its elements, then apply the first to the rest.

evaluate says nothing at all about addition. To the interpreter + is a name like pi, and its value is a Python function that adds. Our Lisp can’t do arithmetic on its own: it hands arithmetic to the doll outside, Python, and Python hands it to the processor. On the other hand, the first element of a list can be anything at all, as long as it evaluates to a function: the head of a call is evaluated by the same rule as the arguments.

evaluate does only two things. One is to evaluate an expression in an environment: eval. The other is to apply a function to arguments: apply. Evaluating a list requires applying, and applying a function written in Lisp itself will require evaluating its body. The authors of SICP (1985) draw the two as a ring, with the caption “The eval-apply cycle exposes the essence of a computer language.” Everything that follows is detail: what to evaluate, and where to look names up.

Special forms

The three-line rule doesn’t fit everything. Take a conditional. If if were a function, all its arguments would be evaluated before the call: the condition and both branches. But the branch that isn’t chosen must not be evaluated: it may divide by zero, or make a recursive call that never ends. The same goes for define: in (define r 10) the name r means nothing yet, so it can’t be evaluated, only recorded. And sometimes we want the list itself, unevaluated; that is what quote is for. Expressions that are evaluated by rules of their own instead of the general one are called special forms. Each one needs its own branch in the interpreter.

The output starts with the area of a circle of radius 10 and the word small; then comes the pair that quote exists for: (quote (+ 1 2)) is a list of three elements, while (+ 1 2) is the number 3. In Lisp, programs and data are written the same way, and quote switches between them. The last line crashes with a ZeroDivisionError, even though the condition (= r 0) is true and the answer should have been 0. The function if-function received its arguments already evaluated, and to get them, the interpreter divided one by zero. The special form if never got as far as the “no” branch.

Everything except False counts as true here, as in Scheme, the closest relative of our Lisp. Python is stricter about empty values: to it, 0 and the empty list are false too.

The third doll: where names live

With a single table of names the interpreter survives only until its first function. Here is where it trips:

When (square 3) is called, the name x has to mean 3. But the table already holds x = 10, and after the call it must still be ten. In Chapter 5 we saw how Python handles this: every call gets its own workbench, a frame that holds its variables. We will do the same. A frame is a dictionary of its own names plus a reference to the outer frame. To find a name, we look in our own frame, then in the outer one, then in the one outside that, and so on out to the global frame. The chain of frames in which names are looked up is called an environment.

Next come functions. The special form (lambda (x) (* x x)) computes nothing: it creates a function value that remembers three things, the parameters, the body, and the frame it was evaluated in. We met this construction in Chapter 10: a function together with the place where it was born is a closure. Back then we promised an interpreter in which functions are data, like numbers. Here it is. (define (square x) …) is shorthand for (define square (lambda (x) …)).

Calling a closure works like this: evaluate the arguments, create a new frame in which the parameters equal the arguments, and evaluate the body in it. There is one subtle point: which frame becomes the outer one for the new frame. In the code below it is the frame stored in the closure, f.env: the place where the function was born, not the place it was called from.

The first line of output is 9 and 10: inside the call x was three, outside it stayed ten. The second line is more interesting. make-adder was called twice, and each call created its own frame: in one k = 5, in the other k = 10. The calls ended long ago, but the frames are alive: the closures add5 and add10 refer to them, and when (add5 100) looks for k, the search goes from the new frame with n = 100 to the outer one, which holds the 5. A frame lives as long as something refers to it, not as long as the call lasts. The sourdough of Chapter 10 depended on the same thing: every counter had its own living frame.

Recursion came for free: define put count into the global frame, and the body, when it runs, finds the function there. The last line is a debt we will come back to two sections from now. Step through a few programs in the diagram and watch the frames grow and where their arrows point.

Lexical or dynamic

The line Env(f.params, args, f.env) is the biggest decision in the whole interpreter. It could have been written differently: Env(f.params, args, env), where env is the caller’s frame. A three-line program shows the difference:

The function show has no x of its own and looks for one in its outer frame. If the outer frame is the place where show was defined, it finds the global value. If the outer frame is the caller’s frame, it finds the x of test. The first rule is called lexical scope: what a function sees follows from the program text, from where the function is written. The second is dynamic: what it sees depends on who calls it and from where. In the environment diagram above, pick the program “whose x?” and flip the rule.

Today almost every language is lexical: Python, JavaScript, C, Java. Dynamic scope has survived in an odd place, the shell of Chapter 36, where variables declared inside a function with the word local are visible to every function it calls. Place your bet before you run it.

Dynamic scope is hard to read: to know what show will print, you have to know everyone who might call it. Lexical scope can be understood by looking at one function. This rule has a consequence you can use every day: a Python function sees the variables of the place where it is written, and sees them alive. A closure keeps the frame itself, not a copy of the values in it. That is why in the puzzle from Chapter 10 the three lambdas made in a loop all gave the same answer: they all hold one frame, where by the end of the loop i had become 2.

Recursion with no bottom

Time to pay the debt. (count 100) worked, and (count 1000) fell over with a RecursionError. Our evaluate is recursive: a Lisp function call is a call of evaluate on its body, inside that a call on the branch of the if, and inside that another one for the next call. Every Lisp call costs two Python frames, and Python, as we saw in Chapter 9, stops at a thousand. A binary search on n finds the border: (count 495) still gets through, (count 496) doesn’t.

But count has a peculiarity. Once it has called itself, it does nothing more: the result of the inner call is its own result. The frame waiting for the inner call to return waits in vain; all it has left to do is pass the answer up. A call after which the calling function has nothing left to do is called a tail call. And a frame that isn’t needed doesn’t have to be kept. Instead of calling evaluate recursively for the branch of an if or for a function body, we can swap in the new expression and environment and go around the loop again:

The condition (= n 0) and the arguments are still evaluated by recursion, because there is more work to do after them. The function body and the chosen branch are not, and for them the stack of Python calls doesn’t grow. (count 100000) runs in a fraction of a second.

Scheme ran tail calls without growing the stack from the start, in 1975, and later became the first Lisp to require it of every implementation, so Scheme programmers write their loops as recursion. Python doesn’t do this and has no plans to. In 2009 Guido van Rossum explained why on his blog. The short answer, he wrote, is that “it’s simply unpythonic”; the weightier reason is that tail recursion elimination “is incompatible with nice stack traces”: the frames it removes leave no trace in the traceback, and bugs become harder to find. Our interpreter pays the same price: if an error happens deep inside (count 100000), nobody will know on which call.

The whole interpreter

Here everything goes into one program, with a few conveniences added. The lexer now drops comments after ; and understands the quote mark: 'x is shorthand for (quote x). The atoms #t and #f become True and False. There are three more special forms: set! changes the value of a name in the frame where the name is found; begin evaluates expressions one after another; cond is a chain of conditions, like if … elif … else in Python. A function body may consist of several expressions, and its value is the value of the last. And a closure has learned to be called from Python like an ordinary function, so the built-in map and apply work with functions written in Lisp too.

Two hundred lines, and we have a language with numbers, lists, functions, closures, recursion and mutable state. The output shows the factorial of twenty; count making a hundred thousand calls without a single extra frame; a counter that remembers its n in the frame of make-counter; and map handed a lambda written in Lisp. Skip the last line for now: we will need it at the end of the chapter.

Read, eval, print, loop

An interpreter can do something a program translated in advance can’t: you can talk to it. Read a line, evaluate it, print the answer, wait for the next one. Read, eval, print, loop: the abbreviation REPL reads like the program itself, print(to_str(evaluate(parse(tokenize(input())), env))) in a loop. Python’s >>> prompt, the browser console, Jupyter notebooks are all REPLs. The name comes from Lisp. McCarthy credits L. Peter Deutsch with the first interactive Lisp, built for the PDP-1 in 1963, and the description of that system, published in 1964, names the loop outright: the “READ-EVAL-PRINT cycle.”

Below is a REPL for your Lisp. Every expression goes to the course server and is evaluated by the interpreter from the cell “lisp.py”. The server remembers nothing between runs, so each time the REPL replays the whole history of successful definitions; that is how your define survives to the next line. Change the cell, and the REPL will change with it: add, say, the line "sqrt": math.sqrt, to standard_env and ask for (sqrt 2).

Try to break it. (car '()) ends in a Python IndexError: our Lisp doesn’t check the arguments of built-in functions, so an error of the outer doll shows through from inside. (fact 1000) fails with a RecursionError: the multiplication after the call keeps it from being a tail call. But (define (fact2 n acc) (if (= n 0) acc (fact2 (- n 1) (* acc n)))) followed by (fact2 1000 1) gives a number with 2,568 digits.

A doll inside a doll: Lisp in Lisp

McCarthy started with eval written in Lisp itself, and that is our next step: we write it and run it inside our interpreter. The inner doll’s program is an S-expression, that is, a list, and Lisp knows how to take lists apart: car is the first element, cdr is all but the first, cons puts an element in front. The inner doll’s environment is a list of pairs ((name value) …), like the list a in the 1960 paper. A closure is a list (closure parameters body environment).

Read m-eval from top to bottom: it is our evaluate, retold in another language. A name is looked up in the environment, a number returns itself, quote hands back the list untouched, if picks a branch, lambda builds a closure, and everything else is a call: evaluate the head, evaluate the arguments with m-list, and pass them to m-apply. That function in turn either evaluates the closure’s body in an environment where the parameters are bound to the arguments (bind), or, if it is handed a built-in function of the outer doll, applies it on the spot. The special form label dates from the same 1960: McCarthy writes that Nathaniel Rochester invented it so that a nameless lambda could call itself. Our label makes a closure that knows its own name, and home adds that name to the environment on every call.

Load eval.lisp into the REPL with the “eval.lisp” button and ask the inner doll for a factorial:

The answer, 3628800, has passed through three interpreters. CPython runs the bytecode of our evaluate. evaluate runs m-eval. m-eval runs the factorial, which knows nothing about Python or about our evaluate. An interpreter written in the same language it runs is called metacircular. The circle lies in this: every feature of the language is defined through the same feature of the host: the inner doll’s if through the outer doll’s if, addition through addition. Lexical scope is another matter: the inner doll builds that itself. A closure carries its environment, as you can see in m-apply. Replace (home f) there with the caller’s environment (you will have to pass it to m-apply as an extra argument), and the inner Lisp turns dynamic, like McCarthy’s first Lisp.

Alan Kay, the creator of Smalltalk, told the magazine ACM Queue in a 2004 interview how, back in graduate school, he finally understood that the half page of code at the bottom of page 13 of the Lisp 1.5 manual was Lisp defined in itself. “These were ‘Maxwell’s Equations of Software!’” he said: the whole world of programming in a few lines he could cover with his hand. Maxwell’s four equations describe all of classical electrodynamics; in the same way, eval and apply say what any Lisp program means.

What a doll costs

Each doll runs the next one, and every doll has its price. One call of fib in Python takes a few tens of nanoseconds. In our Lisp the same call goes through evaluate: compare the head with "quote", "if", "cond"…, find the names by walking the chain of frames, create a dictionary for the new frame. The inner doll has it harder still: each of its actions is several Lisp function calls, and each of those is dozens of steps of evaluate. We can measure on the server what each layer costs.

On the course server, when this chapter was written, the numbers came out like this: a call of fib took about 0.02 microseconds in Python, about two in our Lisp, and about 160 in the inner doll. Each layer of interpretation costs nearly two orders of magnitude: our Lisp is eighty to a hundred times slower than Python, and Lisp in Lisp is slower than our Lisp by about as much again. Python itself, as we measured in Chapter 33, is tens of times slower than C. If the inner doll could run a copy of itself, a third doll would spend about ten milliseconds on a single call, and (fib 20), which Python finishes in half a millisecond, would take several minutes.

Cleaning up: mark and sweep

One more chore remains, and our interpreter gives it no thought at all. Every cons, every call, every frame takes up memory. The frame of make-adder with k = 5 is needed as long as add5 lives; the frames of count are useless by the next lap. In our interpreter Python frees them, with the reference counts and the cycle collector of Chapter 38. Russell, on the IBM 704, had no Python.

We can build Lisp’s memory ourselves. Say it consists of n cells with two fields each, car and cdr; a field holds a number, a name, the empty list, or a reference to another cell. Free cells sit in a list, and cons takes one from there. When no free cells are left, a collection starts, in two passes. Mark: from every variable of the program, follow the references and mark everything you can reach. Sweep: walk through the whole memory in order and return every unmarked cell to the free list. A collector of this kind is called mark and sweep, and the places where marking starts are called roots.

In the first line of output, memory is almost full: list a has taken cells 0–2, the loop of x and y cells 3 and 4, list b cells 5 and 6. We built the loop on purpose: the two cells refer to each other, but no variable points at them. After (set! a (cdr a)) cell 2, the one holding the 1, is needed by no one. List c needs three cells, only one is free, and on the second cons a collection begins. It returns cells 2, 3 and 4: the 1 and the whole loop. Reference counting would never find the loop: x and y have one reference each, from one another, and their counts will never drop to zero. Loops like this are the reason CPython backs up its reference counts with the collector we met in Chapter 38.

Before collecting, cons hands its arguments a and b to collect. Without that, the collector would free half of list c, which make_list is in the middle of building: no variable in roots points at it yet, and it is held only by the local variable x. That is why McCarthy marked everything reachable from the stack as well as from the variables: the roots are everything the program can still read. Forgetting a root is the worst mistake a collector can make: it frees live data, and the program breaks somewhere at random.

Mark and sweep has its own price. While a collection is running, the program stands still, and the more memory there is, the longer the pause; at McCarthy’s demonstration the collector, statistics and all, ate up the rest of the talk. That is why production collectors are cleverer. They break the collection into small portions interleaved with the program’s work, or they divide objects into generations: most objects die young, so most of the time it is enough to tidy up among the new ones. CPython’s cycle collector works by generations. But underneath, every one of them rests on the same idea from 1959: whatever can be reached from the roots is alive, and the rest is garbage.

Tasks

Six steps that build your own interpreter, from the lexer to tail calls. The tests feed each step ready-made tokens and trees, so you can take the steps in any order, and the starter code of the last two is the finished solution of the step before, so you can’t get stuck on one for good.

What next

The nesting doll is complete. Our evaluate, with its frames and closures, does to Lisp programs everything Python does to yours, and you have seen every line of it.

But remember the last line of the cell “lisp.py”: (fib 20) takes about a hundred times longer in our Lisp than in Python, and Python itself is tens of times slower than C. The time goes into the same questions, asked over and over. On each of the twenty-two thousand calls of fib, evaluate checks whether it is looking at a string, compares the head with "quote", "if", "cond", "define", "set!", "lambda", "begin", and looks up fib, n, < and - by walking the chain of frames. The tree of the body never changes, and neither do the answers, yet the interpreter asks again on every call. It behaves like the interpreter of Chapter 33, the person who translates the same sentence every time somebody says it.

Early Lisps, according to McCarthy, did numerical computations 10 to 100 times slower than FORTRAN, a language that was translated into machine instructions in advance. Could we read a program once, answer every question about its structure ahead of time, and translate it into machine code, so that afterward it runs on its own, with no interpreter at its side? In the next chapter we will write such a translator, a compiler, for Iskra-8, the computer you built out of gates in Part IV of the course.