Tail/Non tail recursion

[Thomas Lindgren]

--- "Richard A. O'Keefe" <ok@REDACTED> wrote:
> To so that we're all signing off the same
> song-sheet,
> the question is whether the function
> 
>     f([H|T]) -> [X+1 | f(X)];
>     f([])    -> [].
> 
> can be tail recursive.
> 
> The answer of course is that it could be, quite
> easily.
> The Prolog equivalent
> 
>     f([H1|T1], [H2|T2]) :-
>         H2 is H1 + 1,
>         f(T1, T2).
>     f([], []).
> 
> is certainly tail recursive.  A couple of years ago
> I proposed to Kostas
> Sagonis that HiPE should also do this, but given the
> need for HiPE to work
> with BEAM, I don't know if that was ever found to be
> practical. 

First, let me say that I don't support user-accessible
destructive operations in Erlang. Keep the language as
pure as possible. Under the hood, however, destructive
updates are interesting.

I know that on smaller programs, it can be a big win.
A (very much) older version of Hipe had a destructive
assignment BIF, for that purpose and others, e.g.,
pure, fast hashtables, again a la Prolog. We
hand-coded the assignments for some microexamples, and
found that it gave good speedups. I don't have the
precise numbers anymore. (This was in 96-98.)

BEAM for a time had some support for destructive
update but I believe this intreacted badly with GC
when generational garbage collection appeared, and was
removed. This can likely be fixed if there is need for
it.

(Getting destructive assignment near the speed of C is
still difficult, mostly due to garbage collector
issues.)

The obvious next step would be to automatically detect
when to do this, and to introduce assignments and
extra "pointer arguments". That would mean one could
evaluate the effect on real code. My guess is it could
be worthwhile.

Best,
Thomas


__________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
http://search.yahoo.com