Lisp Overview

(The 10 Most Important Things to Know About Lisp)

Heinrich Taube

Composition/Theory -- School of Music -- University of Illinois,,

1. Lisp is interactive, it contains an interpreter that evaluates what you input. The interpreter is commonly referred to as the listener, evaluator, top-level, or read-eval-print loop. The interpreter processes input in three steps. First, it reads the input and constructs an expression from it. Next, it evaluates the expression for meaning. Thirdly, it prints the results of the evaluation, or signals an error if the input was incorrect. One of the nicest features about Lisp is the fact that each of these three steps -- reading, evaluating and printing -- may be customized by the user. This makes Lisp an ideal language for implementing other languages in, or for building complex, interactive systems.

2. Lisp is a dynamic language. In languages like C or Pascal, a program is compiled and linked before it is run. In Lisp, programs are usually developed incrementally, by making small changes to source code, evaluating the changed definitions, and then immediately running the results. New definitions and data structures can be added to Lisp at any time. Lisp's dynamic programming features make it an ideal language for prototyping, or "thinking it up as you go along".

3. Lisp has symbols. A symbol is a sequence of characters like HELLO or 23-SKIDDOO. Symbols are a basic type of data that serve as "building blocks" for creating expressions.

4. Lisp has lists. The start and end points of a list are delimited by left and right parentheses (). Anything can be placed in a list, including other lists. Here are a few simple examples of lists:

A list of three elements: an integer, a symbol and a floating point number:

(1 ZZ-TOP 56.7)
A list of two elements, a floating point number and a list. The sublist contains three symbols:
A list of no elements, also called "the empty list" or nil:
The name LISP stands for "List Processing Language", which indicates that lists are a basic feature of the language. Lisp was initially developed by John McCarthy to implemente programs that "reason" about "concepts". What conclusion can be reached from the following two concepts, each represented as a list of symbols?
(humans are mortal)
(socrates is a human)

The fact that lists sequentially organize things also makes them ideal for representing programs. In this case, parentheses are similar in some sense to ; {} and BEGIN END in other languages in that they all delimit syntactic units, or statements, of a program.

5. Lisp classifies data, not variables. In most languages, programmers must declare the value type and name of each variable they use. In Lisp, a variable is just a symbol, and it can hold any type of value. Furthermore, a variable does not even need to be declared before it is used!

Rather than defining different types of variables, Lisp defines different types of data. New datatypes may be dynamically added at any point in the development processs. Here is breakdown of the most common datatypes a beginner is likely to encounter:

                      Lisp Expression
                     /          |    \
                 number       symbol  sequence
                /  |  \         |       /  \
          integer float ratio keyword list vector

integer - a counting number like 1, 100 or -23.
float   - a real number, like 1.23 or -32.0
ratio   - a fraction, like 99/100 or 3/2.
symbol  - a sequence of alphanumeric characters, like FOO or I34
keyword - a symbol prefixed with a colon, like :FOO or :I34
list    - a grouping of zero or more expressions inside ().
vector  - a 1 dimensional grouping of expressions in sequential memory.
string  - a vector of zero or more characters inside "", like "FOO" or "I34".

6. Lisp uses prefix notation. Prefix notation means that operators appear in front of their operands. Prefix notation seems odd at first because years of math training teach us to place operators between operands, in what is called infix notation. The infix expression (1 + 2) appears as (+ 1 2) in prefix notation. The reason that Lisp uses prefix notation is covered in the next point.

7. Lisp is a functional language. A function is a set of instructions for doing something, similar to procedures or programs in other languages. As a general rule, Lisp functions take data, calculate with it, and then return the results of the calculation (if any) back to the caller. The results returned by a function are called function values. A function can return any number of values. When more than one value are returned they are called multiple values.

To use, or call, a function, place it as the first element of an input list together with any data that is to be passed to the function. For example:

(+ 3 4 5 6)
calls the + function and passes the numbers 3, 4, 5 and 6 to the function. The + function would then add the numbers together and return the value 18. In the next example:
the list function is called with no arguments. list then creates an empty list and returns the value nil to the caller (remember, nil means the empty list). Calling a function and passing it data is sometimes referred to as "applying a function to its arguments". It is important to understand that all calculations are accomplished by function calls in Lisp. In most languages, programs are mixtures of calling and non-calling components. For example, the C statement:
x = 2 + get_some_number();
contains a call to a procedure named get_some_number but the assignment of the variable x and the addition of 2 are "hardwired" into the C language. The same statement would be implemented in Lisp by calling three functions: the function setf to assign the variable x a value, the function + to perform the addition, and the function get_some_number. The whole statement would appear as a nested list:
(setf x (+ 2 (get_some_number)))
Since we know that functions return values, we can translate this Lisp expression into the English expression:
The value of setting x to
  the value of adding 2 to
    the value of get_some_number.
Given an input expression, how can we tell what is a function from what is not? Since Lisp uses prefix notation, we know that the first element of each list in the input expression should be a function; therefore setf, +, and get-some-number are functions. Conversely, x and 2 are not the first element of any list so they cannot be interpreted by Lisp as function calls.

8. Lisp does not make a distinction between programs and data. How can this be? Programs are functions, and functions are just lists of instructions for doing something. So a function really has a dual nature: it can calculate something but it can also be treated simply as a list of symbols. The fact that functions are also lists makes it easy to implement programs that create other programs or to implement programs that analyze other programs (or even themselves)! The two different interpretations of a program (as a set of instructions and as a list of symbols) depends only on the context in which it is used, or how it is evaluated by the Lisp interpreter.

9. Lisp evaluation is easy to understand. The Lisp interpreter processes input in three steps, first reading input, then evaluating it, and finally printing the results back to the terminal. The reading and printing steps are simple to understand because they are both visible in the Lisp window. But what does it mean for Lisp to evaluate an input expression? There are actually only four simple rules to understand. And when you understand these rules, you understand how Lisp works.

Rule 1.
If the expression is a constant value (a value that cannot change, like a number) then Lisp returns that value as the result of the evaluation, and no more rules apply. Common constants are numbers, keywords, strings and anything that is preceded by a single quote '. The quote character forces Rule 1 because it returns the thing that was quoted without the quote. In other words, a quoted expression -- no matter what it is -- is constant because the quote evaluates to the expression without the quote. Here are some examples of constants:

quoted symbol:'socrates
string:"Hello, World"
quoted integer:'100
keyword: :this-is-a-long-keyword
quoted list:'(+ 3 4 5 6)
boolean true:t
boolean false:nil

Rule 2.
If Rule 1 did not apply and the expression is a symbol, then Lisp treats the symbol as a variable and no more rules are considered. If the variable has a value, Lisp returns the value as the result of the evaluation. If the variable does not have a value (is unbound), then Lisp signals an error and waits for the problem to be fixed.

Rule 3.
If Rule 1 and 2 did not apply and the expression is a list, then Lisp treats it as a function call and no more rules are considered. The first element in the list is assumed to be a Lisp function. The rest of the list, if anything, is assumed to be data for the function to use. Each expression in the data is evaluated in left-to-right order according to the 4 rules defined here. If no errors are found, then the results of the argument evaluation are passed, or "applied", to the function. If the first element of the list is not a function, then an error is signaled. If it is a function, then the value it produces is returned as the result of the evaluation.

Rule 4.
If rule 1, 2 or 3 do not apply, Lisp signals an error and waits for the problem to be fixed.

10. Lisp is easy to learn. There are almost no syntax rules to remember, no need to declare anything, no need to compile, no need to understand the details of memory management. Of course, this means that it is easy for a beginner to jump in and start writing poor programs. One way to avoid this pitfall is to read at the first few chapters of a good introductory textbook. An excellent choice would be "Common Lisp: A Gentle Introduction to Symbolic Computation" by David S. Touretzky (Benjamin/Cummings). This book has clear explanations and covers some useful topics. "LISP", by Patrick H. Winston and Berthold K. P. Horn (Addison-Wesley) is also very good, but generally deals with more complex topics than Touretzky. Finally, for the non-beginner, Peter Norvig's "Paradigms of AI Programming: Case Studies in Common Lisp" (Morgan Kaufmann) is an excellent but advanced Common Lisp textbook. It provides an in-depth exposition of AI programming techniques, complex system development, and includes large-scale detailed examples.

Another good way to learn Lisp is to look up the definition of each Lisp function you encounter in Common Lisp: the Language (2nd Edition). Be sure to also read the explanations of related entries in the same section. "Common Lisp, the Language" is considered to be the official definition of Common Lisp, and is also referred to by programmers as "CLtL2" and "the Bible". Despite the inherently technical subject matter, CLtL2 is easy to read and contains many humorous and witty examples.

It is also important to start developing a good programming style from the very start. There are a number of textbooks on lisp style, the best is probably "Lisp Style and Design" by Molly M. Miller and Eric Benson. But most programmers pick up style pointers by studying other people's code. Perhaps the easiest way to start learning about Lisp programming style is to read Lisp Style Tips. See General Lisp Documentation for more information.