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

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.

Organizing principles for services

One of the questions that comes up from time to time is how to define your services. This has come up for me in two independent fora: within the OASIS Service Oriented Architecture work and in the context of human provided services, for example at Genietown . In the work on the SOA Reference Model we decided that "services are the mechanism by which needs and capabilities are brought together"; i.e., its about needs and capabilities to satisfy those needs, and the access mechanism. However, this still begs the question somewhat. In the domain of human services, where the services are things like "building a home", "walking the dog", "taking care of my elderly parents"; it gets even fuzzier. Sometimes a service seems to organized around the person offering the service, for example, an architect, or a doctor. Sometimes the service is organized around a particular kind of product, such as doors or skylights. At other times, the service is organize...

About the right tools for the job

Some time ago I was involved in a running debate about whether we should be using Ruby on Rails rather than the Java stack (junkyard?) that we were using. At the time, I did not really participate in the discussion except to note that everything seemed to be at least 5 times too difficult. I had this strong intuition that there were so many moving parts that that was the problem. The application itself was not really that hard. My assertions really ticked some of my colleagues off; for which I apologize; sort of. I guess that I come from a tradition of high-level programming languages, by high level, I would say that I would consider LISP to be a medium level language, and Prolog is slightly better. I would say that it is a pretty common theme of my career that I end up having to defend the position of using high-level tools. I have gotten a number of arguments, ranging from "it will not be efficient enough" to "how do you expect to find enough XX programmers?". I u...