Parentheses are more annoying in infix

There's a lot of code in functional languages written with a C or Java accent. The reverse is much rarer, but I have seen some: C++ written with a Lisp accent.

I didn't like it.

I didn't like the fooP convention for predicates. I didn't like the large multi-line expressions. And I especially didn't like the redundant parentheses.

What? A lisper doesn't like parentheses?

Parens are not high on the list of things that bother me in Lisp. They're only a little verbose, only a little distracting, only a little trouble to match. Large expressions don't bother me either; they're clearer than the alternative. And I like foo-p, because it's short and pronounceable.

Was I just objecting to C++ that didn't look like C++? Was I offended by contact between pretty Lisp and icky C++?

For fooP, that's probably the whole of it. It's camelCase instead of hyphenated, so it looks wrong as Lisp, and it's not standard C++ style, so it looks wrong as C++. And I'd rather not have to explain to other C++ programmers why I'm using a convention from some weird academic language. But I don't have a substantive objection.

For the other two features, I do.

Large expressions in prefix notation are easy to parse. The root operator is plainly visible at the beginning, and indentation goes a long way toward making the structure clear. Large expressions in infix are not so easy. The root operator is buried somewhere in the middle, and one must parse much of the expression to find it. There's no easy way to indent infix expressions, so breaking an expression across multiple lines doesn't alleviate much of the parsing load. This is why programmers in infix languages usually prefer to break such expressions into multiple statements.

Parentheses in Lisp are consistent: they all delimit lists, and almost all delimit forms. The semantics of the forms may be arbitrarily variable, but those of the parens are always the same. In C++, however, parentheses have several different meanings. They sometimes override precedence, sometimes call (or declare) functions, sometimes do typecasts, and sometimes delimit conditions in control structures. So a nest of parentheses in C++ is much more ambiguous than in Lisp, and it takes more parsing effort to determine which ones are which.

This goes some way toward explaining why so many programmers are suspicious of Lisp's syntax. Large expressions and nests of parentheses are suspicious in infix languages, and this suspicion does not instantly vanish in a new language.

Where do closures come from?

Common Lisp's function form is usually described as a device for switching between namespaces: it evaluates its argument in the “function” namespace instead of the normal “variable” namespace.

Older sources have a completely different idea: they say function makes closures. The Hyperspec says:

If name is a lambda expression, then a lexical closure is returned.

and

function creates a closure of the lambda expression

Both of these lines were inherited from CLtL, so this is not a new interpretation, nor one incompatible with the best of knowledge. What's going on?

To begin with, these two interpretations of function aren't observably different in portable Common Lisp. The only portable way to get a closure is by (function (lambda ...)) or by macros like defun that might expand to it. ((lambda ...) expands to (function (lambda ...)), because unlike all other special forms, lambda is in the function namespace, but that's just a historical quirk.) The only way to use lambda without function is ((lambda ...) ...), which has the same semantics regardless of whether it makes a closure. So portable code can't tell the difference.

Implementation-specific extensions can. If compile is extended to non-null lexical environments, it will make closures out of lambda-expressions without any help from function. Or if there's a named-lambda form that makes closures, it's unnecessarily complex to attribute the closure in (function (lambda ...)) to function.

So Common Lisp culture favors the simpler interpretation: lambda makes closures, and function is a mere namespacing operator.

Like so many oddities of CL, the old interpretation comes from Lisp Machine Lisp. The 1984 Lisp Machine Manual introduces function by saying it “has two distinct, though related, meanings.” The first is to get a symbol's function definition, and the second is to make a closure:

(let (a)
  (mapcar (function (lambda (x) (push x a))) l))

passes mapcar a specially designed closure made from the function represented by (lambda (x) (push x a)). When mapcar calls this closure, the lexical environment of the function form is put again into effect, and the a in (push x a) refers properly to the binding made by this let.

These two meanings were reflected in implementations. Guy Steele's reference interpreter (in the CL mailing list archive) doesn't bother to make a closure for ((lambda ...) ...), only for (function (lambda ...)). But when optimizing compilers became the norm, it no longer seemed silly (or inefficient) for lambda to always make a closure, so reinterpreting function as a namespacing operator made sense.

Surprisingly, this is not the first time function has been reinterpreted. The Pitmanual says Maclisp's function didn't make closures — it took a different form, *function, to even partially do that. function was equivalent to quote, except that in compiled code it would make a compiled function instead of just a lambda-expression — it permitted compilation but didn't change scoping. When Lisp Machine Lisp changed it to make closures, that was largely backward compatible, since most lambdas were intended to use lexical scope anyway. (I'm not sure when compilers started to use lexical scope — was that in Maclisp?)

I don't think any other language construct has had so many unrelated meanings over the years, let alone done so while preserving the meaning of existing code. function was originally a hint to the compiler, then a way to make closures, and then a namespacing operator. Its history probably ends there, since most new lisps eschew multiple namespaces and omit function rather than repurpose it, but three unrelated meanings is impressive.

“However, the compiler arranges for it to work anyway.”

There are some things you don't want to hear from a language manual...

You might expect this not to work if it was compiled and res was not declared special, since non-special compiled variables are not represented as symbols. However, the compiler arranges for it to work anyway.

...especially not in the section on a low-level primitive like, say, pointers.

That's from page 110 of the 1979 Lisp Machine manual (20 MB of interesting history).

Unlike most lisps, Lisp Machine Lisp had pointers, called “locatives”: first-class places, implemented as (unboxed, IIUC!) pointers. One of their uses was to refer to variables by pointing to their names' value cells. But local variables generally don't live in their names' value cells, so locatives on them do nothing useful (and potentially something harmful). Apparently there was a workaround for this: the compiler recognized these locatives as intended to refer to local variables, and replaced them with something else.

Isn't it nice using a language with clean, well-specified semantics?

Return of the Lisp Machine package system features

Xach pointed out that Nikodemus Siivola recently added support for reading package::(arbitrary form) in SBCL.

I had heard that Zetalisp had this feature, but apparently it's older than that — this was how packages originally worked. The 1979 Lisp Machine manual says:

The colon character (":") has a special meaning to the Lisp reader. When the reader sees a colon preceded by the name of a package, it will read in the next Lisp object with package bound to that package.

I don't know why CL degeneralized the package prefix to only work on symbols. The only reason I've heard is that a misplaced colon could accidentally cause the next form to be read in the wrong package, but that doesn't sound more dangerous than other typos like stray parentheses.

Update August 2015: It's more dangerous because unlike most typos, it has a read-time side effect: it pollutes the other package with lots of unwanted symbols.

Old Lisp manuals are a fascinating mix of futuristic and primitive. Lisp Machine Lisp also had hierarchical packages: package names were symbols, not strings, and could therefore live in other packages. But there are no earmuffs on package, nor on any other special variables; apparently they hadn't been invented yet.

Why use keywords as symbols?

From the beginning, Lisp has been associated with symbolic programming, for which symbols have always been the canonical type. So it's odd that many Lisps also have a separate :keyword type, which they use instead of symbols for all symbolic purposes except representing their own programs. Why bother? Why have two separate types that mean the same thing?

The motivation, in Common Lisp and (AFAIK) Clojure, is that these languages' symbols aren't pure symbols: in addition to identity and name, they include some other features, in particular a package or namespace. That's useful for representing programs, but most other applications of symbols don't want namespaces, so the languages also have keywords to serve as pure symbols. Lisps whose symbols don't have packages don't usually bother with keywords, but Racket and elisp have them anyway for use with keyword arguments. (In Racket, they need to be distinct from symbols because the function call form handles them specially rather than just passing them as part of the arglist. In elisp, they're only cosmetic; plain symbols could have been used instead.)

Avoiding namespaces is a good reason to use keywords, but I don't think it's the only reason, because users don't see keywords as a workaround; they seldom have to be told to avoid symbols because they're more complex than they appear. Instead, they overwhelmingly prefer keywords, not just for keyword arguments but as symbolic values. Even in elisp, where there's no reason not to use ordinary symbols, keywords are sometimes used instead. Why?

For one thing, they help distinguish programs from data. Humans, even Lispers who know better, tend to see these as two different things, and get confused when they mistake one for the other. When programs are written with symbols and data is written with keywords, it's easy to tell them apart.

Keywords are also more regular in appearance, because they're self-evaluating. It's tempting (for beginners, and as an unconscious heuristic for non-beginners) to think of symbols and keywords as differing only in their prefix character: 'x is the practical equivalent of :x, right? But they're not equivalent, because symbols have a quote only when they appear as forms. When they appear in a larger piece of quoted data, or as output from the REPL, or in non-evaluated contexts, they don't have the quote. This is only a superficial inconsistency, but it's annoying:

CL-USER> (list 'a 'b 'c)
(A B C)
CL_USER> (second '(a b c))
B
CL-USER> (defclass foo () ((a type integer initarg a accessor foo-a)))

(That last is not valid CL, obviously; it's what defclass would look like without keywords. I suspect users would perennially forget that most of the slot options aren't evaluated, even more than they already do, and put in quotes anyway, because they're not accustomed to writing unquoted symbols.)

Keywords, because they're self-evaluating, don't have this variation. They look the same whether they're in quoted data, or in the output of the REPL, or standing alone as forms, or as non-forms:

CL-USER> (list :a :b :c)
(:A :B :C)
CL-USER> (second '(:a :b :c))
:B
CL-USER> (defclass foo () ((a :type integer :initarg :a :accessor foo-a)))

More comfortable, isn't it? I wonder if this explains some of the popularity of keywords. (And also of Clojure's vectors, which while not strictly self-evaluating are similarly more regular in appearance than lists, because they don't usually require quoting.) If so, this is a disappointment to me, because it means this seemingly pointless distinction, like that between symbols and strings, is actually doing something important, and can't necessarily be simplified away.

Quote should not terminate tokens

Haskell allows the single-quote character in identifiers, so you can use variable names with primes, like x'. This is so convenient (especially for naming “revised” versions of variables, which seems to happen a lot when assignment isn't available) that I've been missing it in Clojure recently.

There's no reason lisps can't have this. Common Lisp supports nonterminating macro characters — characters that have special meaning when they appear on their own, but not when they appear in the middle of a token. Like many of CL's features (generic functions, anyone?) this isn't used much in the standard library; by default there's only one nonterminating macro character, #, and that's only for historical reasons (compatibility with Maclisp, I think). But it's easy to make new ones, which solves the x' problem in one line:

CL-USER> (set-macro-character #\' (get-macro-character #\') t)
T
CL-USER> '(x x' y y')
(X |X'| Y |Y'|)

(T as the third argument of set-macro-character means “nonterminating”.) Note that quote still works. Symbols with primes print funny, because the printer doesn't realize nonterminating macro characters don't have to be escaped, but they work fine; you can name variables with primes to your heart's content.

This should be the default in any new lisp: ' should not terminate tokens. Neither should any macro character except ), ], } and ;, really — termination only matters when you leave out spaces between tokens, and who does that?

How typep got its name

Paul McJones has a large collection of old Lisp manuals, which shed a lot of light on historical questions like how unary typep got its irregular name. The earliest reference I've found is in a 1973 Maclisp manual, which describes it thus, immediately after the other type predicates:

typep  SUBR 1 arg
  typep is a general type-predicate.  It returns an atomic symbol
  describing the type of its argument, chosen from the list
    (fixnum flonum bignum list symbol string random)
  symbol means atomic symbol.  Random is for all types that don't
  fit in any other category.

A “general type-predicate”? This wording suggests typep got its name because it was seen as a generalization of the regular type predicates. This makes sense: as Maclisp acquired an increasingly unwieldy number of type predicates, its maintainers would want to merge them into one operation, and would probably think of that operation as “a general type-predicate”, even though it's not actually a predicate.

(That random type is probably just an implementation detail showing through, but it's still adorable. Rudimentary type systems are to languages what tiny clumsy paws are to kittens.)

The curious attraction of one-argument typep

In Maclisp, the function typep takes one argument and returns its type in the form of a symbol. This is a fundamental operation, and it's egregiously misnamed, as it's not a predicate. (The -p convention is much older than typep, so the name was misleading even in Maclisp.) Lisp Machine Lisp preserved it for compatibility, but Common Lisp fixes the confusion by calling it type-of and using typep only for the two-argument type membership predicate.

I've never used Maclisp, nor any dialect with one-argument typep, so this misnaming should interest me only as historical trivia. But I find it oddly compelling. When I read typep, I think of the unary version first, and only remember the type membership test when context reminds me. When I refer to the “what type is this?” operation without having a specific language in mind, I tend to carelessly call it typep.

Why? I suspect it's because the most obvious name, type, is too bare — it sounds like it might collide with something else, although it doesn't in either Maclisp or Common Lisp — so I look for an affix to distinguish it. The -of in type-of works, but it's meaningless and irregular, and sounds wrong — more like function application than part of a name. -p is semantically inappropriate, but it's so common and familiar that it sounds right anyway. So I latch onto it and don't think about the meaning.

I can't be the only one with this problem. I've heard other people call it “one-argument typep”, and someone must have made the same mistake decades ago to give typep its misleading name in the first place. (Was it derived from a predicate? Did its designers have a different interpretation in mind, like “return the type predicate that's true of this value”?) If you are also drawn to this misnomer, or if you know more of its history, I'd like to hear about it.

Followup: How typep got its name

No value

Slime (the Emacs mode for Common Lisp) is nothing if not helpful. It autoindents, it completes symbols, it shows backtraces, it fontifies output. It even helpfully points out when an expression returned no values:

CL-USER> (values)
; No value

This is missing the point. Almost all CL functions can find something useful to return — even those, like rplacd or write, that are called purely for their side effects usually return one of their arguments, just to make them easier to insert into existing code. Functions producing zero values usually do so not because they have nothing to return, but because they're intended to be used at the REPL, and they don't want to clutter up the output with an uninteresting value. But Slime's helpful comment defeats their efforts. Observe:

CL-USER> (describe 'values)
VALUES is an external symbol in #<PACKAGE "COMMON-LISP">.
Function: #<FUNCTION VALUES>
Its associated name (as in FUNCTION-LAMBDA-EXPRESSION) is VALUES.
The function's arguments are:  (&REST VALUES)
Function documentation:
  Return all arguments, in order, as values.
On Fri, Mar 24, 2006 07:42:39 AM EST it was compiled from:
SYS:SRC;CODE;EVAL.LISP
  Created: Friday, April 15, 2005 09:57:55 AM EDT

; No value

How is this an improvement on a meaningless NIL?

(Hey, look, a logical pathname! I didn't know anyone used those.)

how-much-space-do-those-hyphens-take?

In a rant about naming conventions, Yossi Kreinin praises the way Lisp does multi-word names:

I think that the best naming convention out there is the Lisp one: case-insensitive-dash-separated. It just doesn’t get any better:

• You never have to hit Shift or Caps Lock in the middle of a name, which makes typing easier. This is especially important for names because you use auto-completion with names. Auto-completion requires you to press things like Ctrl-Space or Alt-Slash or Ctrl-P. Together with another Shift needed for the name to be completed correctly, auto-completion is much more likely to cause repetitive strain injury.
• You never have to think about the case. Figuring out the case of a letter in a case-sensitive naming convention can be non-trivial; more on that later.
• The dash-as-a-separator-convention is used in English, so your names look natural.

I'm not so fond of this convention. Well, it is nice to read; I can't think of anything more natural. And case-irrelevance is nice. (If your favourite lisp stopped case-folding one day and became case-sensitive in practice as well as theory, would you even notice?) There's just one problem: those hyphens take space.

How much?

(let ((syms 0) (chars 0) (hyphens 0))
  (do-symbols (s (find-package :cl))
    (incf syms)
    (incf chars (length (symbol-name s)))
    (incf hyphens (count #\- (symbol-name s))))
  (format nil "~S symbols, ~S chars (avg. ~2,2f)~%~
             ~S hyphens, ~2,2f% hyphens (avg. ~2,2f)~%"
    syms chars (/ chars syms 1.0) hyphens
    (/ hyphens chars 0.01) (/ hyphens syms 1.0)))

"978 symbols, 11271 chars (avg. 11.52)
875 hyphens, 7.76% hyphens (avg. .89)"

Hmm. Not as bad as I thought. 7.7% sounds like a lot, but most of those hyphens are in rarely-used names; the common ones are short. The big expression above has only four hyphens (plus the #\-), so it's not a huge problem. On the other hand, standard library names (even in CL) tend to be short; user code is often full of rather long names. Let's see...

(defun slurp (filename)
  "Read the contents of a file as a string."
  (with-open-file (s filename)
    (let* ((len (file-length s))
           (str (make-string len)))
      (do ((i 0 (1+ i)))
          ((>= i len) str)
        (setf (schar str i) (read-char s t)))))

(defun count-hyphens (filename)
  (let ((s (slurp filename)))
    (format t "~2,2f% of ~S chars~%"
    (/ (count #\- s) (length s) 0.01) (length s))))

(count-hyphens "asdf-install/installer.lisp")
3.13% of 12210 chars
(count-hyphens "edit-modes/python.el")
3.13% of 90348 chars   ;coincidence
(count-hyphens "keywiz.el")
2.88% of 10230 chars
(count-hyphens "tetris.el")
4.54% of 22458 chars
(count-hyphens "edit-modes/slime/swank.lisp")
2.86% of 191438 chars

There's a lot of variation (partly because some files are diluted with lots of comments, which I didn't try to strip out), but evidently hyphens are still significant. Tetris.el has a lot because it has a lot of names with short words, like tetris-top-left-x. Elisp in general suffers (in total length as well as hyphens) because it has no module system, so every name needs a module prefix. (If you want to make a language's code shorter, this is the first thing to worry about: make sure users don't have to defend against name collisions.) But even in CL, hyphens take around 3% of the code. That's about half as much as parentheses.

Maybe this isn't directly a problem. People probably don't look at the hyphens even as much as they look at parentheses, so what does it matter how many there are? But they still lengthen lines, making the eyes move farther, and increasing the chance of linebreaks. When one character accounts for 3% of your code, it's hard to argue that it doesn't matter. But as with parentheses, it's even harder to do anything about it, since all the alternatives are harder to read. So we use hyphens. But I still don't feel altogether good about them.

Update: It seems some people think I'm bashing Lisp on the grounds that hyphenated names make its code 3% longer. Relax; of course this is not a big problem, and I like Lisp, or I wouldn't be worrying about its naming conventions. And I prefer hyphens to every alternative, because they're so much more readable. But this readability isn't free, and at 3% the cost (in screen space) is surprisingly high. I don't have a solution, but it's nice to be aware of the problem. I will take CamelCase a little more seriously now.

Lisp without lists

Any significant program uses collections heavily, so most languages have several collection types - usually at least one sequence type and one dictionary type. Many languages have more, but library effort is limited, so every language omits some useful collections. As long as there are good alternatives, it's not a big problem.

Ruby doesn't have lists. RLisp borrows Ruby's data structures, so it doesn't have lists either. But it's a Lisp dialect! How can you have a Lisp without lists?

Pretty easily, it turns out. Despite their historical importance, lists don't have much to do with Lisp being Lisp. Their most important use is to represent S-expressions - but they aren't the only data structure that can do that. The important feature of S-expressions isn't that they read as lists - it's that they read as something simple and flexible and easy to work with. Vectors have all of these advantages, so RLisp programs are made of vectors instead of lists.

This is not traditional, but it's not a bad idea. Sure, cons and cdr are more expensive, and those are common operations on code, but performance of code manipulation is rarely a problem. And vectors are smaller than lists, which recovers some speed, and makes it cheaper to keep code around for debuggability. So I think other new Lisps should consider using vectors instead of lists.

I don't mean to suggest that lists aren't important. They are the functional sequence data structure, and every language that intends to support functional programming should have them. But RLisp is in its infancy, and it's forgivable if it doesn't have lists yet.

On the other hand, there's no excuse for its convention of writing close parentheses on their own lines. They look so lonely! More to the point, they waste space, separating the lines that have actual code. This is just as annoying in Lisp as it is in C, and there's no reason to do it in Lisp. Let indentation show program structure, and leave the parentheses at the ends of lines, regardless of whether they delimit vectors or lists.

Alternating lists

I complained about the awkwardness of processing alternating lists, such as in (let (var1 form1 var2 form2) ...), because ordinary collection operations don't understand them. But this is easy to fix. Arc's assignment operator uses an alternating list: (= a 1 b 2) is (do (= a 1) (= b 2)), just like setf in Common Lisp. So Arc has a function pair to convert (a 1 b 2) to ((a 1) (b 2)). A look through the Arc source shows it's always used with some sort of map, so there's still some repetition to remove. But it reduces the added difficulty of processing alternating lists to one function call. The inverse operation is easily accomplished with some sort of mappend. So difficulty of processing alternating lists is not really a significant problem.

My other objection was that they're hard to read. But alternating lists turn up in other places: keyword arguments, plists, #s(...) syntax - anywhere you need to write a dictionary in sexprs. I don't find any of these especially hard to read, so I suspect my discomfort with alternating let is just unfamiliarity. I suppose I should get used to it and stop complaining.

What was the problem with internal define in Arc?

According to Paul Graham, an early version of Arc had internal define, but there was a problem:

In a language with implicit local variables and macros, you're always tripping over unexpected lexical contours. You don't want to create new lexical contours without announcing it. But a lot of macros that don't look like blocks in the call expand into blocks. So we provided a second block operator, called justdo, which was like do but didn't create a new lexical contour (i.e. it is Common Lisp progn), and this is what you were supposed to use in macroexpansions.

The trouble was, I kept forgetting and using do instead. And I was thereby writing utilities with the worst sort of bug: the kind that might not show up for years, and only then in someone else's code.

Huh? My own Lisp dialect also has internal define, and I haven't had a problem with unexpected contours. Neither have thousands of Schemers. (They might point out the disagreement over define in let-syntax, and the difficulty of writing macros that expand into multiple defines, but I don't think anyone counts these among the biggest problems with the language.) I haven't even had trouble remembering to use justdo in my Lisp, possibly because it has the more distinctive name splice. What are these problems I'm supposed to be having?

I'm also surprised by how complicated the implementation was said to be:

We wrote a hideously complicated interpreter that allowed local variables to be declared this way. The ugliness of this code worried me: ugly things are generally a bad idea.

I suspect they just implemented it the wrong way. You can implement internal define quite simply by defining begin (including implicit begin!) as a macro which transforms define to letrec*. Most Schemes do it this way, and my own Lisp does too, more consistently: basic special forms like lambda and begin are actually macros over more primitive ones. It feels a little odd at first, but once you stop expecting to write in primitives all the time, it's quite comfortable. You get internal define and other macro-based luxuries without compromising the simplicity of the language kernel.

My experience with internal define has been almost entirely positive. This is so different from Graham and Morris' that I wonder if they were really doing something else. Now, how did they describe it?

In Arc we were planning to let users declare local variables implicitly, just by assigning values to them.

Were they actually creating variables by assignment? This is well known not to work, and for reasons having nothing to do with macros — ask a Python user about global. The Arc designers couldn't be repeating this old mistake. Could they?

Clojure

While I'm talking about new Lisps, I should mention Clojure, a new Lisp with close JVM integration and fancy concurrency support. I've been meaning to write something in it and post about the experience, but it may be a while before I get around to that. So here's the quick summary:

Clojure has the usual features of modern Lisps: lisp-1-ness, case-sensitivity (because it's hard to do case-insensitivity right), distinguishing () from nil from |nil|, pure symbols, shorter names, modules. It's quite clean, although Lispers should watch out for the renamings (familiar names like cons and do aren't what you expect). There is destructuring in binding constructs, and lambda is really case-lambda. Its Lispy core looks quite good (although as I said, I haven't used it much yet), and it closely resembles the orthodox modern Lisp.

Except for one thing: most data is immutable. Clojure aims at the most popular open problem in languages today: safe concurrency. Like Erlang, it tries to provide state only in forms that are easier to use safely in concurrent programs. Clojure has three: mutable special variables (since their bindings are per-thread), software transactional memory, and reactive message-passing. (See those pages for explanations and examples. There's also a wiki with more examples.) What it doesn't have is the ordinary mutation we take for granted in other Lisps. There's no setf, no mutable arrays or hashtables, no push.

Fortunately there's a lot of careful support for immutable collections, including syntax for [vectors] and {maps}, and generic iteration (even on Java collections!). It includes some useful functions that are often forgotten, such as mapcat and range. Clojure may not have state, but it tries to do the alternatives well enough that you don't feel the lack.

The ultimate alternative to language limitations is an FFI. Clojure is implemented in Java and runs on the JVM, so its FFI takes the form of extensive Java integration: nil is Java null, some interfaces are supported (in both directions!), and it's very easy to call Java code. There are some downsides to staying so close to Java: there's no tail-call optimization, and since threads are Java threads, their number is limited (potentially annoying, in a concurrent language). The upside is that it inherits all sorts of functionality from Java - the VM, massive libraries, even mutable data if you need it. This goes a long way toward explaining the completeness and high quality of the implementation.

There's something I'm wondering about, though. How do you pronounce Clojure? Same as "closure"? Or with /ʤ/ as in "Java"?

Orthodox Otter

Here's another new Lisp: Perry Metzger's Otter is a sketch of a case-sensitive Lisp-1 with short names and a little extra syntax and a module system and regular expressions and a cute animal mascot. Hygenic macros and a fancy compiler are planned but have been put off. It's supposed to be radical and heretical.

Radical? Heretical? Quite the opposite! There are a lot of new Lisps nowadays, and most of them include most of Otter's features (except maybe the mascot). There's hardly anything unusual here, except maybe the distaste for improper lists (a mistake which I also made for a while) and the choice of ! for setf (which seems obvious in retrospect - I will steal it now kthx). The rest of Otter is a reflection of what most Lispers consider the right way forward. It's not heretical, it's orthodox!

It's hard to detect these changes from the inside, but it seems to me this is a new development. Ten years ago, there was not so much agreement on what new Lisps should look like, nor on their desirability. The old orthodoxy was to cling to the existing dialects, as the language was perceived to be under threat. Remember when everyone was defending Common Lisp, except the Schemers, who claimed their language wasn't even a Lisp? But nowadays most Lispers don't think of the language as threatened. Instead we look forward to its future growth, and we aren't afraid to let a hundred flowers bloom.

But Otter probably won't be one of them. That presentation, from last August, seems to be the only available information on it. There's still nothing on the website but a picture of some sea otters. Sketching new lisps is fun (well, I think so, and evidently Perry does too) and easy, especially when you have an orthodoxy to guide you. Implementing them, and solving all the problems that surface in the process, is a lot of work, and prone to being put off forever. I suspect that's what happened to Otter.

But where one person can sketch a Lisp, others can build one. And we should. Never in the history of Lisp (or any programming language, IMO) have we had such an appealing orthodoxy. It is an irony not surprising in the Lisp community that that orthodoxy is now a language that does not actually exist; you cannot use it. But it is the sort of language that makes you want to. The popularity of new Lisps, and the extent of agreement on their features, suggest that it will have many incarnations in the years to come.

And now I'm better go work on mine...

Don't I like to hack Lisp?

I've noticed a disturbing pattern in my motivation to play with Lisp implementations. Now and then I fall prey to a new idea and start writing one, and it goes fast at first. I dash off the basic interpreter, perhaps an experimental representation of environments, a new macro system, modules, primitives... And then I get the the point where the kernel is basically working, and I need to write enough library - macros, mostly - to get some simple programs running.

And I stop. I like macrology. I like rebuilding the foundations of a language. I like seeing programs running on a tool I built myself. But as soon as I switch from writing the language to writing in the language, I lose interest.

This applies to implementations in an existing lisp, but even more to ones in C. I'll happily spend all day writing a garbage collector, even though I know it's an unoriginal waste of time. But when I start building library infrastructure, an understudied area where I could make a difference, I get bored.

Could it be that I actually enjoy low-level hacking? It is superficially rewarding, because it presents a constant supply of easy problems to solve, and they can be solved in familiar ways. It's programming candy - the fun of debugging without the pesky intellectual challenges. In C I can enjoy constant victories over my tools, whereas when growing a Lisp I'm confronted more directly with the problems. And they're sufficiently ill-defined and hard to think about that I recoil and go do something else instead.

I am not a good programmer when I prefer irrelevant problems to those I want to solve. I suspect this is a common tendency, and it may explain some of the puzzling lack of enthusiasm for more expressive languages. Who wants to face new challenges when you can keep solving the ones you know?

It's not homoiconicity

Lisp, say inumerable introductions, is a homoiconic language: its programs are represented in the same data structure they operate on.

I'm not bringing this up to complain about how often introductory material is copied uncritically. (I suspect that's because introductions tend to be conservative, and what's more conservative than repeating something other people have said before?) I'm bringing it up because it is so often repeated, even though everyone knows it is wrong.

It's commonplace to point out that C is homoiconic, and so is Perl, and every language that can process text. They can generate and manipulate their own code. It is often overlooked that this is actually useful, even in C. It's possible for a C program to generate and compile C code - this is how Goo is implemented. And of course many languages have self-hosted REPLs and other tools. Homoiconicity matters.

So why is Lisp better for metaprogramming? It's because the representation of code is a convenient one. Lisp trees are terse and closely reflect the abstract structure of programs, so they are easy to work with. This convenience isn't a simple, formalizable quality (although attempts to do so could produce some interesting papers). Like so many questions in programming languages, convenience is not a matter of adding some interesting new power, but of minimizing the amount of work spent doing uninteresting things.

When abstract code is hard to work with, it loses its metaprogramming benefits. Scheme, for instance, virtually requires a more elaborate representation of code in order to implement syntax-rules. Many Schemes expose that representation, but hacking it hasn't caught on, because it's quite inconvenient. This isn't a necessary problem with richer abstract syntax; it's just that this one is done badly. (In retrospect, it's a bad sign when you have an important type called syntax-object.) I think there could be better alternatives to S-expressions that preserve their all-important convenience.

By the way, a language needn't be homoiconic to benefit from a good representation of programs. Imagine a language whose domain does not include its programs, but which is hosted in another language which does. The host language can manipulate the trees, so it can metaprogram the embedded language - easily, if the representation is a good one. This is the case for many DSLs embedded in Lisp. They benefit from their convenient representation, even though they themselves can't manipulate it.

Please, Lispers, stop telling people what's special about Lisp is homoiconicity! If you want another fancy Greek word, you could speak of euiconicity. But let's not. Much as text is an inconvenient representation for programs, these big words are inconvenient for simple concepts. Just say S-expressions make metaprogramming convenient because they match the abstract structure. That's easier to understand, and as a bonus it transfers well to other data structure questions.

Unspecial forms

case-lambda, aif, with-condition-restarts, load-time-value... Lispers like to talk about special forms.

We rarely talk about the others. Most code, even in Lisp, consists almost entirely of a few anonymous constructs that aren't special forms. They're anonymous because they're too abbreviated to have names, and they're abbreviated because they're so common. These are the forms that are not special: variable reference, function call, and self-evaluating forms.

Their abbreviations are in structure, not syntax, but abbreviations can be done at the syntactic level too. And if you design syntax, keep the unspecial forms in mind. More than anything else, they need to be terse.

It's possible, but painful, to write code without the abbreviations. (I know someone else has written about this before, but I can't find the article.) Here's what the ordinary factorial might look like, in a Lisp-1, with the abbreviations replaced by special forms:

(defun factorial (n)
  (if (call (var <=) (ref n) (quote 1))
    (quote 1)
    (call (var *)
          (call (var factorial) (call (var -) (var n) (quote 1)))
          (var n))))

In these 16 forms, there are seven variable references, four calls, three literals, and two special forms (if and defun). There are also a few things that aren't forms: the binding occurrences of factorial and n, and the argument list. There are a few other nonform constructs not seen here: keywords for keyword arguments; docstrings; the structural lists that occur in forms like let and do.

I was curious about their frequencies, so I wrote a form counter to collect more data. This would be a perfect task for a code-walker, except that it has to understand the structure of every macro directly, rather than expanding it. I quickly got tired of adding cases to my form counter, so I only counted about a hundred lines. Bear in mind that this is a Lisp-1, so about half of the variable references are to functions (mostly from the standard library, of course).

Role	Count	Frequency
Variable reference	182	40%
Function call	78	17%
Binding occurrence	65	14%
Special form (including macros)	51	11%
Argument list	24	5%
Structural list	23	5%
Integer literal	18	4%
Keyword	10	2%
String or character literal	5	1%
Docstring	2	0.4%
Total forms	334	73%
Total	458	100%

Variable bindings and references account for over half of all nodes. 30% of the bindings are top-level definitions, but if the remainder are each referenced once on average, then 20% of all nodes are spent naming local variables. This is a powerful argument for points-free style.

Both structural lists and special forms are less abundant than I expected. It's tempting to try to shrink programs by abbreviating some common special forms - lambda, define, let, and perhaps partial application - but it can't help much, unless programming style changes significantly in response.

Data can be so disappointing sometimes.

let there be fewer parentheses

Lisp binding forms like let are prone to excruciating nests of parentheses: (let ((x (some expression))) ...). They can be hard to read, hard to edit, and surprisingly verbose. Can we do anything about this?

I've tried the alternating-list variation of let, which saves a pair of parentheses per variable:

(let* (x 2
       y (+ x x))
  (= y 5))

Unfortunately, that's its only virtue. Despite the reduced parentheses, it can be harder to read than regular let, because there is nothing delimiting each binding. It's also inconvenient to use in macros, because the alternating list often has to be split into names and init-forms, and mapcar won't do it. This would be easy if there were sequence functions for alternating lists, but the lack is a reminder that the alternating list is a slightly unnatural structure. Maybe we shouldn't use it. Rather than removing the pair of parentheses around each binding, we should look for ways to remove those around the list of bindings.

Every Lisp form gets an implicit list for free: its tail. (Well, not for free - it costs a pair of parentheses, but those are already spent.) Many macros use the list as an implicit progn. This is obviously useful for stateful code, and for internal define (when available). But modern Lisp style is increasingly functional, and of course define is unlikely in a let. There is usually only one body form, so the implicit list is wasted.

We can use the implicit list as the list of bindings instead, for a form reminiscent of Haskell's where syntax (but as an expression, not a feature of top-level definitions):

(defmacro where (body &rest bindings)
  "Backwards LET* - one body form followed by zero or more bindings."
  `(let* ,bindings ,body))

(where (= y 5)
  (x 2)
  (y (+ x x)))

This puts the body first, which is often a natural order. Unfortunately it may be confusing in an eager language, since forms no longer appear in order of evaluation.

Update May 2012: Mitchell Wand proposed this in 1993.

It's possible to put the body-form last, and use the implicit list at the beginning. This is an unusual pattern, but not hard to implement:

(defmacro lets (&rest bindings-and-body)
  "LET* with fewer parentheses and only one body form."
  (if bindings-and-body
    (let ((body (car (last bindings-and-body)))
          (bindings (butlast bindings-and-body 1)))
      `(let* ,bindings ,body))
    nil))

(lets (x 2)
      (y (+ x x))
  (= y 5))

Just don't expect your editor to indent it properly. :)

There is something unsatisfying about all of these solutions, because the problem they solve is purely one of syntax. The problem with let isn't that it has a list of binding pairs - that's its natural structure. The problem is that we have to explicitly delimit that list and those pairs, and we use the same characters for both. Languages with more syntax can avoid both of these problems.

Alternatively, you can avoid let by using internal define instead. I have a post on that coming soon.

eqsplanation

Visitors to Lisp from ML-land often ask: “Why does eq work on immutable objects? ‘The same object’ isn't meaningful without mutation!”

The reasoning goes like this:

1. Lisp supports mutable data, because state is a useful tool (even if we don't like to use it too much). So identity is meaningful.
2. Since values are usually represented as tagged pointers, identity comparison can be implemented as simple pointer comparison.
3. This happens to work for immutable objects as well.
4. The Lisp Way is to be permissive, so we won't disable eq in situations where it's not thought to be interesting. (Besides, it would take additional work to disable it.)

It turns out to be useful. For one thing, eq is very fast. We can arrange to make it equivalent to another predicate, without losing its speed, by interning the values: only keeping one of each set of equivalent values (as determined by the other predicate). This is how symbols work.

eq is also the only general way to detect shared structure. This is essential for things like *print-circle*, which makes printing circular data safe.

eq is total: it works on everything. This makes it handy for implementing general-purpose library code. In particular, it's a good default method for equality predicates. It's also handy when you want to distinguish one value from all others, of any type.

Finally, object identity is a basic fact of implementations. It shouldn't be hidden without a good reason. Allowing programs to see it helps you learn to “feel the bits between your toes”. In addition to being fun, that's important to writing efficient code.

Yes, eq exposes a detail of representation which usually doesn't matter. But it's a harmless exposure. No program has a bug because it is possible to compare its values for identity; neither do any interesting properties of programs cease to be true. So we get a variety of uses for free.

That's why Lisp has eq.