tp.js

tp is a lightweight, experimental, library which optimize your tail-recursive functions so they won’t blow up the stack.

Install

With Node

Install it with npm:

[sudo] npm install [-g] tp

Then use:

var tp = require('tp');

In the browser

Include tp.min.js in your page, before using it. The file is 0.4kb, and only 0.2kb gzip'd. You can download it from GitHub.

Usage

Here is a tail-recursive sum function, which sums all positive numbers below its first argument:

function sum( e, acc ) {
    if (acc == undefined) {
        acc = 0;
    }
    return e <= 0 ? acc : sum( e-1, e+acc );
}

sum(2); // 3
sum(200); // 20100
sum(20000); // RangeError: Maximum call stack size exceeded

Here is the same function defined using tp:

var sum = tp(function(recur) {
    return function sum( e, acc ) {
        if (acc == undefined) {
            acc = 0;
        }
        return e <= 0 ? acc : recur( e-1, e+acc );
    }
});

sum(2); // 3
sum(200); // 20100
sum(20000); // 200010000
sum(2000000); // 2000001000000

The function is the same, but we define it in an anonymous function which takes a mysterious recur as an argument, and use it for recursive calls instead of the original name of the function.

Limits

Because this library is experimental, it only works in a few cases. The function must be tail-recursive and must use recursion to return something. Below are some examples of functions that won’t work:

• function fibo(x) { return x < 2 ? 1 : (fibo(x-1) + fibo(x-2)); }: not tail-recursive
• function lX(s, n) { if (n == 0) { return; } console.log(s); lX(s, n-1); }: the recursive call is not used to return something
• function a() { return function() {}; }: tp doesn’t support functions that return functions (see below for more explanations).

Please not that tp doesn’t speed up your function, it only prevents it to blow up the stack. It means you can make an infinite recursive function, it’ll work.

How it works

From Wikipedia:

a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail-recursive function calls in stack-oriented programming languages.

tp uses a little bit of magic to bind recur in your function to pre-binded version of itself. Your function now returns either a final result, either itself binded to some arguments. Then, tp repeatedly calls your function until it returns something that’s not a function. So it won’t work if your function returns a function, because tp doesn’t know if it has to call this function or return it. tp then works as a proxy to your original function, handing the annoying stuff.

Licence

MIT

Changelog

v0.1.0

• first version