Update 2013-03-19: Much lighter implementation: js.metaret

## JS mutual tail recursion optimization: Production examples

#### by Guillaume Lathoud

This page is an example of Javascript mutual tail recursion elimination, run once on the server side:

 (1) (2) Source code ⇒ Optimized code ⇒ Compressed code (Tail calls removed) (Used by this page)
• (1) The proposed optimization works e.g. under Google's V8 engine (see ./prep_tailopt.js).
• (2) Any code compression will do.
• You can run the compressed code.

Example of source code:

```// `tailopt()` is the identity function, used as a marker.
function tailopt (x) { return x; };

// ...

function fact_tailrec (n)    // Not marked for optimization
{
return loop( n, 1 );
function loop( k, acc ) { return k < 2 ? acc : loop( k-1, k*acc ); }
}

var fact_tailopt = tailopt(    // Marked for optimization
function (n)
{
return loop( n, 1 );
function loop( k, acc ) { return k < 2 ? acc : loop( k-1, k*acc ); }
}
);```

Example of optimized code:

```function fact_tailrec (n)  // Not marked in the source code -> not optimized
{
return loop( n, 1 );
function loop( k, acc ) { return k < 2 ? acc : loop( k-1, k*acc ); }
}

var fact_tailopt = function (n) {  // Marker removed, body optimized
var undef, n, loop, k, acc, k_new, acc_new;
k = n;
acc = 1;
_L_loop_: while (true) {
if (k < 2) {
return acc;
} else {
k_new = k - 1;
acc_new = k * acc;
k = k_new;
acc = acc_new;
continue _L_loop_;
}
return;
}
};```

### Performance results

Speed is expressed in number of iterations per second (the higher, the better). You can all performance tests right here on your computer (results marked with «??»). Mobile users are encouraged to send me their results.

• an: Android 2.3.1 on the android-sdk-linux_x86 (virtual device).
• ch: Google Chrome 7.0.517.41 beta on a laptop with linux Ubuntu.
• ff: Firefox 3.6.13 (Firebug off) on a laptop with linux Ubuntu.
• ie: Internet Explorer 8 on Windows 7.
• sa: Safari 5.0.3 (7533.19.4) on Windows 7.
ExampleMutual recursionTail-recursiveTail-optimized
Speed
ratio
(iter/sec)(iter/sec)(unitless)
source codeNo
source codeNo
source codeNo
source code
Yes
(2 functions)
source code
Yes
(3 functions)
source code
Yes
(2 functions)

### Code excerpts

These are excerpts of the source code.

#### Factorial

``````// `tailopt()` is the identity function, used as a marker.
function tailopt (x) { return x; };

function fact_tailrec (n)    // Not marked for optimization
{
return loop( n, 1 );
function loop( k, acc ) { return k < 2 ? acc : loop( k-1, k*acc ); }
}

var fact_tailopt = tailopt(     // Marked for optimization
function (n)
{
return loop( n, 1 );
function loop( k, acc ) { return k < 2 ? acc : loop( k-1, k*acc ); }
}
);``````

#### Greatest Common Divisor (GCD)

``````// `tailopt()` is the identity function, used as a marker.
function tailopt (x) { return x; };

function gcd_tailrec (a,b)     // Not marked for optimization
{
if (a > b) return gcd_tailrec( a-b, b);
if (a < b) return gcd_tailrec(b - a, a);
return a;
}

var gcd_tailopt = tailopt(     // Marked for optimization
function (a,b)
{
if (a > b) return gcd_tailopt( a-b, b);
if (a < b) return gcd_tailopt(b - a, a);
return a;
}
);``````

...etc. From now one I'll only give the `tailopt()` version:

#### String replication

``````var stringrepli_tailopt = tailopt(
function(s0, n0)
{
if (!((n0 > 0) && s0)) { return ''; }
return loop(s0, n0, []);
function loop(s, n, tmp){
if (n & 1) { tmp.push(s); }
return n ? loop(s + s, n >> 1, tmp) : tmp.join('');
}
}
);``````

#### Odd/Even

``````var isEven_tailopt = (function ()
{
// Proof of concept: test the mutual tail-recursion of 2 functions.

var isEven = tailopt( function (n)
{
if (n > 0) return isOdd(n-1);
if (n < 0) return isEven(-n);
return true;
});

var isOdd = tailopt( function (n)
{
if (n > 0) return isEven(n-1);
if (n < 0) return isOdd(-n);
return false;
});

return isEven;
})();``````

#### Modulo 3

``````var is_0_mod_3_tailopt = (function ()
{
// Proof of concept: test the mutual tail-recursion of 3 functions.

var is_0_mod_3 = tailopt(
function (n) { if (n > 0) return is_2_mod_3( n - 1 );
if (n < 0) return is_1_mod_3( n + 1 );
return true; }
);

var is_1_mod_3 = tailopt(
function (n) { if (n > 0) return is_0_mod_3( n - 1 );
if (n < 0) return is_2_mod_3( n + 1 );
return false; }
);

var is_2_mod_3 = tailopt(
function (n) { if (n > 0) return is_1_mod_3( n - 1 );
if (n < 0) return is_0_mod_3( n + 1 );
return false; }
);

return is_0_mod_3;
})();``````

#### Sorted Search

``````Array.prototype.sortedSearch_tailopt = tailopt(
function (x, less, equal)
{
// Assume `this` is a sorted array. Search for the first and
// last occurences of `x`.
//
// If `x` found, return `[ first_index, last_index ]`
// (integers).
//

less  = less || function (a,b) { return a < b; };
equal = equal || function (a,b) { return a == b; };

var sortedArray = this;

return searchFirst(0, sortedArray.length - 1, false, false);

// Implementation: joint binary search.

function searchFirst(i, j, first_found, last_found)
{
first_found = first_found || isFirstFound(i);

// Termination tests

if (i > j)

if (first_found && last_found)
return [i, j];  // Done: `x` found.

// Update

if (!first_found)
{
i++;

var ind = i + ((j - i) >> 1)
, v_ind = sortedArray[ind]
;

if (less(v_ind, x) || isFirstFound(ind))
i = ind; // Update
}

return searchLast(i, j, first_found, last_found);
}

function searchLast(i, j, first_found, last_found)
{
last_found = last_found || isLastFound(j);

// Termination tests already done in `searchFirst` -> not needed here.

// Update

if (!last_found)
{
j--;

var ind = j - ((j - i) >> 1)
, v_ind = sortedArray[ind]
;

if (less(x, v_ind) || isLastFound(ind))
j = ind; // Update
}

return searchFirst(i, j, first_found, last_found);
}

function isFirstFound(i)
{
return equal(x, sortedArray[i])  &&  (i < 1  ||  !equal(x, sortedArray[i - 1]));
}

function isLastFound(j)
{
return equal(x, sortedArray[j])  &&  (j > sortedArray.length - 2  ||
!equal(x, sortedArray[j + 1]));
}
}
);
``````

Produced on 2014-06-06 by tomrec_prod.scm - by Guillaume Lathoud (glathoud _at_ yahoo _dot_ fr)