[erlang-questions] tail recursion : sharing a learning and a question
Amit Murthy
I just learned that every iteration of the below code goes onto the stack.
The evaluation of the "catch" has something to do with it though I could
understand why.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Bad code, Bad code, Bad code, Bad code, Bad code, Bad code,
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
do_maintenance(CacheSz, HKIntvl, Oldest) ->
try
receive
Message ->
met_util:log_info(" pid -~p recieved unexpected message[~p].
",[self(), Message])
after HKIntvl ->
NOldest = do_cleanup(CacheSz, Oldest, 100),
do_maintenance(CacheSz, HKIntvl, NOldest)
end
catch
error:Error ->
met_util:log("~p do_maintenance() caught exception ->
~p",[?MODULE, Error]),
do_maintenance(CacheSz, HKIntvl, Oldest)
end.
%%%%%%%
The right way of course is to not trap exceptions here, remove the try-catch
and put the whole thing under a supervisor (with restart) behavior.
Which is what I have done now.
Would still like to know as to why the try-catch ends up killing tail
recursion. Can't the compiler catch this (pun intended) and optimize it for
tail recursion?
Regards,
Amit
Witold Baryluk
> Hi,
>
> I just learned that every iteration of the below code goes onto the stack.
> The evaluation of the "catch" has something to do with it though I could
> understand why.
It is not tail recursive version, because there is some additional work
after exit of last function, namely change catch handlers, to the
previous ones.
This should work.
do_maintenance(CacheSz, HKIntvl, Oldest) ->
try
do_maintance0(CacheSz, HKIntvl, Oldest);
catch
error:Error ->
met_util:log("~p do_maintenance() caught exception ->
~p",[?MODULE, Error]),
do_maintenance(CacheSz, HKIntvl, Oldest)
end.
do_maintenance0(CacheSz, HKIntvl, Oldest) ->
receive
Message ->
met_util:log_info(" pid -~p recieved unexpected
message[~p].",[self(), Message])
after HKIntvl ->
NOldest = do_cleanup(CacheSz, Oldest, 100),
do_maintenance0(CacheSz, HKIntvl, NOldest)
end.
--
Witold Baryluk <bar...@smp.if.uj.edu.pl>
David Mercer
> Would still like to know as to why the try-catch ends up killing tail
> recursion. Can't the compiler catch this (pun intended) and optimize it
> for
> tail recursion?
Well, you *could* remove the try-catch and put that in a function that calls
do_maintenance/3, enabling the tail-call optimization, but that would change
the semantics of the function. I believe the function, as written, would
need to keep the stack around (that is, not optimize the tail-call - which
isn't really a tail-call, since it is within the try-catch) unless you
decide to carry around an accumulator with the state that would have been in
the stack (specifically, a list of Oldest's).
That is, whatever mechanism you use to handle errors in the error-handler
would have to be handled in a tail-call-optimizable way. I'm sure someone
else can explain it better than me, but I'm thinking of errors in the call
on the following line:
> do_maintenance(CacheSz, HKIntvl, Oldest)
Your code, as written, handles that by pushing it up to the next exception
handler on the stack. If you were to tail-call-optimize that stack frame
away, then the behavior of your program has changed.
Cheers,
David
________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org
Richard Carlsson
> I just learned that every iteration of the below code goes onto the stack.
> The evaluation of the "catch" has something to do with it
>
> try
> receive
> after HKIntvl ->
> ...
> do_maintenance(CacheSz, HKIntvl, NOldest)
> end
> catch
> error:Error ->
> do_maintenance(CacheSz, HKIntvl, Oldest)
> end.
>
> The right way of course is to not trap exceptions here, remove the try-catch
> and put the whole thing under a supervisor (with restart) behavior.
> Which is what I have done now.
It would be sufficient to rewrite it like this:
do_maintenance(CacheSz, HKIntvl, Oldest) ->
try
receive
...,
Oldest
after HKIntvl ->
...,
NOldest
end
of
NewOldest -> do_maintenance(CacheSz, HKIntvl, NewOldest)
catch
error:Error ->
...
do_maintenance(CacheSz, HKIntvl, Oldest)
end.
The "protected" part of the code is the one between 'try' and 'of',
or between 'try' and 'catch' if there is no 'of' section. In the
protected part, tail recursive calls are not possible. (The call
in the 'catch...end' section, however, is tail recursive here.)
Basically, what your version of the code says is "if the recursive
call fails, we must catch that before we are allowed to exit from
the current call". The rewritten version above says "do the receive
and the log_info or cleanup, and catch any errors in that part (but
only in that part), then do a tail call to exit from the current call".
> Would still like to know as to why the try-catch ends up killing tail
> recursion. Can't the compiler catch this (pun intended) and optimize it for
> tail recursion?
No, because what the code says is that it should catch errors that may
happen in the recursive call, and handle the errors using the context of
the current call (e.g., the current value of Oldest). This means that
the compiler must keep the stack entry for the current call until the
recursive call has finished. Hence, no tail recursion optimization.
/Richard
Amit Murthy
Amit