undefined | Better HN

0 pointscomex6y ago0 comments

Of all the bugs you've ever dealt with in programs in general, what fraction of them of them were infinite loops?

For me I'd guess maybe... 0.1%? It's definitely under 1%.

Given that, it makes no sense to me that I'd want to make myself jump through hoops to express some basic coding patterns [1], just to rule out that single class of bugs. It seems like a solution in search of a problem.

[1] https://github.com/dhall-lang/dhall-lang/wiki/How-to-transla...

0 comments

2 comments · 1 top-level

jose_zap6y ago· 1 in thread

I think the Non-Turing completeness is misunderstood as "no infinite loops!". Of course, that's the obvious effect of not having it, but it has more important effects:

1. Any expression can be normalised at compile time. This means that you can remove all abstractions in your code and audit the result before running it. This is great of debugging and understanding a codebase you may not be familiar with.

2. You can be sure that the language cannot do a jailbreak and potentially read files or make network calls it was not supposed to. Not because the Dhall developers are security geniuses but because it is literally impossible without Turing completeness.

An example of a NT complete language that you would hate if it could read a file in your system and send it to attackers is Regular Expressions, for example.

3. It helps the language stay focused. This limitation is the biggest motivator to keep the language being focused on a single domain, and not try to be everything. This also helps execution performance of the language.

jholman6y ago

I feel like you've made in "inverse error" here repeatedly.

If a language L1 is Turing complete then you have some potential liabilities: there's no general normalization plan, you cannot in general ensure security guarantees, etc. But another language, L2, might be not-Turing-complete and still have all the same problems. It may especially be the case that L2 has no known normalization algorithm, or no known general security audit.

For example, many interesting properties are undecidable for the general case of context-free languages (a class that I'm sure you know is much more restricted than the class for Turing-complete languages). For example universality is undecidable in this class, as is language equivalence. As for being sure that the language cannot do a jailbreak, you can't be sure until you write a proof. It's nice that Godel isn't telling you that no such proof can possibly be written, but that's still a long way from having a proof.

I agree with you that this sort of thinking seems to be why people say that they do not want certain languages to be Turing-complete, but I'm not at all convinced that those people have correctly named the property that they want.

j / k navigate · click thread line to collapse