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

[Jeff Schultz]

On Mon, Nov 21, 2011 at 03:17:25PM +0800, Barco You wrote:
> I'm struggling to understand ASM code generated by the erlang compiler.

I don't think there's a lot of documentation about BEAM.  I interpret
it based more on its (general) similarity to the Warren Abstract
Machine than on any more direct knowledge.  You might find Hassan
Ait-Kaci's book on the WAM a useful primer.
(http://wambook.sourceforge.net/)

The similarities between BEAM and the WAM are most certainly not total.

> Could you please tell the difference of the asm code between map2  and map3?

I'm not sure what you are asking.

You can see that map3/4 is tail recursive by observing the use of
call_last (which appears to be a portmanteau of deallocate and
call_only) instead of call.  call_only appears to be BEAM's tail call
instruction.


    Jeff Schultz

> {function, *map2*, 3, 12}.
>   {label,11}.
>     {func_info,{atom,test},{atom,map2},3}.
>   {label,12}.
>     {test,is_nonempty_list,{f,13},[{x,1}]}.
>     {get_list,{x,1},{x,3},{x,4}}.
>     {test,is_nonempty_list,{f,11},[{x,2}]}.
>     {allocate,3,5}.
>     {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}.
>     {move,{x,0},{x,3}}.
>     {move,{y,1},{x,1}}.
>     {move,{y,2},{x,2}}.
>     {move,{y,0},{x,0}}.
>     {move,{x,3},{y,2}}.
>     {trim,2,1}.
>     {call,3,{f,12}}.
>     {test_heap,2,1}.
>     {put_list,{y,0},{x,0},{x,0}}.
>     {deallocate,1}.
>     return.
>   {label,13}.
>     {test,is_nil,{f,11},[{x,1}]}.
>     {test,is_nil,{f,11},[{x,2}]}.
>     {move,nil,{x,0}}.
>     return.
> 
> 
> {function,* map3*, 3, 15}.
>   {label,14}.
>     {func_info,{atom,test},{atom,map3},3}.
>   {label,15}.
>     {test,is_nil,{f,16},[{x,1}]}.
>     {test,is_nil,{f,16},[{x,2}]}.
>     {move,nil,{x,0}}.
>     return.
>   {label,16}.
>     {move,nil,{x,3}}.
>     {call_only,4,{f,18}}.
> 
> 
> {function,* map3*, 4, 18}.
>   {label,17}.
>     {func_info,{atom,test},{atom,map3},4}.
>   {label,18}.
>     {test,is_nonempty_list,{f,19},[{x,1}]}.
>     {get_list,{x,1},{x,4},{x,5}}.
>     {test,is_nonempty_list,{f,17},[{x,2}]}.
>     {allocate,4,6}.
>     {get_list,{x,2},{x,1},{y,3}}.
>     {move,{x,0},{x,2}}.
>     {move,{x,4},{x,0}}.
>     {move,{x,3},{y,0}}.
>     {move,{x,2},{y,1}}.
>     {move,{x,5},{y,2}}.
>     {call_fun,2}.
>     {test_heap,2,1}.
>     {put_list,{x,0},{y,0},{x,3}}.
>     {move,{y,2},{x,1}}.
>     {move,{y,3},{x,2}}.
>     {move,{y,1},{x,0}}.
>     {call_last,4,{f,18},4}.
>   {label,19}.
>     {test,is_nil,{f,17},[{x,1}]}.
>     {test,is_nil,{f,17},[{x,2}]}.
>     {move,{x,3},{x,0}}.
>     {call_ext_only,1,{extfunc,lists,reverse,1}}.
> 
> 
> On Mon, Nov 21, 2011 at 9:35 AM, Jeff Schultz <jws@REDACTED>wrote:
> 
> > 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
> > _______________________________________________
> > erlang-questions mailing list
> > erlang-questions@REDACTED
> > http://erlang.org/mailman/listinfo/erlang-questions
> >