DSL Writers: Put Turing Completeness Out Of Your Mind

At the recent DSL DevCon, Martin Fowler gave an excellent keynote speech discussing domain-specific languages, an important subject that seems certain to be the buzzword of the next year or two.

However, one slide of his got my goat, leading me to foam at the mouth, beat the table with my shoe, wag my finger angrily, and otherwise mix my metaphors. In that slide, he said something along the lines of “a DSL probably ought not to be Turing complete.”

I think this is terrible advice. First, I think it’s a pedagogical mistake. Second, I think it’s incorrect.

Proof

shell ? sql | (minesweeper && life)

Q.E.D.

Discussion

Is SQL a less powerful programming language than the game of minesweeper?

To the extent that we want to broaden the number of people writing domain-specific languages, we can’t put that question on the entrance test.

Even if the percentage of people who know the answer can be made large, the percentage who comprehend it is quite a bit smaller, and the number who can apply it is a very small number. In a DSL, it’s smaller still, because you have to analyze your language in the context you’ve embedded it. You’ve climbed right up Bloom’s taxonomy! That’s why I think it’s a mistake pedagogically.

Why I think the advice is flat-out wrong is that DSLs are necessarily embedded in the context of a general-purpose language. Say I want a DSL that converted the numbers 1 through 256 into a set of CA rules following the obvious structure implied in:

elementarycarule110_1000

A DSL with exactly one production ({byte} -> {CA rules}) is not Turing complete (duh). But the context in which this DSL is expressed is one that leads to a (possibly profound) discovery of Turing completeness. (In case it’s not obvious from the context — the illustrated ‘Rule 110’ CA is Turing complete.)

Fowler referred to this when he advised DSL writers to avoid “accidental” Turing completeness. That really set the hook deep in my mouth, because it has a whiff of this stuff. To raise the issue and then to hand-wave it away is leaving yourself one heck of a big escape hatch. The mention of ‘Turing completeness’ or ‘Turing equivalence’ begs attention; they’re either forbidden holy-words or they’re used precisely and must be discussed with precision. (Thus, O’Brien’s Corollary (1991) to Godwin’s Law: The first person to mention ‘Turing equivalence’ in a debate of programming languages loses.)

Solution

It’s only because Fowler generally gives such excellent advice that the “Turing complete” stuff provoked me so much. Sure enough, a moment after the slide I didn’t like, he came up with what seems like the answer. I’m not sure of his exact words, but it was along the lines of:

Start with a general language that you think is readable and take stuff out. If you can’t take out quite a bit, don’t write an external DSL.
 

Great advice.

5 thoughts on “DSL Writers: Put Turing Completeness Out Of Your Mind

  1. I think the advice is sound, in general, to not try to create a general purpose language in a DSL. That is, don’t add all the bits required to program general purpose programs into the language. This can add up to an injunction to avoid Turing completeness for a quite colloquial definition of Turing completeness, because after all only a tiny amount of computation, an if-construct and a function call-construct can add up to Turing completeness.

    I’ve created a DSL in the past, one that was primarily expression-oriented and used for data-binding in a declarative model of a web application UI. When designing it, we explicitly didn’t want it to be used for general-purpose programming, because (1) the DSL necessarily has less investment in debugging infrastructure, (2) the DSL necessarily has less design to cope with large programs, and (3) the little slots we had put aside for this language in the overall declarative framework really didn’t cope well with more than a line or two of text.

    So, if you’re a stickler for the precise definition of Turing completeness, I agree, it’s the wrong way to approach things. However, as a synonym for “general-purpose language”, or at least a language with all the basic bits of sequence, selection, looping, functions, expressions etc., I think it’s good advice. I think a language should be missing one or more of those things; basic SQL, as an example, only has a sequence of statements and most of the language is expressions.

  2. BTW, your captcha fails if cookies are disabled in the user’s browser, but it gives no error message to that effect – it merely says “you got the captcha wrong, press back and try again”.

  3. Oh, and I forgot to mention; that little expression binding DSL did have functions, expressions and if-statements, so it was indeed Turing complete. You could do looping through recursion, but I was careful not to tell any of the business developers this… :)

  4. What an odd post Larry. It’s like you just threw the context of Fowler’s talk right out the window. You latched onto a keyword that has particular meaning to you, and you just shut your brain off from there.

    I think Barry’s got the right idea:

    “However, as a synonym for “general-purpose language”, or at least a language with all the basic bits of sequence, selection, looping, functions, expressions etc., I think it’s good advice.”

    Exactly. It is possibly the best advice for a person new to DSL’s to receive.

    Fowler, Ayende, other people have talked about this before. DSL’s are designed for a specific, narrow purpose. The idea of the DLS is to make that specific, narrow purpose easier to deal with than if one were just using the general purpose language.

    But it’s a common beginner’s mistake to try and build a DSL that does too much; they up reinventing the wheel. It becomes time wasted, because instead of building a DSL they’re just building another version of a general purpose language. They could have achieved the end result quicker by forgetting their (faux) DLS and just using their general purpose language to solve the problem in a non-DLS way.

    People who are new to concepts typically make the same mistakes. Programmers who are new to OO end up making God objects and methods with 1,000 lines of code. These are common mistakes among the newly initiated.

    It’s the mark of a GOOD teacher that they can recognize the patterns of these repeating newbie mistakes and try to correct their next group of students before they make the same ones. Fowler is trying to cut this sort of mistake off at the pass by saying, essentially, “Don’t try and make your DLS a complete language; just make it do its specific job.”

    It seems like instead of hearing that message, you got caught up in the verbiage of “Turing complete” and went off on a tangent that wasn’t necessary.

  5. “It’s like you just threw the context of Fowler’s talk right out the window….instead of hearing that message, you got caught up in the verbiage of ‘Turing complete’ and went off on a tangent that wasn’t necessary.”

    I tried to make it clear that I admire Martin, enjoyed the talk, agree with the gist of the message, and think that he gave one piece of advice that I think is very bad. The advice I object to is not “limit your language” but “you need to know what Turing completeness is and worry about it.”

    I don’t think it’s fair to say that I “latched onto a keyword that has particular meaning to you.” The central point is that ‘Turing complete’ and ‘Turing equivalence’ are not subjective. The use of precise terms begs for a strong response precisely because it shifts the level of discourse. If you want to say “limit expressiveness” I agree 100%. If one thinks there are patterns that express reasonable boundaries (I heard one suggestion that maybe ‘allowing users to write functions’ is near the border of “domain-specific” and “general” languages) then that’s good, let’s talk about experiences and successes and failures.

    You and I both think “Barry’s got the right idea!” You point at language elements and I point at “You could do looping through recursion, but I didn’t tell the biz devs that.” Exactly — put Turing completeness out of your mind.

    I believe the premise of Fowler’s talk was “more people should be writing (domain-specific) languages.” So I’d submit that pedagogy is every bit as in context as a discussion of techniques and tools. Further, it’s my premise that a low percentage of developers understand Turing completeness, a lower percentage understand what Fowler calls ‘accidental’ Turing completeness (the TC of Minesweeper or a DSL in the domain of tiling bathroom walls or what-have-you), and to the extent that we want to broaden the population writing DSLs, we have to worry about what barriers to learning they face.

    — Larry

Comments are closed.