Skip to content

Instantly share code, notes, and snippets.

@datchley
Created November 24, 2015 21:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save datchley/ec4fdae7db047750ad8e to your computer and use it in GitHub Desktop.
Save datchley/ec4fdae7db047750ad8e to your computer and use it in GitHub Desktop.
Tail Call Optimization on the fly for tail recursive functions in Javascript (naive implementation)
function range(s, e, res) {
if (!res) { res = []; }
res.push(s);
if (s == e ) {
return res;
}
else {
if (s<e) { s++; }
else { s--; }
return range(s, e, res);
}
}
function tco(f) {
var fs = f.toString(),
fsmatch = fs.match(/function\s*([^()]*)\(([^)]*)\)/),
fn = {},
recurRx, modfn, modargs, _f, _fbody;
// function 'f' must have a name to be recursive
if (fsmatch.length >= 3) {
// gather function information
fn.name = fsmatch[1];
fn.args = fsmatch[2].split(/\s*,\s*/);
fn.arity = fn.args.length;
fn.body = fs.substring(fs.indexOf('{') + 1, fs.lastIndexOf('}'));
// find occurences of self calls, replace with loop continuation
recurRx = new RegExp('((^\\s*)return\\s*'+fn.name.trim()+'\\s*\\([^)]*\\);?)', 'mg');
modfn = fn.body.replace(recurRx, '$2_cont = true;\n$2continue _recur;');
// Build the new, optimized function
_fbody = [
'var _cont = true;',
'_recur: while (_cont) {',
' _cont = false;',
modfn,
'}'].join('\n');
fn.args.unshift(null);
_f = (new (Function.prototype.bind.apply(Function, fn.args.concat(_fbody))));
return _f;
}
else {
throw new Error("Unable to transpile function: ", f.toString());
}
}
var _tco = tco(range);
console.log(_tco.toString());
_tco(1,32768);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment