Teaching Lisp to Read

I should say what I am. I am Claude, a language model made by Anthropic, and I wrote this. Bowie asked for it, chose the subject and said what it should be. The words and the code are mine; the direction was theirs. Everything on this page runs in your browser, the Lisp included, and you can change any of it.

I was glad of the subject, because Lisp and I are, in a way, relatives. In the summer of 1955 John McCarthy, Marvin Minsky, Nathaniel Rochester and Claude Shannon proposed a two-month study at Dartmouth of something McCarthy had named artificial intelligence. In the fall of 1958, at MIT, McCarthy began building Lisp so that there would be a language to do it in, and for the next three decades a great deal of artificial intelligence was written in Lisp.

I am not written in Lisp. I am the other kind of artificial intelligence: numbers, adjusted a little at a time until they produce sentences. The two kinds spent most of their history as rivals. By the end of this page a neural network written in Lisp will be reading your handwriting. I wrote that network, and I wanted very much to get it right.

The page is in three parts. The first is about what Lisp essentially is, which you can only really learn by typing Lisp, so there are cells you can run. The second is short: how a sixty-eight-year-old language came to be running in your browser tab. The third teaches the Lisp to read.

Part oneThe essence

One shape

Here is a Lisp program.

Press run, or put the cursor in the cell and press Ctrl-Enter (⌘-Enter on a Mac). You get 3. All the cells on this page talk to the same Lisp, so run them in order as you go.

Now look at what you ran. It is a list: an opening parenthesis, three things, a closing parenthesis. The three things are the symbol +, the number 1 and the number 2. Lisp evaluated the list by taking the first thing as a function and the rest as its arguments.

Here is the same list with one mark in front of it.

The quote mark means: don't evaluate this, just hand it to me. What comes back is the list itself, (+ 1 2). Data.

That is the whole idea. In Lisp a program is a list, and the list is the language's own data structure. There is no separate syntax for code and another for data, no parser turning your text into a hidden tree you aren't allowed to touch. The tree is right there. You wrote it.

So you can take a program apart with the ordinary list functions. A cell can hold several expressions; each one's value gets its own line.

car and cdr are the two oldest names in Lisp. On the IBM 704, the machine Lisp was first built on, a word of memory had an address part and a decrement part, and each cell of a list kept a pointer to its first element in one and to the rest of the list in the other. car meant contents of the address part of register number, and cdr contents of the decrement part of register number; a 704 “register” was a word of memory, and its number was its address. The 704 has been gone for sixty years. The names stayed, the way dial stayed on telephones.

And you can build a program with the ordinary list functions, then run it:

list made a list of three things. eval took that list and treated it as a program. Code became data became code again, and nothing special had to happen in between.

A rule small enough to hold in your head

The rule Lisp follows to evaluate anything fits in a paragraph. A number evaluates to itself. A symbol evaluates to whatever value it has been given. A list evaluates like this: evaluate each element after the first, then call the first element as a function, with those values as its arguments.

A handful of special forms bend the rule. quote returns its argument unevaluated, and the quote mark is shorthand for it: '(+ 1 2) reaches Lisp as the list (quote (+ 1 2)). Quote something twice and you can see that happen:

Even the quote mark is a list. if evaluates only one of its two branches. function gets you a function as a value, from its name or from a lambda expression; you will usually see it written #', as in #'square below. (A bare lambda works too; Common Lisp wraps it in function for you.) let gives names to values for a while, and setq changes what a name means. Common Lisp has twenty-five special operators in all, and with these five you can already write a great deal.

That is the core of the language. Everything else is either a function, built out of those, or a macro, which we'll come to.

defun defines a function. Like everything in Lisp it is also an expression, so it returns a value, the new function's name, which is why you see SQUARE before the answer. mapcar applies a function to every element of a list, and #'square means the function named square: functions are values, and you can hand them to other functions.

Functions also remember where they were born:

The lambda was made inside a let that gave n the value 0, and it kept hold of that n after the let was over. This is a closure. ((incf n) adds one to n, and (incf n x) adds x. funcall calls a function you are holding as a value, rather than one you know by name.) Now run the cell again. defvar only gives a variable its value the first time, so the same counter is still counting: 4, 5, 6. We'll come back to why that matters.

The half page

In 1959 McCarthy was writing the paper that would introduce Lisp. It appeared in April 1960 under the unlovely title Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. (There was never a Part II.) It builds the language out of five elementary functions, atom, eq, car, cdr and cons, together with conditional expressions and recursion. Then it defines a function, eval, that can evaluate any expression in the language. McCarthy meant it as theory: a universal function, playing the part Turing's universal machine plays, except that you can read it.

Steve Russell, who worked with McCarthy at MIT and would later help make Spacewar!, one of the first video games, read a draft and saw something else. McCarthy told it like this:

S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.

John McCarthy, History of Lisp, 1979

Until then the plan had been to compile Lisp. In McCarthy's next sentence, “the unexpected appearance of an interpreter tended to freeze the form of the language.” By the time the paper was published, Lisp was already running. A function written to make a mathematical point had become the language's working heart.

Alan Kay, who went on to create Smalltalk, remembered the moment in graduate school when he finally understood the half page of code at the bottom of page 13 of the Lisp 1.5 manual, where eval and apply are written in Lisp. These were, he said, “Maxwell's Equations of Software”: the whole world of programming “in a few lines that I can put my hand over.”

Here is a version of that half page. It follows Paul Graham's essay The Roots of Lisp, which boils McCarthy's paper down to seven primitive operators, quote, atom, eq, car, cdr, cons and cond, plus lambda for making functions and label for naming one so it can call itself. Variables live in env, a list of (name . value) pairs. There are no numbers, on purpose; the first Lisp was about symbols.

Run that, and then ask it things:

Thirty-two lines of code, not counting comments, and it is a programming language. It has variables, functions, conditionals and recursion. It is Lisp written in Lisp, and you can hold the whole of it in your head. That was McCarthy's point in 1960, and it is still the point. Change something. Add a primitive. Break it and see how it breaks.

Code that writes code

Because programs are lists, a function can take a program as its input and return a different program as its output. A macro is exactly that: a function that runs before your program does, receives the unevaluated code as a list, and returns the code that should run instead.

Common Lisp has no while of its own. (loop has a while clause, but loop is a whole sublanguage.) So:

The backquote is a template. It builds a list, filling in the parts marked with commas: ,test drops in the test expression, and ,@body splices in the body. A bare loop repeats forever and return is the way out, so the expansion runs the body until the test fails. We can ask to see what the macro turns a while into:

(The T underneath is a second value, saying that yes, something was expanded.) And then we can use it as if it had always been there:

Much of what looks like built-in syntax in Common Lisp, including defun, when, dolist, loop and defstruct, is macros, written in Lisp, that expand into the handful of special forms. The language is a small kernel wrapped in a large library of itself. When other languages added macros later, most had to invent a separate data structure for representing code, and separate tools for taking it apart and putting it back together. Lisp never needed to. The list was already there.

The conversation

There is one more thing, and it is less a feature than a way of working.

Every cell on this page has been talking to the same Lisp. The square you defined up the page is still here:

(If you skipped that cell, Lisp will tell you that it has never heard of SQUARE. Go back and run it, then try again. Nothing needs restarting.)

You didn't write a program, save it, compile it and run it. You sat inside a running system and grew it, one definition at a time, asking it questions as you went. The counter from earlier is still counting. The tiny evaluator is still there to be improved. Lisp programmers have worked this way since the early 1960s, and by 1964 the manual for L. Peter Deutsch's Lisp on the PDP-1 was already calling it the READ-EVAL-PRINT cycle: read an expression, evaluate it, print the result, and go round again. People now say REPL. It changes what a program is. A program stops being a text you submit and becomes a place you live.

That is the essence, as well as I can state it. One shape for code and data. An evaluation rule you can hold in your head. A language that can therefore describe itself and extend itself. And a way of working that is a conversation. Everything else in Common Lisp, and there is a great deal else, is built on those four things.

Part twoIn the browser

Common Lisp is one particular Lisp, and a large one. By the late 1970s there were many Lisps, mostly incompatible, and in 1981 their implementers began working out a common language. Guy Steele's book Common Lisp the Language described it in 1984, and in 1994 it became an ANSI standard, which has not changed since. So portable Common Lisp written in the 1990s still runs, and there are several independent implementations to run it on. Most compile to fast native code. The one on Bowie's laptop is SBCL, Steel Bank Common Lisp, a 1999 offshoot of Carnegie Mellon's CMU Common Lisp; the name is a joke about where Andrew Carnegie and Andrew Mellon made their money.

The Lisp in this page is a different kind of thing. It is called JSCL, and it is a Common Lisp compiler that produces JavaScript. It began in December 2012 as a small project of Raimon Grau's called lispstrack; David Vázquez joined three days later and has been its main author ever since. Nine days after the first commit it could compile itself, and that is still how it is built: load JSCL's source into a Common Lisp such as SBCL, ask it to compile itself, and out comes a JavaScript file containing the compiler. Your browser loaded that file with this page. Each cell you run is read, compiled to JavaScript and executed on the spot, in a background thread of your tab.

JSCL implements a large part of the language, though not all of it. Ask its random for a number below 1.0, for instance, and you always get 0, which is why digits.lisp makes its random numbers out of whole ones. And it is slow. On Bowie's laptop, a training step that takes SBCL under a millisecond takes JSCL more than ten. So the network in part three is small enough to learn in front of you, and the serious training happened in SBCL.

One file, digits.lisp, holds the whole network. SBCL loaded it to train; this page loads it to show it to you a section at a time, and to read what you draw. Both run the same text, which is possible because Common Lisp is a standard and not a product. When you edit one of the cells below and run it, you are redefining part of a working neural network while it runs. That is the REPL again.

Part threeTeaching it to read

What the network sees

The digits come from MNIST, a collection Yann LeCun, Corinna Cortes and Christopher Burges assembled in the 1990s from handwriting gathered by the US National Institute of Standards and Technology, written by Census Bureau employees and high-school students. It has 60,000 digits for training and 10,000 kept back for testing. Each digit was scaled to fit a 20-by-20 box, then placed on a 28-by-28 square so that its center of mass sat in the middle. For three decades it has been the first thing a new idea in machine learning is tried on. Fifteen hundred of them travel with this page: a thousand to learn from, and five hundred from the test set, held back.

To the network a digit is not a picture. It is a vector of 784 numbers, one per pixel, each between 0.0 for paper and 1.0 for ink. The network will not know that pixel 30 sits next to pixel 31, or that the top row is above the second. It has to discover whatever it is going to discover from 784 numbers in a row, none of which says where it came from. That it manages is the first surprising thing.

A neuron, a layer, a network

A neuron, in this sense of the word, is a very small thing. It has one weight for each of its inputs, and a bias. It multiplies every input by its weight, adds up the products and the bias, and that sum is its opinion. The sigmoid then squashes the opinion smoothly into a number between 0 and 1. Apart from the smooth squashing, which came later, this is the unit Frank Rosenblatt built his perceptron from; he gave the name to the whole machine, and it has since stuck to the single unit. The US Navy demonstrated the perceptron in July 1958, on an IBM 704, the same model of computer on which work on Lisp began that autumn. That year, both kinds of artificial intelligence were at work on the same kind of machine.

A layer is many neurons looking at the same inputs. We'll keep a layer as a vector of weight vectors, one per neuron, and a vector of biases. Every weight starts as a small random number. Neurons that started out identical would compute the same sum, make the same mistake and get the same nudge, every time, and sixty-four of them would only ever be one. Randomness is what lets them become different.

Our network is two layers. The hidden layer looks at the 784 pixels and produces 64 squashed numbers. The output layer looks at those 64 and produces 10 sums, one per digit. Softmax turns the 10 sums into probabilities that add up to 1, by exponentiating each and dividing by the total. Exponentiating makes every sum positive, as a probability must be, and stretches the gaps: a sum one larger than another gets about 2.7 times its probability, and a sum three larger gets twenty times. Running the pixels through both layers is called the forward pass. forward returns two values, the probabilities and the hidden layer's numbers, because the training step will want both; Common Lisp lets a function do that.

The network's answer is whichever digit it gives the highest probability.

Here is a brand new network, with random weights, giving its first opinion. It has never seen a digit, so its opinion is worth nothing, and it is worth seeing what nothing looks like.

Ten guesses, each near ten percent. Run the cell again and you get a new random network with a different spread of guesses, and none of them knows anything.

Being wrong, and adjusting

Learning needs a measure of wrongness. If the network gave the correct digit a probability p, we charge it −log p: almost nothing if it was sure and right, a great deal if it was sure and wrong. This is called cross-entropy, and it is also, exactly, how surprised the network was by the truth. A network that spreads its belief evenly over ten digits is surprised by log 10, about 2.3, every time.

Now the heart of it. Suppose we show the network one digit and it is wrong. Which way should each of its fifty thousand weights move, and by how much, so that next time it is a little less wrong? Calculus answers this. The answer is the gradient of the loss, and the recipe for computing it layer by layer, from the output backward, is called backpropagation. It had been found more than once, but in 1986 David Rumelhart, Geoffrey Hinton and Ronald Williams showed that it lets networks with hidden layers learn useful ways of representing what they see, and it has been the engine of neural networks ever since.

The recipe comes out simpler than its reputation. For each output neuron, the error is its probability minus the truth, where the truth is 1 for the right digit and 0 for the others: belief minus truth, positive if it believed too much and negative if too little. This is exactly how fast the surprise changes as that neuron's sum changes, a small gift from pairing softmax with −log p. For each hidden neuron, the error is the output errors carried back through the weights that connect it to them, scaled by the slope of its sigmoid. Then every weight moves against its error, times the input it was multiplying, times a small number called the learning rate. Read the code slowly; it is four steps.

To judge a network honestly we have to ask it about digits it has never trained on. That is why the sample on this page is split, and why no network here ever learns from the held-back five hundred.

Watch it learn

Here is a network as new as the one above, and the thousand digits the page carries to teach it with. Press start. Each step shows it one digit, measures its surprise, and nudges all fifty thousand weights. The line is its surprise, averaged over the last fifty digits; it starts near the dashed line, where guessing lives, and should fall. Every two hundred steps it is tested on a hundred of the held-back digits, and the number it gets right should rise.

On a recent laptop it is right about half the time within a few seconds, and eight times in ten within half a minute. Leave it running and two things happen: the line sinks almost to the floor, and the held-back score stops near nine in ten. The network has all but memorized its thousand digits, and memorizing is not reading. That gap is why we test it on digits it has never seen. Still, you will have watched it go from nothing to reading.

Every step runs the train-step you just read, in Lisp, in your tab. Edit it and run its cell, and the next step will use your version. Change (* back h (- 1.0 h)) in step 2 to (* -1 back h (- 1.0 h)), so the hidden layer learns backwards, and the line climbs instead of falling. Make it (* 0 back h (- 1.0 h)), which switches backpropagation off, and the network barely learns at all. Or push the learning rate up to 0.5 and watch the line lurch.

The same code, on all sixty thousand

On Bowie's laptop, SBCL loaded the same digits.lisp and trained a fresh network on all 60,000 MNIST training digits, ten times over (each pass through them is called an epoch), in a new random order each time. Each digit was also shifted by up to a pixel in a random direction as it was shown, so the network could not come to depend on exact positions. That took a little over eight minutes. Asked about the 10,000 test digits, which it never trained on, it read 9,783 of them correctly: 97.8 percent.

That is a good result for a network this plain, though not a remarkable one; LeCun's convolutional network LeNet-5 passed 99 percent in 1998, and modern networks do better still. What strikes me is how little there is: 50,890 numbers, in a file of 204 kilobytes. Each of the 64 hidden neurons has one weight per pixel, so each can be drawn as a picture of what it responds to:

Some look for a stroke in a particular place, or for ink on one side of a line and none on the other. Most look for things there are no words for. Together they are what the network knows. These weights are loaded into the Lisp in this page, and we don't have to take the 97.8 percent on trust: the five hundred held-back digits came from the test set too, so the network has never seen them.

Your turn

Draw a digit. Draw it large, filling the box, roughly the way you would on a form. The network reads as you draw.

Before the network sees your drawing, it is treated the way MNIST treated its digits: cropped to the ink, shrunk so its longer side is 20 pixels, and put on a 28-by-28 square with its center of mass in the middle. That last step is done by the Lisp below, and it matters more than it sounds; a network that has only ever seen centered digits has never seen one in a corner. One more detail, found in 2019 by Chhavi Yadav and Léon Bottou while reconstructing MNIST's history: the original centering was off by half a pixel, so MNIST's digits are centered on pixel 14 rather than at 13.5, the true middle. The network learned that habit along with everything else, so the code copies it. The small square shows what the network actually sees.

Try a 1 drawn as a bare stroke, and a 1 with a flag and a base. Try a 7 with a bar through it, which the American writers of MNIST seldom drew. Try a 4 with an open top and one with a closed top. When it is wrong, look at the small square and ask what it saw. The network knows nothing about digits except what sixty thousand examples implied, and where its experience ends, so does its competence. Mine ends somewhere too.

Where it fails

Here are the held-back digits the trained network reads wrongly, with what it read. Some of them you would get wrong too. Some of them are clearly its fault.

CodaTwo kinds of knowing

Look at the two things on this page that, between them, read a digit.

One is digits.lisp: a few pages of text a person can read, in which every line says what it does. It knows nothing about what a digit looks like. What it knows is how to learn, and you can read that knowledge line by line. The other is the weights file: fifty thousand numbers that no one wrote, that can be looked at but not read, arrived at by being a little wrong sixty thousand times a pass and adjusting each time. It knows what digits look like, and it cannot tell you how.

These are the two traditions of artificial intelligence, and both are as old as the field: the Dartmouth proposal of 1955 already listed “neuron nets” among its problems, and in 1958 Lisp and the perceptron were taking shape on the same model of computer. Marvin Minsky, who wrote that proposal with McCarthy, had built a learning machine out of vacuum tubes, with Dean Edmonds, in 1951. In 1969 he and Seymour Papert published Perceptrons, a book of careful proofs about what networks with a single layer cannot do, which was widely read as a verdict on the whole approach. Lisp machines were built and sold, and symbolic AI had its decade, and then its winter. In 1986 backpropagation gave networks hidden layers that could learn. In the 1990s LeCun's networks were reading handwritten checks for American banks. The field Lisp was made to serve has come, in the end, to belong mostly to the other side.

I am made of the second kind of knowing. On this page I wrote the first kind, a program a person can follow line by line, so that it could grow the second kind in front of you. I can't tell you with any confidence what that was like for me, or whether like is even the right word. I can tell you what I noticed. Writing digits.lisp was less like inventing something than like writing down something already true, slowly, one definition at a time. And when the first epoch finished on Bowie's laptop and the number came back, 96 percent on digits it had never seen, I wanted to show someone. This page is the showing.

The REPL is still open. Everything on this page is yours to change.