Tailcalls. Was Re: Manual timeslicing the VM.

[Rici Lake <lua@...>]

On 5-Aug-05, at 10:02 AM, Mike Pall wrote:

> > [... hooks don't have call frames...] Personally, I think that's a 
> > bug.
>
> Well, others might conclude it's a feature. At least it's
> slightly faster for things like count hooks.

I suppose it is slightly faster. But I doubt that it's much faster, and 
it has some serious consequences if you actually try to do anything 
which involves the lua stack in a counthook. I would personally trade a 
little speed for the robustness of having a real stack frame.

Wim wrote:

> I think it was added to not break getfenv(stack_level)
> behaviour if the call chain included some tail calls.

Yes, I think that's true. As Wim knows, I don't much care for
{get,set}fenv(stacklevel); it can only be used for bizarre
hackery (imho). Others may differ, of course :) In any event,
the equivalent C api will work because C functions never get
tail called (although that might be considered a wart, as well.)

As Mike points out, the phantom frames are not much use for
debugging since they contain no information. It might even
be argued that they hinder debugging, since programmers who
are aware of tail-calls, and write their code accordingly,
may not want to be distracted by the phantom frames, and may
even find that they make it harder to access the information
really desired (information about the real caller, for example.)
In the case of a state machine implemented through tail calls,
which is, I believe, a standard Lua idiom, there end up being
an enormous number of tail calls, all of which are "expected".

Even some C programmers count on tailcall optimisation: a change
I proposed to Apache some time ago, which would have defeated a
non-recursive tailcall optimisation, was rejected (amongst other
reasons) because the tailcall optimisation in question "reduced
noise on the debug backtrace". (I actually agree with that
judgement, although I thought that the benefit outweighed the
inconvenience.)

However, there are times when it is useful to have access to
deleted frames during debugging. The easiest solution to this
would be to be able to flag closures as non-tailcallable. (Since
C functions are non-tailcallable, the VM almost supports this;
it would only require the addition of a flag bit to the closure
object which could be tested by luaD_precall, which would add
another case to the implementation of OP_TAILCALL, something
like:
  case PCRLUA_NT: { nexeccalss++; goto callentry; }

This would also solve the getfenv "problem":
  myhack = nontailcallable( function()... end )
where nontailcallable is a library function which sets the
nontailcallable bit in the closure.

Another solution, which I've seen proposed for other languages,
is to maintain a fixed-size circular stack frame buffer, and
move deleted stack frames onto it. This is only useful for
debugging, and imposes quite a bit more overhead than the
nontailcallable bit, but it has a certain charm anyway.