Comment Re:you have no idea what you're talking about (Score 1) 1270
The undecidability if two random programs are equivalent it does not mean that there is no algorithmic way to do the transformation. It would mean that ANY transformation is impossible, which is, of course silly.
You can have operators which maintain the equivalence of the program, you can have series of that operators etc. For any program you can generate a lot of equivalent programs (which is what all the optimizers do).
But I think that this overwhelming effort to get rid of the stack is a bit misdirected. At the big picture level the question is how big the stack will be, more exactly what is the spatial complexity of the problem. And now there, indeed you have some hard limits, which depend on the problem, not on your algorithm.
You can have operators which maintain the equivalence of the program, you can have series of that operators etc. For any program you can generate a lot of equivalent programs (which is what all the optimizers do).
But I think that this overwhelming effort to get rid of the stack is a bit misdirected. At the big picture level the question is how big the stack will be, more exactly what is the spatial complexity of the problem. And now there, indeed you have some hard limits, which depend on the problem, not on your algorithm.
