RE: Confused about proper tail calls

["Tai Meng" <tmeng@...>]

Thanks for this wonderful email! I'll put it on my list of to-do's and let you know how it goes,

Tai

-----Original Message-----
From: RLake@oxfam.org.pe [mailto:RLake@oxfam.org.pe]
Sent: Wednesday, October 01, 2003 1:09 PM
To: Lua list
Subject: RE: Confused about proper tail calls


In the ongoing saga of tailcalls, Tai analyzes:

> If function B made a tail call, Lua seems to skip over its
> activation record in two different ways (when calling lua_getstack()).

> Case 1: If function A called (not a tail call) function B,
> and function B made tail calls, info about function B is lost.
> However, lua_getstack() returns 1 for function B anyway, so that
> we can eventually get to the activation record of A.

> Case 2: On the other hand, if B was the main chunk (and no
> function called it), and B made a tail call, lua_getstack()
> will return 0 for B because there are no more functions to
> return to after we come back to B.

That is my analysis, too. 

> I still wonder if there is a known patch to treat both
> cases like case 1. Case 1 allows the display of a complete
> call stack (though missing information), which is good
> to have in a debugger. 

At the risk of being obvious, my suggestion would be to ensure
that the script doesn't execute in the base execution frame.
That could be done very easily; instead of calling the script,
call a function which calls the script.

static int doit(lua_State* L) {
  return lua_call(L, 0, LUA_MULTRET);
}

I'll leave you to work out the usage mechanics :)

However, the whole thing raises a semi-philosophical question.
All this is fine if we are just thinking of tail calls as an
optimisation, but that is not necessarily the case. It may be
that tail calls are essential in order to keep storage usage
constant. For example, the program I may be debugging might be
a state machine which uses tail calls for state transitions.
Or it might be a "recursive" function which I am counting on
being optimised into a tail iteration. In these cases, I as
the programmer am fully aware of the fact that I am tailcalling,
and I do not want the debugger to fake a non-tailcall, because
that just obscures what is going on.

My recommendation has been, for some time actually, that tail
calls should just be tail calls, and that there should be a
way of disabling them for people who want that (for example,
during debugging). This could be easily accomplished in a number
of ways, one of which is to simply run through the compiled
VM code and change all the TAILCALL opcodes to CALL opcodes
(this is perfectly safe, because the Lua compiler always
follows a TAILCALL with a "redundant" return; only Lua functions
are tailcalled and it is not known at compile time whether the
function called is a Lua function or a C function.)

An even simpler alternative is:

1) change line 639 of lvm.c,
which currently reads:
          if (GET_OPCODE(i) == OP_CALL) {  /* regular call? */
to
          if (GET_OPCODE(i) != G(L)->tailcallflag) {  /* regular call? */

2) at line 115 (or so) in lstate.h, add the definition:
  OpCode tailcallflag;

3) somewhere in lapi.c, add the following little api:

LUA_API int *lua_enabletailcalls (lua_State *L, int yesno) {
  lua_lock(L);
  OpCode old = G(L)->tailcallflag == OP_TAILCALL ? 1 : 0;
  G(L)->tailcallflag = yesno ? OP_TAILCALL : 0;
  lua_unlock(L);
  return old;
}

4) declare the api in lua.h (probably line 346):

LUA_API int lua_enabletailcalls (lua_State *L, int yesno);

5) in lstate.c, somewhere around line 96, initialise tailcalling to on:
  g->tailcallflag = OP_TAILCALL;

6) Document the API in the manual, in the debugging section, perhaps on
   page 35 just before the description of the lua_Debug structure:

   Lua normally optimizes tail calls into a direct jump to the called
   function, which effectively releases the local variables used by
   the calling function. In some cases, it may be useful to prevent
   this optimisation in order to retain complete activation records
   during debugging. You can enable and disable the tail call
   optimisation by calling
      int lua_enabletailcalls (lua_State *L, int yesno);
   This function enables tail calls if yesno is any true value, and
   disables them if yesno is 0. It returns the previous enabled state.
   A newly initialised lua_State has tail calls enabled.

Now, personally, I would then ditch all the machinery put in to detect
and fake tail calls, which would more than compensate for the slight
extra overhead created by the above patch.

But that's just me.

Rici