Lisp

Lisp is a programming language originally created by John McCarthy in 1958. It is widely regarded as the second oldest high-level programming language and 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, Scheme, Clojure, and Racket. 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 function's 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). In Common Lisp and Emacs Lisp, 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.

Proper Tail Recursion

Tail recursive functions are functions where a tail call is used. A tail call happens when the function is called with a tail as its argument.

 > (define (list-sum list tail)
     (if (null? list)
         tail
         (list-sum (cdr list)
                 (+ tail (car list)))))
 > (list-sum '(1 2 3) 0)
 6

An advantage to this is that all Scheme implementations and most Common Lisp implementations will optimize this function so it takes less memory. Instead of calling itself multiple times which causes it to copy data over and over again, the function copies all the data once and simply changes it in place. Once it stops recursing, it returns the tail. This is equivalent to a while loop, but it's expressed using recursion. Usually, people don't define tail recursive functions, they define normal functions that call the tail recursive variant somewhere in a local scope, e.g. defining the function inside the other function in Scheme/Racket or LABELS/CL-LABELS in Common Lisp and Emacs Lisp respectively..

Homoiconicity

In Lisp, code is a first-class citizen. It means that you can control Lisp code using Lisp itself. Lisp is expressed using lists, and gives you many tools to modify and generate lists. Lisp is also known for having its READ, EVAL, and PRINT, which have no equivalent in most other languages. READ parses a string from a stream (usually stdin inside the REPL), and returns it as a Lisp object. Then, it returns the data as if it was a Lisp object.

 > (read)
 "string" ; this is my input
 "string"
 > (read)
 symbol ; this is also my input
 'symbol
 > (read)
 6/4 ; a fraction
 3/2
 > (read)
 (a list of symbols)
 '(a list of symbols)

PRINT is the opposite of READ. Instead of reading from a stream, it writes to it. It prints everything the same way it appears inside your source code, even strings have the quotation marks.

 > (print "string")
 "string"
 > (print 1)
 1
 > (print 'symbol)
 'symbol

EVAL evaluates the code. Any list can be evaluated as if it was Lisp code. For example, if you have a list '(+ 3 6), you can evaluate using EVAL:

 > (eval '(+ 3 6))
 9

When you EVAL a symbol, it returns the variable the symbol is bound to

 > (define x 3)
 > (eval 'x)
 3

EVAL is the opposite of QUOTE.

The difference between these and READ, EVAL, PRINT from other READ, EVAL, PRINT in other languages, is that Lisp's READ returns code, EVAL evaluates code, and PRINT prints code. In languages such as Ruby and Python READ, EVAL (or their equivalents) work on strings, and PRINT is completely separate from READ (i.e. if you modify READ, you won't see any changes in how PRINT works).

Macros

Code is lists, we can create and modify lists, and then evaluate them. So let's do this!

 > (define x 3)
 > (define (inc! var)
     (let ((code (list 'set! var
                             (list '+ 1 var))))
       (eval code)))
 > (inc! 'x)
 > x
 4

This is called a macro. It gets an input, generates a list, and then evaluates it. This created a

 '(set! x (+ 1 x)) 

list, and then evaluated it. Lisp macros are turing complete, and are defined in the language itself instead of a separate language (e.g. C preprocessor, C++ templates, Template Haskell, and others). Macros can recurse or loop, and can be of any complexity.

Compile-time Macros

At some point, people realized that quoting all arguments is inconvenient, and that all most of their code generation can be done in compile time. This has three major benefits: the program runs faster, it's safer because you don't use EVAL in runtime, the programmer can look at the expansion without evaluating the macro using MACROEXPAND. Compile-time macros are created using DEFMACRO. The macro above in DEFMACRO looks like this:

 > (require compatibility/defmacro)
 > (defmacro inc! (var) 
     (list 'set! var
                 (list '+ 1 var)))
 > (define x 5)
 > (inc! x)
 > x
 6

People usually don't use LIST inside macros, they use backquote (`) and unquote (,) reader macros, like this:

 > (defmacro inc! (var)
     `(set! ,var (+ 1 ,var)))
 > (inc! x)
 > x
 7

The backquote quotes the entire list and lets you choose which arguments to unquote by putting a comma before it. In this example, var is 'x, so it expands into

 (set! x (+ 1 x))

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 language 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