Instantly share code, notes, and snippets.

# Gozala/example.js

Created January 29, 2012 03:46
Star You must be signed in to star a gist
Workaround for lack of "tail call optimization" in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // Lack of tail call optimization in JS var sum = function(x, y) { return y > 0 ? sum(x + 1, y - 1) : y < 0 ? sum(x - 1, y + 1) : x } sum(20, 100000) // => RangeError: Maximum call stack size exceeded // Using workaround var sum = tco(function(x, y) { return y > 0 ? sum(x + 1, y - 1) : y < 0 ? sum(x - 1, y + 1) : x }) sum(20, 100000) // => 100020
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 function tco(f) { /** Takes `f` function and returns wrapper in return, that may be used for tail recursive algorithms. Note that returned funciton is not side effect free and should not be called from anywhere else during tail recursion. In other words if `var f = tco(function foo() { ... bar() ... })`, then `bar` should never call `f`. It is ok though for `bar` to call `tco(foo)` instead. ## Examples var sum = tco(function(x, y) { return y > 0 ? sum(x + 1, y - 1) : y < 0 ? sum(x - 1, y + 1) : x }) sum(20, 100000) // => 100020 **/ var value, active = false, accumulated = [] return function accumulator() { // Every time accumulator is called, given set of parameters // are accumulated. accumulated.push(arguments) // If accumulator is inactive (is not in the process of // tail recursion) activate and start accumulating parameters. if (!active) { active = true // If wrapped `f` performs tail call, then new set of parameters will // be accumulated causing new iteration in the loop. If `f` does not // performs tail call then accumulation is finished and `value` will // be returned. while (accumulated.length) value = f.apply(this, accumulated.shift()) active = false return value } } }

### Raynos commented Jan 29, 2012

I don't see how this would work. You have a `while (accumulated)` loop that will only run once as `accumulated` is set to `null`. Should that be an `if` instead?

### Gozala commented Jan 29, 2012

@Raynos so the way it works is following:

1. Every time `accumulator` (in our case `sum`) is called `accumulated` variable is set to passed arguments (see line #7)
2. If `accumulator` is not `active` (is in the process of tail recursion) then we enter if clause (see line #8).
3. If `accumulated` is set, reset it (by setting to `null`) and call wrapped `f` with a accumulated arguments.
3.1. `f` calls `accumulator` (in our case `sum`) if given `y` is not `0`.
3.2. This will perform 1. and will return quickly since `active` is true.
4. Return value of `f` is set to `value` variable (which will be undefined unless `y` is `0`)
5. Repeats loop 3 until `accumulator` is `null` (which will be only in case if `accumulator` is not called from itself which is when `y` is `0`).
6. Once finished looping deactivate `accumulator` and return last value returned by `f`.

So trick is that on tail recursion will cause `accumulated` to be set to a new parameters causing next iteration of the loop, this will continue until function returns with something other than tali recursion.

### Gozala commented Jan 29, 2012

Also note that this function has side effects, and will break if `foo = tco(function() { ... })` calls `bar` that calls `foo`. I don't think this is common case, but even if you have that case you can always call `tco(foo)` from `bar` instead of calling `foo`. As far as I know tail call optimizations are on the table for ES.next so this is designed as temporary workaround until then.

### jdalton commented Jan 29, 2012

@Gozala Awesome code!

You can simplify tco() to:

```function tco(fn) {
var active, nextArgs;
return function() {
var result;
nextArgs = arguments;
if (!active) {
active = true;
while (nextArgs) {
result = fn.apply(this, [nextArgs, nextArgs = null][0]);
}
active = false;
}
return result;
};
}

// OR

function tco(fn) {
var queue;
return function() {
var args, result;
if (queue) {
queue.push(arguments);
} else {
queue = [arguments];
while ((args = queue.pop())) {
result = fn.apply(this, args);
}
queue = null;
}
return result;
};
}```

### Gozala commented Jan 30, 2012

Thank for suggestion @jdalton version with array indeed reads better so I revised implementation to use that.

### BrendanEich commented Jan 30, 2012

``````    result = fn.apply(this, [nextArgs, nextArgs = null][0]);
``````

creates a gratuitous array literal. How about just putting nextArgs = null; on its own line?

/be

### Gozala commented Jan 30, 2012

@BrendanEich current version build on @jdalton array suggestion but in slightly diff way avoiding that.

### jdalton commented Jan 30, 2012

@BrendanEich

The reason that version uses an array is because `nextArgs` needs to be falsey before `fn.apply(...)` is executed and I didn't want to juggle another variable just for that purpose.
Putting `nextArgs = null;` on its own line would either kill the args passed to `fn.apply(...)` causing the loop to exit early

```while (nextArgs) {
nextArgs = null;
result = fn.apply(this, nextArgs);
}```

or null `nextArgs` too late causing the loop to exit early as well

```while (nextArgs) {
result = fn.apply(this, nextArgs);
nextArgs = null;
}```

@Gozala's original version used the variable `args` just for this juggle

```while (nextArgs) {
args = nextArgs;
nextArgs = null;
result = fn.apply(this, args);
}```

### BrendanEich commented Jan 31, 2012

@jdalton: right, I should have acknowledged that -- two extra lines. Still, seems worth avoiding an array per iteration of the while.

@Gozala: thanks!

/be

### jdalton commented Jan 31, 2012

I created a jsPerf of the variations here as well as non-recursive alternatives:
http://jsperf.com/tco#chart=bar

### Gozala commented Jan 31, 2012

I have made a module out of this as I intend to use it nodejs
https://github.com/Gozala/js-tail-call

Thanks for feedback and suggestions!

### youurayy commented Feb 5, 2012

Slightly off-topic - I knew semicolons were mostly optional in JS but I did not know the code looks so much more readable without them! Something to learn for me coming from Java/C/C++:) Great stuff.

### Gozala commented Feb 5, 2012

@ypocat Yeah I think so too. You might want to check out:
http://aresemicolonsnecessaryinjavascript.com/

### jdalton commented Feb 5, 2012

Hurray for bad coding styles :P

### youurayy commented Feb 5, 2012

@Gozala Thanks much for that link Irakli, the few gotchas are good to know.

@jdalton Well, coffee-script is the second most-depended-upon module in npm, but I will not use it because its local variable scoping is total trash (same as Ruby), the function parameter "shims" make for ambiguous APIs (same as Ruby), and besides the better code readability, it doesn't solve any real problems (e.g. async programming with proper error handling), to justify another compilation and indirection layer on top of JS. But seeing Gozala's code, I realized that the main reason why I was looking at CofeeScript was a slightly better readability, which JS without semicolons fully gives me. You could call it broken, but in my book, if there is a feature of the language which comes directly from the spec, and people don't use it despite the fact that it makes the code much more readable, I think it's actually their code that deserves the label "bad coding style", logically speaking.

### jdalton commented Feb 6, 2012

@ypocat I meant we all prefer a certain code style and others stink :)

### githubhy commented Mar 30, 2016

@Gozala. Thanks for your sharing. This is a little tricky at the first sight. I've got one question: Is this line `active = false` at the `accumulator()` really necessary?

### glathoud commented Jul 7, 2018 • edited

@Gozala Congratulation for the conciseness of the solution.

Along similar lines, but taking the path of "explicit" tail calls, similarly to Syntactic Tail Calls, there is fext.js. It deals with performance and mutual recursion.

to join this conversation on GitHub. Already have an account? Sign in to comment