François-René Rideau (fare) wrote,
François-René Rideau
fare

  • Mood:
  • Music:

What Makes Lisp Great

Lisp has this particularity that (1) there are distinct syntaxes for data structures and for program code, that (2) code syntax is a subset of data syntax (code can be seen as data), and that (3) data syntax can be embedded easily into code syntax (by enclosing it in the QUOTE special form). It is then possible to write in Lisp a small program that executes Lisp programs seen as data structures, EVAL. The discovery of such a simple canonical correspondance between code and data is what made Lisp so great. Alan Kay called it Maxwell's Equations of Software.

And indeed, it was a discovery: the initial plan for Lisp was to be a programming language with a syntax as similar to usual mathematical usage as possible, just like FORTRAN; this was the M-expression. A small part of the syntax was dedicated to describing the data to be manipulated, that were nested lists of numbers and Symbols; this was the S-expression. Lists were delimited by parentheses, and elements separated by commas (in practical implementations, the separator would be spaces instead of commas). In the earliest years, programs, written on paper as M-expression, were hand-compiled into machine code. That programs could be encoded as data that could be interpreted with a universal function, EVAL was mostly an intellectual exercise for theoreticians, at first. But then a young lad, Steve Russell, took that exercise seriously, translated the function EVAL itself to machine code, debugged it, and obtained an interpreter for Lisp programs in S-expression form. People could then enter program code as S-expression, test it, and not have to worry anymore about the tedious error-prone process of translating programs manually into machine code. Thus was started the tradition of using the data syntax subset for writing actual code: so as to use a very useful metaprogram, the interpreter, itself made possible by the universal nature of the language. The M-expression survived for some time, at least in paper documentation and usage. M now stood for Meta more so than for Mathematical, because it was used in the Metalanguage of Lisp. But in the end, the use of the data syntax stuck because it was found to be actually more natural.

Just what is so great about having a data syntax for code? The ability to easily write metaprograms, that is, programs that manipulate other programs, by seamlessly turning data into code and code into data. This makes it easy to experiment with variants and extensions of the language. Whereas Lisp started as kind of a Functional Programming language, it could and did easily absorb Imperative Programming, Structured Programming, Object-Oriented Programming, Graphical User Interfaces, Pattern-matching, Logic Programming, Distributed Programming, Dynamic Web Applications, etc. As soon as someone, somewhere, invented any feasible programming paradigm, said paradigm could easily be imported into Lisp. Whereas a non-Lisper inventor of some programming idea would, maybe, with a lot of effort, after many years, build a full-fledged programming language from scratch around his one paradigm, Lispers could with comparatively little incremental effort support the same paradigm as the extension of a one programming environment that also supported all the previously invented paradigms and that would also support all the future paradigms whenever these would be invented. And of course, while experimenting, Lispers are not limited to an all-or-nothing approach of language selection, but can explore all kinds of programming language features and ways to combine them, and get an actual running language implementation for each combination. For instance, while experimenting with the Scheme dialect of Lisp, Steele and Sussman were reportedly writing as many as ten interpreters a week. By contrast, non-Lispers may require weeks, months or years between each actually tested iteration of their language design process. This allows Lisp to benefit from a language design experience beyond anything that has ever been tried with any other programming language. Lisp was the only intrinsically programmable programming language.

Now, just any universal programming language can be encoded so that code can be included and manipulated as data by programs in the same language. And indeed, most serious programming languages end up being implemented by a compiler written in same language, after a phase of bootstrap from a different metalanguage, using the very same technique used with Lisp between 1959 and 1961. In any case, any language implementation supposes that a mechanism is provided by which programs can be practically encoded as data, if only as a data stream from user input, to be directly interpreted or compiled without intermediate representation. Thus, any language is, at least in theory, and at least in some contorted practical way, fit for metaprogramming. However, Lisp still possesses quite an edge in this regard, which is intimately tied to its very distinctive characteristic: the encoding of code as nested lists of symbols and other data.

Firstly, this encoding of code as data is well-defined as part of the language itself; this means that there is a common standard representation that serves as the basis for development of metaprograms by anyone. By contrast, in other languages, every would-be metaprogrammer has to start from scratch, and sharing his metacode with other people will be hampered because encoding is implementation-dependent, subject to changes, restricted by intellectual property barriers, etc. This restrains considerably the potential for human collaboration about metaprograms.

Secondly, the Lisp encoding of code as nested lists is very simple and powerful. The choice of a single universal and versatile data-structure means that it is very easy to write metaprograms both from Lisp and to Lisp. As said Alan Perlis: It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. The overhead for writing metaprograms in Lisp is thus very low, as compared to what you have in about any other language; there is opportunity for writing code that is both shorter and more widely applicable than in other languages -- less expensive and more valuable.

Thirdly, the natural mapping between the nested list structure of code as data and the semantics of said code also contribute to making metaprogramming simple. The recursive evaluation model where all expressions yield values makes it much simpler to manipulate programs than the common dual statements vs expressions model found in most other languages. More generally, the Lisp grammar has two non-terminals, pairs and atoms, where other languages commonly have a lot of non-terminals, that lead to a combinatorial explosion for metaprograms. The ability to locally define lexical, dynamic and syntactic bindings, as well as higher-order functions, method combinations, and many other features, also allow for local code transformations to be much more expressive than they could possibly be in other languages, where the same effects would require global program rewrite. Lisp code can thus be factored in much nicer ways than code in other languages.

Fourthly, because Lisp code can be compiled efficiently and dynamically, it is not only easy, but also efficient, to use Lisp as the target for metaprograms. In other languages, people have to use slow interpreters or to target special-purpose virtual machines when generating code dynamically, because dynamic production, linkage and execution of code is so difficult. Interestingly, technical difficulties with these languages can often be overcome, at the price of bulk, slowness, unsafety and various limitations; but intellectual property restrictions on the availability and use of the compiler and linker make these techniques impossible to use on the mainstream of computers running proprietary systems with mainstream languages. All in all, this means that with Lisp, the work of metaprogrammers is both greatly simplified and made to bring higher pay-off and wider applicability. But this also opens tremendous opportunities for the reuse and combination of metaprograms, that are not available with other languages. Since the target language doesn't change depending on static or dynamic generation, metaprograms don't have to be written in two or more completely different copies that may cost a lot to keep consistent; this makes metaprogramming affordable where it isn't in other languages. Since source and target languages are the same, the output of Lisp metaprograms are susceptible to being used as the input of other interesting metaprograms; many original combinations can thus take place that were unintended by the authors, and that will never see the light when using different languages.

Now, since metaprograms are themselves programs, Lispers have also experimented with ways of making metaprogramming easier, automating it with a proper set of metametaprograms. One notable invention for that was Lisp macros. If you have never used them, and associate the word macro to something you've seen in any other language, you probably can't grasp the power and elegance of Lisp macros. C macros are a pitiful lame caricature in comparison; the macros in some macro-assemblers are sometimes more serious, but extremely tedious and messy and often not powerful enough still; the macros in macroprocessors such as m4 are powerful enough, but a horror to program, and the implementations are both slow and buggy; additionally, such external macroprocessors are not integrated with the compilation environment and it is often a tremendous pain to either reconstruct the compile-time information or deal without it. Macros of all these kinds are a kluge with limited expressive power, each depending on a special tiny crippled caricature of a programming language, and each completely disconnected from the rest of the language implementation. In contrast, Lisp macros, originally invented by Timothy Hart as published in October 1963 (see MIT AI Memo No. 57), and refined afterwards with the evolution of Lisp, give you the full power of the extensible Lisp programming language to further extend the Lisp programming language in a clean incremental way fully integrated in the programming environment. The modern macro system of Common Lisp was the culmination of many attempts to define proper language extension protocols. People in the Scheme community have continued to explore macro systems, and they have found quite nice solutions; however, what was ultimately standardized long afterwards by the Scheme committee was yet another crippled special language. Sigh.

Another essential tool that was invented to ease the development of meta-programs in general (and macros in particular) is quasiquotation, as gradually discovered in the 1970's, and recently well documented by Alan Bawden. Quasiquotation allows one to easily write templates of data (including most particularly code representation) where part of the structure is fixed whereas other parts are computed. The syntax is almost the same as for quoted data, except for unquotes at places where the structure is not fixed and computation is to happen. Quasiquotes can be nested, which allows for meta-meta-programs, or metan-programs. Interestingly, quasiquotation is a concept independent from the actual representation of programs: it helps abstract away from the fact that programs be encoded as lists or otherwise. It gets even better when it can be used for matching code as well as for generating code. Lists are still useful, though, and so are straight quotes, in combination with quasiquotes: lists allow to handle the variable part of program patterns, and quotes are instrumental in distinguishing levels of nested unquotation. Thus, it is unclear whether use of quasiquotation in other languages matches the utility of quasiquotation in Lisp; a notable exception is Slate, which, with tagged quasiquotation, can do unquotation in a clearer and more powerful way than is possible in straight Lisp (though Lisp can be extended to match this feature). Also interestingly, the discovery of quasiquotation and the power unleashed by nesting it and combining it with quote, is tied to the existence of quote, and hence to the specifically Lispy tradition of a separate data syntax.

Last but not least, the Lisp language also includes a lot of reflective infrastructure, from BOUNDP to GET-SETF-EXPANDER to the CLOS MOP, that allows one to write language extensions that take advantage of each other, instead of being mutually incompatible as happens in so many other languages. In any mainstream language, language extension implies having mutually incompatible new compilers for each set of new features; by contrast, language extension in Lisp is a matter of using components that most of the time interoperate out-of-the-box. You may have to ensure that globally-rewriting metaprograms are run in the right order, but this is intrinsic to the problem of combining such metaprograms, and the infrastructure of Lisp makes such problems far less frequent than in other languages. The worst you usually have to do is to ensure that symbols are interned in the right package.

In conclusion, unlike most other languages, Lisp is not an arbitrary design based on the whims of some author, but it is a discovery produced by a long evolution and a deep tradition. It has seen several revolutions: transition from M-expression to S-expression, from EVALQUOTE to EVAL or from dynamic binding to static binding, introduction of data-structures, of object-oriented programming and of a meta-object protocol, the invention and latter standardization of many many individual features. Many dialects of Lisp also introduce their own revolutions, such as continuations and single name space in Scheme, the graphical user interface and dreaded DWIM features in InterLISP, etc. If anything remains among all these revolutions and variants, it is the ability to evolve. Lisp is a language fit for evolution -- not just by a small group of wizards who control the language implementation, but by every single programmer who uses the language. And this wasn't a conscious intended part of the original design: this was the great discovery of Lisp.

If this article made you want to start using Lisp, I can recommend The Quick #lisp Guide to Starting with Common Lisp. If you want to know why metaprogramming matters, see my article Metaprogramming and Free Availability of Sources.

In a next article, I will write about how some other languages allow for evolution in different ways, what they still have to learn from the Lisp tradition, what the Lisp tradition has to learn from them, what makes it difficult for either mainstream languages or Lisp languages to acquire features from the other world, and what we can envision for realizing the best of both worlds.

Tags: code evolution, dynamism, en, essays, lisp, meta, tao of programming
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 14 comments