Lua proper tail calls

[sagasw]

Lua proper tail calls

Lua 是一门支持 proper tail calls 的语言。

1）什么是 proper tail calls？

当一个函数的最后行为是函数调用时，我们把这个函数调用称之为 tail calls

在 Lua 中，简单的来说，在函数中出现一个形如 return f(......) 的表示式，其中 f 这个函数调用就是 tail calls，一个支持 proper tail calls 的语言，将在 tail calls 发生之后清理调用函数的栈空间。

2）初探 proper tail calls

我们先看一段 c/c++ 代码：

int foo(int n)
{
    return foo(n);
}

很显然，运行上面的函数，将导致 stack overflow。

我们再看一段 lua 的代码：

function foo(n)
  return foo(n)
end

这段代码不会导致 stack overflow。

那么，简而言之导致 proper tail calls 的函数在 tail calls 之后，栈中将不保留任何的关于调用函数的信息，因此 lua 中 tail calls 永远不会导致 stack overflow。

3）Lua 中的 tail calls

在 Lua 中，只有满足 return f(.....) 这种形式的调用才是 tail calls：

-- 几个要注意的例子
function f()
  f() -- 在 Lua 中将引起 stack overflow
end

function f(n)
  return n * f(n - 1) -- 在 Lua 中将引起 stack overflow
end

4）proper tail calls 的用途

最典型的用途就是实现状态机，用一个函数表示一个状态：

local status1, status2, status3, status4 -- 注意前置声明

function status1()
  if something then
    return status2()
  elseif something then
    return status3()
  elseif something then
    return status4()
  end
end

function status2()
  if something then
    return status1()
  elseif something then
    return status3()
  end
end

如果在 c/c++ 中我们这么写，那么将会导致 stack overflow