Last active
November 28, 2021 15:39
-
-
Save XoseLluis/4dddff58f049321efbb8381839465b0f to your computer and use it in GitHub Desktop.
Yield based trampoline in JavaScript. https://deploytonenyures.blogspot.com/2021/11/yield-based-trampolines.html
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 recursiveFactorial(n, accumulator) { | |
if (n <= 0) return accumulator; | |
return recursiveFactorial(n-1, n*accumulator); | |
} | |
console.log("recursiveFactorial: " + recursiveFactorial(50,1)); | |
console.log("--------------------------"); | |
//rewrite the above to be used with a "classic" trampoline | |
function trampolineReadyFactorial(n, accumulator){ | |
if (n <= 0) return accumulator; | |
return () => recursiveFactorial(n-1, n*accumulator); | |
} | |
function createTrampoline(fn){ | |
return (...args) => { | |
let result = fn(...args); | |
while (typeof result === "function") | |
result = result(); | |
return result; | |
}; | |
} | |
let factorialTrampoline = createTrampoline(trampolineReadyFactorial); | |
console.log("factorialTrampoline: " + factorialTrampoline(50, 1)); | |
console.log("--------------------------"); | |
//creating a trampoline enabled "recursive" function helped by "yield" | |
//there's no recursion cause invoking the generator function returns a generator object, and the code | |
//inside the generator function is not executed until we call next() on the returned generator object (iterable/iterator) | |
function* yieldBasedFactorial(n, accumulator){ | |
if (n <= 0) | |
yield accumulator; | |
else | |
yield yieldBasedFactorial(n-1, n*accumulator); | |
} | |
//remember that a generator Object is both iterable and iterator | |
function createTrampolineFromYieldBasedFn(yieldBasedFn){ | |
return (...args) => { | |
let genObj = yieldBasedFn(...args); | |
let item = genObj.next(); | |
//either we have returned a generator Object to continue with the "recursion", or the final result | |
while (item.value.next !== undefined ) | |
item = item.value.next(); | |
return item.value; | |
} | |
} | |
let yieldBasedFactorialTrampoline = createTrampolineFromYieldBasedFn(yieldBasedFactorial); | |
let result = yieldBasedFactorialTrampoline(50, 1); | |
console.log("yield based Trampoline 2: " + result); | |
console.log("--------------------------"); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment