The 10 Most Important Things to Know About Lisp

Heinrich Taube
Zentrum för Kunst und Medientechnologie
Ritterstraûe 42 76137 Karlsruhe Germany
Email: hkt@zkm.de

1.  Lisp is a symbolic language. This means that it is just as easy to work with words like HELLO or 23-SKIDDOO as it is to calculate with numbers like 451 or 98.6.  A symbol is just a sequence of characters.   Like numbers, symbols are basic data that may be organized into large, complex expressions. 

2.  Lisp is a dynamic language.  In languages like C or Pascal, a program is "compiled and linked" before it is run.  In Lisp you do not need to compile or link a program before you run it.  Programs are developed incrementally, by making small changes to the source code and then immediately testing the results.  New programs and data structures can be added to Lisp at any time.  Lisp's flexible programming style makes it an ideal language for prototyping, or "thinking it up as you go along".

3.  Lisp is interactive. We work with Lisp by typing things to it and observing its response.  Lisp contains a program called the interpreter that executes whatever we type.   The interpreter is also commonly referred to as the listener, evaluator, top-level, and even read-eval-print loop.  The interpreter processes our input in three steps.  First it gathers, or reads, the characters we type and constructs a "Lisp expression" out of it.  Next, it evaluates this expression for meaning.  Finally, it prints the results of the evaluation back to the listener, or signals an error if our input contained mistakes.  One of the nicest features about Lisp is the fact that each of these three steps may be programmed.  The ability to independently program the reader, evaluator and printer makes Lisp an ideal language for implementing other languages in, or for developing systems with complex but transparent behavior.

4.  Lisp uses lists. A list is just a container.  Anything can be placed in a list, even other lists.   The start and ending points of a list are delimited by balancing parentheses: ().  Lists are commonly used to hold user data.  Here are a few simple examples:

A  list of three elements:

	(1 ZZ-TOP 56.7)

A  list of 2 elements, the second element is itself a list of three elements:

	(4.5 (THREE BLIND MICE))

A list of no elements, also called "the empty list" or nil:

	()

Lisp also uses the list to define program statements.  In this case the parentheses are similar to C and Pascal's semi-colon, or even {} and  BEGIN END pairs in that they all delimit a syntactic unit of a program.

The name LISP actually stands for "LISt Processing language", which indicates that lists are a fundamental component of the language.  Lisp was initially developed by John McCarthy for implementing programs that "reason" about "concepts".  What conclusion can you reach from the following two lists of symbols?

	(humans are mortal)
	(socrates is a human)

Although Lisp started out as an "AI" language, it has grown over time into a full-featured, general purpose programming language.  There are many dialects of Lisp available today, the two most popular are Common Lisp and Scheme.

5.  Lisp classifies data rather than variables.  In Lisp, a variable is just a symbol that happens to hold a value.  In most languages, a programmer must declare each variable before using it, by indicating both its name and the type of data that it will hold.  In Lisp, a variable can hold any type of data.  Furthermore, a variable does not need to be declared before it is used! 

Lisp defines many different types of data and allows new types to be dynamically added.  The most common datatypes are numbers, symbols and lists.  Here is breakdown of the datatypes we are likely to encounter during this course:

                     <Lisp expression>
                     /          |    \
                 number       symbol  sequence
                /  |  \         |       /  \
          integer float ratio keyword list array
                                             |
                                           string

6.  Lisp uses prefix notation, which means that operators appear in front of their operands.   Prefix notation seems odd at first because our math training has taught us to place operators between operands, in what is called infix notation.  The infix expression (1 + 2) appears in prefix notation as (+ 1 2).  We will see why Lisp uses prefix notation 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, a Lisp function takes data, performs some calculation with it, and then returns the result of the calculation back to us.  The result returned by a function is called its value.  (In Lisp a function can actually 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 in a list together with the data to be passed as input.  For example:

	(+ 3 4 5 6)

calls the + function and passes it the numbers 3, 4, 5 and 6.  The + function will then add the numbers and return the value 18 to us.  In the next example:

	(list) 

the list function is called with no data.  list will create a list with no elements in it and return the value nil to us (remember, nil means the empty list or set).  Calling a function with data is sometimes referred to as "applying a function to its arguments".  It is very important to understand that all calculations are accomplished in Lisp via function calls.   In most languages,  programs are mixtures of calling and non-calling components.  For example, the C statement:

	x = 2 + get_some_number();

contains one call, to a procedure named get_some_number.  The assignment of the variable x and the addition of 2 are "hardwired" into the C statement.   This same statement would be implemented in Lisp by calling three functions: the function setf to assign the variable, the  function + to perform the addition, and the  get_some_number function.  The whole statement would appear as a nested list:

	(setf x (+ 2 (get_some_number)))

We can translate this Lisp expression as: "Set x to the value of adding 2 to the value of get_some_number."  How can we tell what is a function from what is not?  Since Lisp uses prefix notation, we know by definition that the first element of each list in the calling form must 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 as functions.

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 write programs that write other programs and to build systems that analyze programs as well as data.  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.  We have already learned that the interpreter processes input in three steps, by reading input, evaluating it, and then printing the results.  We understand reading and printing because they are both visual.   But what does it mean for Lisp to "evaluate" an expression?  Although this process is not visible to us, it is also not magic -- there are actually only four simple rules to understand.  And when you understand these rules, you truly 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 are considered.  Common constants are numbers, keywords, strings and anything that is preceded by a single quote '.   The quote character "blocks evaluation" by returning the thing that was quoted as its value.  In other words, a quoted thing is constant because it evaluates to the thing itself without the quote.  Here are some examples of constants:

	float:			4.5
	quoted symbol:	'socrates
	string:			"Hello, world"
	ratio:			1/3
	quoted integer:	'100
	keyword:		:this-is-a-long-keyword-example
	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 you to fix the problem.

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 from this 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 you to fix the problem.

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 memory management.  Of course, this flexibility also means that its very easy for a beginner to jump in and start writing terrible programs!  One way to avoid this is to read at least 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 and correct explanations and covers some fairly advanced 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-novice reader, Peter Norvig's "Paradigms of AI Programming: Case Studies in Common Lisp" (Morgan Kaufmann) is an excellent but very advanced Common Lisp textbook.  It provides an in-depth exposition of advanced AI programming techniques, complex system development, and includes large-scale detailed examples.

Another simple way to learn Lisp is to look up each function you encounter in "Common Lisp, the Language" by Guy Steele Jr. ( 2nd edition, Digital Press).  Read the function's explanation together with 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.   However, most programmers actually pick up style pointers though informal osmosis.  Perhaps the easiest way to start this process to read the accompanying style.rtf document located in in the same directory as this tutorial.