[erlang-questions] [erlang-question] How to comprehend two lists synchronously?

[Jeff Schultz]

On Fri, Nov 18, 2011 at 11:37:24AM +0400, Dmitry Demeshchuk wrote:
> Okay, I admit, this isn't an "honest" tail-recursed function, since a
> list concatenation operator is going to be called at the end. However,
> Erlang compiler optimizes such cases and converts them to
> tail-recursive:
> http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive

Not really.  Here's what R14B compiles your map2/3 to (with my
comments added):

{function, map2, 3, 2}.
  {label,1}.
    {func_info,{atom,map2},{atom,map2},3}.
  {label,2}.
    {test,is_nonempty_list,{f,3},[{x,1}]}.
    {get_list,{x,1},{x,3},{x,4}}.
    {test,is_nonempty_list,{f,1},[{x,2}]}.
    {allocate,3,5}.		% allocate stack frame
    {get_list,{x,2},{x,1},{y,2}}.
    {move,{x,0},{x,2}}.
    {move,{x,3},{x,0}}.
    {move,{x,2},{y,0}}.
    {move,{x,4},{y,1}}.
    {call_fun,2}.		% Fun(H1, H2)
    {move,{x,0},{x,3}}.		% could be reordered
    {move,{y,1},{x,1}}.
    {move,{y,2},{x,2}}.
    {move,{y,0},{x,0}}.
    {move,{x,3},{y,2}}.		% cute
    {trim,2,1}.			% trim the stack frame
    {call,3,{f,2}}.		% map2(Fun, T1, T2)
    {test_heap,2,1}.
    {put_list,{y,0},{x,0},{x,0}}.
    {deallocate,1}.		% deallocate stack frame
    return.
  {label,3}.
    {test,is_nil,{f,1},[{x,1}]}.
    {test,is_nil,{f,1},[{x,2}]}.
    {move,nil,{x,0}}.
    return.

So if T1 and T2 have length N, you get a peak stack use of N frames.
Unless the VM does some clever transformation when it loads this code,
of course.

In this case, the stack frame is able to be trimmed to 1 entry before
the recursion, so it quite possibly ends up taking a similar amount of
space to the intermediate list produced by the usual tail recursion
transformation.

This may actually be better than Erlang tail recursion followed by
reverse/2 because it avoids garbage collecting the intermediate list
produced by the usual tail recursion transformation.  Whether this
ends up as a net speed gain as well is something one would have to
measure.

(The trim instruction seems weird.  I'm curious about why it was done
this way.)


    Jeff Schultz