Description
Performance results
Code excerpts
   Factorial
   GCD
   String Replication
   Odd/Even
   Modulo 3
   Sorted Search
Download code
 
⇒ Back to the article
⇒ Back home
⇒ email
 
Flattr this

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 codeOptimized codeCompressed code
 (Tail calls removed)(Used by this page)

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.

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).
        //
        // If `x` not found, return `null`.
        
        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)
                return null;    // Done: `x` not found.

            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)Valid HTML 4.01 Strict