Why Tailcalls
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.)
Contents
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
