Lua 正确的尾调用(proper tail call)

时间:2022-07-27 04:40:17

Lua支持“尾调用消除(tail-call elimination)”。
尾调用(tail call):当一个函数调用是另一个函数的最后一个动作时,该调用才算是一条“尾调用”。例如,下面的代码就是一条“尾调用”:

function f (x) return g(x) end

也就是说,当f调用完g之后就再无其他事情可做了。因此在这种情况下,程序就不需要返回那个“尾调用”所在的函数了。所以在“尾调用”之后,程序也不需要保存任何关于该函数的栈(stack)信息了。当g返回时,执行控制权可以直接返回到调用f的那个点上。有一些语言实现(例如Lua解释器)可以得益于这个特点,使得在进行“尾调用”时不好非任何栈空间。将这种实现称为支持“尾调用消除”。
由于“尾调用”不会耗费栈空间,所以一个程序可以拥有无数嵌套的“尾调用”。例如,在第哦用以下函数时,传入任何数字作为参数都不会造成栈溢出:

function foo (n)
if n > then return foo(n-) end
end

判断当前的调用是一条“尾调用”的准则:一个函数在调用完另一个函数之后,是否就无其他事情需要做了。
例如,下面的代码就不是一条“尾调用”:

function f (x) g(x) end

这个示例的问题在于,当调用完g后,f并不能立即返回,它还需要丢弃g返回的临时结果。类似的,以下所有调用也都不符合上述准则:

return g(x) +         -- 必须做一次加法
return x or g(x) -- 必须调整为一个返回值
return (g(x)) -- 必须调整为一个返回值

在Lua中,只有“return <func>(<args>)”这样的调用形式才算是一条“尾调用”。Lua会在调用前对<func>及其参数求值,所以它们可以是任意复杂的表达式。举例来说,下买的呢调用就是一条“尾调用”:

return x[i].foo(x[j] + a*b , i + j)

[“尾调用” 迷宫游戏示例]
“尾调用”类似一条goto语句。在Lua中“尾调用”的已答应永久是编写“状态机(state machine)”。这种程序通常以一个函数来表示一个状态,改变状态就是goto(或调用)到另一个特定的函数。举一个简单的迷宫游戏的例子来说明这个问题。例如,一个迷宫有几间房间,每间房间中最多有东南西北4扇门。用户在每一步移动中都需要输入一个移动的方向。如果在某个方向上有门,那么用乎可以进入相应的房间;不然,程序就打印一条警告。游戏目标就是让用户从最初的房间走到最终的房间。
这个游戏就是一种典型的状态机,其中当前房间就是一个状态。可以将迷宫中的没见房间实现为一个函数,并使用“尾调用”来实现从一件房间移动到另一间房间。在以下代码中,实现一个具有4间房间的迷宫:

function room1 ()
local move = io.read()
if move == "sourth" then return room3()
elseif move == "east" then return room2()
else
print("invalid move")
return room1() -- stay in the same room
end
end function room2()
local move = io.read()
if move == "sourth" then return room4()
elseif move == "west" then return room1()
else
print("invalid move")
return room2()
end
end function room3()
local move = io.read()
if move == "north" then return room1()
elseif move == "east" then return room4()
else
print("invalid move")
return room3()
end
end function room4()
print("congratulations!")
end

通过调用出世房间来开始这个游戏:

room1()

若没有“尾调用消除”的话,每次用户的移动都会创建一个新的栈层(stack level),移动若干步之后就有可能会导致栈溢出。而“尾调用消除”则对用户已动的次数没有限制。这是因为每次移动实际上都只是完成一条goto语句到另一个函数,而非传统的函数调用。
对于这个简单的游戏而言,或许会觉得将程序设计为数据驱动的会更好玩一点,其中将房间和移动记录在一些table中。不过,如果游戏中的没见房间都有个字特殊的情况的话,采用这种状态机的设计会更为合适。