Lisp

Lisp is a programming language originally created by John McCarthy in 1958. Despite its age, it is still a popular choice for modern programmers. Lisp has proven itself flexible enough to evolve to meet the needs of modern programmers. Modern implementations often come "batteries-included", meaning that the programmer has access to powerful libraries for databases, regular expressions, networking, and more.

Lisp comes in different dialects, which are divided into different implementations. Three important dialects are Common Lisp, Emacs Lisp, and Scheme. The name Lisp originally referred to one language but has come to be used as a generic term for all languages sharing its distinctive syntax.

Important Concepts

Evaluation

A Lisp program can be seen as the evaluation of Lisp forms, this occurs through a REPL (read evaluate print loop). A Lisp form is read from the programs input, evaluated, then printed. The most basic programs consist only of forms that evaluate themselves:

> 5
5
> "hello world"
"hello world"
> 6/4
3/2

Above we enter an integer, a string, and a rational number into the REPL (the inputs in these examples are written following a chevron (>)). These all evaluate themselves, and so return the values you would expect which are then printed out (outputs do not have the chevron). "6/4" is a rational number, which are defined as the simplest form of a fraction, so it is simplified to "3/2" before printing.

Lists

A list is delimited by parenthesis, the elements of a list are separated by whitespace. A list is evaluated by taking its first element and applying it as a function to the rest of the elements.

> (+ 1 2)
3
> (* 2 4)
8
> (+ 1 (* 2 3))
7

As you can see in the final example, a functions arguments are evaluated recursively before it is called. Functions may also produce lists; the simplest of these is "list":

> (list 1 (+ 1 2) "three")
(1 2 "three")

You may have noticed that final element of this list if of a different type to the first ones, this is because lists in Lisp are heterogeneous (the elements can be of different types).

Cons

Lists in Lisp aren't magic, they are actually built up out of cons cells. Cons is short for construct, a cons cell is just a pair of two values.

> (cons 1 2)
(1 . 3)
> (car (cons 1 3))
1
> (cdr (cons 1 3))
3

A cons cell is written as above, with the first part (the car) and the second part (cdr) separated by a dot. A list has two parts, the first element (car), and the rest of the list (cdr). The empty list is a primitive value (written as '()), like true or false in other languages.

> (car (list 1 2 3))
1
> (cdr (list 1 2 3))
(2 3)
> (cons 1 (cons 2 3))
(1 2 . 3)
> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)
> (cons 1 (list 2 3))
(1 2 3)

Special Forms

Some forms in Lisp aren't functions, yet still look like them.

> (if (= 1 2)
    (list 2 3)
    (list 1 3))
(1 3)

The "if" special form takes three arguments, the first is a test, then two clauses. First the test is evaluated, if it returns true, then the first clause is evaluated, otherwise the second is. We might read this as "if, then, else". In the case above "=" is the Lisp function to compare numbers, one does not equal two and so the list (1 3) is printed.

Quoting

Another special form is quote, it will simply return its argument unevaluated.

> (quote 1)
1
> (quote (+ 1 2))
(+ 1 2)
> '(1 . 2)
(1 . 2)

In the last example, we can see a shorthand for writing quote. Putting a single quote character (') before a list is the same as passing that list as an argument to quote. These sorts of shorthands are called "reader macros" and I will write quote like this from now on.

Symbols

It is of interest that in the example above we were able to quote the "+". This a new data-type that you may not have encountered before called a symbol. The functions we have called thus far have been represented by symbols, any of which can be quoted.

> 'list
list
> 'symbol
symbol
> '(symbol-1 symbol-2 symbol-3)
(symbol-1 symbol-2 symbol-3)

Symbols are not strings, they are usually represented by something closer to a hash of the string that they came from when they were read (read in this case refers to the read of "read, eval, print"). Because they are represented this way, they can be compared cheaply. Symbols are not variables. While a program is running it has a symbol table, which maps symbols to their values. When a symbol is evaluated, the value returned is the one stored in the table.

> list
#<procedure list>

This will output a different thing depending on which dialect of Lisp you are using. Some of the following examples assume that the dialect of Lisp being used is Scheme, as such they may not work in others.

Functions

In most Lisps, "lambda" is the constructor of anonymous (unnamed) functions (also called procedures). The first argument to lambda is a list of the arguments that the function will receive, the rest are forms that will be evaluated and returned form the function.

> (lambda (x)
    (* 2 x))
#<procedure>
> ((lambda (x) (+ 1 x)) 1)
2

A lambda can be used in place of a named function when evaluating lists, it is still applied in the same way though. The lambda has introduced lexical bindings. Lexical means that, instead of something like "list" which we can use anywhere in our code, this entries only work in the body of the lambda. The above lambda binds its arguments to the symbol "x", then evaluates it's body. Any value can be passed to a lambda, even symbols.

> ((lambda (x) x) 'foo)
foo

To evaluate a lambda as a function, each instance of a argument's name is replaced with the value passed to the lambda, then the body is evaluated. We can see through this that a program is a series of evaluations, until some primitive expression is reached that directly returns a value.

> ((lambda (x) (if (< x 4)
                 "less than 4"
                 "4 or greater"))
    8)
=> (if (< 8 4)
     "less than 4"
     "4 or greater")
=> (< 8 4)
=> "4 or greater" ; remember that if evaluates the form that is chosen
"4 or greater"

Any text following a semi-colon (;) is ignored by Lisp, these are known as comments.

Higher Order Functions

Even functions may be passed as arguments to functions; a function that operates on functions is known as a higher order function. One such function is map, it takes a function and a list, then returns the new list formed by applying that function to each element of the original list.

> (map (lambda (x) (* 2 x))
       '(1 2 3 4 5 6 7 8 9 10))
(2 4 6 8 10 12 14 16 18 20)

We may also create our own:

> ((lambda (f x) (f x))
    (lambda (y) (+ y 1))
    9)
=> ((lambda (y) (+ y 1)) 9)
=> (+ 9 1)
10

This is very awkward to read however.

Dynamic Binding

We have seen an example of lexical binding in the functions section (where a variable was not added to the symbol table, and was only valid in a function's body). Dynamic binding creates values that are globally valid, and can be achieved through define.

> (define x 3) ; Define is one of a number of functions that do not return anything.
> x
3
> (+ x 1)
4

This way we can name our functions, and improve the readability of our program.

> (define add-1 (lambda (x) (+ x 1)))
> (add-1 4)
5
> (map add-1 '(1 2))
(2 3)

It is convention to use hyphens (-) to separate words in variable names, as a space would cause a symbol to be split in two.

Recursion

Lisp is famous for its recursion (where a function is defined in terms of itself). This is possible as the symbol table is not consulted for a definition until a symbol is evaluated.

> (define return-x (lambda () x))
> (define x 4)
> (return-x)
4

Even though "x" wasn't defined when "return-x" was, it wasn't evaluated until "return-x" was called, so no error occurred. A function can therefore also call itself.

> (define recursive-function
    (lambda (x)
      (if (< x 3)
        (recursive-function (+ x 1))
        x)))
> (recursive-function 0)
=> (if (< 0 3)
     (recursive-function (+ 0 1))
     0)
=> (recursive-function 1)
=> (recursive-function 2)
=> (recursive-function 3)
3

I have elected for brevity to skip some intermediate evaluations and will continue to do so in future.

Dialects

Common Lisp

Common Lisp was designed by Scott Fahlman, Richard P. Gabriel, David Moon, Guy L. Steele, and Dan Weinreb, and is described in CLTL2, as well as the Common Lisp Hyperspec.

Popular implementations include Allegro Common Lisp, Steel Bank Common Lisp, GNU Clisp, ClozureCL, ECL, and LispWorks.

Emacs Lisp

Emacs Lisp (Elisp) is used to program and extend Emacs. Programmers who either use or are interested in using Emacs should learn Elisp.

A very good tutorial, as well as primary langugage documentation for Elisp is available from directly within Emacs. The introduction can by found by pressing C-h i then typing mEmacs Lisp Intro and pressing Return, and the language documentation can be found by typing mElisp instead. (the "m" tells Info that you are looking for a menu entry, and the rest is the title)

Scheme

Scheme, created by Guy L. Steele and Gerald Jay Sussman, is the dialect used in SICP.

Two of the most popular implementations are Chicken and GNU Guile, both of which are embeddable, and include a well-designed C API, and an FFI for interfacing with C libraries.

Niche Lisps

System scripting

• LUSH
• newLISP
• Picolisp
• scsh

CUDA & OpenCL

• Harlan

Programming language research

• GNU Epsilon
• Kernel (implementation here)
• Racket