Within a language like the Calculus of Coinductive Constructions like Morte appears to implement it's not such a strange idea to have normalization.
So, no infinite loops means no Halting Problem means no completeness.
The upside is a larger set of easy-to-perform optimizations, much greater mathematical elegance. The downside is that you cannot directly write an interpreter for a complete language. Though you could write one which halts every N steps and requires user input to continue. In practice, that isn't the worst idea for a repl anyway.
There are a number of general examples, though.
1. You can leave termination guarantees in foreign code up to the programmer using an "unsafe" marker.
2. You can model effects using a monad
3. You can model the whole program as codata which is "driven" by the runtime
4. You can write a compiler of an embedded language in CIC and execute complete programs in, say, C
I believe this is the case. So the article's promise (as I read it) can not hold true in the general case.
On a similar note, just write a program that runs the collatz conjecture and prints the result and a program that prints 1. Run them through Morte. If they compile to the same code, then boom, you've solved the Collatz conjecture :)
http://en.wikipedia.org/wiki/Calculus_of_constructions (What morte is based on)
and
http://en.wikipedia.org/wiki/Normalization_property_(abstrac...
answers the point on Turing completeness.
My concern on the practicality point is that the superoptimizer here really isn't "superoptimizing" so much as super-simplifying. There's a reason modern compilers don't aggressively inline every single function called if they have access to the source code, and for the same reasons they don't aggressively unroll every loop they come across if the loop bounds are known compile time.The tradeoffs of such optimizations are very complicated and hard to reason about because processors are very complicated and hard to reason about.
Nothing prevents a turing complete program from entering an infinite loop. A GUI program for example is terminated only when the user decides to, which is impossible to predict.
Yes, this is my point: the proposed super-optimiser would, it seems to me, en passant be solving the halting problem, which means that it can't actually exist (or, at least, can't actually satisfy the stated guarantee).
> Nothing prevents a turing complete program from entering an infinite loop. A GUI program for example is terminated only when the user decides to, which is impossible to predict.
On the level of the lambda-calculus, this is reflected in the corresponding term's having no normal form, in which case the algorithm described (which relies on reducing everything to a normal form) cannot do anything with it.
I suspect that I've got some bad conceptual misunderstanding here; but, on the other hand, I also have a hard time believing that, if beta- and eta-reduction alone were sufficient to express such powerful optimisations, it would have taken this long to discover that.