Tail call optimization

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Tail call optimization

Salikhov Dinislam
Hello.

Erlang guarantees tail recursion optimization and states it in the documentation:
http://erlang.org/doc/reference_manual/functions.html#id78464

Does erlang guarantee that tail call optimization is done in a generic case, without recursion?
Say, we have a function calling a function from another module as its final statement:
    alpha() ->
        xxx:beta().
Is it guaranteed that xxx:beta() will use the stack of alpha() regardless whether recursion is involved.
I mean whether the language guarantees it rather than virtual machine may provide such optimization.

Thanks in advance,
Salikhov Dinislam

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Dmytro Lytovchenko
In the doc page you linked:
> If the last expression of a function body is a function call, a tail recursive call is done.

Compiler will replace call opcode with a tail call (call_last, call_ext_last, apply_last). You can check it with "erl -S test.erl" to see assembly, and in erl console: "l(modulename)." to load the module then "erts_debug:df(modulename)." to create disassembly from BEAM VM memory (it will be a bit different from the erl -S output).

See that your calls are replaced with one of: call_last, call_ext_last, apply_last.

2016-10-17 10:58 GMT+02:00 Salikhov Dinislam <[hidden email]>:
Hello.

Erlang guarantees tail recursion optimization and states it in the documentation:
http://erlang.org/doc/reference_manual/functions.html#id78464

Does erlang guarantee that tail call optimization is done in a generic case, without recursion?
Say, we have a function calling a function from another module as its final statement:
    alpha() ->
        xxx:beta().
Is it guaranteed that xxx:beta() will use the stack of alpha() regardless whether recursion is involved.
I mean whether the language guarantees it rather than virtual machine may provide such optimization.

Thanks in advance,
Salikhov Dinislam

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Salikhov Dinislam
The confusing thing is that the doc says about tail recursive call.
For example, if I have a call chain:
    a() ->
        % some code
        b().
    b() ->
        % some code
        c().
    % ...
    y() ->
        %some code
        z().
Recursion is not involved here. And I'd like to know if erlang requires (and guarantees) that all tail callees in the chain above use the stack of the caller.
AFAIU, compiler is free to not apply the optimization if it is not stated in the specification (and it is pure luck that the compiler does).

Salikhov Dinislam

On 10/17/2016 03:00 PM, Dmytro Lytovchenko wrote:
In the doc page you linked:
> If the last expression of a function body is a function call, a tail recursive call is done.

Compiler will replace call opcode with a tail call (call_last, call_ext_last, apply_last). You can check it with "erl -S test.erl" to see assembly, and in erl console: "l(modulename)." to load the module then "erts_debug:df(modulename)." to create disassembly from BEAM VM memory (it will be a bit different from the erl -S output).

See that your calls are replaced with one of: call_last, call_ext_last, apply_last.

2016-10-17 10:58 GMT+02:00 Salikhov Dinislam <[hidden email]>:
Hello.

Erlang guarantees tail recursion optimization and states it in the documentation:
http://erlang.org/doc/reference_manual/functions.html#id78464

Does erlang guarantee that tail call optimization is done in a generic case, without recursion?
Say, we have a function calling a function from another module as its final statement:
    alpha() ->
        xxx:beta().
Is it guaranteed that xxx:beta() will use the stack of alpha() regardless whether recursion is involved.
I mean whether the language guarantees it rather than virtual machine may provide such optimization.

Thanks in advance,
Salikhov Dinislam

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Dmytro Lytovchenko
There is nothing about recursion in documentation.

Your module:
-module(tc).
-export([a/0]).
a() -> b().
b() -> c().
c() -> z().
z() -> self().

Compiles to (memory dump):
00007F07875A2DA8: i_func_info_IaaI 0 tc a 0.
00007F07875A2DD0: i_call_only_f tc:b/0.

00007F07875A2DE0: i_func_info_IaaI 0 tc b 0.
00007F07875A2E08: i_call_only_f tc:c/0.

00007F07875A2E18: i_func_info_IaaI 0 tc c 0.
00007F07875A2E40: i_call_only_f tc:z/0.

00007F07875A2E50: i_func_info_IaaI 0 tc z 0.
00007F07875A2E78: self_r x(0).
00007F07875A2E80: return.

Note the call_only functions. These are the tail calls.


2016-10-17 14:28 GMT+02:00 Salikhov Dinislam <[hidden email]>:
The confusing thing is that the doc says about tail recursive call.
For example, if I have a call chain:
    a() ->
        % some code
        b().
    b() ->
        % some code
        c().
    % ...
    y() ->
        %some code
        z().
Recursion is not involved here. And I'd like to know if erlang requires (and guarantees) that all tail callees in the chain above use the stack of the caller.
AFAIU, compiler is free to not apply the optimization if it is not stated in the specification (and it is pure luck that the compiler does).

Salikhov Dinislam


On 10/17/2016 03:00 PM, Dmytro Lytovchenko wrote:
In the doc page you linked:
> If the last expression of a function body is a function call, a tail recursive call is done.

Compiler will replace call opcode with a tail call (call_last, call_ext_last, apply_last). You can check it with "erl -S test.erl" to see assembly, and in erl console: "l(modulename)." to load the module then "erts_debug:df(modulename)." to create disassembly from BEAM VM memory (it will be a bit different from the erl -S output).

See that your calls are replaced with one of: call_last, call_ext_last, apply_last.

2016-10-17 10:58 GMT+02:00 Salikhov Dinislam <[hidden email]>:
Hello.

Erlang guarantees tail recursion optimization and states it in the documentation:
http://erlang.org/doc/reference_manual/functions.html#id78464

Does erlang guarantee that tail call optimization is done in a generic case, without recursion?
Say, we have a function calling a function from another module as its final statement:
    alpha() ->
        xxx:beta().
Is it guaranteed that xxx:beta() will use the stack of alpha() regardless whether recursion is involved.
I mean whether the language guarantees it rather than virtual machine may provide such optimization.

Thanks in advance,
Salikhov Dinislam

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions





_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Salikhov Dinislam
> There is nothing about recursion in documentation.
The only doc that I've managed to find about the subject is the link from my initial post (http://erlang.org/doc/reference_manual/functions.html#id78464).
And it says about recursion: in sub-chapter's header, in sub-chapter itself and in the example (all in all, everywhere). Is there another documentation that you mean?

On 10/17/2016 03:36 PM, Dmytro Lytovchenko wrote:
There is nothing about recursion in documentation.

Your module:
-module(tc).
-export([a/0]).
a() -> b().
b() -> c().
c() -> z().
z() -> self().

Compiles to (memory dump):
00007F07875A2DA8: i_func_info_IaaI 0 tc a 0.
00007F07875A2DD0: i_call_only_f tc:b/0.

00007F07875A2DE0: i_func_info_IaaI 0 tc b 0.
00007F07875A2E08: i_call_only_f tc:c/0.

00007F07875A2E18: i_func_info_IaaI 0 tc c 0.
00007F07875A2E40: i_call_only_f tc:z/0.

00007F07875A2E50: i_func_info_IaaI 0 tc z 0.
00007F07875A2E78: self_r x(0).
00007F07875A2E80: return.

Note the call_only functions. These are the tail calls.


2016-10-17 14:28 GMT+02:00 Salikhov Dinislam <[hidden email]>:
The confusing thing is that the doc says about tail recursive call.
For example, if I have a call chain:
    a() ->
        % some code
        b().
    b() ->
        % some code
        c().
    % ...
    y() ->
        %some code
        z().
Recursion is not involved here. And I'd like to know if erlang requires (and guarantees) that all tail callees in the chain above use the stack of the caller.
AFAIU, compiler is free to not apply the optimization if it is not stated in the specification (and it is pure luck that the compiler does).

Salikhov Dinislam


On 10/17/2016 03:00 PM, Dmytro Lytovchenko wrote:
In the doc page you linked:
> If the last expression of a function body is a function call, a tail recursive call is done.

Compiler will replace call opcode with a tail call (call_last, call_ext_last, apply_last). You can check it with "erl -S test.erl" to see assembly, and in erl console: "l(modulename)." to load the module then "erts_debug:df(modulename)." to create disassembly from BEAM VM memory (it will be a bit different from the erl -S output).

See that your calls are replaced with one of: call_last, call_ext_last, apply_last.

2016-10-17 10:58 GMT+02:00 Salikhov Dinislam <[hidden email]>:
Hello.

Erlang guarantees tail recursion optimization and states it in the documentation:
http://erlang.org/doc/reference_manual/functions.html#id78464

Does erlang guarantee that tail call optimization is done in a generic case, without recursion?
Say, we have a function calling a function from another module as its final statement:
    alpha() ->
        xxx:beta().
Is it guaranteed that xxx:beta() will use the stack of alpha() regardless whether recursion is involved.
I mean whether the language guarantees it rather than virtual machine may provide such optimization.

Thanks in advance,
Salikhov Dinislam

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions






_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Pierpaolo Bernardi
On Mon, Oct 17, 2016 at 2:47 PM, Salikhov Dinislam
<[hidden email]> wrote:
>> There is nothing about recursion in documentation.
> The only doc that I've managed to find about the subject is the link from my
> initial post
> (http://erlang.org/doc/reference_manual/functions.html#id78464).
> And it says about recursion: in sub-chapter's header, in sub-chapter itself
> and in the example (all in all, everywhere). Is there another documentation
> that you mean?

Yes, the chapter sub-header has 'recursion' in the name.

But the text says: "If the last expression of a function body is a
function call, a tail recursive call is done."

This in no way can be read as meaning that when the last expression of
a function body is a function call then a tail call is not mandated.

Maybe changing "tail recursive call" to "tail call" would remove an
element of distraction and be more to the point though.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Salikhov Dinislam
Tail call != tail recursive call. The former is more general and includes the latter as a particular case.
I'd change the wording as follows:
    6.3 Tail function call
    If the last expression of a function body is a function call, a tail call optimization is done.
IMO, it would eliminate any ambiguity here.
Anyway, thank you for clarification.

Salikhov Dinislam

On 10/17/2016 04:57 PM, Pierpaolo Bernardi wrote:
On Mon, Oct 17, 2016 at 2:47 PM, Salikhov Dinislam
[hidden email] wrote:
There is nothing about recursion in documentation.
The only doc that I've managed to find about the subject is the link from my
initial post
(http://erlang.org/doc/reference_manual/functions.html#id78464).
And it says about recursion: in sub-chapter's header, in sub-chapter itself
and in the example (all in all, everywhere). Is there another documentation
that you mean?
Yes, the chapter sub-header has 'recursion' in the name.

But the text says: "If the last expression of a function body is a
function call, a tail recursive call is done."

This in no way can be read as meaning that when the last expression of
a function body is a function call then a tail call is not mandated.

Maybe changing "tail recursive call" to "tail call" would remove an
element of distraction and be more to the point though.


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Raimo Niskanen-2
In reply to this post by Pierpaolo Bernardi
On Mon, Oct 17, 2016 at 03:57:29PM +0200, Pierpaolo Bernardi wrote:

> On Mon, Oct 17, 2016 at 2:47 PM, Salikhov Dinislam
> <[hidden email]> wrote:
> >> There is nothing about recursion in documentation.
> > The only doc that I've managed to find about the subject is the link from my
> > initial post
> > (http://erlang.org/doc/reference_manual/functions.html#id78464).
> > And it says about recursion: in sub-chapter's header, in sub-chapter itself
> > and in the example (all in all, everywhere). Is there another documentation
> > that you mean?
>
> Yes, the chapter sub-header has 'recursion' in the name.
>
> But the text says: "If the last expression of a function body is a
> function call, a tail recursive call is done."
>
> This in no way can be read as meaning that when the last expression of
> a function body is a function call then a tail call is not mandated.
>
> Maybe changing "tail recursive call" to "tail call" would remove an
> element of distraction and be more to the point though.

Yes!  We should change that detail in the documentation.  Recursion is not
a prerequisite for tail call optimization.

This is an implication of the fact that neither the compiler nor the VM,
due to hot code loading and due to that modules are compiled independently,
can depend on what a Module:Function call does (this time) so the tail call
optimization has to be done from the caller's side.

And it is hard to figure out a real use case where code depending on tail call
optimization does not eventually call back to itself hence use recursion.

So the tail call optimization is something the language depends hard on,
and the documentation is confusing when using the word "recursive" in this
context.  It probably comes from the course material where it talks about
"tail recursive" vs. "body recursive" calls, so this documentation probably
just wanted to use a familiar (but slightly incorrect) term...

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Tail call optimization

Joe Armstrong-2
I think there is a confusion between what is commonly called
"tail recursion" and "last call optimization" - so to clarify this
I'll try to  explain exactly what happens.

The correct name for the optimization used in Erlang is "last
call optimization".

Saying that something is "tail recursive" is a short-hand way of
saying "the function is recursive" and that we only find pure function
calls in the tail-positions of all branches of a function.

Last call optimization is best understood by looking at how we compile
code for a simple stack-based language.

Suppose we have some code like this:

X ->
    call a
    call b
    call c

This is a kind of pseudo code, it just means the function X just calls
three functions a,b and c (could be any programming language)

On a conventional stack machine, this is compiled into something like
this:

X: pushAddr 1
   goto a
 1:pushAddr 2
   goto b
 2:pushAddr 3
   goto c
 3:ret

pushAddr pushed a return address onto the stack.  goto <label> jumps
to the start address of the routine.  The last statement will be a
return (ret) which expects to find a return address on the top of
stack.

ret pops the stack and jumps to the address that it has just popped
from the stack.

Imagine the stack contains an address AAA before X is called.

Just after the pushAddr 1
the stack looks like

    Address of label 1 <- Top of stack
    AAA

when we returns (with a ret instruction) the stack is popped
and we jump to the address of label 1

Just before we call c the stack looks like this:

    Address of label 3
    AAA

When c returns it pops the stack and jumps to the code it found
on the top of stack - but the code it jumps into just pops the
stack and jumps to the address *it* was called from.

So if we don't bother to push the final address, the code for
X becomes:

X:
pushAddr 1
goto a
1: pushAddr 2
goto b
2: goto c

Then when c hits a return statement it will jump directly to the
AAA address which was on the top of stack when c was called.

This is called 'last call optimization' - it just says that if the
last thing a function does is call another function, then the call
can be replaced by jump to the start of the function.

In the first compiler I implemented this as a peep hole optimisation
something like:

   optimize([{pushAddr,L},{goto,X},{label,L,ret}]) ->
       [{goto,X}];
   ..

Last call optimizations mean that 'tail recursive calls' run in
constant stack space, ie they don't need to create new stack frames
when they recursively call themselves, provided the the recursive call
is the last thing they do.

Mutually recursive calls (ie a calls b, b calls c, c calls a again,
where these calls are the last things the functions do) also
run in constant stack space.

Languages like Erlang must implement tail call optimizations, since
persisted data is stored as "loop variables" in infinite loops.
This happens when we write code like this:

     loop(Data) ->
          ....
 ...
 loop(newData).

When I see code like this I mentally "see" the last call as a "jump"
to the start of the code, rather than a recursive call to loop.

Languages that do not implement last call optimisations rapidly run
out of stack space when co-routineing - in fact I've never really
understood why languages like C don't implement the last call
optimization.

Compiler writers have used the word "tail" to refer to the last thing
a branch of code does before returning, tail calls are just
regular function calls that occur in  "tail positions".

Tail recursion is where the function called in the tail position
is the function itself and not a different function.

Tail recursive functions are functions where all branches of the
function end with function calls (and not data constructors or
operator)

Cheers

/Joe

On Mon, Oct 17, 2016 at 4:22 PM, Raimo Niskanen
<[hidden email]> wrote:

> On Mon, Oct 17, 2016 at 03:57:29PM +0200, Pierpaolo Bernardi wrote:
>> On Mon, Oct 17, 2016 at 2:47 PM, Salikhov Dinislam
>> <[hidden email]> wrote:
>> >> There is nothing about recursion in documentation.
>> > The only doc that I've managed to find about the subject is the link from my
>> > initial post
>> > (http://erlang.org/doc/reference_manual/functions.html#id78464).
>> > And it says about recursion: in sub-chapter's header, in sub-chapter itself
>> > and in the example (all in all, everywhere). Is there another documentation
>> > that you mean?
>>
>> Yes, the chapter sub-header has 'recursion' in the name.
>>
>> But the text says: "If the last expression of a function body is a
>> function call, a tail recursive call is done."
>>
>> This in no way can be read as meaning that when the last expression of
>> a function body is a function call then a tail call is not mandated.
>>
>> Maybe changing "tail recursive call" to "tail call" would remove an
>> element of distraction and be more to the point though.
>
> Yes!  We should change that detail in the documentation.  Recursion is not
> a prerequisite for tail call optimization.
>
> This is an implication of the fact that neither the compiler nor the VM,
> due to hot code loading and due to that modules are compiled independently,
> can depend on what a Module:Function call does (this time) so the tail call
> optimization has to be done from the caller's side.
>
> And it is hard to figure out a real use case where code depending on tail call
> optimization does not eventually call back to itself hence use recursion.
>
> So the tail call optimization is something the language depends hard on,
> and the documentation is confusing when using the word "recursive" in this
> context.  It probably comes from the course material where it talks about
> "tail recursive" vs. "body recursive" calls, so this documentation probably
> just wanted to use a familiar (but slightly incorrect) term...
>
> --
>
> / Raimo Niskanen, Erlang/OTP, Ericsson AB
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions