Sub-turing complete programming languages

Here is an interesting intuition: the key to liberating software development is to use programming languages that are not, by themselves, turing-complete.

That means no loops, no recursion ‘in-language’.

Why? Two reasons: any program that is subject to the halting problem is inherently unknowable: in general, the only way to know what a turing-complete program means is to run it. This puts very strong limitations on the combinatorics of turing-complete programs and also on the kinds of support tooling that can be provided: effectively, a debugger is about the best that you can do with any reasonable effort.

On the other hand, a sub-turing language is also ‘decidable’. That means it is possible to predict what it means; and paradoxically, a lot easier to provide a rich environment for it etc. etc. An interesting example of two languages on easier side of the turing fence are TeX and CSS. Both are designed for specifying the layout of text, TeX is turing complete and CSS is not.

CSS is still young but, for all its warts, an order of magnitude easier to work with than TeX. Further more, there is actually no much that TeX can do that CSS cannot; with the proviso that sometimes missing functionality must be ‘buried’ in the CSS language.

For example, TeX is powerful enough to implement an indexing scheme, CSS is not. It would be easy enough to extend a CSS engine to provide key indexing mechanisms.

I think that there are many fundamental merits to this approach to programming languages. The biggest is that a sub-turing complete language would (have to) be inherently more high-level than a turing-complete language. Secondly I believe (no evidence presented here) that such a language could be closer to the way people think about tasks than programming in Java (or even Haskell).

About these ads

8 thoughts on “Sub-turing complete programming languages

  1. Sorry, lots of not turing complete languages have loops and some sort of recursion and so on, more over every algorithm that have a well defined worst-case complexity is expressible in some non turing complete languages.
    look to
    http://en.wikipedia.org/wiki/Μ-recursive_function
    and
    http://en.wikipedia.org/wiki/Lambda_calculus(typed version)

    More over I will not be sure that css is not turing complete until I see a demonstration.
    And if it is not, even an amazing little improvement could change this.

    • So, I do not believe that CSS is turing complete.
      There is no capability to define a function in CSS.
      In order for a system to be turing-complete it has to be possible to write an interpreter: a function that interprets expressions that denote programs to execute. CSS has no variables that are directly accessible to the user; so you cannot even model the structure that represents the program to be interpreted in CSS.

  2. Your intuition is not unsound and currently being explored under the name of ‘Total functional programming’. The basic idea is that all programs should provably terminate, by disallowing general recursion. One of the more interesting results is that very many programs can still be written under such a discipline. For more information look into the programming languages Epigram, Charity and Agda. The programs look more like proofs that the program does what it is supposed to, however…

  3. “CSS is still young but, for all its warts, an order of magnitude easier to work with than TeX.”

    I confess I don’t remember exactly what the state of CSS was in 2008 when you wrote this, but in hindsight CSS has definitely turned out to be at least as difficult as TeX, while remaining much less powerful for (non-animated, text and line art) layout.

    If all else were equal, it might be useful to compare CSS and TeX for their position on Turing-completeness, but these languages are completely different in much more important aspects. TeX is as close to a bug-free program as you’ll ever find, while I have yet to write any non-trivial CSS that didn’t find at least one significant bug in a current version of a top-3 browser (as of 2013).

    You say that for Turing-complete languages like TeX, “a debugger is about the best that you can do with any reasonable effort”. True, but at least I’m debugging my own little TeX problem. With CSS, I have to debug my web browser.

    There may be “fundamental merits” to sub-Turing languages, but there are far more fundamental merits to having a language implementation which isn’t full of bugs. CSS is only 16 years old, so it’s possible it’ll get there some day, but TeX was already incredibly stable by the time it was 16, and I still don’t see the CSS designers and implementors taking stability one tenth as seriously as Knuth did from the start.

    • I agree that stability and reliability are very important features of TeX. TeX is reliable, but the same cannot be said for the many packages that I am ‘forced’ to use to get output that meets my publication standards.

      I am sorry for your experience with CSS. (Don’t know why I should be; not my responsibility :). However, my main point still stands: sub-turing complete languages represent an important design point in the space of languages.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s