Friday, November 10, 2006

Cumulative DSLs

I like first class constructs. Every time the language gurus out there manage to find an old thing they overlooked, a thing which wasn't first-class yet, and promote it to a first-class citizen, the programming world gets better. At least for those who aren't prevented from using the language by company rules.

It's not an issue of fairness at all. I'd like everything to be first-class, but not for the same reason that I'd like everyone to be allowed to vote, think, speak and live respectably. In fact it's quite the opposite: I'm being completely selfish.

I don't want the language designers to be involved in my design decisions. I want all the power for myself, because the solutions I dream up are fabulously elegant and who do they think they are, thinking in general-purpose terms and leaving the actual programmers that do the real work trapped with their domain-specific problems.

So I (sometimes) end up reinventing the wheel by writing my own domain-specific language. But my languages are small and boring and what I really wanted was all the general-purpose stuff plus this one new weird kind of method dispatch. And while we're at it, also throw in a new kind of literal for this custom type I always use. And a new module system which handles versions. And this new scoping rule for variables whose name begins with $$. If my general-purpose language had first-class dispatchers and first-class literal parsers and first-class module-resolution rules and first-class scoping rules, then I could implement all of this at my leisure. So what's stopping people from implementing a general-purpose language in which every single thing would truly be utterly and completely first-class?

I have an hypothesis: language designers are doing their best, but getting it right is simply really really hard.

Saturday, October 28, 2006

Monads as Universe Helpers

To see if the grass is greener on the other side of the programming fence, I've been accumulating a scaffolding of knowledge about functional programming which recently culminated in my understanding of the really cool and deep concept of monads.

Monads chain computations in a special way. There are many types of monads, and each chains its computations in its own special way. One of them chains computations in good old procedural fashion, keeping results around inside good old assignable variables and running computations according to our good friends the flow constructs; if, while, for and collaborators. Another familiar face is the layer-based architecture, the bureaucratic tower in which each floor's computation feeds the layer immediately above it. Another monad lets any computation abort part of the remaining computational chain by throwing an exception, and yet another generalizes the idea to the also-quite-cool concept of continuations.

Now, given that I already knew these useful models, was it really worth it to bang my head against the wall until monads finally made sense? Well, walls as just as rigid you would imagine them to be, so I would not recommend doing so if you're only looking for a new tool to add in your ever-growing bag of programming tricks. I believe the concept is more of a philosophical tool, actually. Or perhaps a mathematician's cute pet.

Remember what happened last time philosophers played with the concept of computability? Their fellow physicists had experimented with the world and made very impressive predictions about the behaviour of thrown balls and sliding blocks and complicated pulley systems. What do you know, it seems the world might be computable after all; determinism enters the scene and turns us all into emotionless mechanical contraptions.

The mechanical contraptions cried and argued against their fate, ridiculed defenceless pulley systems so they would feel better about themselves, and actively looked for escape clauses in their contract with the universe. Then one triumphal morning, quantum mechanics defeated the crooked determinism beast by invalidating science's dream of perfectly accurate predictions. What a relief; we could now choose to be emotionless lottery contraptions if we so wished. But of course what we really wanted all along was free will, not unpredictability.

Enter monads. And markov chains. You are an anthropomorphic dot moving in a large graph representing the universe. At each time-step, you must choose one of your node's outgoing edges and follow it to a new node. Some universe implementations may be deterministic or random about this and you won't be left with much of a choice. Some implementations might be kind enough to give you free will. But the gods who subcontracted the construction of the universe to our firm aren't quite sure which it will be yet, so we better make our implementation modular in that respect.

We also better make sure that our implementation can scale well, because universes tend to grow astronomically large. For one thing, we definitely don't want to fill up drive after drive with nodes and edges, so we will need to use a trick. We will only keep track of your current node and compute your possible outgoing edges, on the fly, whenever we need them. The architecture of our universe is thus composed of three parts: a function mapping nodes to possible actions (Laws), a current node (Creature), and that thing which chains executions of the functions using either free will or not (Monad). Yes, a free will monad; I told you this stuff was deep.

Sunday, August 20, 2006

Lisp is Low-Level

Lisp is built out of an amazing idea: like everything else in the machine, code is also data. This is true in any language, but Lisp's syntax makes the code especially easy to manipulate as data.

This feature allows new language constructs to be implemented as program transformations, without touching the core language. Given this uncommon ability, how could any language ever beat Lisp in terms of level of abstraction? Any missing functionality, it would seem, can only be temporarily missing, awaiting a sufficiently dedicated macro writer. Surely, Lisp must be the most high-level language ever designed!

Well, I think not. Lisp is low-level.

Macros may allow you to write programs more abstractly, but writing macros themselves is more painful than needed. A macro is manipulating a raw syntax tree, devoid of meaning, especially since it may contain new macro constructs it has never heard of. How can it be expected to do the right thing?

The only hope, for the poor macro, is to leave the new constructs alone. Thus, some constructs shadow the influence of other constructs, effectively preventing a class of independently developed language extensions from being used together. That's a shame, and that's a direct consequence of Lisp's macro facilities being too low-level tools.

What would a high-level macro system look like? Personally, my bet is on more advanced reflection mechanisms. In an upcoming post, I'll explain how reflection and macros are interrelated, and provide a much needed example to illustrate the kind of things which Lisp cannot do.