How come the FSM example in "An FSM Example" does not blow the stack up?

[Pierre Rouleau]

Hi all,

I'm new to Erlang and in the process of learning it. Looks
promising!

On page 128 in Chapter 5 the FSM example shows how functions are used
to implement the sates. The code states that it's tail recursive, but
function idle() calls function ringing() and vice versa. Since
functions return a value, I don't see how the compiler can optimize
the code so that it does not end up consuming stack space for each
call. Is it?

Thanks.

Pierre

[Hynek Vychodil]

When you read 'tail call optimization' there is word 'optimization'
little bit strong there. It is very simple process. Erlang compiler
just detect last call in each code branch and turns it to jump instead
of call. Then originating function lets target function to return
value instead originating gone. So it turns to idle() -> ... jmp
ringing() -> ... jmp idle() -> ... jmp xxx() and so forth. It ends up
that there is not any stack space consumed because there is not calls
but just jumps. It is far simpler since there are all functions in
Erlang so everything returns values (except exit, hibernate and such)
and returned values can be any type because Erlang is dynamically
typed.

> --
> Erlang Programming Website:
> http://www.erlangprogramming.org/
>

--
--Hynek (Pichi) Vychodil

Analyze your data in minutes. Share your insights instantly. Thrill
your boss.  Be a data hero!
Try GoodData now for free: www.gooddata.com

[Pierre Rouleau]

Thanks for your reply, but I probably was not clear enough in my post.
Let me try again.


The book states, just before the example: "With a tail-recursive
function for every state, actions implemented as function calls and
events...."

My question is twofold:

- why can the compiler perform this tail call optimization when the
functions are returning something? Is the compiler analyzing all
functions involved? What if there were 50 different functions
involved and the 50th would call back one of the previously called
function? Will the compiler examine all possible call sequence to
identify that it can perform the optimization? I can easily understand
a function that perform tail recursion into itself. We know we do not
need to look at the returned value. But calling another function
would be a different story if that function is returning a value.
Would it not? Is the fact that the function's returned value not used
the indication the compiler need?

- My second point is more related to the book itself. I would have
liked that point (tail recursion involving multiple functions and the
possibility of tail call optimization (and how it's done) to be
discussed a little bit more in the FSM example.

Thanks!

On Aug 5, 9:46 am, Hynek Vychodil <vychodil.hy...@gmail.com> wrote:
> When you read 'tail call optimization' there is word 'optimization'
> little bit strong there. It is very simple process. Erlang compiler
> just detect last call in each code branch and turns it to jump instead
> of call. Then originating function lets target function to return
> value instead originating gone. So it turns to idle() -> ... jmp
> ringing() -> ... jmp idle() -> ... jmp xxx() and so forth. It ends up
> that there is not any stack space consumed because there is not calls
> but just jumps. It is far simpler since there are all functions in
> Erlang so everything returns values (except exit, hibernate and such)
> and returned values can be any type because Erlang is dynamically
> typed.
>
>
>
>
>
> On Thu, Aug 5, 2010 at 2:10 PM, Pierre Rouleau <prouleau...@gmail.com> wrote:
> > On page 128 in Chapter 5 the FSM example shows how functions are used
> > to implement the sates.  The code states that it's tail recursive, but
> > function idle() calls function ringing() and vice versa.  Since
> > functions return a value, I don't see how the compiler can optimize
> > the code so that it does not end up consuming stack space for each
> > call. Is it?
>

> --Hynek (Pichi) Vychodil
>
>

Thanks,

-- Pierre

[Marc van Woerkom]

Hi Pierre,

the recursion either
a) goes on, then only the function arguments change in-place from recursion to
recursion, or
b) the recursion stops, meaning the call at that recursion level returns something,
and all prior recusion levels simply pass the result up, so in the end only one
function instance is returning something.

If this is still unclear, please give example code here, it is easier for discussion.

I also found this blog article interesting

http://prog21.dadgum.com/1.html

Regards,
Marc

2010/8/6 Pierre Rouleau <proul...@gmail.com>

[Pierre Rouleau]

Hi Marc,

thanks for the link. It does help. I gave my original question some
more thought and I can see how Last Call Optimization can work in the
Book's FSM example. Another page contains interesting discussion of
that topic: http://learnyousomeerlang.com/recursion .



On Aug 6, 3:29 am, Marc van Woerkom <marc.vanwoer...@googlemail.com>
wrote:

> Hi Pierre,
>
> the recursion either
> a) goes on, then only the function arguments change in-place from recursion
> to
> recursion, or
> b) the recursion stops, meaning the call at that recursion level returns
> something,
> and all prior recusion levels simply pass the result up, so in the end only
> one
> function instance is returning something.
>
> If this is still unclear, please give example code here, it is easier for
> discussion.
>
> I also found this blog article interesting
>
> http://prog21.dadgum.com/1.html
>
> Regards,
> Marc
>

> 2010/8/6 Pierre Rouleau <prouleau...@gmail.com>

>
>
>
>
>
> > - why can the compiler perform this tail call optimization when the
> > functions are returning something?

Thanks,

-- Pierre