Difference between revisions of "Why Tailcalls"

From JVMLangSummit
Jump to navigationJump to search
(New page: Are tailcalls fated to come in second place on every feature priority list? Let's gather the use cases and consider the implementation. (Note: This page is about "hard tail calls" as def...)
 
 
(9 intermediate revisions by 4 users not shown)
Line 4: Line 4:
  
 
(Note: This page is about "hard tail calls" as defined in the [http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm Rose blog].  Soft TCO is already in many compilers, but does not have a strong effect on software architecture.)
 
(Note: This page is about "hard tail calls" as defined in the [http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm Rose blog].  Soft TCO is already in many compilers, but does not have a strong effect on software architecture.)
 +
 +
;[[Why_Tailcalls_%28GLS%29|Note from Guy Steele]]
  
 
== use cases ==
 
== use cases ==
Line 10: Line 12:
  
 
=== languages with guaranteed TCO ===
 
=== languages with guaranteed TCO ===
These are languages with functional patterns, including Scheme, Scala, F#.
+
These are languages with functional patterns, including Scheme, Scala, F#. Seph also aims to give this guarantee.
 +
 
 +
=== robust support for design patterns ===
 +
Comment from Matthias Felleisen:
 +
<blockquote>
 +
One common misunderstanding about TCO is due to the word 'optimization'. It is indeed a space optimization (don't use more space than goto, as Guy said in the 1970s) but a language should implement TCO in support of PROPER DESIGN. To wit, go through the OO design pattern books and inspect all the little patterns. Pick some -- say interpreter or composite -- and design your Java program accordingly. Then run a stress test and weep. Java blows up even if all the method calls are tail-recursive because it doesn't support TCO. Now do the same in PLT Scheme's class system and smile. It works -- for all inputs.
 +
 
 +
See my [http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf ECOOP keynote (2004)] for some more details.
 +
</blockquote>
 +
 
 +
Pages 51-59 in the keynote are especially relevant.
 +
 
 +
See also [http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion this discussion] in the Fortress Community website:
 +
 
 +
 
 +
=== guaranteed disposal of stack-frame ===
 +
Clojure needs workarounds to avoid floating garbage
 +
  public static int count(Object o) {
 +
    if (o instanceof Counted)
 +
      return ((Counted) o).count();
 +
    return countFrom(Util.ret1(o, o = null));
 +
  }
 +
  static public Object ret1(Object ret, Object nil) { return ret; }
 +
 
 +
=== Reduce call stack size ! ===
 +
(Rémi) Avoid to show language implementation internals by collapsing runtime stack frame.
  
 
== external links ==
 
== external links ==
Line 17: Line 44:
 
;mlvm Wiki: http://wikis.sun.com/display/mlvm/TailCalls
 
;mlvm Wiki: http://wikis.sun.com/display/mlvm/TailCalls
 
;mlvm Code: http://hg.openjdk.java.net/mlvm/mlvm/hotspot/file/tip/tailc.patch
 
;mlvm Code: http://hg.openjdk.java.net/mlvm/mlvm/hotspot/file/tip/tailc.patch
 +
;Fortress discussion: http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion

Latest revision as of 14:05, 20 July 2011

Are tailcalls fated to come in second place on every feature priority list?

Let's gather the use cases and consider the implementation.

(Note: This page is about "hard tail calls" as defined in the Rose blog. Soft TCO is already in many compilers, but does not have a strong effect on software architecture.)

Note from Guy Steele

use cases

multi-core task distribution

(Doug Lea) chaining task execution; without tail calls you blow the stack needlessly

languages with guaranteed TCO

These are languages with functional patterns, including Scheme, Scala, F#. Seph also aims to give this guarantee.

robust support for design patterns

Comment from Matthias Felleisen:

One common misunderstanding about TCO is due to the word 'optimization'. It is indeed a space optimization (don't use more space than goto, as Guy said in the 1970s) but a language should implement TCO in support of PROPER DESIGN. To wit, go through the OO design pattern books and inspect all the little patterns. Pick some -- say interpreter or composite -- and design your Java program accordingly. Then run a stress test and weep. Java blows up even if all the method calls are tail-recursive because it doesn't support TCO. Now do the same in PLT Scheme's class system and smile. It works -- for all inputs.

See my ECOOP keynote (2004) for some more details.

Pages 51-59 in the keynote are especially relevant.

See also this discussion in the Fortress Community website:


guaranteed disposal of stack-frame

Clojure needs workarounds to avoid floating garbage

 public static int count(Object o) {
   if (o instanceof Counted)
     return ((Counted) o).count();
   return countFrom(Util.ret1(o, o = null));
 }
 static public Object ret1(Object ret, Object nil) { return ret; }

Reduce call stack size !

(Rémi) Avoid to show language implementation internals by collapsing runtime stack frame.

external links

Proposal
http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm
Thesis
http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/
mlvm Wiki
http://wikis.sun.com/display/mlvm/TailCalls
mlvm Code
http://hg.openjdk.java.net/mlvm/mlvm/hotspot/file/tip/tailc.patch
Fortress discussion
http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion