3 ms·

It's best to call it "Tail Call Elimination". It's not a nice-to-have optimization in Scheme as using tail calls is the only way to iterate (do is a convenience

It's best to call it "Tail Call Elimination". It's not a nice-to-have optimization in Scheme as using tail calls is the only way to iterate (do is a convenience built on tail calls), it's a necessity for any non-toy Scheme implementation.

kazinator 3y ago
Tail call elimination isn't a very good term. - The only optimization that completely eliminates calls is inlining, so it is misleading. An optimized tail call still has some trappings of a call, like a control transfer somewhere else, with arguments. - In Scheme lingo, the procedure calls so optimized are called tail calls; they are produced, and thus not eliminated. When the goto is taken, the procedure is said to be making a tail call, or tail calling. In assembly language, if you hand coded such a goto, you might put in a comment saying "this is a tail call", so it's not just Scheme lingo.
- soegaard 3y ago
  You know this, but being explicit helps the casual reader: The "elimination" in "tail call elimination" refers to the "elimination" of the call frame. In languages like C each call pushes a frame to the call stack. When the called procedure is done, execution returns to the site of the call. In a tail call there is no work to done, so the frame is now removed and execution continues where the previous frame points. But ... if we simply never omit the call frame, then executation then exectuation automatically returns to the parent frame. The spec talks about allowing an "unbounded number of active tail calls". In an implementation with frames, it means tail calls can't just keep pushing frames. Seen in isolation "tail call elimination" doesn't seem like a big deal, but combined with "real macros" (structural, scope-respecting macros) it is possible to implement control structures as a user without worrying about stack overflow.

kazinator 3y ago

Tail call elimination isn't a very good term. - The only optimization that completely eliminates calls is inlining, so it is misleading. An optimized tail call still has some trappings of a call, like a control transfer somewhere else, with arguments. - In Scheme lingo, the procedure calls so optimized are called tail calls; they are produced, and thus not eliminated. When the goto is taken, the procedure is said to be making a tail call, or tail calling. In assembly language, if you hand coded such a goto, you might put in a comment saying "this is a tail call", so it's not just Scheme lingo.

soegaard 3y ago
You know this, but being explicit helps the casual reader: The "elimination" in "tail call elimination" refers to the "elimination" of the call frame. In languages like C each call pushes a frame to the call stack. When the called procedure is done, execution returns to the site of the call. In a tail call there is no work to done, so the frame is now removed and execution continues where the previous frame points. But ... if we simply never omit the call frame, then executation then exectuation automatically returns to the parent frame. The spec talks about allowing an "unbounded number of active tail calls". In an implementation with frames, it means tail calls can't just keep pushing frames. Seen in isolation "tail call elimination" doesn't seem like a big deal, but combined with "real macros" (structural, scope-respecting macros) it is possible to implement control structures as a user without worrying about stack overflow.