The Light Cone

Where past and future meet at a point in spacetime

Category Theory Reveals Value of Autoiconicity

Suddenly it hit me: Category Theory is to Math as Lisp is to Programming. I’ve always had an instinctive preference for autoiconic programming languages over non-autoiconic, and now I know why.

An autoiconic language is one in which the format for code and the format for data are identical. Add “quote” and you have instant metaprogramming built-in. That means that when you write code, you’re really writing a DSL (Domain-Specific Language), always. With non-autoiconic languages, e.g., all the C’s, Javas, Algols and Fortrans, that is, the mainstream, DSLs are a special case and require tons of enabling machinery like expression-object-models, serializers, lexers, yaccers, compilers, decompilers, metadata managers, and on and on. All standard or near standard, and all equally unnecessary since none of it at bottom does any more nor less than quote, quasi-quote, and unquote.

With Haskell and its ancestors Miranda, KRC, and SASL; and with Scala, F#, and all the ML’s, DSL programming is done via user-defined types. With these languages, DSL programming is not a special case, but remoting is still a special case requiring extra machinery. This is not a small thing, but really the crux of the argument. The real gold in the era of cloud programmability is DSL + remoting. I need to send expressions written in my DSLs to servers – for data affinity, and to clients – for data privacy. Why is remoting a special case? Because I don’t have quote and eval. Why not? This, I don’t know. It must be a conscious decision on the part of language designers, because all these languages conspicuously lack quote and eval. I do not know the reason. Be that as it may…

Granted one might say “the difference is just a matter of degree.” True, but that’s like saying the difference between a rock and the entire Earth is just a matter of degree. That’s why the Lisps won’t die: it’s just plain easier to write remotable DSLs in Lisp, by orders of magnitude, and you always need remotable DSLs. And remotable DSLs are enabled by distributed metaprogramming platforms.

I argue that any sufficiently rich application will become a distributed metaprogramming platform eventually, and will need all that stuff. Especially on the web, where code-remoting is a necessity – confer the massive amounts of machinery and years of work behind .NET Expressions for IQueryable and friends. Beautiful, it’s true, because the thinking and the engineering behind them were first-rate and I was privileged to participate. But, if our mainstream languages had been Mathematica or some kinds of Lisp, remoting and rewriting would have been for-free; a “duh, obviously;” not even an afterthought; but a built-in assumption. Reflecting on the whole remotable-DSL-enabling infrastructure of .NET Expressions, it’s nothing but an implementation of quote, quasi-quote, and unquote for C#. All that work just to get into the mineshaft where the gold of remotable DSLs lies.

This entire screed is just an addendum to Greenspun’s Tenth Rule, my asserting that the specific thing that these “sufficiently complicated C or Fortran” programs strive to find in their “ad-hoc, informally specified, bug-ridden, slow implementations of half of Common Lisp” – the specific half they need – is the half that enables remotable DSLs, namely distributed, remotable metaprogramming via quote, quasi-quote, and unquote.

What does this have to do with Category Theory? That is a use of autoiconicity in mathematics. It uses the language of mathematics to explain mathematics. Every branch of mathematics is just a DSL of Category Theory.

All this philosophizing came about because Fogus, of “Joy of Clojure” recently tweeted about SICP – Structure and Interpretation of Computer Programs, which is now influencing its second or third generation of developers. That reminded me of Philip Wadler’s critique of SICP and got me thinking why I always thought that, outside of his pedagogical context, Wadler’s argument was weak, specifically because it did not note the trade-off of losing remotability by giving up on autoiconicity, granting that when Wadler wrote, remoting was not center-stage the way it is now with the cloud. Then I remembered that John D. Cook, of “The Endeavor” sent around a link to a deeply intriguing new book by David I. Spivak on category theory, and it hit me.