Over the next months I'll be looking at Lisp, Common Lisp, and recent developments in Lisp programming that make the language an interesting option for professional programmers. This month, I'll prepare the ground by taking a look at Lisp in general, debunking some myths, giving a sense of what it's like to program in Lisp, and sketching the history of the language, leading to the establishment of the Common Lisp standard.
One of the programming paradigms I wanted to explore when I conceived this column was interactive recursive function-based list processing: Lisp. Learning Lisp back in the 1970s was a revelation for me, opening my eyes to the arbitrariness of the Fortran/Basic/Pascal approach I had naively thought was the one true methodology of programming. Lisp was really a different paradigm, requiring a different way of thinking about problems, and embodying different ideas about the value of memory and time.
That reference to the value of memory and time was intended to be only partially ironic. Lisp implementations of the 1970s generally were written by people who believed that memory was cheap and was getting cheaper, and who valued development flexibility over execution speed -- these were implementations that ate cycles and RAM. But there is time and there is time. While the Lisp systems of the 1970s were not generally fast number crunchers, they were demonstrably good for developing highly-complex applications, and some Lisp-based numeric applications of this era probably could not have been developed in, say, Fortran in any acceptable span of time. Lisp became the language of choice for artificial intelligence work, but for years, as a result of execution-time slowness, memory hungriness, and a proliferation of incompatible dialects, it could not be considered seriously for commercial applications. Recent developments, though, have made Lisp a language worth any serious programmer's attention.
One of these is the increasing power of personal computers. With brief exceptions, memory has indeed continued getting cheaper, and systems have been getting faster and more powerful. Another development is the work that has gone into creating efficient Lisp implementations. Some of this work has been tied to specific hardware, but progress has also been made in Lisp implementations on standard hardware. Together, these developments have been whittling away at the stumbling blocks between Lisp and the non-academic programmer.
But arguably the most important event in Lisp's history is the definition and acceptance of the Common Lisp standard, which has probably saved the life of the language.
This is a good thing, because there is a whole list of problems for which Lisp is the best language in existence. I'm pretty sure there is, anyway, although I couldn't prove it; probably nobody could. Wade Hennessey, in his book Common Lisp (McGraw-Hill, 1989), runs down the somewhat longer list of problem areas in which, for some people at least, Lisp is the language of choice. His claim is a provable and correct version of my unprovable assertion. His list includes: Emulating human vision, doing symbolic algebra, developing special-purpose languages, exploring natural language understanding, theorem proving, planning complex actions, computer-aided design, programmer education, and even writing text editors (such as Gnuemacs)and doing system programming (at least on Lisp machines).
Pulling together a standard for Lisp after 20 years of divergent development was a little like gathering the scattered energy of the Big Bang. Guy Steele found a better simile. He prefaces his definitive Common Lisp: The Language (Digital Press, 1984) with a James Madison quotation from The Federalist about the difficulty of hammering out consensus on the Constitution. It took a kind of electronic Constitutional Convention to unite the rebel colonies of Lisp development.
Lisp had grown, after its creation around 1960 by John McCarthy, in many directions, the most important in the 1970s being the MacLisp, InterLisp, and Scheme dialects. By 1980, Scheme had begotten T, MacLisp had inspired NIL and Franz Lisp, special purpose hardware had given the world Zetalisp and others, and the needs of university researchers had produced SpiceLisp and the wistfully-named Portable Standard Lisp (PSL). Common Lisp was the compromise dialect designed in the early 1980s to be palatable to as many Lisp developers as possible. Common Lisp is not the collection of features that the above-mentioned dialects have in common, as the name might suggest. It is much more a union of features than an intersection.
One of the areas into which Common Lisp extends Lisp is object-oriented programming, particularly with CLOS, the Common Lisp Object System, aka Thmalltalk, about which we'll hear more next month.
Some of these characterizations will not seem true of, say, CLOS, but what I'm describing here is the core to which things such as CLOS are extensions.
Lisp is recursive. Is it ever. Data structures and functions are routinely defined through recursion. The professor from whom I learned Lisp told a lot of lies, such as that all of Lisp could be constructed by recursive definitions using just five primitive functions. It's a good lie, because it suggests the degree to which Lisp depends on recursion.
Lisp is function-based. Programming in Lisp is a matter of expressing a problem as a composition of functions. To write a program, you define a function, and the definition consists primarily of function calls, with some scaffolding. (You need a little more than five primitive functions, and not all functions are defined recursively.) Values passed to functions are typically the values returned by other functions, although functions themselves can be passed, just as other data can. The same professor taught that no Lisp function should take more than five lines to write, another useflie that gives a sense of how the functional style works: "pure" Lisp programming makes less use of structuring tools than Pascal programming, using the function as almost the only structure.
Lisp is LISt Processing. A Lisp program is a list, and the list is the fundamental data structure of Lisp. The obvious implication of these two statements is that Lisp programs are Lisp data, and this is in fact a defining feature of the language. It makes it easy for one program to read, create, or execute other programs. It's the source of the great extensibility of the language, which is in turn the source of the plethora of idiosyncratic versions that sprang up and led to a crisis in compatibility, and then to a kind of Continental Congress of Lisp developers in response to the crisis, and ultimately to Common Lisp.
Lisp is interactive. There have been Lisp compilers for a long time, but the interpreter is central to any implementation -- for several reasons. Lisp was originally designed to be a language in which probably correct programs could be written, but probability constraints tend to be loosened in the tricks that have to be played to generate efficient compiled code from a Lisp system. Moreover, the kinds of problems to which Lisp is typically applied require a lot of exploratory programming that also makes the interpreter necessary.
The style of interaction is not command action, however, but function call. Because even the main program is a function, invoking a Lisp program is usually a different process from invoking a Pascal program. To invoke a Lisp program, you call the function with appropriate arguments, and it returns a value. The argument list can be empty, in which case calling the function feels more like invoking a Pascal program. Rather than supply the input to a function as parameters, you can write an "Input" function that conducts a dialog with the user to get the input. The value returned can be an arbitrarily complex object, and the function can produce side effects.
So to perform a computation and then print the results in a table, you could write a computational function ComputeValues, an input function GetValues, and an output function PrintTable. PrintTable would produce its output as a side effect. You could then perform this function call:
Lisp has a reputation. Some of it isn't deserved.
Lisp is not an AI language. It is, however, the premiere language for artificial intelligence programming. Its virtues for AI programming include, but are not restricted to, the ability to manipulate programs as data, which makes it good for symbolic processing of the sort done in symbolic Algebra programs; and its interactive style, which facilitates exploratory programming and prototyping. These virtues are themselves not restricted to the domain of artificial intelligence.
Lisp isn't inherently slow. It has been a prevailing attitude in the Lisp community that performance is not very important, and that's changed, as I hope to show next month.
Lisp isn't a memory hog. There's nothing inherent in Lisp that makes it a memory hog, although past implementations have often been wasteful of memory. The problems to which Lisp is characteristically applied (see Hennessey's list a few paragraphs back) are a different matter. Some of them do require a lot of memory, no matter what language is used to solve them.
Here's an example that is basically accurate, although it glosses over some complexities.
You define the function using defun, which takes three arguments: A string representing the name of the function to be defined, a list of its arguments, and a list that is a function call. This last list is the body of the function being defined. For example:
Here's a recursive definition of a function that, given a nonnegative integer n, returns 2 to the nth power:
The name of the function is power-of-two, it takes one argument, n, and the body of the definition is
This expression consists of the function (actually a macro) cond applied to two arguments. The arguments are
cond is short for conditional, and it takes any number of two-item lists as arguments, returning the last item of the first list whose first item is true. That is, it works like a case structure, picking out a return value based on tests associated with the possible return values. In this case, the first list is ((= n 0) 1), and cond understands this to mean "if (= n 0)is true, then return 1." The expression (= n 0) is a call to the function =, which follows Lisp prefix-and-parentheses notation and is a Boolean function that returns true if its arguments are equal, and false otherwise. So if (= n 0) returns true, cond returns 1.
If (= n 0) returns false, then cond examines the next expression, (t (* 2 (power-of-two (- n 1)))). The first element of this expression is a system constant, t, which always returns true. This line typifies the syntax of the "else" clause of a cond. Because t always returns true, a cond whose last list starts with t is guaranteed to return some value. In this case, if the last list is examined, the value returned by cond is the value of (* 2 (power-of-two (- n 1))). This is the multiplication function, *, applied to 2 and a recursive call to power-of-two. In the recursive call, power-of-two gets as its argument (- n 1), or n-1 in mathematical infix form.
In other words, the function power-of-two returns 1 if called with the argument 0, and for any larger integer returns 2*power-of-two(n-1). The definition ensures that, for proper arguments, the recursion will terminate.
I worked through this example in excruciating detail because it gives a strong taste of "pure" Lisp. Lisp isn't as pure as it once was, and in one sense that makes it easier to learn. Other languages employ recursion, for example, and Lisp employs structures that avoid some of the costs of deeply-recursive function definitions.
But this similarity of Lisp to other languages can also, paradoxically, make it harder to understand Lisp. Common Lisp has features that will be familiar to Pascal and Smalltalk and Forth and C programmers, which can lead to thinking of it as something other than what it is, so that its unique features seem like eccentricities. Looking at "pure" Lisp can help in understanding what the language is really about. This example was intended to be a taste of that.
Looking through my "Ancient Programming Languages" file, I come across a description of a language called "AND." AND is a remarkably simple and powerful language, written using just four symbols. The symbols combine in triplets to form twenty commands and three marks of punctuation (there is some redundancy in the coding, obviously). AND is invariably implemented as a one-pass compiler. Despite the language's simplicity, no one yet understands it fully, possibly due to the lack of documentation. Work has begun on the manual, which is expected to run into millions of pages.
AND has been around longer than Lisp or Fortran, and there are a lot of AND programs in use today. Some software systems based on AND have solved difficult calculus problems, piloted rockets, won chess matches, solved crossword puzzles, written novels, graduated from prestigious universities, and managed multinational corporations. Despite these impressive achievements, AND is generally regarded as inappropriate for artificial intelligence programming.
Time for Lisp
What Lisp Is
(PrintTable (ComputeValues (GetValues)))
What Lisp Isn't
A Taste of Lisp
(defun <name> <argument-list>
<body>)
(power-of-two (n)
(cond
((= n 0) 1)
(t (* 2 (power-of-two (- n 1)))) (cond
((= n 0) 1)
(t (* 2 (power-of-two (- n 1))))) ((= n O) 1), and
(t (* 2 (power-of-two (- n 1))))
AND (Now for Something Completely Different)