Lisp is the red pill
This is the first article in a series about Lisp.
Lisp was the second programming language ever invented, right after Fortran in the late fifties. John McCarthy, one of the founders of the discipline of Artificial Intelligence, created it.
Lisp is a programmable programming language. What does that mean? It means that you can change Lisp (dynamically, even) to be what you want. So for example if you are writing a text editor, you can turn Lisp into a language for writing text editors. You will never find yourself wishing the language supported some feature that would make your life easier; you can just add the feature yourself.
Lisp achieves that by putting data and code at the same level: data can be used (evaluated, compiled) as code, and vice versa. Whereas C provides naive text-substitution macros and C++ provides brain-dead templates and template meta-programming weirdness, Lisp macros give you full access to the power of Lisp at compilation time. Basically you can tell the compiler “execute this code, and use the result as the code to be included in the program”.
Developing in Lisp is easy: you can use a REPL (read-eval-print loop) to play with your code as you write it. The story of the Deep Space 1 probe is an interesting anecdote about how useful a REPL can be: “Debugging a program running on a $100M piece of hardware that is 100 million miles away is an interesting experience”. Lisp can also be very fast, close to C-level performance according to some benchmarks. It had to be because it is so old (think about the kind of hardware they had in the sixties).
There has been countless dialects of Lisp in history. The ones that are relevant today are:
- Common Lisp: the ANSI standard, which has many implementations such as SBCL (Steel Bank Common Lisp, a high-performance native compiler). Common Lisp includes one the best object-oriented languages I’ve ever seen: CLOS (Common Lisp Object System).
- Scheme: a Lisp with a minimalist design philosophy. It is the programming language used in the textbook SICP. Guile and Racket are popular implementations.
- Emacs Lisp: unfortunately the worse Lisp out there. It uses dynamic binding2 by default, it is single-threaded, and it is super slow. The only good thing you can say about it is “well at least it’s a Lisp”. Finding a replacement is a hot topic today in the Emacs community.
The simplest way to get a taste of Lisp is just to fire up Emacs. There are two ways to interact with ELisp:
M-x ielm(inferior emacs lisp mode) gives you a REPL similar to say
C-DOWNto repeat commands you typed earlier. For example, try to evaluate
- You can use any ELisp buffer such as the scratch buffer.
C-jevaluates the lisp expression before the cursor and inserts the result where the cursor is.
M-C-xevaluates the current form and prints the result in the mini-buffer (also in messages). You can also use functions like
Give it a try: open the scratch buffer and type
"hello world". Then evaluate
M-C-x (meta control x): the mini-buffer should display the string. This
works because strings, like numbers, are objects that evaluate to themselves.
If you want a real hello world, type this and evaluate again3:
This is what Lisp calls a symbolic expression (s-expression or sexp). It calls
which is similar to C’s
printf). Lisp uses the Polish notation for function
calls; for example (1 + 2 + 3) * 5 is written in Lisp as
(* (+ 1 2 3) 5).
The mini-buffer should display the string “hello world” twice: one is the printed text and the other is the returned value, which is also the printed text. Every function returns a value which is normally the last form that was evaluated.
If you wanted the code above to return nil (which in ELisp and Common Lisp means void, false, and the empty list) you could do this:
progn is a bloc (list of sexp) which evaluates each form in sequence and
returns the value of the last form. It is named like that because of an other
prog1 which does the same thing but returns the value of the first
form. Run this code again with
M-C-x: the mini-buffer should display the
string that was printed and the return value nil.
That’s nice but our hello world should really be a function. So let’s define one:
defun is followed by the name of the function, the list of arguments (an
empty list here), an optional documentation string, and the forms. The body of
a function is an implicit
progn. Note that comments begin with a semicolon.
Working with Lists
The basic data structure in Lisp is a single-linked list. The syntax of a list
is exactly the same as a sexp. For example let’s declare a variable
containing a list of integers:
defvar is followed by a variable name and a value (and an optional
documentation string). Notice the quote character before the value: this is
syntactic sugar for
(quote (1 2 3)) which means “don’t evaluate this”. The
quote is needed because otherwise Lisp would try to call a function named “1”
with parameters 2 and 3.
If you wanted to use the result of a function call as value instead, you could
list function, which creates a list containing its arguments:
Here we don’t use the quote because we want the
list form to be
evaluated. There is no need to quote the numbers because a number evaluates to
l is a symbol, which is an object in memory with a unique name. A Symbol
has a name, and possibly a value, a function definition and a property
list. Our function
hello-world above is also a symbol; it has no value but it
has a function definition. There is a special kind of symbol called keyword
which has just a name and evaluates to itself; keywords start with a colon like
:foo (they are like interned strings).
The value of
l is a list containing 3 cells or cons (for construct), each
made of 2 pointers: a pointer to the value and a pointer to the next cell (or
car returns the value of the first pointer, and
cdr the value of
the second pointer (they are named like that for historical reasons4):
You can create a cons using the function that has the same name; its parameters are the car and the cdr.
The call to
cons returns a new list starting with 0 and pointing to the first
l. You can verify that
l2 share the same tail with function
eq, which returns
t (true) if its arguments are the same Lisp object:
Of course Lisp has plenty of functions to manipulate lists. Here is how to reverse our list:
setq sets a variable to a new value (set eq).
That’s it for today. Lots more to come. Stay tuned!
And almost OOP. Alan Kay, who invented Smalltalk and coined Object Oriented Programming, said that “Lisp is the greatest single programming language ever designed”. ↩
As opposed to lexical binding. If you define a local variable x in function foo and then call function bar, bar will see the value of x even if you don’t pass it as parameter. A long time ago people thought it was a good idea for performance reasons. ↩
If you make a mistake and end up in the debugger, just press q to exit. ↩
CAR and CDR were the names of two registers in the CPU of the IBM 704! Those were literally the name of 2 instructions: “contents of the address register” and “contents of the decrement register”. You can also use FIRST and REST if you prefer. ↩