Domain Specific Languages & Turing Completeness

I don’t know if it’s been said before1, so in case it hasn’t, I’ll say it:

Every domain specific language converges towards Turing completeness over its lifetime.

The reason for this observation is that I’ve recently come in contact with a number of new DSLs2, which exhibit the same problem I’ve seen with other DLSs in the past. Except, this time, I noticed that their authors expressly distanced themselves from the idea of implementing Turing complete languages.

So why the observation?

Well, as I gain experience with these DSLs I run into more and more usage problems with them, which other, Turing complete languages don’t usually have (I’ve seen exceptions to that rule, too). And if the authors of these DSLs hadn’t mentioned turing completeness, I wouldn’t even have thought about it.

The problems usually are, on the face of it, relatively trivial things. Right now I was looking for rules concerning variable scoping, only to find that it’s not well-defined (and therefore quite broken). In a roundabout fashion, it reminded me of a proprietary DSL I maintaining several years ago which had no clear definition of its syntax, and therefore – as an implementation detail – allowed if statements within switch statements, but not vice versa. Or the other way around, I forgot. And don’t get me started on proprietary SQL extensions that let you write conditionals in ways the SQL standard never envisioned.

I could name more examples, but that’s not the point. What struck me this time around is that DSLs seem to come about from the same motivation, every time: make a language that does one task well, but keep it simple and clean.

And then it gets popular, and the users ask for more features, some of which they know from Turing complete languages. So those features get added, but with no fundamental rethink of how the language should work. And so the implementation of these features ends up being conceptually shoddy, even if the code is of outstanding elegance3.

There’s a lesson in there somewhere. I think the lesson is that if you set out to write a DSL, start with an existing, Turing complete language, and add syntax constructs to make your special case task very easy. That way, you’re not only ahead of the curve — your users will eventually want all those features anyway — you’ll likely also end up with a pretty powerful language.

Wouldn’t it be even nicer if there was a simple Turing complete language that allowed itself to be extended easily with new syntax constructs?

  1. A quick search hasn’t found anything. []
  2. New to me, that is. []
  3. Though conceptual shoddiness rarely results in elegant code. []