In my search for a practical non-turing complete programming language, I've been paying attention to lambda-calculus with disallowed self-application - that is,
x x forbidden. After taking that language and augmenting it with lists and the
range operations, pretty much any algorithm I've tried so far is implementable. It is trivial to implement
zip and many others - foldl replaces the need for recursion.
Can you think in any practical, important algorithm that would be undoable in that language?
It is no coincidence that all of them use self-application—the application of an expression to itself. It is through self-application that repetitive computation can be simulated in the lambda calculus. Indeed, the third of the previous three examples is famous because it can encode recursive function deﬁnitions.