Hacker News Reader

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.

View 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.

What 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.

Reply on news.ycombinator.com