Simon Cozens <[EMAIL PROTECTED]> formally RFC'd:
> I have no idea how to implement tail recursion elimination, and I'd
> dearly love to learn. Unrolling loops with constant indices shouldn't be
> too hard.
AIUI you trigger your destructors on the appearance
of the "return" keyword rather than on the exiting of the block.
The problem is the life of locals that are referred to in the returned
expression, but that is not a value if you mark them as exempt from destruction
or copy their values onto the new parameter list first.
If we are hastier with our destructions on returns, we get tail optomizations
for free. At any cost? I don't see much cost, please someone who understands
the greater trickiness explain it.
# we've got some kind of data structure implemented in
# a big, ugly hash %buh and $$buh{key}{next} is the next
# element from key, if defined
sub recursive_list_end($){
my $element = $buh{$_[0]};
return $_[0] unless defined $element{next};
# warning: reference loops kill!
return recursive_list_end $element{next};
};
I guess right now, C<return> works like a normal function up until it
does it's thing and exits the scope, triggering destruction. It is normal
in that its arguments are evaluated fully.
So all these subroutine scopes stack up, waiting for their last argument,
and it is common to run out of memory or at get seriously into your swap space.
I think that tail recursion could be made possible by simply making C<return>
a more magical keyword:
Each thread would maintain a global Thing_That_Is_Being_Returned pointer,
and on entry into a C<return> call, opposed to on completion of the gathering
of the parameter list, That_Which_Is_Being_Returned starts pointing to
the expression which is C<return>'s argument list, and destruction of the
current scope (except for elements referred to from TWIBR's parameters).
We do not have to run complex heuristics to recognize tail-optimizable situations
if we always do things this way (early destruction on return).
CLASSIC RECURSION: return is just another function, gathering all its data
before "running" and leaving the scope, at which time destruction occurs.
TAIL-OPTIMIZED RECURSION: return triggers destruction, except for things passed
to functions named in expressions. Memory which is tied up in stack frames
and other undestroyed structures in Classic model is available for reuse.
--
David Nicol 816.235.1187 [EMAIL PROTECTED]
"The most powerful force in the universe is gossip"
