My take on Arc

The nerdosphere is abuzz about Arc, Paul Graham's long-awaited new dialect of Lisp, so I figured I might as well pile on. For the benefit of those of you who read this blog for its political content, beware: this is going to be a seriously geeky post. You have been warned.

Some quick background: I am as big a fan of Lisp as you could ever hope to find. I've been using Lisp since 1979 (my first Lisp was P-Lisp on an Apple ][ ) and I used it almost exclusively for over twenty years until I lost my faith and switched, reluctantly, to Python (and I was not alone). Recently I have taken up Lisp again since the release of Clozure Common Lisp. I am proud of the fact that my login on Reddit, YC News and Arclanguage.org is Lisper.

Furthermore, I am a huge Paul Graham fan. I think his essays are brilliant. I think Y Combinator is brilliant (to the point where I'm seriously considering moving from LA to the Silicon Valley just so I can go hang out there). Paul is the kind of guy I wish I could be but can't.

And to round out the preliminaries and disclaimers, I am mindful of the fact that the current release of Arc is a first draft, and it's never possible to live up to the hype.

I think all the enthusiasm and buzz about Arc is wonderful, but I am concerned what will happen if people start to think that there's no there there. If Arc doesn't save Lisp it's hard to imagine what would. And unfortunately, I think Arc has some quite serious problems.

The biggest problem with Arc is that it is at the moment not much more than a (very) thin layer on top of Scheme. Now, that would be OK if it were the right thin layer, but I don't think it is. Arc's design path is well-trod, and the pitfalls that lie upon it are mostly well known.

For example, Arc is 1) a Lisp-1 that 2) uses unhygienic macros and 3) does not have a module system. This is bound to lead to problems when programs get big, and not because people forget to put gensyms (which Arc dubs "uniqs") in the right place (although I predict that will be a problem too). The problem is that in a Lisp-1, local variable bindings can shadow global function names, and so if you use a macro M that references a global function F in a context where F is shadowed then M will fail. If you're lucky you'll get an error. If you're not lucky your program will just do some random weird thing. Hygienic macros were not invented just because some intellectuals in an ivory tower wanted to engage in some mathematical masturbation. This is a real problem, and the larger your code base the more real it becomes.

I cite this problem first because macros are, according to Paul Graham, the raison d'etre for Lisp. Macros are the reason for putting up with all those irritating parentheses. And macros in Arc are broken.

Unfortunately, it gets worse.

Arc is supposed to be a language for "exploratory programming" so it's supposed to save you from premature commitments. From the Arc tutorial:


Lists are useful in exploratory programming because they're so flexible. You don't have to commit in advance to exactly what a list represents. For example, you can use a list of two numbers to represent a point on a plane. Some would think it more proper to define a point object with two fields, x and y. But if you use lists to represent points, then when you expand your program to deal with n dimensions, all you have to do is make the new code default to zero for missing coordinates, and any remaining planar code will continue to work.


There are a number of problems with this. First, the kind of flexibility that Paul describes here is not unique to lists. You could accomplish the exact same thing with, for example, a Python object with named slots (which is just a thin wrapper for an abstract associative map -- note that I did not say hash table here. More on this later.) You could have 2-D points with X and Y slots, and 3-D points with X, Y and Z slots. You could even do the 2-D points-return-zero-for-their-nonexistent-Z-slot trick by redefining the __getattr__ method for the 2D point class. Python objects are every bit as flexible as lists except that it's a lot easier to figure out that a <2-D point instance> is a two-dimensional point than a list with two elements. (You can't even assume that a 2-D point will be a list of two numbers, because Paul goes on to suggest:


Or if you decide to expand in another direction and allow partially evaluated points, you can start using symbols representing variables as components of points, and once again, all the existing code will continue to work.


"All of your existing code will continue to work" only if your existing code isn't built with the tacit assumption that the coordinates of a point are numbers. If you've tried to do math on those coordinates then you're out of luck.

Which brings me to my next point...

Lisp lists are quite flexible, but they are not infinitely malleable. They are a "leaky abstraction." The fact that Lisp lists are linked lists (and not, for example, vectors, as Python lists are) is famously exposed by the fact that CDR is a primitive (and non-consing) operation. Make no mistake, linked lists are monstrously useful, but there are some things for which they are not well suited. In particular, Nth is an O(n) operation on linked lists, which means that if you want to do anything that involves random access to the elements of a list then your code will be slow. Paul recognizes this, and provides hash tables as a primitive data structure in Arc (the lack of which has been a notable shortfall of Scheme). But then he backpedals and advocates association lists as well:


This is called an association list, or alist for short. I once thought alists were just a hack, but there are many things you can do with them that you can't do with hash tables, including sort them, build them up incrementally in recursive functions, have several that share the same tail, and preserve old values.


First, hash tables can be sorted, at least in the sense that associated lists can be sorted. Just get a list of the keys and sort them. Or create a sorted-hash-table that maintains an adjunct sorted list of keys. This is not rocket science. But that is not the problem.

The problem is that the functions for accessing association lists are different from those used to access hash tables. That means that if you write code using one you cannot pass in the other, which completely undermines the whole idea of using Arc as an exploratory language. Arc forces you into a premature optimization here.

The Right Thing if you want to support exploratory programming (which to me means not force programmers to make premature commitments and optimizations) is to provide an abstract associative map whose underlying implementation can be changed. To make this work you have to commit to a protocol for associative maps that an implementation must adhere to. The trouble is that designing such a protocol is not such an easy thing to do. It involves compromises. For example, what should the implementation do if an attempt is made to dereference a non-existent key? Throw an exception? Return some unique canonical value? Return a user-supplied default? Each possibility has advantages and disadvantages. The heavy lifting in language design is making these kinds of choices despite the fact that there is no One Right Answer (or even if there is, that it may not be readily apparent).

And that is my main gripe about Arc: it has been so long in the making and set such lofty goals and then it seems to pretty much punt on all the hard problems of language design.

Now, as I said, I am mindful of the fact that this is just a first draft. But some Big Decisions do seem to have been made. In particular, it seems a safe bet that Arc will not have an OO layer, which means no generic functions, no abstract data types, and hence no way to build reliable protocols of the sort that would be needed to eliminate the kinds of forced premature optimizations that Arc currently embraces. It also seems a safe bet that it will remain a Lisp-1 without hygienic macros (because Paul seems to regard both hygiene and multiple name spaces as Horrible Hacks). Whether it gets a module system remains to be seen, but it seems doubtful. If you think designing a protocol for abstract associative maps is hard, you ain't seen nothin' yet.

So there it is. Paul, if you're reading this, I'm sorry to harsh on your baby. I really hope Arc succeeds. But I gotta call 'em as I see 'em.