ANN: sleep() patch for Lua 4.0

["Thatcher Ulrich" <tu@...>]

I've created a patch for Lua 4.0 that makes calls from Lua to Lua
non-recursive (i.e. "stackless").  This allows the implementation of a
"sleep()" call, which exits from the host program's lua_do* call with
a LUA_SLEEP code, and leaves the lua_State in a condition where the
script can be resumed later via a call to a new API function,
lua_resume(lua_State*).

The patch is on the "Power Patches" page at lua-users.org :

http://lua-users.org/wiki/LuaPowerPatches

This is the core functionality that Bret Mogilefsky has described in
the "sleep()/yield() for Lua" thread, and has been much bandied about
in the archives.

As part of the VM changes, I also made it so OP_TAILCALL is properly
non-recursive.  This lets you implement long iteration-like
computations using recursive syntax (provided the compiler emits an
OP_TAILCALL for the tail call -- I'm not totally sure what the right
conditions for that are).  See the test program below for a contrived
example.

The patched lua correctly executes all the test scripts in the 4.0
distribution, but it's very possible there's a bug somewhere,
especially with error handling and such.

Also, these changes need to be ported to 4.1, to take advantage of Lua
threads.  I started with 4.0 in order to have a stable platform to
work in.

The biggest known problem with this patch is that sleep() will not
actually succeed if it's called from a tag method, or from a recursive
call to lua_do* (i.e. script calls a C function, which then calls
lua_do*).  Instead you get an error message and the script continues
execution.  So the semantics of sleep() depend somewhat on the
internal workings of the interpreter.  For practical use in a game
scripting language, this shouldn't be a problem.

Feedback welcome!

-- 
Thatcher Ulrich <tu@tulrich.com>
http://tulrich.com



------ test/sleep.lua -------
-- test the sleep patch.  The sleep patch adds a sleep() function,
-- which suspends script execution in a restartable state (via the API
-- function lua_resume(L)).  The sleep patch also implements true tail
-- recursion for the OP_TAILCALL opcode.


function donothing_tailrec(x)
	return x
end

function donothing_rec1(x)
	return donothing_tailrec(x)
end

function donothing_rec2(x)
	for i = 1,1000 do
		donothing_rec1(x)
	end
	return donothing_rec1(x)
end

function donothing_rec3(x)
	for i = 1,1000 do
		donothing_rec2(x)

		-- exit script execution, returning LUA_SLEEP to the caller.
		-- The caller can resume the script via lua_resume(L).
		sleep()
	end
	return donothing_rec2(x)
end

c = clock()
r = donothing_rec3(10)
t = clock() - c
print("time = " .. t .. ", result = " .. r);


count = 0

function increment_tailrec(ct)
-- stupid recursive function to increment 'count'
	if ct <= 0 then
		return 0
	else
		count = count + 1
		return increment_tailrec(ct-1)	-- for some reason, we must return a value for OP_TAILCALL to be generated.
	end
end


function test(x)
	count = 0
	increment_tailrec(x)
	if count == x then
		print("success --> count = " .. x);
	else
		print("failure --> count = " .. count .. " but x = " .. x);
	end
end


-- The sleep patch also implements proper tail recursion for the
-- OP_TAILCALL opcode.  In unpatched Lua 4.0, one of the following
-- calls will probably cause a stack overflow error.
test(1)
test(10)
test(100)
test(1000)
test(10000)
test(100000)
test(1000000)