Tail/Non tail recursion

[Thomas Lindgren]

--- "Richard A. O'Keefe" <ok@REDACTED> wrote:
> I mentioned how 
>     f([H|T]) -> [X+1 | f(X)];
>     f([])    -> [].
> could be tail recursive.
> 
> Thomas Lindgren <thomasl_erlang@REDACTED> wrote:
> 
> 	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 am rather baffled by this, in context.
> The scheme I alluded to doesn't use destructive
> operations,
> only initialising writes.  (While a data structure
> might be
> constructed incrementally, it would only become
> readable once
> it was fully initialised.)

Let me explain my terminological choice. 

For our purposes, the example loop is a two step
process:

1. create A = [X+1 | <null value>]

2. in the next iteration of the loop, update the tail
element of A.

The <null value> is written only so that the GC can
scan the data structure. If the GC can detect this
anyway, then one can omit that write.

Between 1 and 2, there may in general be a garbage
collection. Thus, if a generational collector is used,
the code needs to check whether A was tenured or not,
and if tenured, record an old-to-new pointer.

(As I recall, BEAM:s GC furthermore did not support
such recording, since there was no need for it
elsewhere. I'm not sure of how things are now.)

The general operation is then, in my mind at least, a
full destructive update, hence the term. 

Certainly, one can detect special cases and optimize
the runtime system, change the GC, etc. to reduce
costs. Taking advantage of the writes being
initialising is one such case.

> [compile time reuse and module replacement as
destructive operations]

No, I was thinking of the much simpler and more
restricted case being discussed, and using destructive
updates of terms to implement this technique. Sorry
about being imprecise.

Disregarding terminology, while this technique seems
fairly straightforward, I for one haven't seen it used
in functional language implementations. (Well,
possibly excepting Jim Larus's thesis, which is a
corner case.) I think it would be interesting to try
it out.

Best,
Thomas


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