This is the text of a talk I gave at EnthusiastiCon 2019.

That language is an instrument of human reason, and not merely a medium for the expression of thought, is a truth generally admitted.

—George Boole¹

We use programming languages to solve problems. Very often, this means telling the computer to do something. But a programming language is more than a set of instructions. The abstractions provided by the language frame our problems and shape our solutions. A programming language offers us a way to think.

Recently, I wondered what it means to think in the language of Lisp. Lisp is not one language but a family of languages. In pursuit of this question, I found my way to the root of the Lisp family tree, to a paper by John McCarthy titled “Recursive Functions of Symbolic Expressions and Their Computation By Machine, part 1” That’s a long title for a short paper about a small language, LISP, developed for research at MIT.

McCarthy’s paper reminded me of Philip Guston’s cartoon paintings. Overlapping the work of McCarthy and Guston reveals a common pattern of thought, a way of thinking I believe to be Lisp. In that way of thinking, there are four ideas.

I. Write everything the same way

Guston had one way of painting. Hands, cars, cigarettes, brick walls, and books—regardless of the subject, Guston gave every form the same lumpiness. And regardless of the subject’s natural color, Guston predominantly used a fleshy pink.

When Guston painted an object, he did not paint from life. The cigarette in his painting could be any cigarette. It is not identifiable as the cigarette in his ashtray. Guston painted objects in the way that you and I write the letter “A”—just about the same way every time. Guston’s style, like handwriting, was a personal notation for what he wanted to say.

Notation was also one of McCarthy’s primary concerns. Programming languages often use different notations for different abstractions. Functions and for-loops tend to be written in different ways. But McCarthy gave all abstractions the same notation.

McCarthy’s notation is called a S(ymbolic)-expression. An S-expression is either an atom or a pair of S-expressions. An atom is a sequence of characters, including spaces.

FOO

FOO BAR BAZ

A pair is two S-expressions enclosed by parens and separated by a dot.

(FOO . BAR)

(FOO . (BAR . BAZ))

(((FOO . BAR) . BAZ) . QUX)

All LISP programs can be written with this notation. But McCarthy used a third notation for convenience. A list is many S-expressions separated by commas.

(FOO, BAR, BAZ)

(FOO . (BAR . (BAZ . NIL)))

Lists desugar to nested pairs terminated by the atom NIL. Everything in LISP is written as an atom or a list.

II. Start with just a few things

I must have done hundreds of paintings of shoes, books, hands, buildings, and cars, just everyday objects.

—Philip Guston²

Guston continually painted the same subjects but each painting is a new experience. Some are quiet. Some are strained. Some overflow with a sense of dread. Guston does not depend on new subjects for expressiveness. With the economy of a child learning to speak, Guston used a few subjects to say everything.

McCarthy designed LISP with the same economy. He had a notation for data but he wanted a language for computation. Instead of extending his notation, McCarthy gave S-expressions a double purpose.

An S-expression is both a data format like JSON or XML, and code for the LISP programming language. A LISP interpreter evaluates atoms and lists as computational expressions.

An atom is evaluated as a variable. A list of many S-expressions is evaluated as the application of an operator to its arguments. S-expressions are only evaluated as data, as literal atoms and lists, when they are wrapped in a QUOTE expression.

McCarthy’s LISP came with only a few operators built-in. First, there are operators for transforming S-expressions:

• ATOM: test if an S-expression is an atom
• EQ: test if two atoms are equal
• CONS: construct a pair
• CAR: get the first item in a pair
• CDR: get the second item in a pair

With these five operators, LISP begins to be a programming language. But McCarthy needed a general purpose abstraction, a way to compute anything. For this, McCarthy added anonymous functions.

A function is a list containing the atom LAMBDA, a list of function parameters, and any S-expression for the function body.

(LAMBDA, (X), X)

A function is applied to arguments just like any operator, by placing it first in a list.

((LAMBDA, (X), X), FOO)

McCarthy gave LISP functions two powerful properties. They can be passed as arguments to other functions and they can be defined recursively.

The λ-notation is inadequate for naming functions defined recursively.

—John McCarthy³

McCarthy recognized that recursive anonymous functions, while possible to write, are hard to read because the function doesn’t refer to itself directly. So McCarthy introduced the operator LABEL. LABEL binds an S-expression to a variable.

(LABEL, FOO, <S-expression>)

By binding a function to a variable, the function can be defined directly in terms of itself. Here is a function that calls itself infinitely.

(LABEL, LOOP,
  (LAMBDA, (X),
    (LOOP, X)))

Recursive functions had long been known to mathematicians. But mathematicians had no formal notation for describing conditions when recursion terminates.

So McCarthy invented the conditional expression. A conditional expression is a list of pairs. Each pair contains a proposition (an expression whose value is true or false) and a value to give if the proposition is true.

(COND, (<if>, <then>),
       (<else if>, <then>),
       (<else if>, <then>),
       ...)

The value of this conditional expression is (QUOTE, BAZ):

(COND, ((ATOM, (QUOTE, ())), (QUOTE, FOO)),
       ((ATOM, (QUOTE, BAR)), (QUOTE, BAZ))) 

With a way to define functions and less than a dozen operators, McCarthy’s LISP was complete.

III. Use those things to make a world

...when I leave the studio and get back to the house and think about what I did, then I like to think that I've left a world of people in the studio. A world of people. In fact they are more real than the world I see.

—Philip Guston⁴

Guston’s paintings are all filled with the same stuff and painted in the same way because they all refer to the same world. Sometimes this world feels familiar. We might recognize the hand’s grip on the cigarette, the bare lightbulb, the broken bed. But each of us would paint it differently. This is Guston’s world, a distillation of the reality he lived.

In what world does a programmer live? We build architectures. We situate our architectures in environments. But where do those architectures and environments exist? They exist within the world of the interpreter. The interpreter wraps around the architecture and the environment, enforcing the laws that govern everything within.

The culmination of McCarthy’s paper is a LISP program that evaluates LISP programs. In less than 30 lines, McCarthy defines two functions: EVAL and APPLY. These functions compute the value of any LISP expression. To show us the LISP language, McCarthy constructs the world of the LISP interpreter.

IV. Step into the world

They are self-portraits. I perceive myself as being behind the hood.

—Philip Guston⁵

As a young factory worker, Guston joined his coworkers on strike. When the Klu Klux Klan was hired to break the strike, Guston painted his experience. Those paintings were shown in a local coffee shop until they were found by the Klan and, in Guston’s words, “mutilated”.

During his cartoon period, Guston returned to that experience but this time, as a participant. Guston painted himself as a Klansman—making art, smoking cigarettes, driving around town. He did this in order to understand what it means to be evil. In a serious way, Guston went to live in the world he had constructed, not to escape life but to understand it.

McCarthy says nothing about stepping into self-constructed worlds. What McCarthy says is this: “The program APPLY has been imbedded in the LISP programming system…”⁶ The LISP interpreter can be invoked from within a LISP program. That has profound implications for how the programmer relates to the interpreter, to the world in which their programs exist.

We have a language that can transform its own source code; a language that is easily implemented in terms of itself; a language with direct access to the interpreter used by the underlying system.

McCarthy has given us everything we need to extend the language, to wrap the world of the LISP interpreter in the worlds of our own interpreters. We can change the semantics of the language. We can add and remove operators. We can fit the language to the problem at hand. We can make the world of LISP our world, a world that distills our reality just as Guston’s world distilled his.

Edited on June 2, 2019. The first version of this article incorrectly stated that the S-expression syntax for a list uses semicolons. Semicolons are used in the M-expression syntax. The S-expression syntax uses commas. The first version of this article incorrectly stated that a list of one atom substitutes the atom for its bound value. This claim has been removed.