Reference: Deconstructing Functional Programming
Because if you think about it, the stack itself is just an optimization. Right? There are these frames which contain information about each invocation. Each stack frame. Each activation record. And that’s what they are–they’re activation records. They’re sort of objects. If you really have objects on the brain, like I do, then you realize that they’re all just objects.
And they should be treated uniformly. You can even build a language that works this way–as I have. If that’s the case, this is really a garbage collection problem. Right? Your stack traces might go away if you don’t need them. You do need them when it’s not a tail call because you need to go back there and use that information. But if it’s a tail call, you don’t need them, you don’t need a tail call back to that frame. You need a pointer back to the last frame that wasn’t a tail call. And they might get collected.
Which doesn’t mean you actually have to implement it that way. Erlang sort of does. And there are many implementations that do that. They are not noted for their speed. If you can have real stacks, what happens when you run out of space? If you don’t run out of space, it didn’t really matter if you optimized the tail calls or not.
When you run out of space, you should GC the damned stack. You shouldn’t just throw up your hands and say you’re dead. And for all the normal programs that people write where it didn’t matter, they won’t care. And for your tail recursive programs, well, they might be a bit slower, but they will work. And then it’s a matter of flags to the garbage collector if in production you don’t want to debug it if you’re sure it’s all going to be fine–then go ahead and tell it to don’t bother and just slam it and overwrite those frames directly.
Why is this so hard for implementers to do? Optimization is an optimization and should be optional.
It’s a cool algorithm, but there’s nothing nice that I’m prepared to say about Hindley-Milner.
He nails a lot of things I didn’t like about Haskell.
All in all, this talk gets a lot of things right.