[FoRK] Larry Masinter talk today: origins of Lisp at PARC & modern Medley

Gregory Alan Bolcer greg at bolcer.org
Thu Dec 17 21:39:10 PST 2020


The Idea of Lisp
Eric Normand
6-8 minutes

Cover image for The Idea of Lisp

LISP. It conjures up visions of a bygone age of computers the size of 
refrigerators, ALL CAPS CODE, and parentheses. Oh! so many parentheses! 
So why is Object-Oriented Programming's creator so enamored with the 
idea of Lisp? And what can he mean by a programming language being an 
idea anyway? Should I blame my Computer Science education for not 
teaching it to me?

Lisp was first introduced to the world in a paper called Recursive 
Functions of Symbolic Expressions and Their Interpretation by Machines, 
Part I, written by John McCarthy. In it, McCarthy introduces many new 
ideas to programming. Among them are conditional expressions (that's 
right, if/then/else) and using more than one letter--sometimes even 
words and phrases--for variables (like they still do in math). Your 
favorite programming language owes those two features to John McCarthy. 
But there is an even deeper idea lurking in the definition of Lisp itself.

John McCarthy

He defines 5 primitive operations (atom, eq, cons, car, and cdr) along 
with a conditional expression. It also assumes the ability to define 
functions. And then he uses those to define an entire programming 
language, defined in itself. Let me say that again: John McCarthy wrote 
6 easy things in machine code, then combined them to make a programming 
language. Before that, the only higher-level programming language was 
Fortran, which took 18 man-years to develop. Fortran was a big 
achievement, but Lisp was a big idea.

Let's unpack this tremendous idea a bit:
The bootstrapping material was very small.

These 6 things give you lists of symbols which can be interpreted. They 
define a very small "kernel" which can be easily ported to other 
systems. It is a small "fixed point" of agreement. All other meaning can 
be defined in terms of them.
The language was defined in terms of itself as an interpreter.

This is a proof by construction that the language is universal. The idea 
of Turing Completeness actually has two parts. The first is that you can 
compute anything computable. That one is satisfied by just about all 
programming languages (Lisp included since it has recursive functions). 
However, the second part is much more special. Turing Machines can be 
seen as universal when they can interpret any other Turing Machine. 
Well, Lisp is defined as an interpreter in terms of itself from the 
get-go, just like a Universal Turing Machine. Lisp is a universal 
language because it can interpret its own code. While you can certainly 
write a JavaScript interpreter in JavaScript, none of the work is done 
for you.
The meaning of expressions in the language is defined by the interpreter.

You could write your own interpreter that assigned different meanings to 
the expressions. This is Alan Kay's notion of "late binding". Since we 
don't know much about how to program well, it would be a mistake to 
build in too many assumptions into the base of the language. So we want 
a system that will allow us to swap out the assumptions as we learn more 
without having to throw it all away.
The expressions are written in data structures usable in the language.

The expressions are written as recursive linked lists. The 5 primitives 
are all you need to walk these data structures and interpret them.

Lispers have enjoyed working with this highly flexible "kernel", though 
most Lisp systems make practical compromises, like compiling the 
expressions to machine code instead of interpreting it each time. Here 
are some of the features of Lisp that follow directly from the Idea of Lisp.

Macros are functions that take code and return code. They are code 
transformers. They extend the expressiveness of the language and allow 
you to do computation at compile time.
Data-Driven Programming

Lispers often write their own interpreters in Lisp for new languages 
they create. They re-enact the bootstrapping of Lisp for their own 
languages. These can be seen as Domain-Specific Languages.
Programming language experimentation

Because it was made to write its own interpreter, Lisp is great for 
experimenting with alternative semantics for languages.

We're all too forgetful of the history of our field. The most 
significant languages in our industry are changed every so often. The 
new hot language will be gone in 15 years. But Lisp, the idea, endures. 
Its most promising incarnation at the moment is Clojure, which runs on 
the JVM and in JavaScript.

However, the ideas of Lisp actually live on in your favorite language:

REPL stands for Read-Eval-Print-Loop, which are the names of the four 
Lisp constructs that defined it. If your language has an interactive 
prompt where you can type in code and see it run, that comes from Lisp.
Recursive functions

Computer Scientists in 1960 knew that recursive functions were possible, 
but they thought they would be too expensive. Fortran, the other major 
language at the time, did not have recursive functions back then. Now 
recursive functions are table stakes.
Garbage collection

Lisp was the first language with garbage collection, mainly because the 
language created a lot of temporary objects and it ran for a long time.
Conditional expressions

Yes, John McCarthy invented the conditional expression. He lobbied the 
Algol committee to add them to Algol, from which most languages got them 
Multi-character variable names

I mentioned this before, but it bears repeating: programmers were 
following math's lead and using one-letter variable names before 
McCarthy came along.
Literal data structures

Can you write arrays and maps directly with syntax in your language? 
Well, Lisp did that first using parens ().

Here's the full quote from Alan Kay:

     Most people who graduate with CS degrees don’t understand the 
significance of Lisp. Lisp is the most important idea in computer science.

I didn't graduate with that significance. It took a lot of reading and 
exploration after university to feel like I had a proper education in 
Computer Science. I try to share what I'm learning in my newsletter. The 
more I read and learn, the more fascinated I am by the depth and breadth 
of what was done over forty years ago.

If you're interested in the big ideas in Computer Science, the history 
of programming, or Lisp, you should check out the PurelyFunctional.tv 
Newsletter. It's a weekly romp through the history, present, and future 
of Lisp and functional programming.

More information about the FoRK mailing list