Tail recursion

["Stefano Lanzavecchia" <stf@...>]

Roberto says:

> To optimize this
> opcode as a "real"
> tail call (and avoid exiting the luaV_execute function), you
> must check at
> run-time whether what you are calling is a Lua function (or a
> recursive
> call).

That's no problem. My scheme for calling functions in the stackless
implementation required luaV_execute to exit on CALL, TAILCALL, END and
RETURN and it's luaD_call which handles the situation. What I was trying to
say (sorry for my being so unclear) is that normally a tail call does not
need a new stack frame, whereas it would appear that in Lua it does (surely
it does in the way luaV_execute is implemented in the standard
distribution). This is not much a matter of speed, but more a matter of
space: normally tail calls are used to write expressions such as
(pseudo-code):

def factorial(n,acc) =
	if (n=1) return acc
	else return factorial (n-1,acc*n)
enddef

factorial (1000,1)

This definition in many languages (all of the functional programming
languages starting from Scheme) will not use the stack at all, since the
tail call can be implemented in such a way that the stack frame in use when
factorial(1000,1) is executed can be re-used to execute factorial
(999,1000*1). In Lua this will use the stack and I could not find a way,
even in my stackless implementation where instead of the C stack, an array
of structure is used, to re-use the current stack frame. It seemed that
somehow the way the code is compiled by Lua, it expects that stack frame to
be there (for upvalues maybe?). Every time I tried to re-use the current
stack frame (which also meant to cleverly re-arrange the VM stack), the
interpreter would get stuck in an infinite loop (OP_TAILCALL ended up
calling the wrong function).
Sorry if I am reporting trivial things, known to everybody here. I just did
not know another way to express myself.

Sabby adds:

> Well, tailcalls have been my worst case in making Lua stackless.
> Since they basicly do the job of a call and a return in the same
> opcode, this tends to go agains making lua stackless. So what i did,
> was to add a flag fiels to the state of the Lua VM, that i push on
> calls. One of thoes flags indicate, that we are on a tailcall, so
> when i return from the call, i then see the flag indicating that it
> was not an ordinary call but a tailcall, so i simulate another
> function return to carry down the parameters.

Right. That's how I did it in the end. But in the process I "wasted" a stack
frame.

Finally Roberto comments:


> If it is so bad, you can avoid this opcode. Just remove this code from
> lcode.c:

Since as far as stack occupation is concerned the semantic of a TAILCALL is
the same of a CALL, this is probably the best solution, for me at least.

Thanks everybody.
--
WildHeart'2k - mailto:stf@apl.it
Homepage: http://come.to/wildheart/

<<<Yake sou na  kimi no Mystic eyes ---
   It's like they're burning, your Mystic eyes>>>