Erlang:带有递归函数的堆栈溢出，没有优化尾部调用

Question

是否有可能获得一个在 Erlang 中没有优化尾部调用的函数的堆栈溢出？例如，假设我有一个这样的函数

sum_list([],Acc) ->
   Acc;
sum_list([Head|Tail],Acc) ->
   Head + sum_list(Tail, Acc).

看起来，如果传递了一个足够大的列表，它最终会耗尽堆栈空间并崩溃。我尝试像这样测试：

> L = lists:seq(1, 10000000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...]
> sum_test:sum_list(L, 0).
50000005000000

但它永远不会崩溃！我尝试了 100,000,000 个整数的列表，花了一段时间才完成，但它仍然没有崩溃！问题：

1. 我是否正确测试了？
2. 如果是这样，为什么我无法生成堆栈溢出？
3. Erlang 是否在做一些防止堆栈溢出发生的事情？

Answer 1

你正在正确测试这一点：你的函数确实不是尾递归的。要找出答案，您可以使用 erlc -S <erlang source file> 编译代码。

{function, sum_list, 2, 2}.
  {label,1}.
    {func_info,{atom,so},{atom,sum_list},2}.
  {label,2}.
    {test,is_nonempty_list,{f,3},[{x,0}]}.
    {allocate,1,2}.
    {get_list,{x,0},{y,0},{x,0}}.
    {call,2,{f,2}}.
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}.
    {deallocate,1}.
    return.
  {label,3}.
    {test,is_nil,{f,1},[{x,0}]}.
    {move,{x,1},{x,0}}.
    return.

作为比较，函数的以下尾递归版本：

tail_sum_list([],Acc) ->
   Acc;
tail_sum_list([Head|Tail],Acc) ->
   tail_sum_list(Tail, Head + Acc).

编译为：

{function, tail_sum_list, 2, 5}.
  {label,4}.
    {func_info,{atom,so},{atom,tail_sum_list},2}.
  {label,5}.
    {test,is_nonempty_list,{f,6},[{x,0}]}.
    {get_list,{x,0},{x,2},{x,3}}.
    {gc_bif,'+',{f,0},4,[{x,2},{x,1}],{x,1}}.
    {move,{x,3},{x,0}}.
    {call_only,2,{f,5}}.
  {label,6}.
    {test,is_nil,{f,4},[{x,0}]}.
    {move,{x,1},{x,0}}.
    return.

请注意，尾递归版本中缺少allocate和call_only操作码，而不是非递归函数中的allocate/call/deallocate/return序列。

您不会因为 Erlang "堆栈"非常大而出现堆栈溢出。实际上，堆栈溢出通常意味着处理器堆栈溢出，因为处理器的堆栈指针离得太远。传统上，进程具有有限的堆栈大小，可以通过与操作系统交互来调整。例如参见 POSIX 的 setrlimit。

但是，Erlang 执行堆栈不是处理器堆栈，因为代码是解释的。每个进程都有自己的堆栈，可以通过调用操作系统内存分配函数（通常是Unix上的malloc）根据需要增长。

因此，只要调用成功malloc函数就不会崩溃。

作为记录，实际列表L使用与堆栈相同的内存量来处理它。实际上，列表中的每个元素都包含两个单词（整数值本身，由于它们很小，因此被框为单词）和指向列表下一个元素的指针。相反，堆栈在每次迭代时通过操作码增加两个单词allocate：一个单词表示由allocate本身保存的CP单词，一个单词用于当前值的请求（allocate的第一个参数）。

对于 64 位 VM 上的 100,000,000 个单词，该列表至少需要 1.5 GB（幸运的是，实际堆栈不会每两个单词增长一次）。监控和冲洗这在外壳中很困难，因为许多值仍然有效。如果生成一个函数，则可以看到内存使用情况：

spawn(fun() ->
    io:format("~pn", [erlang:memory()]),
    L = lists:seq(1, 100000000),
    io:format("~pn", [erlang:memory()]),
    sum_test:sum_list(L, 0),
    io:format("~pn", [erlang:memory()])
end).

如您所见，递归调用的内存不会立即释放。