Last active
August 29, 2015 14:18
-
-
Save erikbern/ba3456f836ccc9c044e8 to your computer and use it in GitHub Desktop.
simple javascript task framework to flip recursion inside out
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 serializeArgs(args) { | |
return JSON.stringify(args); | |
} | |
function unroll(f) { | |
if (f._cache == undefined) | |
f._cache = {}; | |
var f_new = function() { | |
var key = serializeArgs(arguments); | |
if (f._cache[key] != undefined) | |
return f._cache[key]; | |
else | |
throw f_new.task.apply(null, arguments); | |
} | |
f_new.task = function() { | |
var task = function() { | |
var task = arguments.callee; // same | |
return runTasks([task]); | |
} | |
var args = arguments; | |
task.run = function() { | |
var result = f.apply(null, args); | |
var key = serializeArgs(args); | |
f._cache[key] = result; | |
return result; | |
} | |
return task; | |
} | |
return f_new; | |
} | |
function runTasks(tasks) { | |
while (tasks.length > 0) { | |
var nextTask = tasks.pop(); | |
try { | |
// We're running this synchronously, but it could also be async | |
var result = nextTask.run(); | |
} catch(anotherTask) { | |
tasks.push(nextTask); | |
tasks.push(anotherTask); | |
} | |
} | |
return result; | |
} | |
var fib = unroll(function(x) { | |
return x > 1 ? fib(x-1) + fib(x-2) : x; | |
}); | |
var factorial = unroll(function(x) { | |
return x > 0 ? x * factorial(x-1) : 1; | |
}); | |
var nChooseK = unroll(function(n, k) { | |
return factorial(n) / factorial(k) / factorial(n - k); | |
}); | |
// Mutual recursion | |
var isOdd = unroll(function(n) { return n == 0 ? false : !isEven(n-1); }); | |
var isEven = unroll(function(n) { return n == 0 ? true: !isOdd(n-1); }); | |
var t1 = fib.task(43); | |
var t2 = factorial.task(10); | |
var t3 = nChooseK.task(12, 7); | |
var t4 = isEven.task(39); | |
console.log(t1()); | |
console.log(t2()); | |
console.log(t3()); | |
console.log(t4()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment