[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Confused about proper tail calls
- From: "Tai Meng" <tmeng@...>
- Date: Mon, 29 Sep 2003 17:26:10 -0700
Hi, I'm trying to understand how proper tail calls work in conjunction with the Lua debug interface.
I'm having difficulties understanding this paragraph from section 2.5.7 of the Lua 5.0 user manual:
> Lua implements proper tail calls
> (or proper tail recursion): In a tail call, the called function reuses the stack entry of the calling
> function. Therefore, there is no limit on the number of nested tail calls that a program can execute.
> However, a tail call erases any debug information about the calling function.
I originally understood this as: when function A makes a proper tail call to function B, the stack containing A's activation record is *replaced* by that of B (since A's stack entry is reused). However, this does not seem to be true. When I ran a script containing a recursive function, this is the call stack I got:
========= CALL STACK ============
Function 0: myth() @../../scripts/factorial.lua, line: 3
Function 1: made tail call so its info is erased by Lua.
Function 2: made tail call so its info is erased by Lua.
Function 3: made tail call so its info is erased by Lua.
Function 4: made tail call so its info is erased by Lua.
Function 5: made tail call so its info is erased by Lua.
Function 6: main() @../../scripts/factorial.lua, line: 7
===== END CALL STACK ============
So, main() -- the main chunk -- called myth(), which called itself several times. I had expected only 1 stack for myth(). But having not observed that, I placed a conditional in the code, so that if the activation record retrieved by lua_getstack() had its attribute 'what' equal to 'tail', I output the message seen beside functions 1 to 5.
My call stack code is simplified below, and the Lua script is further below. Am I doing something wrong? Or is this a known functionality of Lua?
Thanks a lot,
Tai
---- call stack display code ------
void DisplayCallStack( lua_State* L, lua_Debug* ar )
{
while ( lua_getstack( L, level, ar ) == 1 ) // 1 = success
{
if ( lua_getinfo( L, "Sln", ar ) != 0 ) // no errors
{
// print out info about current stack.
// if ar->what == 'tail', output tail call message
}
level++;
}
lua_getstack( L, 0, ar );
// return to the state before this function call.
}
---- myth.lua ------------------
function myth( n )
if n == 0 then return 0 end
return myth(n-1)
end
s = myth(5)