Tail calls again and again
Rémi Forax
http://weblogs.java.net/blog/forax/archive/2009/12/18/tailcall-anyone
I have do some tests and it works very well :)
R�mi
Charles Oliver Nutter
> Rémi
>
>
> --
>
> You received this message because you are subscribed to the Google Groups "JVM Languages" group.
> To post to this group, send email to jvm-la...@googlegroups.com.
> To unsubscribe from this group, send email to jvm-language...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en.
>
>
>
fo...@x9c.fr
Great piece of news !
Sorry to ask such a naive question, but why is it the responsibility
of the bytecode emitter to mark a call as "tail" ?
It seems fairly easy for HotSpot to decide whether a call is tail or not.
Does this mean that some language implementers would like to have
their calls unoptimized even when they could be ? The only reason I
can think of is to have full stack trace. However, in this case, I would
expect to just have a "-XX" flag to disable tailcall optimization when
one wishes to have full stack traces.
Xavier Clerc
Patrick Wright
> of the bytecode emitter to mark a call as "tail" ?
> It seems fairly easy for HotSpot to decide whether a call is tail or not.
>
> Does this mean that some language implementers would like to have
> their calls unoptimized even when they could be ? The only reason I
> can think of is to have full stack trace. However, in this case, I would
> expect to just have a "-XX" flag to disable tailcall optimization when
> one wishes to have full stack traces.
see http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm, "hard"
versus "soft" tail calls.
fo...@x9c.fr
Thanks for the pointer.
If I understand correctly, tailcall information will be emitted by the compiler
for the sole purpose of being sure that HotSpot will actually perform the
optimization (and raise an exception if not).
While ensuring that the optimization is actually performed is very important,
it seems to be a novelty in the JVM: to the best of my knowledge, there is no
other way to guarantee that any optimization will actually occur.
Is this correct ?
Xavier Clerc
Per Bothner
> While ensuring that the optimization is actually performed is very important,
> it seems to be a novelty in the JVM: to the best of my knowledge, there is no
> other way to guarantee that any optimization will actually occur.
> Is this correct ?
Tail-call optimization is not a pure optimization, as it changes the
semantics in a fundamental way: It removes stack traces, which are
part of both observable behaviour (stack traces) and the Java security
architecture. Conversely, the lack of tail-call optimization when it
is expected (or demanded by some [non-Java] language specification)
means that a program that should run in finite memory will run out of
stack.
--
--Per Bothner
p...@bothner.com http://per.bothner.com/
Patrick Wright
> If I understand correctly, tailcall information will be emitted by the compiler
> for the sole purpose of being sure that HotSpot will actually perform the
> optimization (and raise an exception if not).
>
> While ensuring that the optimization is actually performed is very important,
> it seems to be a novelty in the JVM: to the best of my knowledge, there is no
> other way to guarantee that any optimization will actually occur.
> Is this correct ?
What I can say is just based from trying to follow the various
discussions here. This "optimization" allows you to have repeated tail
calls without blowing out your stack. Without this "optimization", you
have a serious (and unpredictable) hard limit on how deep you can
recurse. With the optimization, you don't (all else being equal). So
the issue here is that language designers/implementors and programmers
know they can use tail calls without running into a wall.
This is different from other "optimizations" we usually talk about in
the JVM. And it's not just HotSpot, though the current patch is a
HotSpot patch. The idea would be to make the bytecode, and its
interpretation, a standard feature of any compliant JVM.
John Cowan
> Tail-call optimization is not a pure optimization, as it changes the
> semantics in a fundamental way: It removes stack traces, which are
> part of both observable behaviour (stack traces) and the Java security
> architecture. Conversely, the lack of tail-call optimization when it
> is expected (or demanded by some [non-Java] language specification)
> means that a program that should run in finite memory will run out of
> stack.
Indeed. We need to be careful to distinguish between tail-calling as
an optimization and proper tail calling as a language feature. We
also need, while I'm at it, to distinguish between mere tail recursion
and generalized tail calling. I've been hammering on these
terminological confusions lately; it's all too easy for people, even
people who know better, to write "TCO" when they mean "proper tail
calling".
--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures
fo...@x9c.fr
I do wholeheartedly agree ; indeed for (direct) tail recursion, we need
nothing new: a goto with the first instruction of the method as the destination
does the trick.
Xavier Clerc
John Cowan
> I do wholeheartedly agree ; indeed for (direct) tail recursion, we need
> nothing new: a goto with the first instruction of the method as the destination
> does the trick.
Unless you are generating Java source rather than bytecode! Hence my
plea for goto support in Janino.
Rich Hickey
All points granted, but "proper" isn't that great either.
Rich