Re:Spectre and the end of langsec
by kibwen on Thursday January 11, 2018 @01:11PM
(#16126156)
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.
[ Parent
| on HN ]
That'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
Yeah, 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.
Yup, 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.
Yes, 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.