You are viewing fare

eyes black and white

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.

Comments

Evolutionism in other languages

I removed the paragraph about evolution in other languages, and the concept of extrinsic language evolution vs intrinsic language evolution. The paragraph was worded poorly and couldn't do justice to these other languages. The topic deserves a post of its own, and I will write about it in an upcoming article.

Lisp is great for exploratory programming, but in the real life it is not widely used for a very simple reason: horrible ergonomics. A maze of little parentheses, all look alike.

Programming is done by humans and for humans. Computers are merely medium for expression, not the target or raison d'etre for the profession. In the real world, an understandable program is much better than a program which is elegant, or fast, or even provably correct.

It is not natural for people to deal with endless levels of nesting. People use all kinds of shortcuts and ad hoc structures to convey meaning in the natural languages. That's what our brains are tuned for by the evolution. That's why no artificial "universal" language ever got widely accepted, despite simplicity and ease of learning.

A good language design must recognize that fact, and deal with it. Syntactic richness is not a curse, far from it -- note that the recent generation of popular "scripting" languages got even more of those little syntactic nooks and crannies (especially Perl, heh). Different things should look differently. It is semantic deficiencies which are most annoying in the conventional languages, not their syntax or limited expandability.

There's a very old observation that verbosity significantly impedes comprehension. That's why highly successful standard mathematical notation is so compact, and that's why people use tens of thousands of words instead of combinations of fewer simple qualifiers, and that's why the programmers "in the field", the ones who actually have to deliver working software on time, prefer languages like C++ or Java and, yes, even the decidedly ugly Perl, over Lisp.

PS. And, no, that's not because they don't know better. A lot of people studied Lisp in college, it is a staple of any CS curricula; and some of us programmed in more languages than can be counted on all fingers (I was once asked to count how many languages I used in 20+ years of my carreer... I was surprised that the tally came to five dozen, if various assemblers and things like Verilog are included). It is not a matter of language religion, then, it is a matter of using the most convenient tools for the job.

Reasons for adopting a language

Your arguments about Lisp are irrelevant, plain wrong, or mixing true and false statements; Lisp fares very well in domains where you suggest that it is bad. I could discuss your message point by point, but won't bother here. Try comp.lang.lisp for a good flame.

There are actual reasons, both good and bad, why Lisp isn't used, but those you give mostly are not. And the question begins with the the people who invent new languages.

I dispute the notion that languages be usually chosen on technical merit. "convenience for the job" includes most importantly compatibility with the pointy haired boss who gets to pick the language -- and who often prefers not to make a decision, but let either the previous pointy haired boss or the surrounding trend decide for himself. There is such thing as rational irrationality, in programming as in politics.

At heart, this is all a matter of culture difference. Culture difference is not the cause of the lack of popularity of Lisp -- it is the very thing. Why are some cultures mainstream, while other remain confidential or even die? I like what Alan Kay wrote about "Pop culture". But before we may ever explain why some culture is mainstream why the other is not, we may investigate what each culture is; its contents in terms of beliefs, patterns of behaviors, etc. Then we may appreciate the costs and benefits of adopting a culture, for a person with a given psycho-epistemology in a given context -- which may or may not be positively or negatively correlated to the technical advantages of said culture.

Re: Reasons for adopting a language

Your arguments about Lisp are irrelevant, plain wrong, or mixing true and false statements; Lisp fares very well in domains where you suggest that it is bad. I could discuss your message point by point, but won't bother here. Try comp.lang.lisp for a good flame.

Thank you for a very argumented reply :) No, I'm not about to argue which language is better, it is a matter of taste.

There are actual reasons, both good and bad, why Lisp isn't used, but those you give mostly are not. And the question begins with the the people who invent new languages.

Yeah, sure, there's an Evil Conspiracy Of New Language Inventors.

I dispute the notion that languages be usually chosen on technical merit. "convenience for the job" includes most importantly compatibility with the pointy haired boss who gets to pick the language -- and who often prefers not to make a decision, but let either the previous pointy haired boss or the surrounding trend decide for himself. There is such thing as rational irrationality, in programming as in politics.

I did not say that languages are choosen on technical merits - they are choosen based on convenience for humans who want to get a particular thing done. As for the "pointy-haired boss" argument, its absurdity is easily demonstrated by one word: Linux. See any PHBs around in the Open Source crowd?

At heart, this is all a matter of culture difference.

I'm very familiar with two significantly different and formerly, to a significant extent, independent computer cultures, arising on the different sides of the Iron Curtain. In both the functional languages didn't gain any kind of wide acceptance outside of AI and programming language research.

In the reality new languages get created and gain popular acceptance without any recourse to the PHBs, marketing antics, or any other forms of "unfair play". Python, Ruby, Perl, PHP - to name the few of the latest crop. Each of those gained more users in a year or two than Lisp in its entire 30-year history - often against wishes of corporate folks. How come?

I think that Lisp an its progeny are simply too hard to use by people without serious mathematical background. And, no, by far not everyone is interested in elegance and power.

Frankly, I'd be way more impressed with Lisp crowd if you folks instead of contemplation of the greatness of one-page interpreter designs, cool garbage collectors, and innovative ways to implement a switch would address some problems which bug people out there - like how to produce code of good quality fast, how to ensure that code is maintainable, or how to make software less brittle.

Re: Reasons for adopting a language

Once again, you're mixing a lot of issues, some on which we agree, and some on which we disagree.

(1) Just because I've argued that one thing made Lisp great that other languages do not possess, doesn't mean that I claimed that Lisp had the only thing that ever mattered. I never denied that there are good things in other software than Lisp, and even many things that Lisp is lacking. It just wasn't the purpose of my current article. You seem to be setting a straw man, arguing against what I didn't say rather than against what I did say.

(2) There are indeed many good things that happen outside the Lisp community, with great technical value. Programming languages that have recently advanced the state of the art indeed include Python, Perl, Ruby, PHP, and many more, for all their other warts. (We're not talking about Operating systems here, so discussion of Linux is off-topic, least you are ready to compare it seriously to Windows, VMS, UNIX, Multics, Genera, etc.)

(3) Even these technically innovative languages have only a relatively small impact on the industry, at its margin (which is undeniably the economically interesting place). Despite that, I maintain that by and large, the adoption of programming languages and technology in general in the industry is motivated mainly by non-technical reasons (which also makes economic sense).

(4) I claim that even amongst technically minded people, many meaningful technical features are wrongfully dismissed by people who might be concerned. If you claim I'm wrong and have myself dismissed meaningful technical features (which I haven't -- I've just focused on one), you're actually making my point.

(5) You say that Lisp is too hard to use by people without serious mathematical background. My claim is that you're wrong, and that it's not a matter of education, but of psycho-epistemology. Of course, education and psycho-epistemology may be correlated in many ways; but what matters to psycho-epistemology seems to be innate traits more than acquired traits, and as far as acquired traits go, the general approach of life more than the specific contents of any course taught. This divide is actually much deeper than any geographical, political, social or educational divide (though once again, you could find correlations).

(6) If you think that simple universal semantics capturable by small interpreters, garbage collection, containment of side-effects, macros and metaprogramming, object-oriented frameworks with multiple dispatch and meta-objects, continuation-passing, dynamic programming, etc., are not related to how to produce code of good quality fast, how to ensure that code is maintainable, or how to make software less brittle, well, think again.

(Anonymous)

Re: Reasons for adopting a language

And, no, by far not everyone is interested in elegance and power.

Have fun with C and Java....they were great when software was merely glorified accounting packages, and "programmers" were merely coders. Methinks you're a little out of your league, nowadays, sonny.

(Anonymous)

Re: Reasons for adopting a language

> 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.

I believe you missed the historical explanation - and the goals of the
Scheme commitee.

When the last Scheme standard (R5RS) was written there were three (3)
different low level macro systems available: syntax-case, explicit renaming
and syntactic closures. Since all technologies were still
relatively new, it wasn't at all clear which technology ought to
be standardized.

Since the RnRS commitee unamimous decisions, it was agreed to include
syntax-rules as a high level macro (which is "easy" to implement in
the low level macro systems), and then leave it up to the next committee
to include a low level macro system.

The work on the next standard has begon, and some kind of majority
vote is used - thus the probability of getting a low-level macro
system in the standard has increased.

Progress so far: <http://www.schemers.org/documents/standards/charter/>

/Jens Axel Søgaard


(Anonymous)

< you > < are absolutely="right" > < people > < dont > < like deeply="nested" > < expressions > < / expressions > < / like > < / dont > < / people > < / are > < /you >

(Anonymous)

See also: http://lemonodor.com/archives/001096.html

(Anonymous)

...

" (1) there are distinct syntaxes for data structures and for program code " or There are *NO* distinct syntaxes for data structures and for program code. ?

(Anonymous)

Excellent piece/quasiquotation in Slate, ML

Hi Faré --

As always, we learn so much from you. I have two requests: first, please copy this to Tunes; second, you said (regarding quasiquotation): "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."
I would kindly ask that you elaborate further on this point in a future article, that is, quasiquotation in Slate vis-à-vis Lisp. It would also be nice to elaborate on what are the issues of quasiquotation in the ML-family, and why there's a need for preprocessors, instead of just writing the expressions in the REPL. Is it the syntax introducing too much complexity?
Thank you for an excellent read.

Henry Lenzi

Re: Excellent piece/quasiquotation in Slate, ML

As for Slate, it allows for tagged quasiquotation, which in Lisp would be like (qq :foo (bar (1 2) (uq :foo (+ 3 4)))) ==> (bar (1 2) 7). That is, quasiquotation and unquotation take a tag argument and only matching unquotations matter to a given quasiquotation.

As for quasiquotation in ML, several factors contribute to its limitations. Firstly, static typing prevents dynamically extensible types, and extension functors are a horror to use. What static languages lack is a dynamic meta-programming environment that manages coherent program-wide transformation of types and objects.

Aha!

A practical illustration of my theoretical musings: Greg Trasuk finally gets Lisp. (Cám ơn, lemonodor.)

(Anonymous)

good conclusion

lisp seems old and deprecated at first but as said it's evolving with every important concept found, not some fashioned useless idea.
eyes black and white

July 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Tags

Powered by LiveJournal.com