3 ms·
Not just self-recursion, but all recursion, including transitive mutual recursion. I think it may be possible to do this via strictly lexically-scoped symbols (
by kibwen 9y ago
Not just self-recursion, but all recursion, including transitive mutual recursion. I think it may be possible to do this via strictly lexically-scoped symbols (so imagine C with no forward declarations). Might still be ways to sneak recursion in there though.
- scatters 9y agoThat's what fix point combinators are for. The Y combinator won't work in a language like C++, but the Z will work fine. For example, here's Z in C++14, used to compute 5 factorial: https://godbolt.org/g/se5B8u https://godbolt.org/g/se5B8u
- kibwen 9y agoYeah, I specifically had combinators in mind when considering ways to sneak recursion in. :P And it occurs to me you'd have to forbid function pointers too.
- greiskul 9y agoYup, and you would probably not be able to do Object Oriented Programming either (or have to limit it horrendously), cause an object is similar to a closure, and you therefore can use it for unbounded recursion.
- nine_k 9y agoYes, I meant any recursive calls via a chain of calls to other functions. I think proving that no recursion exists should be relatively simple, just keep following the call graph and keep a set of the nodes (functions) called; you either reach the terminal node(s), or reach an already-visited node again, which means a recursion exists.
- soberhoff 9y agoWhat if functions are first class? Then imagine a function gets passed in as an argument and called. You won't know what function you're calling until runtime.