Re: Tail Calls for C Functions

[David Manura <dm.lua@...>]

On Tue, Aug 31, 2010 at 6:17 PM, Patrick Donnelly <batrick@batbytes.com> wrote:
> Has there been any thought to adding tail call support to the Lua C
> API? Something like this I would assume: return lua_tailcall(L, n);
> ...this would help with projects like Lua To Cee [1]

Just a few comments, as the author of lua2c (LuaToCee version)...  The
5.2.0 (work4) enhancements can eliminate some or most of the current
limitations in lua2c, as now mentioned on the wiki page [1].  Even if
you don't care about lua2c, I think this fact, that almost all Lua
code can be translated naturally into C API code, provides some
measurement of the increased expressiblility of the Lua C API and is a
positive sign on Lua 5.2's direction.

Support for tail calls in C, however, remains absent.  Your
suggestion, I suspect, will fix the problem and doesn't necessarily
seem difficult to implement if one chooses.  On a search, I saw a
brief suggestion for a "lua_tailcall" here [2], but the problem it was
originally intended to address--yield across pcall--is resolved in
5.2.0-work4.  It presently remains the case, however, that you can't
implement a Lua C function that calls another Lua function but doesn't
increase the stack level.

You can, however, wrap a C function in a Lua function that in turn
performs the tail call.  Appendix A below is an illustration of the
tail-call form of the factorial function reimplemented in terms of the
C API.  So, that approach could probably be taken to implement
functions with tail calls in lua2c.  It's not ideal though, not just
for overhead reasons.  Unlike in your lua_tailcall idea, the stack
levels here will be increased a few levels in the C function by the
Lua wrapper, so code involving things like the level parameter in
error calls will not be right.  OTOH, I've expressed a number of times
before that code relying on Lua stack levels is problematic [3], and
this includes things like error/getfenv/setfenv.

[1] http://lua-users.org/wiki/LuaToCee
[2] http://lua-users.org/lists/lua-l/2004-10/msg00158.html
[3] http://lua-users.org/lists/lua-l/2010-01/msg01255.html

== Appendix A ==

#include <stdio.h>
#include <lua.h>
#include <lauxlib.h>

/*
  function fact(n, acc)
    acc = acc or 1
    if n == 0 then return acc end
    return fact(n-1, n*acc)
  end
*/
int factc(lua_State * L)
{
  double n   = luaL_checknumber(L, 1);
  double acc = luaL_optnumber(L, 2, 1.0);
  /*printf("DEBUG:fac:n=%g,acc=%g\n", n, acc);*/
  if (n == 0) {
    lua_pushnil(L);
    lua_pushnumber(L, acc);
    luaL_dostring(L, "print('DEBUG:stack:\\n', require'debug'.traceback())");
    return 2;
  }
  else {
    lua_pushvalue(L, lua_upvalueindex(1));
    lua_pushnumber(L, n-1);
    lua_pushnumber(L, n*acc);
    return 3;
  }
}

int main()
{
  lua_State * L = luaL_newstate();
  luaL_openlibs(L);

  /* local function fact */
  lua_pushnil(L); /* fact */
  lua_pushcclosure(L, factc, 1);
  luaL_dostring(L,
    "local function tapply(f, ...) if f then return f(...) else return
... end end\n"
    "local function wrap(cf) return function(...) return
tapply(cf(...)) end end\n"
    "return wrap"
  ); /* wrap (function that performs tailcall in Lua) */
  lua_pushvalue(L, -2);  /* factc */
  lua_call(L, 1, 1); /* wrap(factc) */
  lua_pushvalue(L, -1);
  lua_setupvalue(L, -3, 1); /* fact = wrap(factc) */

  /* local y = fact(x) */
  lua_pushnumber(L, 1000000.0);  /* x */
  lua_call(L, 1, 1);
  printf("y=%g\n", lua_tonumber(L, -1));

  return 0;
}