Why Tailcalls

From JVMLangSummit
Jump to navigationJump to search

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