For an example, let's look at the oneOf function from the Maybe module:
oneOf : List (Maybe a) -> Maybe a
oneOf maybes =
case maybes of
[] ->
Nothing
maybe :: rest ->
case maybe of
Nothing -> oneOf rest
Just _ -> maybeWe are able to easily optimize this because it is self-tail-recursive: one of the branches of the case expression returns the value from foldl with different arguments.
It's also the perfect candidate for tail-recursion: if we implemented it as a fold, it would unnecessarily iterate over the entire list.
The basic idea of the transformation is to look at a function containing tail calls, wrap it in a loop, and replace self-tail-calls with parameter assignments, followed by a jump to the loop beginning.
var oneOf = function (maybes) {
oneOf: while (true) {
{
switch (maybes.ctor)
{case "::": {
switch (maybes._0.ctor)
{case "Just": return maybes._0;
case "Nothing":
var _Temp0 = maybes._1;
maybes = _Temp0;
continue oneOf;}
_U.badCase($moduleName,
"between lines 64 and 66");
}
case "[]": return Nothing;}
_U.badCase($moduleName,
"between lines 59 and 66");
}
}
};The idea is simple: we wrap the body of the function with a while-loop, labelled with the function's name. The base case is unchanged, still returning from the function. For the recursive case, we just re-assign the parameter values, and jump to the loop beginning using a continue statement.
This is the same approach used by the common JavaScript TCO implementation.
var oneOf = function (maybes) {
while (true) {
oneOf: {
switch (maybes.ctor)
{case "::": {
switch (maybes._0.ctor)
{case "Just": return maybes._0;
case "Nothing":
var _Temp0 = maybes._1;
maybes = _Temp0;
continue oneOf;}
_U.badCase($moduleName,
"between lines 64 and 66");
}
case "[]": return Nothing;}
_U.badCase($moduleName,
"between lines 59 and 66");
}
}
};This is basically equivalent to the Continue version, but it breaks inside the loop, and uses the loop's structure to jump to the beginning. Benchmarking has shown that on Chrome, this is basically identical for performance to the continue version. It's slightly slower on FF, and slightly faster on IE. I'm hesitant to trust these benchmarks, though, given the recent problems jsperf.com has been having. (It was running briefly, and is again offline now).
var oneOf = function (maybes) {
while (true) {
switch (maybes.ctor)
{case "::": {
switch (maybes._0.ctor)
{case "Just": return maybes._0;
case "Nothing":
var _Temp0 = maybes._1;
maybes = _Temp0;
break;
default: _U.badCase($moduleName,
"between lines 64 and 66");
}
}; break;
case "[]": return Nothing;
default : _U.badCase($moduleName,
"between lines 59 and 66");}
}
};This option would require significant re-factoring of Generate.JavaScript, since right now
the error-throwing expressions for unmatched patterns are placed after a switch-statement,
instead of in a default case.
Because tail call optimization alters the control-flow of a program, If-expressions in Elm containing tail-calls must be converted into if-statements in JavaScript.
Consider the following Elm code:
factorial x =
let
helper x accum =
if (x < 1)
then accum
else helper (x - 1) (x * accum)
in helper x 1
Without TCO, this is compiled into the following code:
var factorial = function (x) {
return function () {
var helper = F2(function (x,
accum) {
return _U.cmp(x,
1) < 0 ? accum : A2(helper,
x - 1,
x * accum);
});
return A2(helper,x,1);
}();
};However, in the TCO version, we replace the tail-call case with a parameter assignments and a break statement. Without switching to if-statements, we would get something like this:
var factorial = function (x) {
{
var helper = F2(function (x,
accum) {
helper: while (true) {
{
return (_U.cmp(x,1) < 0) ?
accum
: (
var _Temp0 = x - 1;
var _Temp1 = x * accum;
x = _Temp0;
accum = _Temp1;
continue helper;
)
}
}
});
return A2(helper,x,1);
}
};Clearly, this isn't syntactically valid JavaScript: the ? operator expects expressions, not statements. So, we compile into an if-statement.
var factorial = function (x) {
{
var helper = F2(function (x,
accum) {
helper: while (true) {
{
if (_U.cmp(x,1) < 0) {
return accum;
} else {
var _Temp0 = x - 1;
var _Temp1 = x * accum;
x = _Temp0;
accum = _Temp1;
continue helper;
}
}
}
});
return A2(helper,x,1);
}
};Previous versions of the Elm compiler often would wrap statements in an empty closure, effectively
converting a statement into an expression. For example, Maybe.oneOf without TCO looks like this:
var oneOf = function (maybes) {
return function () {
switch (maybes.ctor)
{case "::": return function () {
switch (maybes._0.ctor)
{case "Just": return maybes._0;
case "Nothing":
return oneOf(maybes._1);}
_U.badCase($moduleName,
"between lines 64 and 66");
}();
case "[]": return Nothing;}
_U.badCase($moduleName,
"between lines 59 and 66");
}();
};Notice the parameter-less functions. This is necessary on the right-hand-side of a Let declaration, to properly deal with JavaScript's broken scoping. But no other place creates a deep level of scope, then returns to the higher level of scope.
This is not compatible with TCO, since the continue statements would be nested inside a closure, putting them in a different scope from the label they're trying to jump to. The closure representation is still used internally (to please the Haskell typechecker), but the closures are unwrapped whenever an expression is returned or converted into a statement.
Benchmarking shows that on Chrome, removing these unnecessary closures without TCO provides as much speed improvement as tail-call elimination (with removed closures). However, on firefox, TCO is still faster, leading me to believe that Chrome is already doing something clever with tail calls in some cases.
TCO is still incredibly valuable, because both Chrome and Firefox had stack-overflow errors without tail-call optimization for dictionaries of 10000 elements. then
For the oneOf example, if writing the code by hand in JS, I think many programmers would come up with something like this:
var oneOf = function (maybes) {
for (var current = maybes; current.ctor != "[]"; current ) {
switch (current._0.ctor){
case "Just":
return current._0;
case "Nothing":
current = current._1;
break;
}
}
return {ctor : "Nothing" };
};I think this version is the clearest in terms of readability for simple examples. However, I can imagine the code getting quite unruly for more complex cases, particularly where there is more than one base case (we would need another switch-statement after the for-loop), where there is more than one parameter (we might need temporary variables), or whether there is more than one possible constructor for the arguments (we would need a switch statement in the loop body, in addition to the loop condition check).
I haven't benchmarked this case yet, but my instinct is to avoid it unless it provides speed benefits.
If there is only one parameter being assigned, or there is not a dependency cycle between the new values given to the parameters, there is an ordering we can assign them their new values without using temporary variables.
For example, the factorial code from above could be more efficiently expressed as this:
var factorial = function (x) {
{
var helper = F2(function (x,
accum) {
helper: while (true) {
{
if (_U.cmp(x,1) < 0) {
return accum;
} else {
accum = x * accum;
x = x - 1;
continue helper;
}
}
}
});
return A2(helper,x,1);
}
};However, this would not work if, for some reason, the new value for x also referred to accum.
This problem makes sense to tackle during Dead-Code eliminiation, since constructing the variable dependency graph is part of the DCE analysis.
While-loop with break uses
continueand looks to be exactly the same as thecontinueversion above.