Concerning Lisp
by Kaveh Kardan

Introduction

This article is intended to be a quick overview of the Lisp family of languages, providing a glimpse into what makes the language different from other programming languages.

First of all, many people think that Lisp is for AI and only for AI. Questions of the form "How do you do AI with Lisp?" commonly pop on on discussion forums. Although historically the main use of Lisp in decades past was for AI research, you can do AI in other languages, and you can do other things (such as graphics, UI, scripting, databases) in Lisp.

Lisp is a computer language, much like other computer languages. Most of the language overlaps in functionality with "modern" languages such as C, C++, Python, and Java. What makes Lisp interesting are those features which set it apart from the other languages, and from which much of the attraction for (and disdain of) the language stem.

The Lisp Family

There are currently two main dialects of the Lisp language in use.

The first is Common Lisp, which is an industrial strength ANSI standard language with many powerful built-in features such as exceptions and object oriented facilities.

The second is Scheme, which is a small, very elegant, minimal language which in some ways is even more powerful than Common Lisp.

For simplicity's sake, we will use Scheme for our discussion and examples, though almost all we say will be equally applicable to Common Lisp.

Lisp And C

Much of the programming in Lisp involves the same sort of things one does in other languages:

C	Scheme
float double(float x) { return x * 2; }	(define (double x) (* x 2))
float func (float x) { if (x > 0) { return double(x); } else { return -x; } }	(define (func x) (if (> x 0) (double x) (- x)))
float pi = 3.1415926;	(define pi 3.1415926)

Example 1.

Anyone who knows how to program in C should be able to look at the Scheme examples above and understand what they do.

Let's look a bit closer at how the Scheme code differs from C:

Notice how there is no difference between the definition of a function and that of a global variable. Both use define. In fact, in Lisp there is no distinction between a statement and a procedure.
There are no type declarations in the Scheme code. Lisp is a dynamic language, which loosely put means that what is important is not what something is, but rather what it can do. If you pass a string in for x, you will get a runtime error, but an integer (or rational or complex number, both of which are standard Scheme types) will work fine.
The functions have no return statements. All expressions in Lisp have a value. The value of a function is simply the value of the last evaluated expression. C programmers are able to use this feature in limited cases, as the code fragment below shows:

C	Scheme
x +(y > 0 ? y : 2*y);	(+ x (if (> y 0) y (* 2 y)))

Example 2.

All the Lisp expressions are in prefix format. x + 2 in C becomes (+ x 2) in Lisp.
The code in Lisp consists of expressions, not a mixture of expressions and statements as in C. Even function definition and conditionals are expressions.
Every expression is enclosed in parentheses. We will see later why this is a good thing.

So how is Lisp different from C? What does it do that C does not? And what's up with all those parentheses anyway?

There are a number of ways in which Lisp differs from C:

It is a higher level language. By this, I mean that there is more between the language and the hardware than in C. You cannot access memory locations, cannot do pointer math, etc. Whether this is a good thing or a bad thing depends on what you are doing, and the type of programmer you are. In a nutshell, it means you can worry less about the hardware and concentrate on more abstract issues.
It handles memory allocation and garbage collection for you. There are no memory bugs or dangling pointers in Lisp.
Lisp has first class functions and closures. This means that a function can create and return another function on the fly.
Lisp has macros which go way beyond the string substitution macros of C. Macros in Lisp allow you to extend the language, as well as write whole new languages on top of Lisp.

The last two points merit more discussion, as they are what sets Lisp apart from most other languages. People who have never used these features do not realize their power, and therefore do not miss them when using other languages. Lisp programmers often immediately notice and rue the lack of these features when programming in other languages. The language you use shapes the way you think.

Closures

Lisp allows you to create new functions at runtime. For example, the following function takes a number and returns a new function which increments by that number:

(define (make-incrementor delta)
(lambda (x)
(+ x delta)))

Example 3.

The lambda creates an anonymous function (a function with no name). To use such a function at a later date, we can give it a name using define. The following session shows how we do this. The > is a prompt, and values returned by the computer are in bold.

> (define inc-by-2 (make-incrementor 2))
#<procedure inc-by-2>

> (inc-by-2 3)
5

Example 4.

There is a more direct way of doing this, if we only wish to use the function once:

> ((make-incrementor 2) 3)
5

Example 5.

Here's why the above example works:

Each expression in Lisp is a list enclosed in parentheses. When this list is evaluated by Lisp, each element of the list is evaluated recursively. The first element of the list is assumed to be a function, and is applied to the rest of the list as the arguments. In the above example, the first element of the list is itself a list, so it is evaluated and returns a function, which is then applied to the argument 3.

What is a closure, which we mentioned above? Notice that in Example 3, the definition of the anonymous function depends on the value of delta, which is passed in at runtime. What is returned by make-incrementor is a closure, which is a function along with the bindings it has captured from the environment at the time of its creation. This is what allows a different function to be returned for different values of delta.

Macros

Macros are very useful in C, and are used very frequently because they increase the expressive power of the language. But despite their usefulness, every C programmer has at one time or other wanted to do something using macros that was not possible, because what the C macros do is simple string substitution.

Lisp macros go way beyond that. Instead of using string substitution, they operate on expressions of code, and allow the use of all the power of the Lisp language itself in defining the macros.

Say we want to add a conditional unless to Lisp (actually, Common Lisp already has this). We can do it using a macro:

> (define-macro (unless test body else)
`(if (not ,test)
,body
,else))
#<macro unless>

> (unless (> 2 0)
(/ 1 0)
5)
5

> (macro-expand '(unless (> 2 0)
(/ 1 0)
5))
(if (not (> 2 0)
(/ 1 0)
5)

Example 6.

Don't worry about the syntactic details of the macro definition. What it does should be clear to experienced programmers. In effect, we can define a template for some code and fill it with values which are passed in at runtime. In this case, these values are the test condition, the code to execute if the test is true, and the code to execute otherwise.

We can in fact do much more that simply have a static template which we fill with values. Remember that all expressions in Lisp are enclosed in parentheses. In Lisp, things in parentheses are considered lists, which are data, just like any other data type in the language (vectors, strings, characters, etc.). What this means is very significant: the code is represented as data. This means that we can use the language itself to operate on lists (take them apart, build new lists) in order to generate the templates for macros. We can write code which generates code. This is why Lisp has all those parentheses. It is the complete uniformness of the language syntax which allows macros to be so powerful in Lisp. In effect, the code you write is already in a parse tree format, ready for processing by the language itself.

So how is the above macro different from a function? Why can't a function definition using define do the same thing?

Consider this: in Lisp, as in C, the code in the false branch of a conditional should not be executed. In the example above, this code is (/ 1 0), which would cause a division-by-zero error if it is executed. But remember than when Lisp evaluates an expression, it evaluates every element of the expression, so it would try to evaluate all the arguments of the unless expression if it were a function. But when Lisp encounters a macro, it passes the arguments to the macro without evaluating them! The entire expression returned by the macro is evaluated. In this case, that expression is an if expression, which means that the offending code is never evaluated due to the evaluation rules of if.

What we have done here is to extend our language with a new conditional construct. The important thing to realize is that this new conditional works exactly like the ones built into the language. This is something which is not possible in most other languages. This is why Lisp is referred to as a programmable programming language.

Discuss this article in the forums

Date this article was posted to GameDev.net: 6/21/2003
(Note that this date does not necessarily correspond to the date the article was written)