Erlang、Last Call Optimization、lambda 函数以及如何防止堆栈增长

Question

我正在写一些 Erlang 代码，我运行遇到了一个我不明白的奇怪情况。

代码：

-module(recursive_test).
-export([a/2]).

a(_, []) -> ok;
a(Args, [H|T]) ->
    F = fun() -> a(Args, T) end,
    io:fwrite(
        "~nH: ~p~nStack Layers: ~p",
        [H, process_info(self(), stack_size)]
    ),
    b(Args, F).

b(Args, F) ->
    case Args of
        true -> ok;
        false -> F()
    end.

输出：

(Erlang/OTP 20)
12> c(recursive_test).
{ok,recursive_test}
13> recursive_test:a(false, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).
H: 1
Stack Layers: 28
H: 2
Stack Layers: 28
H: 3
Stack Layers: 28
H: 4
Stack Layers: 28
H: 5
Stack Layers: 28
H: 6
Stack Layers: 28
H: 7
Stack Layers: 28
H: 8
Stack Layers: 28
H: 9
Stack Layers: 28
H: 10
Stack Layers: 28
ok
14> recursive_test:a(false, [1, 2, 3, 4, 5, 6]).
H: 1
Stack Layers: 28
H: 2
Stack Layers: 28
H: 3
Stack Layers: 28
H: 4
Stack Layers: 28
H: 5
Stack Layers: 28
H: 6
Stack Layers: 28
ok

根据我从 this article 中了解到的情况，Erlang 使用最后一次调用优化，如果一个函数做的最后一件事是调用另一个函数，BeamVM 会将程序计数器跳转到该函数的开头新函数而不是推送新的堆栈框架。这是否意味着在像上面这样的模式中，我们在堆周围而不是在堆栈周围踩踏？这是否会释放之前保存在这些函数中的内存（在上述代码的情况下，我们是否会一次在内存中分配 one 函数 F 的副本，或者我们是否会多次次在内存中分配函数 F 的副本）？使用此模式是否有任何负面影响（除了明显的调试困难）？

Answer 1

这不是答案，但您应该找到您要查找的内容。我已经编译了你的代码的一个版本（没有 io:format 调用第 7 行。然后你可以反编译光束文件以查看如何解释代码：

-module(recursive_test).
-export([a/2]).

a(_, []) -> ok;
a(Args, [H|T]) ->
    F = fun() ->
            a(Args, T)
        end,
    b(Args, F).

b(Args, F) ->
    case Args of
        true -> ok;
        false -> F()
    end.

在 shell:

15> c(recursive_test).                      
recursive_test.erl:5: Warning: variable 'H' is unused
{ok,recursive_test}
16> rp(beam_disasm:file(recursive_test)).
{beam_file,recursive_test,
           [{a,2,2},{module_info,0,10},{module_info,1,12}],
           [{vsn,[224840029366305056373101858936888814401]}],
           [{version,"7.2.1"},
            {options,[]},
            {source,"c:/git/fourretout/src/recursive_test.erl"}],
           [{function,a,2,2,
                      [{label,1},
                       {line,1},
                       {func_info,{atom,recursive_test},{atom,a},2},
                       {label,2},
                       {test,is_nonempty_list,{f,3},[{x,1}]},
                       {allocate,1,2},
                       {get_tl,{x,1},{x,1}},
                       {move,{x,0},{y,0}},
                       {make_fun2,{recursive_test,'-a/2-fun-0-',2},0,88683754,2},
                       {move,{x,0},{x,1}},
                       {move,{y,0},{x,0}},
                       {call_last,2,{recursive_test,b,2},1},
                       {label,3},
                       {test,is_nil,{f,1},[{x,1}]},
                       {move,{atom,ok},{x,0}},
                       return]},
            {function,b,2,5,
                      [{line,2},
                       {label,4},
                       {func_info,{atom,recursive_test},{atom,b},2},
                       {label,5},
                       {test,is_atom,{f,8},[{x,0}]},
                       {select_val,{x,0},
                                   {f,8},
                                   {list,[{atom,true},{f,6},{atom,false},{f,7}]}},
                       {label,6},
                       {move,{atom,ok},{x,0}},
                       return,
                       {label,7},
                       {allocate,0,2},
                       {move,{x,1},{x,0}},
                       {line,3},
                       {call_fun,0},
                       {deallocate,0},
                       return,
                       {label,8},
                       {line,4},
                       {case_end,{x,0}}]},
            {function,module_info,0,10,
                      [{line,0},
                       {label,9},
                       {func_info,{atom,recursive_test},{atom,module_info},0},
                       {label,10},
                       {move,{atom,recursive_test},{x,0}},
                       {line,0},
                       {call_ext_only,1,{extfunc,erlang,get_module_info,1}}]},
            {function,module_info,1,12,
                      [{line,0},
                       {label,11},
                       {func_info,{atom,recursive_test},{atom,module_info},1},
                       {label,12},
                       {move,{x,0},{x,1}},
                       {move,{atom,recursive_test},{x,0}},
                       {line,0},
                       {call_ext_only,2,{extfunc,erlang,get_module_info,2}}]},
            {function,'-a/2-fun-0-',2,14,
                      [{line,5},
                       {label,13},
                       {func_info,{atom,recursive_test},{atom,'-a/2-fun-0-'},2},
                       {label,14},
                       {call_only,2,{recursive_test,a,2}}]}]}
ok
17>

Answer 2

首先，fun（lambda、闭包或任何你想称呼它的东西）由于 Erlang 的不可变特性，可以并且是以你可以想象的方式实现的，比如元组

{fun, {Module, FuncRef, Arity, CodeVersion}, CapturedValues}

所以在你的情况下，它会是这样的

{fun, {recursive_test, '-a/2-fun-0-', 2, 2248400...}, [false, [2,3,4|...]]}

请注意，元数为 2，因为您有 fun 的 0 元数加上 2 个捕获值。

那么应该更容易理解您的代码中发生的事情。请记住，这不是真正的元组，而是一些在数据消耗、堆术语引用、GC、围绕 Erlang 分发协议传输等方面表现非常相似的结构。

这可以让你理解第二件事，即在 b/2 中调用 F() 类似于

recursive_test:'-a/2-fun-0-'(false, [2,3,4|...])

可以很好的尾调用a.k.a跳转。所以你的代码是 fun "tuples" 然后跳转代码。然后每个 fun "tuple" 不再被引用，因此可以随时被 GC 掉。我建议您尝试使用数字而不是列表并尝试越来越大的数字并使用 process_info 或观察者观察内存消耗。这将是一个很好的练习。

顺便说一句，你可以使用

process_info(self(), stack_size)

而不是缓慢和丑陋

roplists:get_value(stack_size, process_info(self()))

Erlang、Last Call Optimization、lambda 函数以及如何防止堆栈增长

Erlang, Last Call Optimization, lambda functions, and how to prevent growing a stack

recursion

erlang

tail-call-optimization

tail-call