4 ms·
This reminds of an old idea of a friend of mine, who said that pure, unrestricted recursion (this applies to iteration as well) is like goto: a primitive too po
by snrji 8y ago
This reminds of an old idea of a friend of mine, who said that pure, unrestricted recursion (this applies to iteration as well) is like goto: a primitive too powerful and not abstract enough that should not be directly exposed to the programmer in a high level language. This post shows that there's an additional reason for avoiding explicit recursion when possible: performance. Sure, you can define any function by using recursion, but the compiler won't be smart enough to parallelize it.
Does anyone know if a language with only high order functions like map, reduce and others could be Turing complete? Probably 80-90% of cases would fit in the schema of some predefined functions like scanl. My intuition is that for some cases you would still need explicit recursion or iteration, for instance if you wanted to loop forever or until a certain condition is met, but perhaps these cases could be modelled with some special high order functions as well, or with explicit infinite recursion as in Rust's 'loop'.
- Athas 8y agoYou need some form of unbounded while loop for Turing completeness, but it can take many forms.
- snrji 8y agoI see, but you could still wrap all other cases in some predefined functions or higher level primitives, and just have an "unsafe" mode for unrestricted recursion. It could even be treated as a side effect.
- Athas 8y agoSure, and you can use things like co-recursion, which is how Agda (a total language) models potentially non-terminating computations. It means that while you can run forever, you need to perform productive work within finite time. As an example, consider producing an infinite sequence of items, but where each item is produced in finite time. Also, in a high-performance setting, a surprising number of programs do not need recursion (and hence Turing-incompleteness) at all. In the vast majority of the Futhark programs I've written, `while` loops are either not used at all, or used for something fairly simple like an outermost convergence loop (and typically with a iteration bound anyway, so it could be written as a `for` loop with early exit).
- snrji 8y agoI see, thanks for your comment.