Those who have watched the critically acclaimed "Egel - The Movie" (8 upvotes on lobste.rs) know that I've been dabbling with a small rewriter with a trivialized semantics. The observant viewer might have noticed an off-the-cuff remark in that movie that Egel, since it rewrites, has less need for tail-call optimization, some stuff comes for free.
Let's revisit a small recursive function, factorial: fac 1 = 1 | fac n = n * fac (n-1).
Those who know some compiler theory will know the runtime behaviour of that function if implemented according to the Algol convention for stack machines: for every invocation, a stack frame is created with a dynamic and static link and some space for local variables. The program will subsequently perform its operations within the context of that frame, and for each recursive call, a new stackframe is pushed to the stack.
Egel in contrast, will rewrite a redex to another number of redexes. For a stack machine that corresponds to removing the callee's stack frame entirely and pushing several stack frames with work to be done to the stack. Hence my remark that there's less need for tail-call optimization, for simple recursive functions that consume constant stack space you get that for free. Also noteworthy, tail-call optimization module cons comes for free too.
And that begs the question of whether other calling conventions are wrong, at least for ML-like languages.
Queue: They might be wrong but at least they're fast! Could also be named: Is TCO a stop-gap solution for having the wrong calling convention.
ReplyDeleteProbably boils down to: the Algol convention is compact and efficient. But don't try to reclaim a property you lost in translation.
ReplyDelete