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

Question

I'm writing some Erlang code, and I've run into a bizarre situation that I don't understand.

The code:

-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.

The output:

(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

From what I understand from this article, Erlang uses a Last Call Optimization where, if the last thing a function does is to call another function, the BeamVM will instead jump the program counter to the start of the new function instead of pushing a new stack frame. Does this mean that in a pattern like the above, we're stomping around the heap instead of around the stack? Does this free the memory that was previously held in these functions (in the case of the above code, would we have one copy of function F allocated in memory at a time, or would we have many copies of the function F allocated in memory at a time)? Are there any negative consequences to using this pattern (other than the obvious debugging struggle)?

score 2 · Accepted Answer · answered Aug 31 '18 at 06:37

First, fun (lambda, closure or whatever you want to call it) due to immutable nature of Erlang could be and is implemented in a way you can imagine like tuple

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

So in your case, it will be something like

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

Note the arity is 2 because you have arity 0 of fun plus 2 captured values.

Then it should be easier to understand what is going on in your code. Remember is not true tuple but some structure which behaves very similarly in regard to data consumption, heap term referencing, GC, transferring around the Erlang distribution protocol and so on.

Which allows you to understand the second thing which is that calling F() inside b/2 is something like

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

which can be nice tail call a.k.a jump. So your code is making fun "tuples" and then just jump around code. Each fun "tuple" is then not referenced anymore so could be GCed out anytime. I recommend you to try it with numbers instead of lists and try bigger and bigger numbers and watch memory consumption using process_info or observer. It would be a nice exercise.

BTW you can use

process_info(self(), stack_size)

instead of slow and ugly

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

Thanks for the info - I'll try out some of the experiments that you suggested. I'm not sure I'm smart enough to reason logically about this code. Thanks for the `process_info` call - I'll edit the original question to include it so that awful `proplists` call can be removed. Thanks again! — distortedsignal, Sep 05 '18 at 17:52

score 1 · Answer 2 · answered Aug 29 '18 at 07:17

This is not an answer, but you should find what you are looking for. I have compile a version of your code (without the io:format call line 7. Then you can decompile the beam file to see how is interpreted the code:

-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.

in the 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>

Thanks for the answer - looks like I need to learn more about Erlang's intermediate form before I can delve too deeply here. When I figure out what the IF is saying, I'll edit the question and provide an answer. — distortedsignal, Aug 29 '18 at 18:35

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

2 Answers2