Tail calls
Jon Harrop
As I understand it, the implementation of tail calls in OpenJDK is complete
but Sun are not adding this feature to their JVM. Is that correct?
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
Patrick Wright
http://mail.openjdk.java.net/pipermail/mlvm-dev/2009-January/000331.html
(continues in postings through February). Prototyping is ongoing.
AFAIK it's not decided yet whether the JSR 292 expert group will
address this explicitly and seek to standardize on it.
HTH
Patrick
Charles Oliver Nutter
>
> As I understand it, the implementation of tail calls in OpenJDK is complete
> but Sun are not adding this feature to their JVM. Is that correct?
It's not necessarily Sun's choice when it exhibits external behavioral
changes. Such changes must be standardized so all JVMs will support
them. If it were just up to Sun, it would probably go in (since I know I
want it and several others want it).
My question back at you is this: what's your motive for posting this
question?
And of course you can certainly build OpenJDK + MLVM with tail calls to
try it yourself.
- Charlie
Jon Harrop
> It's not necessarily Sun's choice when it exhibits external behavioral
> changes. Such changes must be standardized so all JVMs will support
> them. If it were just up to Sun, it would probably go in (since I know I
> want it and several others want it).
Ok. I only care about Sun's JVM because it is the defacto standard. If tail
calls are not adopted as a standard across all JVMs, what are the odds of Sun
including them just in its own JVM as an extension?
> My question back at you is this: what's your motive for posting this
> question?
I want to make sure I've got my facts straight, both in order to make an
informed decision myself and to inform others accurately. Specifically, I am
considering diversifying into Scala and/or Clojure and I need to know whether
or not the elimination of tail calls may become reliable in those languages
in the relatively-near future. If not, that is a serious impediment for
functional languages and will rule out all JVM-based languages for me.
> And of course you can certainly build OpenJDK + MLVM with tail calls to
> try it yourself.
The problem is not my building and installing a custom JDK and testing it to
make sure that it is reliable myself. The problem is that requiring customers
to do that is such a substantial barrier to adoption that it would seriously
undermine commercial viability. Suffice to say, *not* having to do that has
always been one of the strongest selling points of the JVM.
kirk
> On Thursday 02 April 2009 15:09:12 Charles Oliver Nutter wrote:
>
>> It's not necessarily Sun's choice when it exhibits external behavioral
>> changes. Such changes must be standardized so all JVMs will support
>> them. If it were just up to Sun, it would probably go in (since I know I
>> want it and several others want it).
>>
>
> Ok. I only care about Sun's JVM because it is the defacto standard. If tail
> calls are not adopted as a standard across all JVMs, what are the odds of Sun
> including them just in its own JVM as an extension?
>
detail? And an optimization at that?
Why would others have to adopt? Not all have adopted CMS GC or survivor
spaces?
Regards,
Kirk
Patrick Wright
> detail? And an optimization at that?
>
> Why would others have to adopt? Not all have adopted CMS GC or survivor
> spaces?
I believe the idea is to force/require a tail call optimization,
rather than just hoping a JVM heuristic will kick in (assuming I
understand correctly). See
http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm for a more
detailed discussion. To quote from Arthur's email to the MLVM mailing
list (which I linked to previously): "To mark a call as tail call the
programmer emits a 'wide' byte code before the various invoke...
instructions."
HTH
Patrick
Ola Bini
> Jon Harrop wrote:
>
>> On Thursday 02 April 2009 15:09:12 Charles Oliver Nutter wrote:
>>
>>
>>> It's not necessarily Sun's choice when it exhibits external behavioral
>>> changes. Such changes must be standardized so all JVMs will support
>>> them. If it were just up to Sun, it would probably go in (since I know I
>>> want it and several others want it).
>>>
>>>
>> Ok. I only care about Sun's JVM because it is the defacto standard. If tail
>> calls are not adopted as a standard across all JVMs, what are the odds of Sun
>> including them just in its own JVM as an extension?
>>
>>
> why do they have to be exposed? Isn't tail recursion and implementation
> detail? And an optimization at that?
>
become valid with it that isn't valid without it. As such, there is a
real functional difference. It isn't very noticeable for the programs
written using the Java language, but other languages want to expose this
functionality.
Cheers
--
Ola Bini (http://olabini.com)
Ioke creator (http://ioke.org)
JRuby Core Developer (http://jruby.org)
Developer, ThoughtWorks Studios (http://studios.thoughtworks.com)
Practical JRuby on Rails (http://apress.com/book/view/9781590598818)
"Yields falsehood when quined" yields falsehood when quined.
kirk
>> why do they have to be exposed? Isn't tail recursion and implementation
>> detail? And an optimization at that?
>>
>> Why would others have to adopt? Not all have adopted CMS GC or survivor
>> spaces?
>>
>
> I believe the idea is to force/require a tail call optimization,
> rather than just hoping a JVM heuristic will kick in (assuming I
> understand correctly).
competitive thing.. take G1 for example.
> See
> http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm for a more
> detailed discussion. To quote from Arthur's email to the MLVM mailing
> list (which I linked to previously): "To mark a call as tail call the
> programmer emits a 'wide' byte code before the various invoke...
> instructions."
>
a passive kick in mechanism might get you to what you want faster...
it's working for other things ;-)
Kirk
Jon Harrop
> Jon Harrop wrote:
> > On Thursday 02 April 2009 15:09:12 Charles Oliver Nutter wrote:
> >> It's not necessarily Sun's choice when it exhibits external behavioral
> >> changes. Such changes must be standardized so all JVMs will support
> >> them. If it were just up to Sun, it would probably go in (since I know I
> >> want it and several others want it).
> >
> > Ok. I only care about Sun's JVM because it is the defacto standard. If
> > tail calls are not adopted as a standard across all JVMs, what are the
> > odds of Sun including them just in its own JVM as an extension?
>
> why do they have to be exposed? Isn't tail recursion and implementation
> detail? And an optimization at that?
Elimination of tail calls is a requirement for certain kinds of program to run
correctly. If tail calls are not eliminated, such programs leak stack space
until they die from a stack overflow exception.
In particular, tail calls are important in functional programs because that
paradigm encourages the composition of functions into arbitrarily-long
pipelines that data flow through in order to produce the desired result.
Without tail calls, every stage in the pipeline leaks stack space.
Note that "tail recursion" is a term typically used to describe the special
case of tail calls where the branch target is statically known and is often a
self-call. In general, tail calls refer to any calls in tail position and
they may well be calls to locations that are not statically known. Hence TCO
implementations often globally alter the calling convention used internally
by the VM and this can introduce disadvantages such as degraded performance
on other code.
kirk
> On Thursday 02 April 2009 15:36:38 kirk wrote:
>
>> Jon Harrop wrote:
>>
>>> On Thursday 02 April 2009 15:09:12 Charles Oliver Nutter wrote:
>>>
>>>> It's not necessarily Sun's choice when it exhibits external behavioral
>>>> changes. Such changes must be standardized so all JVMs will support
>>>> them. If it were just up to Sun, it would probably go in (since I know I
>>>> want it and several others want it).
>>>>
>>> Ok. I only care about Sun's JVM because it is the defacto standard. If
>>> tail calls are not adopted as a standard across all JVMs, what are the
>>> odds of Sun including them just in its own JVM as an extension?
>>>
>> why do they have to be exposed? Isn't tail recursion and implementation
>> detail? And an optimization at that?
>>
>
> Elimination of tail calls is a requirement for certain kinds of program to run
> correctly. If tail calls are not eliminated, such programs leak stack space
> until they die from a stack overflow exception.
>
Again, I'd just implement it in Sun and watch others follow. If it is
this big a problem, they will follow. Trying to force a standard will
take a long time and require a lot more effort IMHO.
Regards,
Kirk
Neil Bartlett
major ones -- into its JVM that are not necessarily supported by other
JVM vendors since they are not part of the Java 7 specification. The
specific feature I'm thinking of here is Jigsaw.
I can't comment as to whether Sun actually plans to implement tail
calls in it's JDK 7 or not. I personally would be a lot more
comfortable relying on TCO if it were part of the specification...
remember that the Sun JVM may be the de facto standard on Windows and
Linux but not necessarily on Macs, mobile devices and large enterprise
servers and mainframes.
Of course, for this feature to appear in the Java 7 specification,
that specification has to actually exist. Right now it looks like it
won't until after Sun's JDK 7 is released -- assuming Sun isn't
acquired in the meantime, in which case most bets are off.
Regards
Neil.
kirk
I see a lot of strawman arguments for standardization but I don't really
see anything with substance. I'm not against the standardization route
but I'm just not seeing the need to treat this any differently than
say.. a different GC implementation. How about Escape Analysis or the
internals of IBM's equivalent of HotSpot/JIT which is quite different.
What makes tail recursion different? JRockit 1.4 Mission Control seemed
to force JMX into the 1.5. IMHO, if it is going to make a difference,
others will pick it up and then it will be a lot easier to add it into
the JVM specification.
I hate to divert the thread but is Jigsaw really a feature of Java 7 or
a reworking of the packaging and delivery of Java?
Regards,
Kirk
Patrick Wright
> see anything with substance. I'm not against the standardization route
> but I'm just not seeing the need to treat this any differently than
> say.. a different GC implementation. How about Escape Analysis or the
> internals of IBM's equivalent of HotSpot/JIT which is quite different.
> What makes tail recursion different? JRockit 1.4 Mission Control seemed
> to force JMX into the 1.5. IMHO, if it is going to make a difference,
> others will pick it up and then it will be a lot easier to add it into
> the JVM specification.
It seems this is all premature. The most useful thing right now is to
have a prototype people can test against using OpenJDK and report back
on how much it helps. I'm pretty sure that as sure as the first
changeset is ready there will be a stable full of functional
programmers chomping at the bit to try it out. Then we can see how
much of a benefit it (this particular approach) is in practice.
Patrick
John Cowan
> why do they have to be exposed? Isn't tail recursion and implementation
> detail? And an optimization at that?
No.
Being able to rely on tail recursion is not an implementation detail;
Scheme programmers routinely write programs that tail-call heavily and
would blow up without it. A state machine implementation where state
transition codelets, expressed as functions, are tail-called by the
dispatcher and tail-call it in turn is a classic example. "Lambda:
the ultimate goto."
And since Java exposes the call stack via Exception#fillInStack, the
*presence* of tail recursion is unfortunately not an implementation
detail either.
--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures
Neil Bartlett
major changes like Jigsaw without a JSR, so why not tail calls? Having
said that, if you write code that relies on either Jigsaw or tail
calls then you are locked into one JVM.
I also don't want to divert the thread onto Jigsaw. I have made my
feeling about it clear in other places, but in this thread I use it
only as an example.
Regards
Neil
Ben Evans
I see a lot of strawman arguments for standardization but I don't really
see anything with substance. I'm not against the standardization route
but I'm just not seeing the need to treat this any differently than
say.. a different GC implementation. How about Escape Analysis or the
internals of IBM's equivalent of HotSpot/JIT which is quite different.
What makes tail recursion different? JRockit 1.4 Mission Control seemed
to force JMX into the 1.5. IMHO, if it is going to make a difference,
others will pick it up and then it will be a lot easier to add it into
the JVM specification.
If I'm following this thread right, then what is really meant by TCO is not "JVM implementations are allowed to spot that a certain pattern of bytecodes (eg 0xb6 0xXY 0xZW 0xb0) are a tail-call and MAY be optimised by the JITter" but "a certain, not currently permitted, sequence of bytecodes MUST be optimised as a tail-call so as to not grow the stack"
The MUST condition allows us to make semantic guarantees about certain recursive cases not blowing up the stack - important for functional languages. As I understand it, it is not currently possible to implement Scheme fully on the JVM, as the Scheme spec requires compilers to make a form of the above MUST guarantee (I am not a Scheme head, so if this is too much of a simplification, someone please put me right).
The reason why one implementation can't just unilaterally introduce it is that the pattern does not cuurently constitute valid Java code as per the spec, and the results of that - ie trying to run code compiled with the new bytecode form on a JVM which doesn't support it would not be good.
Imagine the situation where code compiled with one vendor's compiler could not be run on another vendor's JVM, despite them both claiming to support the same classfile version. Dialectisation, vendor-specific extensions to core specs and incompatability of binary files, depending on which compiler you used? Not a world I think we'd like...
Thanks,
Ben
kirk
> On Thu, Apr 2, 2009 at 10:36 AM, kirk <kirk.pe...@gmail.com> wrote:
>
>> why do they have to be exposed? Isn't tail recursion and implementation
>> detail? And an optimization at that?
>>
>
> No.
>
> Being able to rely on tail recursion is not an implementation detail;
> Scheme programmers routinely write programs that tail-call heavily and
> would blow up without it. A state machine implementation where state
> transition codelets, expressed as functions, are tail-called by the
> dispatcher and tail-call it in turn is a classic example. "Lambda:
> the ultimate goto."
>
> And since Java exposes the call stack via Exception#fillInStack, the
> *presence* of tail recursion is unfortunately not an implementation
> detail either.
>
Regards,
Kirk
Bradford Cross
I would imagine people are maintaining their own stacks? stacks and hacks. :-) Sounds like Dr Seuss...I will not hack upon your stack, i'll hack my stack to get you back.
We have talked about the fact that certain programs are invalid without TCO because they will overflow the stack - true enough.
Does anyone have any crude benchmarks re the perf overhead of doing these things in hand rolled stacks vs. at the byte code level. I have to imagine it is massive for certian classes of programs.
Per Bothner
> I want to make sure I've got my facts straight, both in order to make an
> informed decision myself and to inform others accurately. Specifically, I am
> considering diversifying into Scala and/or Clojure and I need to know whether
> or not the elimination of tail calls may become reliable in those languages
> in the relatively-near future. If not, that is a serious impediment for
> functional languages and will rule out all JVM-based languages for me.
A number of JVM-based languages implement tail-call elimination.
The problem is that you have to compile your functions into a
different calling convention that the natural. which has some
performance cost, and complicates interoperability.
Kawa supports two calling conventions, selected by a command-line
switch:
(1) The "obvious" one where a Scheme function call is translated to
a plain method call, with the methods return value being the Scheme
function's result.
(2) Full tail-call support using an extra hidden method argument
that points to a CallContext object. A call is translated thus:
- The parameters are evaluated, and copied into the CallContext.
- The function to be called is evaluated and saved in the CallContext.
- The calling function returns.
- That function's caller implements a "trampoline" (see
http://en.wikipedia.org/wiki/Tail_recursion and
http://en.wikipedia.org/wiki/Trampoline_%28computers%29 )
which then calls the function saved in the CallContext.
- The callee methods extracts its arguments from the CallContext.
This is obviously a bit slower, but not so much slower as
to be unusable. (The CallContext API isn't as tweaked as
it should be.)
The two calling conventions can interoperate, in the sense that
a function compiled with convention (1) can call a function
compiled with convention (2) and vice versa.
On 04/02/2009 09:46 AM, Ben Evans wrote:
> As I understand it, it is not currently possible to implement
> Scheme fully on the JVM, as the Scheme spec requires compilers to
> make a form of the above MUST guarantee (I am not a Scheme head, so >
> if this is too much of a simplification, someone please put me right).
You're right about Scheme, but wrong about it not being possible
to implement Scheme fully on the JVM.
In adding to tail-call-elimination full continuations are a
problem. Kawa doesn't implement those, but there are Scheme-on-JVM
implementations that do. (There is no reason Kawa can't implement
full call/cc, as an option at least - it's just more complexity and
overhead, and other things have had higher priority.)
--
--Per Bothner
p...@bothner.com http://per.bothner.com/
Jim Menard
<bradford...@gmail.com> wrote:
> What is the current state of the art for language implementers working
> around these issues (tail calls, continuations, etc) in Clojure, Scala,
> JRuby, etc?
Clojure uses recur (http://clojure.org/special_forms#toc10), "the only
non-stack-consuming looping construct in Clojure".
Here's the factory example from that page:
(def factorial
(fn [n]
(loop [cnt n acc 1]
(if (zero? cnt)
acc
(recur (dec cnt) (* acc cnt))))))
Jim
--
Jim Menard, ji...@io.com, jim.m...@gmail.com
http://www.io.com/~jimm/
Ola Bini
> What is the current state of the art for language implementers working
> around these issues (tail calls, continuations, etc) in Clojure,
> Scala, JRuby, etc?
>
> I would imagine people are maintaining their own stacks? stacks and
> hacks. :-) Sounds like Dr Seuss...I will not hack upon your stack,
> i'll hack my stack to get you back.
>
> We have talked about the fact that certain programs are invalid
> without TCO because they will overflow the stack - true enough.
>
> Does anyone have any crude benchmarks re the perf overhead of doing
> these things in hand rolled stacks vs. at the byte code level. I have
> to imagine it is massive for certian classes of programs.
but that is a very coarse and limited way of doing it. Scala removes
tail calls where it can be statically transformed into iteration, but
doesn't give any guarantees. Ruby has never had TCO's and JRuby uses the
Java stack too.
SISC is one of the few implementations that do full TCO. There are
basically a few variations on how to do it. CPS is common, trampolining
works too. You can also have your own bytecode engine with your own stack.
The overhead of all of these approaches are pretty severe on the JVM
since the usage pattern is data driven and far away from how regular
Java code looks like. But the most severe problem with it is that all of
these approaches make it much hard to do calls into Java methods.
Cheers
Per Bothner
> Scala removes tail calls where it can be statically transformed into iteration,
> but doesn't give any guarantees.
I should have mentioned that Kawa does this too, even when not
using the full-tail-elimination calling-convention. I assume
most Scheme on-JVM implementations do the same, to at least
some degree.
> The overhead of all of these approaches are pretty severe on the JVM
> since the usage pattern is data driven and far away from how regular
> Java code looks like.
I tried the a port of binarytress from the programming languages
"shootout", but it was too quick to be able to tell the difference.
I need a more serious test program ...
> But the most severe problem with it is that all of
> these approaches make it much hard to do calls into Java methods.
Not quite sure what you mean. Kawa has no problems calling Java
methods. Of course if you want the tail-call-elimination when calling
a Java method in tail position then it gets hairy - Kawa doesn't
try that. Though it doesn't seem that difficult - you could compile the
call into a separate stub function. Or just not "inline" the method
call, so it would be handled by reflection.
Chas Emerick
On Apr 2, 2009, at 1:14 PM, Jim Menard wrote:
>
> On Thu, Apr 2, 2009 at 1:10 PM, Bradford Cross
> <bradford...@gmail.com> wrote:
>> What is the current state of the art for language implementers
>> working
>> around these issues (tail calls, continuations, etc) in Clojure,
>> Scala,
>> JRuby, etc?
>
> Clojure uses recur (http://clojure.org/special_forms#toc10), "the only
> non-stack-consuming looping construct in Clojure".
In practice, recur in clojure is all you ever need to write non-stack-
consuming functions that have excellent performance characteristics
(each recursion is simply a trip through a while loop, IIRC). I
actually like the explicitness of recur, simply because of how it
makes what's going on completely obvious. Of course, that's
fundamentally an issue of style and idiom, and doesn't make the lack
of real TCO any less of a priority.
In those rare circumstances where you need to write mutually-recursive
functions without consuming stack, clojure provides a trampoline
implementation (introduced last November here: http://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454bcb85)
. There's obviously a performance penalty associated with their use,
but it's nice to have that escape hatch.
- Chas
Jorge Ortiz
No one is doing hand rolled stacks. Clojure does explicit trampolining -
Bradford Cross wrote:
> What is the current state of the art for language implementers working
> around these issues (tail calls, continuations, etc) in Clojure,
> Scala, JRuby, etc?
>
> I would imagine people are maintaining their own stacks? stacks and
> hacks. :-) Sounds like Dr Seuss...I will not hack upon your stack,
> i'll hack my stack to get you back.
>
> We have talked about the fact that certain programs are invalid
> without TCO because they will overflow the stack - true enough.
>
> Does anyone have any crude benchmarks re the perf overhead of doing
> these things in hand rolled stacks vs. at the byte code level. I have
> to imagine it is massive for certian classes of programs.
but that is a very coarse and limited way of doing it. Scala removes
tail calls where it can be statically transformed into iteration, but
doesn't give any guarantees. Ruby has never had TCO's and JRuby uses the
Java stack too.
Scala 2.8.0 (due out later this year) will add a @tailrec annotation that produces a compile error if the annotated method can't be statically transformed into iteration when tail-called.
Jorge Ortiz
--j
Charles Oliver Nutter
> If I'm following this thread right, then what is really meant by TCO is
> not "JVM implementations are allowed to spot that a certain pattern of
> bytecodes (eg 0xb6 0xXY 0xZW 0xb0) are a tail-call and MAY be optimised
> by the JITter" but "a certain, not currently permitted, sequence of
> bytecodes MUST be optimised as a tail-call so as to not grow the stack"
>
> The MUST condition allows us to make semantic guarantees about certain
> recursive cases not blowing up the stack - important for functional
> languages. As I understand it, it is not currently possible to implement
> Scheme fully on the JVM, as the Scheme spec requires compilers to make a
> form of the above MUST guarantee (I am not a Scheme head, so if this is
> too much of a simplification, someone please put me right).
>
> The reason why one implementation can't just unilaterally introduce it
> is that the pattern does not cuurently constitute valid Java code as per
> the spec, and the results of that - ie trying to run code compiled with
> the new bytecode form on a JVM which doesn't support it would not be good.
This is a good description of the problem. Any JVM could implement
support for tail calls as long as it was not outwardly apparent (and
really, Hotspot et al eliminating several calls in cases where much of
the recursion chain can be inlined is a limited example of this). But
the MUST guarantee does make the support apparent and explicit, and so
it needs to be done uniformly across JVMs.
- Charlie
Charles Oliver Nutter
> Sun has recently shown willingness to introduce features -- even very
> major ones -- into its JVM that are not necessarily supported by other
> JVM vendors since they are not part of the Java 7 specification. The
> specific feature I'm thinking of here is Jigsaw.
If you're referring to the work in MLVM (Da Vinci Machine), then you're
not talking about released, production JVMs. No Sun-released JVM does
not conform to current standards for all JVMs, which means that tail
calls could not get into a released JVM without being standardized.
I would certainly love to see them in Java 7, but there's no guarantee
it will happen.
- Charlie
Charles Oliver Nutter
> The problem is not my building and installing a custom JDK and testing it to
> make sure that it is reliable myself. The problem is that requiring customers
> to do that is such a substantial barrier to adoption that it would seriously
> undermine commercial viability. Suffice to say, *not* having to do that has
> always been one of the strongest selling points of the JVM.
Well, you can always build and release a binary yourself, since it's
GPLed...you just can't call it "Java" or "JVM" because it's not being
held to those standards. Would that make you comfortable enough to run
something like MLVM with its early tail call support?
- Charlie
Randall R Schulz
> ...
>
> Well, you can always build and release a binary yourself, since it's
> GPLed...you just can't call it "Java" or "JVM" because it's not being
> held to those standards. Would that make you comfortable enough to
> run something like MLVM with its early tail call support?
For uses other than experiments of various sorts or for purely local
development activities, this is a non-starter. I'm pretty sure that the
respective principals behind Clojure and Scala will not alter their
code generation to exploit non-standard JVM bytecodes, so for the large
majority of users, this approach is simply irrelevant.
Furthermore, it's not as if this _concept_ is new—it is not. The
consequences of having or not having TCO are well understood. The point
being that experimentation isn't really what's required by the
community of JVM users (however defined, be it language designers,
compiler writers or programmers using one of the fascinating and
valuable non-Java JVM-based-languages).
Frankly, I cannot see why this is a matter of debate among the ranks of
those who make the decisions about the JVM standard. There is manifest
need for TCO at the JVM level and it should go in forthwith.
> - Charlie
Randall Schulz
Charles Oliver Nutter
> On Thursday April 2 2009, Charles Oliver Nutter wrote:
>> ...
>>
>> Well, you can always build and release a binary yourself, since it's
>> GPLed...you just can't call it "Java" or "JVM" because it's not being
>> held to those standards. Would that make you comfortable enough to
>> run something like MLVM with its early tail call support?
>
> For uses other than experiments of various sorts or for purely local
> development activities, this is a non-starter. I'm pretty sure that the
> respective principals behind Clojure and Scala will not alter their
> code generation to exploit non-standard JVM bytecodes, so for the large
> majority of users, this approach is simply irrelevant.
JRuby already includes logic that will attempt to use invokedynamic when
running on a VM with invokedynamic. I plan to do the same for other
experimental features like TCO. It's not that hard.
- Charlie
Ben Evans
A number of JVM-based languages implement tail-call elimination.
The problem is that you have to compile your functions into a
different calling convention that the natural. which has some
performance cost, and complicates interoperability.
Kawa supports two calling conventions, selected by a command-line
switch:
(1) The "obvious" one where a Scheme function call is translated to
a plain method call, with the methods return value being the Scheme
function's result.
(2) Full tail-call support using an extra hidden method argument
that points to a CallContext object. A call is translated thus:
- The parameters are evaluated, and copied into the CallContext.
- The function to be called is evaluated and saved in the CallContext.
- The calling function returns.
- That function's caller implements a "trampoline" (see
http://en.wikipedia.org/wiki/Tail_recursion and
http://en.wikipedia.org/wiki/Trampoline_%28computers%29 )
which then calls the function saved in the CallContext.
- The callee methods extracts its arguments from the CallContext.
This is obviously a bit slower, but not so much slower as
to be unusable. (The CallContext API isn't as tweaked as
it should be.)
On 04/02/2009 09:46 AM, Ben Evans wrote:You're right about Scheme, but wrong about it not being possible
> As I understand it, it is not currently possible to implement
> Scheme fully on the JVM, as the Scheme spec requires compilers to
> make a form of the above MUST guarantee (I am not a Scheme head, so >
> if this is too much of a simplification, someone please put me right).
to implement Scheme fully on the JVM.
Ah yes, I should have said "whilst maintaining standard calling conventions".
Thanks for the catch,
Ben
Robert Fischer
turning the entire method into a loop. I'm not sure if any language does this currently (I'd be
surprised if they didn't), but it's at least possible.
~~ Robert.
--
~~ Robert Fischer.
Grails Training http://GroovyMag.com/training
Smokejumper Consulting http://SmokejumperIT.com
Enfranchised Mind Blog http://EnfranchisedMind.com/blog
Check out my book, "Grails Persistence with GORM and GSQL"!
http://www.smokejumperit.com/redirect.html
Rémi Forax
Clojure or Scala just compile to plain bytecode.
> - Charlie
>
Rémi
Robert Fischer
> In those rare circumstances where you need to write mutually-recursive
> functions without consuming stack, clojure provides a trampoline
> implementation (introduced last November here: http://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454bcb85)
> . There's obviously a performance penalty associated with their use,
> but it's nice to have that escape hatch.
>
I was thinking about this. For any given tail recursive function, it can be turned into a
non-stack-building loop. The transformation I'm thinking of looks like this:
public int foo(int bar, String baz) {
/* Some logic for foo, including an escape */
int newBar = ...;
String newBaz = ...;
return foo(newBar, newBaz);
}
becomes
public int foo(int bar, String baz) {
label :top;
/* Some logic for foo, including an escape */
bar = newBar;
baz = newBaz;
jump :top;
}
Now consider two mutually recursive functions, 'foo' and 'bar'.
public int foo(int fooInt, String fooString) {
/* Some logic for foo, possibly including an escape */
int newBarInt = ...;
String newBarString = ...;
return bar(newBarInt, newBarString);
}
public int bar(int barInt, String barString) {
/* Some logic for bar, possibly including an escape */
int newFooInt = ...;
String newFooString = ...;
return foo(newFooInt, newFooString);
}
Given those two functions, what's to keep us from creating a structure like this?
private static class FooArgs {
public int fooInt;
public String fooString;
public FooArgs(int fooInt, String fooString) {
this.fooInt = fooInt;
this.fooString = fooString;
}
}
private static class BarArgs {
public int barInt;
public String barString;
public BarArgs(int barInt, String barString) {
this.barInt = barInt;
this.barString = barString;
}
}
public int foo(int fooInt, String fooString) {
return foobar(new FooArgs(fooInt, fooString), null, true);
}
public int bar(int barInt, String barString) {
return foobar(null, new BarArgs(barInt, barString), false);
}
private int foobar(FooArgs fooArgs, BarArgs, barArgs, boolean doFoo) {
String fooString, barString;
int fooInt, barInt;
if(doFoo) {
fooInt = fooArgs.fooInt;
fooString = fooArgs.fooString;
fooArgs = null;
jump :foo
} else {
barInt = barArgs.barInt;
barString = barArgs.barString;
barArgs = null;
jump :bar
}
label :foo
/* Some logic for foo, including an escape */
barInt = ...
barString = ...
fooString = null;
jump :bar;
label :bar;
/* Some logic for bar, including an escape */
fooInt = ...
fooString = ...
barString = null;
jump :foo;
}
I know there are method size limits, but assuming we stay under them, this should work for solving
at least the common case of two, small, mutually recursive functions. And it could be generalized up.
Jim White
> Chas Emerick wrote:
>
>>In those rare circumstances where you need to write mutually-recursive
>>functions without consuming stack, clojure provides a trampoline
>>implementation (introduced last November here: http://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454bcb85)
>>. There's obviously a performance penalty associated with their use,
>>but it's nice to have that escape hatch.
>>
>
> I was thinking about this. For any given tail recursive function, it can be turned into a
> non-stack-building loop. The transformation I'm thinking of looks like this:
> ...
That is what Kawa does (as a code generation option) in order to fully
support tail-calls, as Per explained earlier today (10:11AM).
There is a paper or two and a couple presentations on that which Per
didn't cite.
http://www.google.com/search?q=tail+call+support+in+kawa
Jim
---
http://www.ifcx.org/
Robert Fischer
~~ Robert.
Charles Oliver Nutter
> If you have something like a JIT in your language runtime.
> Clojure or Scala just compile to plain bytecode.
Sounds like a design flaw :)
But seriously... you could certainly AOT compile code that targets those
features when they're present on the compiling JVM.
- Charlie
Jon Harrop
> Jon Harrop wrote:
> > The problem is not my building and installing a custom JDK and testing it
> > to make sure that it is reliable myself. The problem is that requiring
> > customers to do that is such a substantial barrier to adoption that it
> > would seriously undermine commercial viability. Suffice to say, *not*
> > having to do that has always been one of the strongest selling points of
> > the JVM.
>
> Well, you can always build and release a binary yourself,
Obviously "a binary" is not sufficient because it will only run on one version
of one OS. I would need JVMs in binary form for every architecture/platform
combo that our customers use (which is dozens). I've tried that before and it
creates a sufficiently high barrier to entry for customers that it is not
commercially viable for us.
> since it's
> GPLed...you just can't call it "Java" or "JVM" because it's not being
> held to those standards. Would that make you comfortable enough to run
> something like MLVM with its early tail call support?
You mean if I wanted to tinker with it? Sure, but there is little point in me
running it if my customers will not.
Jon Harrop
> It seems this is all premature. The most useful thing right now is to
> have a prototype people can test against using OpenJDK and report back
> on how much it helps. I'm pretty sure that as sure as the first
> changeset is ready there will be a stable full of functional
> programmers chomping at the bit to try it out. Then we can see how
> much of a benefit it (this particular approach) is in practice.
If you want to see how much of a benefit tail calls are in practice, look
at .NET (which has had them for the best part of a decade).
Charles Oliver Nutter
> You mean if I wanted to tinker with it? Sure, but there is little point in me
> running it if my customers will not.
So you're really not looking for a solution then, unless it's someone
else (Sun) putting the work in to get it into a release, right?
Perhaps you could offer up an idea or offer your help to make this
happen, since there's already scant resources available.
- Charlie
Jon Harrop
> What is the current state of the art for language implementers working
> around these issues (tail calls, continuations, etc) in Clojure, Scala,
> JRuby, etc?
The state of the art in all of the major "functional" languages for the JVM
(Scala and Clojure) is that they die with a stack overflow because the JVM
lacks tail calls. :-)
> I would imagine people are maintaining their own stacks? stacks and hacks.
Martin Odersky, the creator of Scala, put a lot of effort into finding
workarounds for the lack of tail calls on the JVM:
http://docs.msdnaa.net/ark_new/Webfiles/WhitePapers/Babel01/bab12.pdf
but, in the end, he gave up completely and Scala provides no workaround.
Clojure also provides no workaround.
The creators of both languages are pinning their hopes on getting tail calls
in the VM and settling for local hand-written trampolines in the mean time.
> We have talked about the fact that certain programs are invalid without TCO
> because they will overflow the stack - true enough.
>
> Does anyone have any crude benchmarks re the perf overhead of doing these
> things in hand rolled stacks vs. at the byte code level. I have to imagine
> it is massive for certian classes of programs.
I am not aware of a performance comparison between a workaround (such as a
global trampoline) and tail calls in the VM. There are comparisons with
non-tail calls in inefficient language implementations that range from
1.2-10x slower but that is of no relevance.
Benchmarking against MLVM with tail calls would be interesting...
Jon Harrop
> Kawa supports two calling conventions, selected by a command-line
> switch:
> (1) The "obvious" one where a Scheme function call is translated to
> a plain method call, with the methods return value being the Scheme
> function's result.
> (2) Full tail-call support using an extra hidden method argument
> that points to a CallContext object. A call is translated thus:
> - The parameters are evaluated, and copied into the CallContext.
> - The function to be called is evaluated and saved in the CallContext.
> - The calling function returns.
> - That function's caller implements a "trampoline" (see
> http://en.wikipedia.org/wiki/Tail_recursion and
> http://en.wikipedia.org/wiki/Trampoline_%28computers%29 )
> which then calls the function saved in the CallContext.
> - The callee methods extracts its arguments from the CallContext.
>
> This is obviously a bit slower, but not so much slower as
> to be unusable. (The CallContext API isn't as tweaked as
> it should be.)
>
> The two calling conventions can interoperate, in the sense that
> a function compiled with convention (1) can call a function
> compiled with convention (2) and vice versa.
When Java calls back into Kawa, where does Kawa get the current CallContext
from when it has not been passed in as the first argument?
Jon Harrop
> On Apr 2, 2009, at 1:14 PM, Jim Menard wrote:
> > On Thu, Apr 2, 2009 at 1:10 PM, Bradford Cross
> >
> > <bradford...@gmail.com> wrote:
> >> What is the current state of the art for language implementers
> >> working
> >> around these issues (tail calls, continuations, etc) in Clojure,
> >> Scala,
> >> JRuby, etc?
> >
> > Clojure uses recur (http://clojure.org/special_forms#toc10), "the only
> > non-stack-consuming looping construct in Clojure".
>
> In practice, recur in clojure is all you ever need to write non-stack-
> consuming functions that have excellent performance characteristics
> (each recursion is simply a trip through a while loop, IIRC).
Here is a trivial counter example written in OCaml:
let even odd n =
printf "even %d\n" n;
odd(n+1)
let rec odd n =
even odd (n+1)
let () = odd 1
The branch target "odd" in the "even" function is not statically known. So
that program cannot be written correctly in Scala or Clojure.
Per Bothner
> When Java calls back into Kawa, where does Kawa get the current CallContext
> from when it has not been passed in as the first argument?
The CallContext is a per-thread structure, stored in a ThreadLocal.
Passing the CallContext from caller to callee in a synthetic parameter
can be thought of as an optimization compared to always using
a ThreadLocal.
One might think of the CallContext structure as a set of "virtual
hardware registers". Obviously, there is some flexibility in
designing a calling convention when you can pick the "register
set" that gives best performance. I don't pretend to have done
a particularly good job in that design - but it works, and the
overhead is tolerable.
I think most people who use Kawa are more interested in the
Java interoperability and/or performance, and so my guess is
the CallContext-based calling convention isn't used as much.
But I don't know. Qexo, the Kawa implementation of the
XQuery language does use the CallContext-based calling convention
by default. One reason is that XQuery is all about returning
sequences of values, which can be implemented efficiently
using a SAX-like "push target" - which is also an implicit
parameter, stored in the CallContext.
Jon Harrop
> Jon Harrop wrote:
> > You mean if I wanted to tinker with it? Sure, but there is little point
> > in me running it if my customers will not.
>
> So you're really not looking for a solution then, unless it's someone
> else (Sun) putting the work in to get it into a release, right?
On the contrary, I am building a new VM from scratch with my own money
precisely because I believe this issue is so important.
If Sun do the work, I will build commercial products on their platform as
well. Otherwise, I'll stick with their competitors.
> Perhaps you could offer up an idea or offer your help to make this
> happen, since there's already scant resources available.
If you cannot get tail calls accepted into the required standard, then release
an additional non-standard JVM that includes the existing implementation of
tail call elimination (and potentially other useful features).
kirk
Now we are getting somewhere ;-)
Ben Evans wrote:
> Hi Kirk,
>
> On Thu, Apr 2, 2009 at 4:51 PM, kirk <kirk.pe...@gmail.com
> <mailto:kirk.pe...@gmail.com>> wrote:
>
>
> I see a lot of strawman arguments for standardization but I don't
> really
> see anything with substance. I'm not against the standardization route
> but I'm just not seeing the need to treat this any differently than
> say.. a different GC implementation. How about Escape Analysis or the
> internals of IBM's equivalent of HotSpot/JIT which is quite different.
> What makes tail recursion different? JRockit 1.4 Mission Control
> seemed
> to force JMX into the 1.5. IMHO, if it is going to make a difference,
> others will pick it up and then it will be a lot easier to add it into
> the JVM specification.
>
>
> If I'm following this thread right, then what is really meant by TCO
> is not "JVM implementations are allowed to spot that a certain pattern
> of bytecodes (eg 0xb6 0xXY 0xZW 0xb0) are a tail-call and MAY be
> optimised by the JITter" but "a certain, not currently permitted,
> sequence of bytecodes MUST be optimised as a tail-call so as to not
> grow the stack"
Ok, this would be a problem if the spec specifically prohibited a
reasonable optimization.
>
> The MUST condition allows us to make semantic guarantees about certain
> recursive cases not blowing up the stack - important for functional
> languages. As I understand it, it is not currently possible to
> implement Scheme fully on the JVM, as the Scheme spec requires
> compilers to make a form of the above MUST guarantee (I am not a
> Scheme head, so if this is too much of a simplification, someone
> please put me right).
Ok, lets inject the Azul JVM into this conversation. If optimizes away a
lot of things because it has the hardware support to manage them.
Pointer swizzling for moved objects for example, transactional memory
affecting synchronization for another. These "optimizations" make the
Azul VM much different than any other implementation yet they are able
to meet the standard. They don't require special class files that won't
run on other VMs. Of course other VMs don't offer the benefits. But then
GC works the same, you won't get G1 benefits unless you are using Sun.
>
> The reason why one implementation can't just unilaterally introduce it
> is that the pattern does not cuurently constitute valid Java code as
> per the spec, and the results of that - ie trying to run code compiled
> with the new bytecode form on a JVM which doesn't support it would not
> be good.
>
> Imagine the situation where code compiled with one vendor's compiler
> could not be run on another vendor's JVM, despite them both claiming
> to support the same classfile version. Dialectisation, vendor-specific
> extensions to core specs and incompatability of binary files,
> depending on which compiler you used? Not a world I think we'd like...
agreed but I'm not sure that we need to go there. However, if the
OpenJDK happens to allow deeper stacks than the others or it knows how
to avoid having stacks build up, that would seem to be a competitive
advantage, not a violation of a specification or an incompatability
unless you did require special byte codes or invalid class files to make
it work. At any rate, I havn't said this shouldn't be part of the spec.
It is just that IME, it's easier to spec a working implementation than
just to go to committee trying to get everyone on board. Like it or hate
it, OSGi has helped demonstrate that hasn't it.
Regards,
Kirk
kirk
> Kirk, this was pretty much my point. Sun are willing to introduce
> major changes like Jigsaw without a JSR, so why not tail calls? Having
> said that, if you write code that relies on either Jigsaw or tail
> calls then you are locked into one JVM.
>
I applaud your principles. If you write code that relies on G1 behavior
then you are locked in also. Clients are doing this right now because
they *need* G1 guarantees and no one else is attempting to offer them
and the need to get work done so the choice is G1 or not Java.
Regards,
Kirk
kirk
>
>
> Frankly, I cannot see why this is a matter of debate among the ranks of
> those who make the decisions about the JVM standard. There is manifest
> need for TCO at the JVM level and it should go in forthwith.
>
Robert Fischer
> On Thursday 02 April 2009 18:10:05 Bradford Cross wrote:
>> What is the current state of the art for language implementers working
>> around these issues (tail calls, continuations, etc) in Clojure, Scala,
>> JRuby, etc?
>
> The state of the art in all of the major "functional" languages for the JVM
> (Scala and Clojure) is that they die with a stack overflow because the JVM
> lacks tail calls. :-)
>
Chas Emerick
On Apr 3, 2009, at 9:18 AM, Robert Fischer wrote:
>
> Jon Harrop wrote:
>> On Thursday 02 April 2009 18:10:05 Bradford Cross wrote:
>>> What is the current state of the art for language implementers
>>> working
>>> around these issues (tail calls, continuations, etc) in Clojure,
>>> Scala,
>>> JRuby, etc?
>>
>> The state of the art in all of the major "functional" languages for
>> the JVM
>> (Scala and Clojure) is that they die with a stack overflow because
>> the JVM
>> lacks tail calls. :-)
>>
> That's odd. I've been programming with Scala for a while now, and
> haven't had this issue.
Agreed, and the same goes for clojure using its recur mechanism.
There's no doubt that in every application-oriented context I've seen,
you can get the job done given the tools that scala and clojure
provide, absent contrived examples.
The issue is that many classic flow control mechanisms (and some
application-oriented algorithms) really do require the optimization of
mutual (or arbitrarily-complex) tail calls. This is where you have to
punt to trampolines. Of course, this is also where a lot of really
phenomenally useful, "foundational" FP constructs operate.
- Chas
Jon Harrop
> Jon Harrop wrote:
> > JVM (Scala and Clojure) is that they die with a stack overflow because
> > the JVM lacks tail calls. :-)
>
> That's odd. I've been programming with Scala for a while now, and haven't
> had this issue.
Search for "stack overflow" in the Scala compiler's own bug tracker. :-)
David MacIver
>
> On Friday 03 April 2009 14:18:32 Robert Fischer wrote:
>> Jon Harrop wrote:
>> > The state of the art in all of the major "functional" languages for the
>> > JVM (Scala and Clojure) is that they die with a stack overflow because
>> > the JVM lacks tail calls. :-)
>>
>> That's odd. I've been programming with Scala for a while now, and haven't
>> had this issue.
>
> Search for "stack overflow" in the Scala compiler's own bug tracker. :-)
Yes. Because all stack overflows are clearly caused by a failure of
tail recursion...
Except that in the real world the only issue you'll find that's even
slightly relevant is that List.equals isn't properly tail recursive
because of these issues (which is a pain, but can be circumvented).
Basically all stack overflows within the compiler itself that I'm
aware of are from the type checker, which you'd have a very hard time
making tail recursive without converting it to CPS to reify the stack
onto the heap.
Charles Oliver Nutter
> If you cannot get tail calls accepted into the required standard, then release
> an additional non-standard JVM that includes the existing implementation of
> tail call elimination (and potentially other useful features).
Or you could do it, since you seem to have the money and resources to
build a new VM from scratch. I think it would be more cost-effective to
start with OpenJDK and improve from there.
- Charlie
Jon Harrop
How difficult would it be to implement typed nulls and value types in OpenJDK?
Charles Oliver Nutter
> On Friday 03 April 2009 14:59:03 Charles Oliver Nutter wrote:
>> Jon Harrop wrote:
>>> If you cannot get tail calls accepted into the required standard, then
>>> release an additional non-standard JVM that includes the existing
>>> implementation of tail call elimination (and potentially other useful
>>> features).
>> Or you could do it, since you seem to have the money and resources to
>> build a new VM from scratch. I think it would be more cost-effective to
>> start with OpenJDK and improve from there.
>
> How difficult would it be to implement typed nulls and value types in OpenJDK?
Here's John Rose's article on tuples:
http://blogs.sun.com/jrose/entry/tuples_in_the_vm
And another on fixnums, which is probably also illustrative:
http://blogs.sun.com/jrose/entry/fixnums_in_the_vm
Typed nulls I'm not sure. Does anyone else know? I imagine this could be
implemented at a Java language level as well...is VM support needed?
- Charlie
John Cowan
> There's no doubt that in every application-oriented context I've seen,
> you can get the job done given the tools that scala and clojure
> provide, absent contrived examples.
Languages with proper tail-calling are a different paradigm from those
that don't provide it, or do so only as an optimization (like gcc).
If we don't have tail-calls in our repository of techniques, we simply
don't *see* the opportunities to use them, like patients with damage
to the visual cortext, who don't complain of being blind because they
have lost the very concept of seeing. It's surprising that so modest
a change can work such a vast transformation in thinking, but it does,
just like the difference between having only subroutines and having
coroutines as well.
--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures
Chas Emerick
On Apr 3, 2009, at 10:24 AM, John Cowan wrote:
>
> On Fri, Apr 3, 2009 at 9:31 AM, Chas Emerick <ceme...@snowtide.com>
> wrote:
>
>> There's no doubt that in every application-oriented context I've
>> seen,
>> you can get the job done given the tools that scala and clojure
>> provide, absent contrived examples.
>
> Languages with proper tail-calling are a different paradigm from those
> that don't provide it, or do so only as an optimization (like gcc).
> If we don't have tail-calls in our repository of techniques, we simply
> don't *see* the opportunities to use them, like patients with damage
> to the visual cortext, who don't complain of being blind because they
> have lost the very concept of seeing. It's surprising that so modest
> a change can work such a vast transformation in thinking, but it does,
> just like the difference between having only subroutines and having
> coroutines as well.
I agree completely. My only point was that many, many tasks have no
reason to use techniques that require anything more than locally-
recursive fns. Of course, YMMV depending on your context and
specialization.
- Chas
Antonio Cuni
> If you want to see how much of a benefit tail calls are in practice, look
> at .NET (which has had them for the best part of a decade).
.NET tail calls are totally inefficient. Here is a benchmark to measure tail
vs non-tail calls:
http://codespeak.net/svn/user/antocuni/cli-bench/tailcall.cs
Of course C# doesn't allow to specify a call as tail, so I had to manually
patch the IL; here is the modified IL version:
http://codespeak.net/svn/user/antocuni/cli-bench/tailcall.il
And here is the final executable:
http://codespeak.net/svn/user/antocuni/cli-bench/tailcall.exe
On windows, the tail call is about 10 times *slower* than the normal call,
which is by itself 2 times slower than the for loop.
ciao,
Anto
Robert Fischer
the functional languages.
~~ Robert.
John Cowan wrote:
> On Fri, Apr 3, 2009 at 9:31 AM, Chas Emerick <ceme...@snowtide.com> wrote:
>
>> There's no doubt that in every application-oriented context I've seen,
>> you can get the job done given the tools that scala and clojure
>> provide, absent contrived examples.
>
> Languages with proper tail-calling are a different paradigm from those
> that don't provide it, or do so only as an optimization (like gcc).
> If we don't have tail-calls in our repository of techniques, we simply
> don't *see* the opportunities to use them, like patients with damage
> to the visual cortext, who don't complain of being blind because they
> have lost the very concept of seeing. It's surprising that so modest
> a change can work such a vast transformation in thinking, but it does,
> just like the difference between having only subroutines and having
> coroutines as well.
>
--
Robert Fischer
...all of which basically means .NET tail calls are in the exact same situation as the functional
JVM languages.
Jon Harrop
> Jon Harrop wrote:
> > If you want to see how much of a benefit tail calls are in practice, look
> > at .NET (which has had them for the best part of a decade).
>
> .NET tail calls are totally inefficient.
"totally inefficient" vs broken.
Jon Harrop
> Typed nulls I'm not sure. Does anyone else know? I imagine this could be
> implemented at a Java language level as well...is VM support needed?
My implementation replaced the references handled by the GC with a struct that
includes a pointer to the run-time type and a pointer to the allocated data.
Most VMs seem to have hard coded the assumption that a reference is just a
word-sized pointer. I assume that is true of the JVM?
Jon Harrop
> Nothing is stopping you from doing tail calls in the JVM languages geared
> for them -- which is all the functional languages.
What exactly do you mean by this?
Robert Fischer
> On Friday 03 April 2009 17:03:31 Robert Fischer wrote:
>> Nothing is stopping you from doing tail calls in the JVM languages geared
>> for them -- which is all the functional languages.
>
> What exactly do you mean by this?
>
As has been stated on this very thread a number of times, at least the major functional languages
have already dealt with tail call recursion, often via trampolines. So while Java might stack
overflow on tail call recursions, Scala, Kawa, and Clojure won't.
John Cowan
<robert....@smokejumperit.com> wrote:
> As has been stated on this very thread a number of times, at least the major functional languages
> have already dealt with tail call recursion, often via trampolines. So while Java might stack
> overflow on tail call recursions, Scala, Kawa, and Clojure won't.
On the contrary. Scala will overflow, because it does not trampoline.
Clojure will overflow, because it does not trampoline; it has highly
localized tail recursion for looping. Kawa can be compiled either
way, but the default will overflow, because it does not trampoline.
Randall R Schulz
> On Fri, Apr 3, 2009 at 12:14 PM, Robert Fischer
>
> <robert....@smokejumperit.com> wrote:
> > As has been stated on this very thread a number of times, at least
> > the major functional languages have already dealt with tail call
> > recursion, often via trampolines. So while Java might stack
> > overflow on tail call recursions, Scala, Kawa, and Clojure won't.
>
> On the contrary. Scala will overflow, because it does not
> trampoline. Clojure will overflow, because it does not trampoline; it
> has highly localized tail recursion for looping. Kawa can be
> compiled either way, but the default will overflow, because it does
> not trampoline.
Clojure has trampolines that must be expressly used by the programmer,
just as its tail-call optimization construct must be used explicitly
when that's what you want. The compiler confirms that a tail-call is
really in tail position rejects the code if it is not.
Randall Schulz
Miles Sabin
> I want to make sure I've got my facts straight, both in order to make an
> informed decision myself and to inform others accurately. Specifically, I am
> considering diversifying into Scala and/or Clojure and I need to know whether
> or not the elimination of tail calls may become reliable in those languages
> in the relatively-near future. If not, that is a serious impediment for
> functional languages and will rule out all JVM-based languages for me.
While I share your enthusiasm for first-class tail-call elimination on
the JVM, I think that functional languages (and languages with a
functional flavour) on the JVM (I can only really speak for Scala, but
I'm sure the same is true for others) are viable even in its absence
...
Cheers,
Miles
--
Miles Sabin
tel: +44 (0)1273 720 779
mobile: +44 (0)7813 944 528
skype: milessabin
Rich Dougherty
wrote:
> have already dealt with tail call recursion, often via trampolines. So while Java might stack
> overflow on tail call recursions, Scala, Kawa, and Clojure won't.
tail calls in Scala. The compiler is able to optimise certain classes
of tail calls, but care must still be taken by the programmer.
http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html
Cheers
Rich
Attila Szegedi
> No one is doing hand rolled stacks.
Rhino is, in interpreted mode. In addition to having stack
continuations support thanks to this, it also gives it automatic tail
call support.
If you set interpreted mode *and* disable emitting debug info, then
all tail calls (not only those to the same function, but to any
function) will eliminate the caller stack frame before invoking the
callee. (It's safer to discard the caller frame and create a new one
for the callee than to reuse the caller frame, as the tail call can
happen as part of a catch block that's unwinding because of an
exception that left the caller frame in a corrupted state - admittedly
a low-likelihood corner case, but still it's good being defensive...).
Note that you need both a) interpreted mode and b) no debug info for
this to work. In compiled mode, Rhino compiles to Java bytecode and
uses the Java stack, so neither continuations nor tail calls stack
frame elimination work. When debug info is enabled, it's possible to
attach a debugger to the running scripts using Rhino debug API, and
TCO would confuse the API contract. Actually, that's something that I
think could be fixed...
> Clojure does explicit trampolining -
> but that is a very coarse and limited way of doing it. Scala removes
> tail calls where it can be statically transformed into iteration, but
> doesn't give any guarantees. Ruby has never had TCO's and JRuby uses
> the
> Java stack too.
>
> SISC is one of the few implementations that do full TCO. There are
> basically a few variations on how to do it. CPS is common,
> trampolining
> works too. You can also have your own bytecode engine with your own
> stack.
Yep, that's what Rhino does in interpreted mode.
> The overhead of all of these approaches are pretty severe on the JVM
That is true. I doubt anyone would use interpreted mode just for TCO.
Pretty much the only justifications for it are If you need
continuations, or you can't generate Java classes on the fly.
Attila.
> since the usage pattern is data driven and far away from how regular
> Java code looks like. But the most severe problem with it is that
> all of
> these approaches make it much hard to do calls into Java methods.
>
> Cheers
>
>>
>> On Thu, Apr 2, 2009 at 9:59 AM, kirk <kirk.pe...@gmail.com
>> <mailto:kirk.pe...@gmail.com>> wrote:
>>
>>
>> John Cowan wrote:
>>> On Thu, Apr 2, 2009 at 10:36 AM, kirk <kirk.pe...@gmail.com
>> <mailto:kirk.pe...@gmail.com>> wrote:
>>>
>>>> why do they have to be exposed? Isn't tail recursion and
>> implementation
>>>> detail? And an optimization at that?
>>>>
>>>
>>> No.
>>>
>>> Being able to rely on tail recursion is not an implementation
>> detail;
>>> Scheme programmers routinely write programs that tail-call
>> heavily and
>>> would blow up without it. A state machine implementation where
>> state
>>> transition codelets, expressed as functions, are tail-called by the
>>> dispatcher and tail-call it in turn is a classic example. "Lambda:
>>> the ultimate goto."
>>>
>> Understood, that said I think Patrick hit the nail on the head.
>>> And since Java exposes the call stack via Exception#fillInStack, the
>>> *presence* of tail recursion is unfortunately not an implementation
>>> detail either.
>>>
>> I would humbly disagree with this last statement.
>>
>> Regards,
>> Kirk
>>
>>
>>
>>
>>
>>>
>
>
> --
> Ola Bini (http://olabini.com)
> Ioke creator (http://ioke.org)
> JRuby Core Developer (http://jruby.org)
> Developer, ThoughtWorks Studios (http://studios.thoughtworks.com)
> Practical JRuby on Rails (http://apress.com/book/view/9781590598818)
>
> "Yields falsehood when quined" yields falsehood when quined.
Attila Szegedi
debating whether TCO is a JVM implementation detail or not.
My stance is that it is, in the same sense as GC is. See, memory
management is not specified *at all* in the JVM specification. A JVM
would be a valid JVM even if it didn't have any GC at all, and thus
never reclaimed heap memory, and simply stopped the programs with
OutOfMemoryError when it run out of heap. Granted, such a JVM would of
course be of limited utility and could only correctly run a subset of
programs that terminate normally before they exhaust the allocated
memory.
If you think a JVM without a GC is absurd, let me tell you that such
JVM actually existed about a decade ago - the JVM for the LEGO
microcontroller computer didn't have memory management, so you had to
take care of working with only a finite set of objects, preferrably
preallocated at program startup. It was limited, but as far as I can
remember, some schoolkids actually won a NASA competition for a
program to be run on a LEGO robot sent to ISS, and they wrote it in
Java that run on this JVM.
TCO is just the same in my eyes. I believe there should be no changes
to the class file format, and the JVM should just optimize tail calls
automatically whenever they spot a combination of an INVOKE
instruction immediately followed by a RETURN instruction, and are not
in a try block. (Mind you, due to the way it is compiled, this'll
prevent calls in a synchronized block to be optimized, as synchronized
blocks are always in a try although if the whole method has the
synchronized attribute, it should be fine).
For programs written to assume TCO, only a subset of them terminating
before they exhaust the stack will work on JVMs with no TCO. See, this
is quite analogous to saying "for programs written to assume GC, only
a subset of them terminating before they exhaust the heap will work on
JVMs with no GC".
If Sun introduced automatic TCO in the JVM that goes in the Java 7
JRE, then programs written with assumption of TCO would just have to
specify "requires Java 7" in the same way as programs written with
assumption of concurrent collection classes had to specify "requires
Java 5" back in the day when Java 1.3 was still widespread.
Throwable#fillInStackTrace is indeed a bit of a problem. It would be
possible to maintain a "logical" stack trace separate from the
"physical" one, but with a deep enough tail recursion, it'd blow
memory away. At least for simple recursive call-to-self, it'd be
possible to just add a counter of how many times that frame repeats
logically; for more complex mutually recursive calls this wouldn't
work and the idea of having a pattern-based compressor for stack
traces kind of scares me, and you could probably still come up with a
pathological example that'd defeat it... Then again, can you imagine
really wanting to print a stack trace of a TCOd call chain containing
few millions of calls? Maybe it'd be better to alter the specification
of stack frame listing instead...
Attila.
--
twitter: http://twitter.com/szegedi
On 2009.04.02., at 18:33, John Cowan wrote:
>
> On Thu, Apr 2, 2009 at 10:36 AM, kirk <kirk.pe...@gmail.com>
> wrote:
>> why do they have to be exposed? Isn't tail recursion and
>> implementation
>> detail? And an optimization at that?
>
> No.
>
> Being able to rely on tail recursion is not an implementation detail;
> Scheme programmers routinely write programs that tail-call heavily and
> would blow up without it. A state machine implementation where state
> transition codelets, expressed as functions, are tail-called by the
> dispatcher and tail-call it in turn is a classic example. "Lambda:
> the ultimate goto."
>
> And since Java exposes the call stack via Exception#fillInStack, the
> *presence* of tail recursion is unfortunately not an implementation
> detail either.
>
John Cowan
> I'm replying more-or-less randomly to this message among all messages
> debating whether TCO is a JVM implementation detail or not.
Well, thanks for the implicit compliment.
> My stance is that it is, in the same sense as GC is.
I grant the force of your analogy between GC, which provides the
illusion of an infinite heap in certain circumstances, and TCO, which
provides the illusion of an infinite stack in certain circumstances.
However, proper tail calling (PTC) is not the same concept as TCO.
In a PTC language like Scheme, Haskell, or XSLT, tail calls serve the
same function as iteration in a non-PTC language. In Scheme, for
instance, the core language contains only constants, lexical
variables, conditional evaluation, assignment, function calls, and
lambda. A classical Scheme compiler reduces the full language
(including two standard iteration constructs and any number of
user-defined ones) to these few primitives, and then works hard to
implement each of them with maximal efficiency.
For a Scheme implementation not to be PTC is not like a JVM without
GC, it's like a JVM that gratuitously pushes a new stack frame for
every iteration of a while- or for-loop, and then carefully unwinds
them (without using an exception) when the loop exits. That's not a
trade-off, it's a pessimization.
> (Mind you, due to the way it is compiled, this'll
> prevent calls in a synchronized block to be optimized, as synchronized
> blocks are always in a try although if the whole method has the
> synchronized attribute, it should be fine).
I don't see how. A synchronized method, like a synchronized block,
has to exit the monitor, and the essence of a tail call is that there
is nothing to do (as opposed to nothing visible to do) in the calling
function after the called function returns.
> Then again, can you imagine
> really wanting to print a stack trace of a TCOd call chain containing
> few millions of calls?
Probably not. But there is also the stack-inspection-based security system.
Jon Harrop
> My stance is that it is, in the same sense as GC is. See, memory
> management is not specified *at all* in the JVM specification.
While that analogy has a sound theoretical foundation it completely ignores
practicality. Imagine how successful the JVM would be if *all* of the
available implementations died if there were 10,000 reachable objects.
kirk
> On Friday 10 April 2009 10:41:57 Attila Szegedi wrote:
>
>> My stance is that it is, in the same sense as GC is. See, memory
>> management is not specified *at all* in the JVM specification.
>>
>
> While that analogy has a sound theoretical foundation it completely ignores
> practicality. Imagine how successful the JVM would be if *all* of the
> available implementations died if there were 10,000 reachable objects.
>
>
Regards,
Kirk
Johannes Rudolph
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
Jon Harrop
> For comparison here's Guido's take on the subject wrt Python:
>
> http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
Not worth reading. Guido has absolutely no idea what he is talking about and
is probably the last person on Earth you should listen to in this context.
John Cowan
> > http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
> Not worth reading. Guido has absolutely no idea what he is talking about and
> is probably the last person on Earth you should listen to in this context.
I profoundly disagree.
His points labeled "First" and "Second" are true: TCO does destroy
stack trace information, and people would (and should) come to depend
on TCO if it was available.
His point labeled "Third" is a matter of opinion.
His point labeled "Last" (which is not the last) is solely about tail
*recursion*, rather than about tail calls in general, and correctly
makes the point that in Python you cannot tell when you are dealing
with the former rather than the latter, because the meaning of a name
(including the name of the currently executing function) can change
dynamically.
His points labeled "Still" discusses possible approaches for detecting
increasingly more "advanced" versions of tail calls, quite soundly.
His final point (unnamed) correctly remarks that Python and C are
generally intertwingled, and that since C does not have TCO, even a
full Python implementation of TCO can still blow out the stack due to
Python-C-Python-C recursion. The same is true of at least some Scheme
implementations with TCO, such as Chicken and Kawa.
Jon Harrop
> On Thu, Apr 23, 2009 at 12:52 PM, Jon Harrop <j...@ffconsultancy.com> wrote:
> > > http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
> >
> > Not worth reading. Guido has absolutely no idea what he is talking about
> > and is probably the last person on Earth you should listen to in this
> > context.
>
> I profoundly disagree.
>
> His points labeled "First" and "Second" are true:
His entire post is supposed to be explaining why "Tail Recursion Elimination"
should not be implemented in Python and, in that context, his points are all
entirely invalid. Moreover, the broken terminology makes it clear that he has
no idea what he is talking about.
> TCO does destroy stack trace information,
So make it optional.
> and people would (and should) come to depend on TCO if it was available.
That is true of any useful feature.
> His point labeled "Third" is a matter of opinion.
His third point is that he believes that arrays are more "useful" than
recursion. That is irrelevant nonsense.
> His point labeled "Last" (which is not the last) is solely about tail
> *recursion*, rather than about tail calls in general,
His entire post is only about recursion. Indeed, he does not appear to even
know what a tail call is and makes no mention of anything that tail calls
facilitate.
> and correctly
> makes the point that in Python you cannot tell when you are dealing
> with the former rather than the latter, because the meaning of a name
> (including the name of the currently executing function) can change
> dynamically.
That is one of the really serious problems with Python but it is irrelevant
here.
> His points labeled "Still" discusses possible approaches for detecting
> increasingly more "advanced" versions of tail calls, quite soundly.
Utter nonsense. There is no such thing as an "advanced" tail call. This
confusion only arose because Guido has absolutely no idea what he is talking
about.
In reality, tail calls are easy to define and easy to identify. There is no
merit in pretending otherwise.
> His final point (unnamed) correctly remarks that Python and C are
> generally intertwingled, and that since C does not have TCO, even a
> full Python implementation of TCO can still blow out the stack due to
> Python-C-Python-C recursion.
The same is true of F# and C# but it has never caused me a problem. The reason
is, of course, that Guido's argument has no basis in reality whatsoever
because he has no practical experience of this at all and has absolutely no
idea what he is talking about. He is just fear mongering.
You would get an equally accurate technical discussion in an asylum. Reading
Guido's blog post was a complete waste of time.
Attila Szegedi
>
> On Thu, Apr 23, 2009 at 12:52 PM, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>
>>> http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
>> Not worth reading. Guido has absolutely no idea what he is talking
>> about and
>> is probably the last person on Earth you should listen to in this
>> context.
>
> I profoundly disagree.
>
> His points labeled "First" and "Second" are true: TCO does destroy
> stack trace information, and people would (and should) come to depend
> on TCO if it was available.
Yes, this can be a problem. I remember it was you who mentioned the
call stack based security systems, and you're right, and Java security
system is exactly of this kind...
For what's it worth (I keep referring to the example I'm familiar
with) in Rhino it is possible to assign CodeSource to .js files and
subject them to Java security policy, and in this scenario
transitioning from caller to callee with a different CodeSource
defeats TCO in interpreted mode.
Now, we couldn't even do it any differently no matter what we tried,
since to effect a different CodeSource, we must call through a
synthetic invoker thunk Java object, loaded through a synthetic
SecureClassLoader that'll effect the new CodeSource on the Java stack.
This naturally causes a JS->Java-JS transition (where "JS" means the
stackless interpreter loop with TCO capabilities) so you can't have
TCO in there.
Of course, the expectation is that most tail calls will happen between
functions with the same CodeSource (trivially true for tail recursive
functions, and also true for algorithms implemented by mutually
recursive functions defined in the same source file) so TCO is not
defeated in most cases, but still transitioning between different code
sources will defeat it.
> [...]
>
> His final point (unnamed) correctly remarks that Python and C are
> generally intertwingled, and that since C does not have TCO, even a
> full Python implementation of TCO can still blow out the stack due to
> Python-C-Python-C recursion. The same is true of at least some Scheme
> implementations with TCO, such as Chicken and Kawa.
Yes, same can happen in Rhino with JS-Java-JS-Java-... as explained
above.
Attila.
--
twitter: http://twitter.com/szegedi
weblog: http://constc.blogspot.com