Lisp design and extensibility

Lisp design principles make the language to be naturally extensible, as well as leading to naturally extensible products: just look at Emacs or Autocad. Why is this so?

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 bottom-up in any language, but Lisp is by far the most natural vehicle for this style.

Bottom-up programming leads to naturally extensible software. If you take the principle of bottom-up programming all the way up 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 the ideal language for writing extensible software.

—Paul Graham, ACL (1996)

Lisp can lead to extensible software, to which Emacs is a real-life proof. So far so good. But what about its extensibility and adaptability as far as the programming paradigms are concerned?

When Lisp was invented in 1958, nobody could have foreseen the advances in programming theory and language design that have taken place in the last thirty years. Other early languages have been discarded, replaced by ones based on newer ideas. However, Lisp has been able to survive, because it has been able to adapt. Because Lisp is extensible, it has been changed to incorporate the newest features as they become popular. [...] Flexibility of Lisp goes beyond adding individual constructs. The brand new styles of programming can easily be implemented. Many AI applications are based on the idea of rule-based programming. Another new style is object-oriented programming, which has been incorporated with the Common Lisp Object System (CLOS), a set of macros, functions and data types that have been integrated into ANSI Common Lisp.

—Peter Norvig, PAIP (1992)

The beginning of the above-mentioned quote from Paul Graham gives the answer as to why is it so: because Lisp can be written in Lisp.

The unusual thing about Lisp -- in fact, the defining quality of Lisp -- is that it can be written in itself. [...] Using just quote, atom, eq, car, cdr, cons, and cond, we can define a function, eval, that actually impements our language, and then using that we can define any additional function we want. [...] Given a handful of simple operators and a notation for functions, you can build a whole programming language [...] What we have here is a remarkably elegant model of computation.

—Paul Graham, "The Roots of Lisp" (2001) <http://paulgraham.com/rootsoflisp.html>

The key idea of Lisp, that makes it all possible, is the code-is-data philosophy, the fact that Lisp programs use the same structure as Lisp data. Using syntactically the same structure for code and data means that in Lisp it is natural to write programs that manipulate code; to write programs that write programs. I'm thinking of Lisp macros, of course. Together with runtime typing, these features make the language to be very flexible and adaptable ...unlike other languages. It is important to note that these features have been present in Lisp since 1960s but are still rare to find out elsewhere in 2003! Which makes that, while extending Lisp is a natural way of working in the Lisp world, extending other languages isn't that natural. For other languages it is much harder to adapt to new trends, and trying to do so often gives rise to an "usine à gaz" class of phenomena, i.e. more or less unnatural stretching of the language beyond its original domain.

Thanks to the code-is-data philosophy, extensibility is a core, natural thing in Lisp by its very design, so that the "usine à gaz" phenomenon is a beautiful stranger here. Let me demonstrate it on a concrete example of the object-oriented paradigm.

Lisp abstractions and OO message-passing model

How hard would it be to extend Lisp to encompass the mainstream OO message-passing model? That is, let's forget that Common Lisp has its own OO system, and let's try to introduce a new mainstream OO message-passing model into a non-OO Common Lisp. How many man-months and lines of code do you think such a system would require?

This is exactly the kind of exercise Paul Graham took in the last chapter of his "ANSI Common Lisp" book, in order to illustrate the embedded language programming in Lisp. And the answer is: eight lines of code to introduce a basic message-passing single-inheritance model:

It's worth pausing to consider what we have done here. With eight lines of code we have made plain old pre-CLOS Lisp into an object-oriented language. How did we manage to achieve such a feat? There must be some trick involved, to implement object-oriented programming in eight lines of code.

There is a trick, but it is not a programming trick. The trick is, Lisp already was an object-oriented language, or rather, something more general. All we had to do was put a new facade on the abstractions that were already there.

Which abstractions did Paul Graham meant? Objects were modelled via hash tables where the attributes were stored, as well as object methods, via lambda functions. This is because functions are first-class citizens in Lisp (meaning that they can be worked with as data, passed into and returned from functions, etc). What was needed to add "on top" of pre-CLOS Lisp was mainly a basic support for inheritance, for which those eight lines of code were enough.

The chapter then goes on expanding and "beautifying" the model, adding user-friendly language constructs for using objects etc, to end up in a complete full-featured OO message-passing system, including multiple inheritance(!), in something like seventy lines of code.

We now have an embedded language suitable for writing real object-oriented programs. It is simple, but for its size quite powerful. And in typical applications it will also be fast. [...] We see what a wide latitude the term "object-oriented" has. Our program is more powerful than a lot of things that have been called object-oriented, and yet it has only a fraction of the power of CLOS [...] One of the disadvantages of CLOS is that it is so large and elaborate that it conceals the extent to which object-oriented programming is a paraphrase of Lisp. The example in this chapter does at least make that clear. If we were content to implement the old message-passing model, we could do it in a little over page of code. Object-oriented programming is one thing Lisp can do. A more interesting question is, what else can it do?

Seventy lines of code... this does not sound like an "usine à gaz" sort of thing, does it?

Does Lisp need OO?

What the above exercise means? Not more and not less than the fact that Lisp has its own powerful set of abstractions, and that the OO point of view on the world doesn't provide any kind of "substantial upgrade" into Lisp way of thinking. It suffices to only "map" new OO constructs onto pre-existing Lisp abstractions, and the job was done. What are these pre-existing key Lisp abstractions?

With macros, closures, and run-time typing, Lisp transcends object-oriented programming.

I've already spoken briefly about (i) code-is-data philosophy and (ii) macros operate on code and produce code. It's worth to underline that Lisp macros have full access to the language, unlike say C "macros" and other "templating" systems that may operate simply textually. As for (iii) runtime typing, it of course means that the types are associated with values rather than with variables: it's a kind of strong dynamic typing that is now fairly popular in many mainstream languages. (iv) Lexical closures are present in Lisp since early 1970s, but are, similarly to macros, still quite rare outside of Lisp. Substantially, lexical closures are functions that "close over" lexically bound variables so that these variables are then unaccessible to the outside code except via the closure function calls. In other words, a closure is a function that can "capture and encapsulate" variables in local state. Sounds like an OO concept, hum? (Peter Norvig in the above-cited PAIP makes the same exercise as Paul Graham in ACL -- how to introduce OO into non-OO Lisp -- for which he uses expressly closures and lambda functions, with similar easiness. And, in the full-featured CLOS, the methods are actually closures, underneath the syntax.)

And I'm not going to elaborate anything about (v) Lisp symbols having had their own "property lists" that could have been used to store object attributes to; (vi) encapsulation and information-hiding that can be provided not only via closures but via interning symbols; (vii) etc, etc... but the list is already long enough and I hope to have shown already why OO does not bring that much of "new" abstraction concepts, which is why it was possible to introduce the message-passing OO model, including multiple inheritance, in about seventy lines of code.

Consequently, it's not a big surprise that many Lisp programmers do not consider OO to be any kind of "ultimate" programming paradigm. Lisp does not really "need" it. This is in sheer contrast to the non-Lisp world where OO brought significant improvements:

Object-oriented programming is exciting if you have a statically-typed language without lexical closures or macros. To some degree, it offers a way around these limitations.

—Paul Graham, "Why Arc Isn't Especially Object-Oriented" <http://paulgraham.com/noop.html>

while in the Lisp world itself:

With addition of CLOS, Common Lisp has become the most powerful object-oriented language in widespread use. Ironically, it is also the language in which object-oriented programming is least necessary.

That said, let's look at CLOS, the Common Lisp Object System, in a later post.