[erlang-questions] Tail call optimization

[Joe Armstrong]

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
<raimo+erlang-questions@REDACTED> 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
>> <Dinislam.Salikhov@REDACTED> 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
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions