Skip to main content

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).
Labels:

Popular posts from this blog

Existential Types are the flip side of generics

Generic types, as can now be seen in all the major programming languages have a flip side that has yet to be widely appreciated: existential types. Variables whose types are generic may not be modified within a generic function (or class): they can be kept in variables, they can be passed to other functions (provided they too have been supplied to the generic function), but other than that they are opaque. Again, when a generic function (or class) is used, then the actual type binding for the generic must be provided – although that type may also be generic, in which case the enclosing entity must also be generic. Existential types are often motivated by modules. A module can be seen to be equivalent to a record with its included functions: except that modules also typically encapsulate types too. Abstract data types are a closely related topic that also naturally connect to existential types (there is an old but still very relevant and readable article on the topic Abstract types have...
Read more

Minimum Viable Product

When was the last time you complained about the food in a restaurant? I thought so. Most people will complain if they are offended by the quality or service; but if the food and/or service is just underwhelming then they won't complain, they will simply not return to the restaurant. The same applies to software products, or to products of any kind. You will only get negative feedback from customers if they care enough to make the effort. In the meantime you are both losing out on opportunities and failing your core professional obligation. Minimum Viable Product speaks to a desire to make your customers design your product for you. But, to me, it represents a combination of an implicit insult and negligence. The insult is implicit in the term minimum. The image is one of laziness and contempt: just throw some mud on the wall and see if it sticks. Who cares about whether it meets a real need, or whether the customer is actually served. The negligence is more subtle but, in the end, ...
Read more

Hook, Line and Sinker

It is well documented that people’s #1 fear is speaking in public ! Effective and efficient public speaking is a whole topic in its own right; but a few simple tips might help to both improve your effectiveness and help to reduce the anxiety. You may be called on to talk about your work at very short notice; or you may have a week’s notice; and you may be required to give a formal slide show or just a brief verbal update. Many, if not most of the issues, are the same. The Hook Newspaper editors call the first paragraph of an article ‘the hook’. Its meant to hook you into reading the rest of the piece. On the other hand, the classical ‘say what you are going to say, say it, and say what you said’ approach gives people plenty of time to switch off. The hook may be playful, it may be controversial, but it must communicate why the listener should pay attention. The Line Its a conversation! Even if no one says anything they are listening and thinking; and maybe replying to you in their head...
Read more