Re: Proper tail recursion

[ramsdell@... (John D. Ramsdell)]

Roberto,

I studied the sources carefully, and think I see the two changes
needed to make the implementation properly tail recursive.  I believe
one of the changes is important to make even if the implementation is
not modified to be properly tail recursive.  I'm sure I don't have a
deep understanding of the interpreter, so I could be on the wrong
track, but I'm sure you'll correct any misunderstanding I introduce.

As I understand it, the control stack for the interpreter is kept in
the C runtime stack, and the argument stack is in the lua_State
object.  To make the Lua bytecode interpreter properly tail recursive,
one must make sure that garbage stack frames are purged from both the
argument stack and the C runtime stack.

To eliminate garbage stack frames from the C runtime stack, the
function luaV_execute in lvm.c must be changed.  The case for a tail
call is currently:

      case OP_TAILCALL: {
        L->top = top;
        luaD_call(L, base+GETARG_A(i), LUA_MULTRET);
        return base+GETARG_B(i);
      }

or abstractly:

      case OP_TAILCALL: {
        Get the real function to be executed;
        if (executing a Lua function) {
          call the interpreter with the Lua function;
        }
        else {
          call the C function;
        }
        return args;
      }

This must be changed to become something that behaves differently when
calling a Lua function.  In particular, rather than recursively
calling the interpreter as it does now, it must restart the
interpreter in its current stack frame so that no garbage frames are
added to the C runtime stack.  Abstractly, the case for a tail call
should be:

      case OP_TAILCALL: {
        Get the real function to be executed;
        if (executing a Lua function) {
          initialize the interpreter;
          goto the interpreter start point;  /* Don't call the interpreter! */
        }
        else {
          call the C function;
          return args;
        }
      }

I strongly suspect this optimization will be beneficial even if no
other changes are made to the interpreter.  The change replaces a C
function call with a goto and eliminates garbage stack frames from the
C runtime stack.  Since the TAILCALL opcode is executed often, this
should result in a faster bytecode interpreter.

The final change needed to make the implementation tail recursive is
to remove the arguments of the function making the tail recursive call
by overwriting them with the arguments of function being called tail
recursively.

      case OP_TAILCALL: {
        Get the real function to be executed;
        Remove garbage values from the argument stack;
        if (executing a Lua function) {
          initialize the interpreter;
          goto the interpreter start point;  /* Don't call the interpreter! */
        }
        else {
          call the C function;
          return args;
        }
      }

The section that removes the garbage from the argument stack could be
added or removed via a compile time variable making it easy to select
either mode.  In this way, it would be easy for people to try Lua both
ways and decide if the debugging and subtle behavior you worry about
are real issues.

John

Roberto Ierusalimschy <roberto@inf.puc-rio.br> writes:

> > It is very easy for a compiler to identify tail calls in a Lua source.
> 
> Yes, it is. But as I said before, a tail call will not always executes as a 
> "proper" tail call, because of C functions.
> 
> Again, it is easy for the interpreter to test whether the called function 
> is C or Lua, and act accordingly. The real problems I see for tail calls in 
> Lua are
> 
> 1 - debugging. Many Lua users do not even know what is a tail call, and
> expect to see them in a stack trace.
> 
> 2 - subtle behaviour. "return f()" is a proper tail call (*if* f is a Lua
> function), but "return x, f()" and "f(); return" are not. This can be
> quite confusing for programmers assuming proper tail calls.
> 
> -- Roberto