3 ms·
Hmm, wouldn't it be better to prove that the optimizations on a loop can also be performed on a recursion and then applying it? If they can't do that, how can t
by ambicapter 1y ago
Hmm, wouldn't it be better to prove that the optimizations on a loop can also be performed on a recursion and then applying it? If they can't do that, how can they take the optimized loop, turn it back into a recursive structure, and assume that it is functionally identical to the starting recursive loop?
- fluoridation 1y agoPresumably because each transformation step preserves semantics. What I'm wondering is what the point of the round-trip conversion is. If you've gone to the trouble of turning a function into an iteration, just leave like that.
- Spivak 1y agoMy guess would be because the transformation would be a user-visible change. If they produce a stack trace inside it wouldn't look as they expect.
- ambicapter 1y agoThat's my question, if each transformation step preserves semantics, how come they can't apply the optimization on the recursive form? I'm asking seeking clarification.
- fluoridation 1y agoIn general, proving things about recursive functions is more difficult. I could be wrong, but I think for example control flow graph builders usually stop at function boundaries, to keep the problem tractable. Turning a recursive function into an iteration makes it so you can see the whole execution as a single call, instead of having to hop around a virtual call stack. What I'm wondering is how they're able to turn the optimized form back into a recursive function. Surely there must be some recursive functions that if you optimize them they turn into simple loops or even a linear function is they're very bad.