Avoiding turing completeness requires either very very careful design OR (trivially) a hard limit on size/iterations the compiler is allowed to make (a sufficiently small limit, obviously we call many things turing complete colloquially that have very low limits anyway like 8-bit cpus with ~kb of memory)
Basically, the expressiveness of a language is unrelated to it being Turing complete. And is much more relevant for most conversations.
it's actually very hard to avoid in a system that is supposed to do some sort of computation.
Which is a terrible outcome, and isn't a problem for nearly any other language save C++.
Avoiding? Why would you want to avoid it? Guaranteeing that a compiler halts on any input is not something that is necessary in practice, and it restricts the amount of processing that can be done on the code during compilation.
I think its restrictions are that it only allows forward jumps and a limited amount of instructions.
So the property "not Turing complete" does not give you anything practical.
A better approach is to have a scheduler which is fair, and which gives the compiler the cycles it deserves, even if it needs many of them.
Secondly, the eBPF constraints put the language even lower in the hierarchy than regular expressions.
The code is executed inline when filtering packets, instrumenting system calls and to prefilter kernel probes for user space. It has to be really fast, i.e. execute in a bounded amount of time.
However, Turing-incomplete sublanguages can be very helpful in practice, for the same reason that a `for` loop is very helpful even though it is not essential and we can solve all of our problems with `goto` which is ultimately what our compilers generate anyway. Why do most people prefer `for` to `goto`? because with the former, you pick up a writer's discipline which makes it harder to create infinite loops and to accidentally miss parts of the data structure.
Well, in any Turing-incomplete subset, it is impossible to make an infinite loop and usually very hard to miss parts of the data structure (since there is usually only a few ways to enter that data structure that the computer can prove won't halt) -- and, if you want, you can build tooling which checks your algorithms to guarantee these things. It guarantees that even any recursive handling you do with the data structure is not going to be infinite.
With that said, there are some examples of perfectly valid algorithms which don't nicely support that sort of structural recursion, e.g. if you can "jump down" to a much smaller (and sometimes hardly-related) data structure rather than incrementally descending into it. A great example of this is the GCD algorithm,
function gcd(x, y) {
if (y < x) {
return gcd(y, x);
}
return x == 0 ? y : gcd(y % x, x);
}
We can easily prove that this halts for positive integers by simply looking at the second parameter; each recursive call makes it strictly closer to 0, which means that it must hit 0 and stop recursing. But a Turing-incomplete subset would probably balk at both of the recursive calls, if, say, we tried to encode integers as lists of booleans to get a "binary"-ish representation: it will say "hey, you can't recurse on gcd(y, x) or gcd(y % x, x), because you're supposed to be going in gcd(x, y) from x to a substructure of x, but y and y % x are not substructures of x!"You might be able to do it by encoding everything as a list of nulls and then first invoking some sort of decrement-increment step to swap x and y, then doing something similar for the modulus, but it means that your runtime might be something like min(x, y) * max(x, y) or something -- ugly.
On the other hand, the language built into Bitcoin [2] was deliberately designed not to be Turing complete. This avoids problems in deciding if a transaction is valid or not.
[1] http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/...
Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.
Alan Perlis
Being Turing complete or not is an intrinsic quality of the type system which has not been shown to have any effect whatsoever on the effectiveness of a language. Similarly, being more or less expressive, being sound or not, supporting subtyping or not, are intrinsic qualities that have not been shown to have either a positive or a negative effect. Those are all true properties -- like Coke cans being red -- but they cannot be assigned good/bad judgment other than in people's personal preferences -- until, that is, someone actually starts collecting data.
> And the "FUD" is nothing more than the very real reality that many teams find those language far too clever for their taste.
I've heard people literally say "we shouldn't use Scala because its type system is Turing complete" (in an organization that was already using Java). I call that FUD.
I agree, but we still don't know which side has the advantage and how big the effect is. I believe that if we somehow control for all other factors, the effect of linguistic features is very small, but that "simpler" languages like Java/Kotlin would have the (small) advantage over "complex" ones like Scala. I can support this from personal experience (and also for theoretical reasons), but I can't prove that. You likely have a different experience (and other theoretical justifications), but can't prove your conjecture, either.
> I call that FUD.
I call that silly. It's just as silly as using intrinsic features as a positive. We shouldn't use Scala for a hundred reasons, none of them having to do anything with the formal language acceptable by its type system. ;)