Why Lisp?

A number of people have contacted me about a comment I wrote yesterday on Hacker News asking me to elaborate, e.g.:

my impression is that lisp is *only* a different notation. Is that correct, or am I missing something? I don't see why it is so important that lisp code matches the data structure (and my assumption is that the match is the answer to 'why lisp') - am I overlooking the importance of macros, or is there even more that I'm still not aware of?

The answer to this question is long, so I thought I'd go ahead and turn it into a blog post.

The short version of the answer is that Lisp is not merely a different notation, it's a fundamentally different way of thinking about what programming is.  The mainstream model is that programming consists of producing standalone artifacts called programs which operate on other artifacts called data.  Of course, everyone knows that programs are data, but the mainstream model revolves around maintaining an artificial distinction between the two concepts.  Yes, programs are data, but they are data only for a special kind of program called a compiler.  Compilers are hard to write, a field of study unto themselves.  Most people don't write their own compilers (except occasionally as academic exercises), but instead use compilers written by the select few who have attainted the level of mastery required to write one that isn't just a toy.

The Lisp model is that programming is a more general kind of interaction with a machine.  The act of describing what you want the machine to do is interleaved with the machine actually doing what you have described, observing the results, and then changing the description of what you want the machine to do based on those observations.  There is no bright line where a program is finished and becomes an artifact unto itself.  Yes, it is possible to draw such a line and produce standalone executables in Lisp, just as it is possible to write interactive programs in C.  But Lisp was intended to be interactive (because it was invented to support AI research), whereas C was not (because it was invented for writing operating systems).  Interactivity is native to Lisp whereas it is foreign to C, just as building standalone executable is native to C but foreign to Lisp.

Of course, there are times when you have no choice but to iterate.  Some times you don't know everything you need to know to produce a finished design and you have to do some experiments, and the faster you can do them the better off you will be.  In cases like this it is very helpful to have a general mechanism for taking little programs and composing them to make a bigger program, and the C world has such a mechanism: the pipe.  However, what the C world doesn't have is a standard way of serializing and de-serializing data.  And, in particular, the C world doesn't have a standard way of serializing and de-serializing hierarchical data.  Instead, the C world has a vast array of different kinds of serialization formats: fixed-width, delimiter-separated, MIME, JSON, ICAL, SGML and its offspring, HTML and XML, to name but a few.  And those are just serialization formats for data.  If you want to write code, every programming language has its own syntax with its own idiosyncrasies.

The C ecosystem has spawned the peculiar mindset that thinks that syntax matters.  A lot of mental energy is devoted to syntax design.  Tools like LEX and YACC are widely used.  In the C world, writing parsers is a big part of any programmer's life.

Every now and then someone in the C world gets the bright idea to try to use one of these data serialization formats to try to represent code.  These efforts are short-lived because code represented in XML or JSON looks absolutely horrible compared to code represented using a syntax specifically designed to represent code.  They conclude that representing code as data is a Bad Idea and go back to writing parsers.

But they're wrong.

The reason that code represented as XML or JSON looks horrible is not because representing code as data is a bad idea, but because XML and JSON are badly designed serialization formats.  And the reason they are badly designed is very simple: too much punctuation.  And, in the case of XML, too much redundancy.  The reason Lisp succeeds in representing code as data where other syntaxes fail is that S-expression syntax is a well-designed serialization format, and the reason it's well designed is that it is minimal.  Compare:

XML: <list><item>abc</item><item>pqr</item><item>xyz</item></list>

JSON: ['abc', 'pqr', 'xyz'] 

S-expression: (abc pqr xyz)

The horrible bloatedness of XML is obvious even in this simple example.  The difference between JSON and S-expressions is a little more subtle, but consider: this is a valid S-expression:

(for x in foo collect (f x))

The JSON equivalent is:

['for', 'x', 'in', 'foo', 'collect', ['f', 'x']]

Rendering that into XML is left as an exercise.

The difference becomes particularly evident if you try to type those expressions rather than just look at them.  (Try it!)  The quotes and commas that seem innocuous enough for small data structures become an immediately intolerable burden for anything really complicated (and XML, of course, like all SGML-derivatives, is just completely hopeless).

The reason that Lisp is so cool and powerful is that the intuition that leads people to try to represent code as data is actually correct.  It is an incredibly powerful lever.  Among other things, it makes writing interpreters and compilers really easy, and so inventing new languages and writing interpreters and compilers for them becomes as much a part of day-to-day Lisp programming as writing parsers is business as usual in the C world.  But to make it work you must start with the right syntax for representing code and data, which means you must start with a minimal syntax for representing code and data, because anything else will drown you in a sea of commas, quotes and angle brackets.

Which means you have to start with S-expressions, because they are the minimal syntax for representing hierarchical data.  Think about it: to represent hierarchical data you need two syntactic elements: a token separator and a block delimiter.  In S expressions, whitespace is the token separator and parens are the block delimiters.  That's it.  You can't get more minimal than that.

It is worth noting that the reason the parens stick out so much in Lisp is not that Lisp has more parens than other programming languages, it's that Lisp as only one block delimiter (parens) and so the parens tend to stick out because there is nothing else.  Other languages have different block delimiters depending on the kind of block being delimited.  The C family, for example, has () for argument lists and sub-expressions, [] for arrays, {} for code blocks and dictionaries.  It also uses commas and semicolons as block delimiters.  If you compare apples and apples, Lisp usually has fewer block delimiters than C-like languages.  Javascript in particular, where callbacks are ubiquitous, often gets mired in deep delimiter doo doo, and then it becomes a cognitive burden on the programmer to figure out the right delimiter to put in depending on the context.  Lisp programmers never have to worry about such things: if you want to close a block, you type a ")".  It's always a no-brainer, which leaves Lisp programmers with more mental capacity to focus on the problem they actually want to solve.

And on that note, I should probably get back to coding.  Iteratively, of course :-)