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

Comments Should be Meaningless

This is something of a counterintuitive idea: Comments should be meaningless What, I hear you ask, are you talking about? Comments should communicate to the reader! At least that is the received conventional wisdom handed does over the last few centuries (decades at least). Well, certainly, if you are programming in Assembler, or C, then yes, comments should convey meaning because the programming language cannot So, conversely, as a comment on the programming language itself, anytime the programmer feels the imperative to write a meaningful comment it is because the language is not able to convey the intent of the programmer. I have already noticed that I write far fewer comments in my Java programs than in my C programs.  That is because Java is able to capture more of my meaning and comments would be superfluous. So, if a language were able to capture all of my intentions, I would never need to write a comment. Hence the title of this blog.
Read more

In Praise of Crappy Code

Not all code needs to be perfect! This is pretty heretical thinking for a software engineer. The issue is simple: how do you go about developing software for a small fixed budget. Imagine that you have $500 to implement a solution to a problem. If you spend more than that you will never recoup the extra that you spent. This comes up a lot in systems integration scenarios and also in customization efforts. Someone wants you to 'tweak' an application that they are using; you know that no-one else would want that feature and that if you spend more than what the customer will pay you will end up losing money. From the customer's perspective, the common 'time and materials' approach to quoting for software development is a nightmare. Being able to offer a fixed price contract for a task is a big benefit for the customer. But, how much do you quote for? Too much and you scare the customer away. Too little and you lose money. This is where 'crappy code' com...
Read more

Action at a distance

We are currently writing our first draft of the SOA Reference Architecture. Everyone is very busy doing their bit. My current section is on the Real World Effect of using a service. The RA is really an abstract architecture: we are not focusing on things like SOAP, or any of the other 60+ Web service specifications out there. We are trying to get at the essence of makes SOA special and how it can be made to work. It is a pretty basic aspect of services that we are trying to get something to happen: buy a book, get the weather forecast whatever. In other words: its action at a distance. I am communicating with you in the hope that we can get some mutual benefit. This already distinguishes SOA from the Web, whose basic abstraction is to acquire a representation of a resource will be rendered locally for human consumption. Actions are not inherently about representations, they are about changing the world - one book at a time. Action itself is a very difficult concept to get hold of. It ...
Read more