Lisp: Tears of Joy, Part 2

I think that it’s extraordinarily important that we in computer science keep the fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while, we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don’t think we are. I think we’re responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don’t become missionaries. Don’t feel as if you’re a Bible salesman. The world has too many of those already. What you know about computing, other people will learn. Don’t feel as if the key to successful computing is only in your hands. What’s in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.

That quote by Alan J Perlis (the first recipient of the Turing Award) would resonate with those who read my previous scholarly article on Lisp, which, after all, is about having fun and stretching the capabilities of the computer and the programming language itself. One of the reasons Lisp does that is because it is designed to be extensible. Read on for more details.

There is no substitute for a good book while learning Lisp. Start with a free resource. I recommend the following resources that are available online:

• On Lisp by Paul Graham
• Practical Common Lisp by Peter Seibel
• Successful Lisp by David B Lamkins

The following text snippets are from Paul Graham’s website, which carry extracts of his books, On Lisp and ANSI Common Lisp.

Bottom-up programming

Lisp is designed to be extensible; it lets you define new operators yourself. This is possible because the Lisp language is made out of the same functions and macros as your own programs. So it’s no more difficult to extend Lisp than to write a program in it. In fact, it’s so easy (and so useful) that extending the language is standard practice. As you’re writing your program down toward the language, you build the language up toward your program. You work bottom-up, as well as top-down.

Almost any program can benefit from having the language tailored to suit its needs, but the more complex the program, the more valuable bottom-up programming becomes. A bottom-up program can be written as a series of layers, each one acting as a sort of programming language for the one above. TEX was one of the earliest programs to be written this way. You can write programs from the bottom-up in any language, but Lisp is by far the most natural vehicle for this style.

Bottom-up programming leads naturally to extensible software. If you take the principle of bottom-up programming all the way to the topmost layer of your program, then that layer becomes a programming language for the user. Because the idea of extensibility is so deeply rooted in Lisp, it makes for the ideal language to write extensible software.

Working bottom-up is also the best way to get reusable software. The essence of writing reusable software is to separate the general from the specific; bottom-up programming inherently creates such a separation. Instead of devoting all your efforts towards writing a single, monolithic application, you devote part of your effort to building a language, and part to writing a (proportionately smaller) application on top of it. What’s specific to this application will be concentrated in the topmost layer. The layers beneath will form a language for writing applications like this one — and what could be more reusable than a programming language?

Rapid prototyping

Lisp allows you to not just write more sophisticated programs, but to write them faster. Lisp programs tend to be short — the language gives you bigger concepts, so you don’t have to use as many. As Frederick Brooks (best known for his book The Mythical Man-Month) has pointed out, the time it takes to write a program depends mostly on its length. So this fact alone means that Lisp programs take less time to write. The effect is amplified by Lisp’s dynamic character: in Lisp, the edit-compile-test cycle is so short that programming happens in real-time.

Bigger abstractions, and an iterative environment, can change the way organisations develop software. The phrase “rapid prototyping” describes a kind of programming that began with Lisp — in Lisp, you can often write a prototype in less time than it would take to write the spec for one. What’s more, such a prototype can be so abstract that it makes a better spec than one written in English. And Lisp allows you to make a smooth transition from prototype to production software. When Common Lisp programs are written with an eye for speed and compiled by modern compilers, they run as fast as programs written in any other high-level language.

All of this obviously means that you can now spend less time working, and finally take your family out for that dinner you’ve been promising them, for the last three years — happy boss, happy family.

Questions answered, and a response to cynical feedback

I received many questions about the Lisp programming language after the first article was published in the June 2011 edition of LINUX For You. Fortunately, David B Lamkins, author of the book Successful Lisp, has provided comprehensive answers to most of these questions here. The questions he answers are:

1. I looked at Lisp earlier, and didn’t understand it.
2. I can’t see the program for the parentheses.
3. Lisp is very slow compared to my favourite language.
4. No one else writes programs in Lisp.
5. Lisp doesn’t let me use graphical interfaces.
6. I can’t call other people’s code from Lisp.
7. Lisp’s garbage collector causes unpredictable pauses when my program runs.
8. Lisp is a huge language.
9. Lisp is only for artificial intelligence research.
10. Lisp doesn’t have any good programming tools.
11. Lisp uses too much memory.
12. Lisp uses too much disk space.
13. I can’t find a good Lisp compiler.

Leave a comment if you couldn’t locate the answer to your question in the link provided, or were unsatisfied with the quality or quantum of information presented, and I will try to respond with the profound knowledge locked up in my highly-evolved brain.

A riveting quality of my mind is that that it spontaneously goes into a meditative state half-way through a negative feedback, and instantly rejects the hypothesis that I may be too dumb to understand that I am a bad writer. My superior brain and eyes then work in sync to dismiss any dissenting remarks or profanities. This enables me to rant on with the technical mumbo-jumbo that you now hold in your hand. If you sent negative feedback about my previous article to the editor, and did not receive a reply, you now know why!

Getting acquainted

Lisp, whose name is an acronym for LISt Processing, was designed to provide symbol-manipulating capabilities to attack programming problems such as symbolic differentiation and the integration of algebraic expressions. Despite its inception as a mathematical formalism, Lisp is a practical programming language.

The basic elements of Lisp include its primary data structure, called the s-expression. This also includes the Lisp interpreter, which is the heart of any Lisp system, and is basically a machine that carries out processes described in the Lisp language. The Lisp interpreter performs computations on s-expressions through a process called evaluation.

Since its earliest days, Lisp implementations have been variously interpreted or compiled, and often both. No modern commercial version of Lisp is without a compiler. The fact that modern Lisp variants often come with an interpreter as well, is simply a convenience for some implementations, to encourage late-binding semantics and promote flexibility, including interactive debugging.

The prompt

I assume that you have CLISP on your machine (please read Part I for instructions on how to install and use CLISP). The exact command to start a Lisp process may vary from one OS to another.

Any Lisp system will include an interactive front-end called the toplevel. You type Lisp expressions into the toplevel, and the system displays their values. Lisp usually displays a prompt to tell you that it is waiting for you to type something. Many implementations of Common Lisp use > (the “greater-than” symbol) as the toplevel prompt; some may use an entirely different prompt, and others may issue no prompts at all.

S-expressions

A Lisp command begins with a parenthesis. Next, specify the name of an operation that you would like to perform. Then give the arguments you want to use. Finish the whole thing off with a final parenthesis. For example, if you want to add two numbers together, type something like the following code:

> (+ 1 2)
3

In this example, you only typed the expression in parenthesis; the prompt and the answer were output by Lisp. In many implementations of Lisp, the user types a carriage return to signal that the command is complete. Other implementations will go to work as soon as they see the closing parenthesis. Also, some implementations will output additional blank lines along with the result.

In the expression (+ 1 2), the + is called the addition operator, and the numbers 1 and 2 are called the arguments. In other programming language(s), this expression would be writen as 1 + 2, but in Lisp the + operator is put first, followed by the arguments, with the whole expression enclosed in a pair of parenthesis. This is called prefix notation, because the operator comes first.

Lisp’s prefix notation offers convenience to programmers. For example, if you want to add five numbers together, in ordinary notation (and programming language) you have to use + four times:

1 + 2 + 3 + 4 + 5

…while in Lisp, you just add other arguments:

> (+ 1 2 3 4 5)
15

Commands like these are called s-expressions, which stands for symbolic expressions. This is a very general term, applicable to just about anything one can say in Lisp.

The basic elements of s-expressions are lists and atoms. Lists are delimited by parentheses, and can contain any number of elements separated by white-space. Atoms are everything else. The elements of lists are themselves s-expressions (in other words, atoms or nested lists). More about lists and atoms will follow in the next article.

Comments — which, technically speaking, are not s-expressions — start with a semi-colon, extend to the end of a line, and are essentially treated like white-space.

> ;demo of multiplication operator
(* 3 7)
21

Because operators can take a varying number of arguments, we need parentheses to show where an expression begins and ends. Expressions can be nested — that is, the arguments in an expression may themselves be complex expressions.

Suppose you want to compute the value of ((4*5)/(2+3)), then the equivalent s-expression in Lisp will be:

> (/ (* 4 5) (+ 2 3))
4

Evaluation

Lisp evaluates everything. It even evaluates its arguments. In Lisp, numbers evaluate to themselves — that is, any time Lisp tries to evaluate 1, the answer is always 1.

> 1
1
> 2
2

In Lisp, + is a function, and an expression like (+ 1 2) is a function call. When Lisp evaluates a function call, it does so in two steps:

1. First, the arguments are evaluated, from left to right. In the case of (+ 1 2), each argument evaluates to itself, so the values of the arguments are 1 and 2, respectively.
2. The values of the arguments are passed to the function named by the operator. In this case, it is the + function, which returns 5.

If any of the arguments are themselves function calls, they are evaluated according to the same rules. So when (/ (* 4 5) (+ 2 3)) is evaluated, this is what happens:

1. Lisp evaluates (* 4 5): 4 evaluates to 4 and 5 evaluates to 5. These values are passed to the function *, which returns 20.
2. Lisp evaluates (+ 2 3): 2 evaluates to 2 and 3 evaluates to 3. These values are passed to the function +, which returns 5.
3. The values 20 and 5 are sent to the function /, which returns 4.

Not all the operators in Common Lisp are functions, but most are. And function calls are always evaluated this way. The arguments are evaluated left-to-right, and their values are passed to the function, which returns the value of the expression as a whole. This is called the evaluation rule for Common Lisp.

Lisp is somewhat unusual in that virtually everything gets done by executing a function. In fact, there is really no more to Lisp than that. All the complexity of Lisp comes from the particular functions Lisp provides, and the details of how various types of functions are treated by the interpreter.

Call 911!!!

If you type something that Lisp can’t understand, it will display an error message and put you into a program called a debugger.

The ordinary Lisp debugger provides the ability to suspend evaluation of a form. While the evaluation is suspended (a state commonly known as a break loop), you may examine the run-time stack, check the values of local or global variables, or change those values.

The exact nature of the debugger is not part of Common Lisp, per se. Rather, this is left to the creators of various Common Lisp implementations. For example, there is no Common Lisp standard specifying the nature of the prompt to be displayed after an error. Nor is there standardisation of the commands the debugger will accept. In some implementations, the user normally does not type a command at all; rather, a special key is reserved just for this purpose.

In CLISP, to get out of the break loop and get back to the toplevel, just type :q as shown below:

[1]> (/ 1 0)

*** - /: division by zero
The following restarts are available:
ABORT         :R1        Abort main loop
Break 1 [2]> :q
[3]>

You must determine how the equivalent of :q has been realised in your local Lisp implementation. Experiment, check the implementation manual, or consult a local expert.

What next?

All the X-Men (movie) fans out there will agree with me when I say that the latest addition to the series — X Men First Class — has been the best yet. What could be better than learning about the origins of characters and a story line you have come to love. This, in fact, seems to be a trend in Hollywood, with movies like Star Wars, the Batman series, etc.

I am going to follow that trend, and in my third article, give you a glimpse of the evolution of Lisp. The modest beginnings of the language you have now started to love (if you are still reading this, you probably have — or is it just my charming self you cannot get enough of?!).

I will also pick up the pace, as we have barely scratched the surface of Lisp. After all, plans for world domination are never fun if they take forever!