Skip to content

Instantly share code, notes, and snippets.

@hurryabit
Last active June 14, 2022 09:34
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hurryabit/76a59348e9f4445f82d93fa75cba2582 to your computer and use it in GitHub Desktop.
Save hurryabit/76a59348e9f4445f82d93fa75cba2582 to your computer and use it in GitHub Desktop.
Stack-safety for free?
// This gist contains the JavaScript version of the code from the blog post
// https://hurryabit.github.io/blog/stack-safety-for-free/
function triangular(n) {
if (n == 0) {
return 0;
} else {
return n + triangular(n - 1);
}
}
function trampoline(f) {
function mu_f(arg) {
const stack = [];
let current = f(arg);
let res = undefined;
while (true) {
const { done, value } = current.next(res);
if (!done) {
stack.push(current);
current = f(value);
res = undefined;
} else {
if (stack.length > 0) {
current = stack.pop();
res = value;
} else {
return value;
}
}
}
}
return mu_f;
}
const triangular_safe = trampoline(function* (n) {
if (n == 0) {
return 0;
} else {
return n + (yield (n - 1));
}
});
const LARGE = 100_000;
console.clear();
if (triangular_safe(LARGE) != LARGE * (LARGE + 1) / 2) {
throw Error("`triangular_safe` computed wrong value.");
}
console.log("`triangular_safe` has not overflowed its stack.");
console.log("`triangular` will overflow its stack soon...");
try {
triangular(LARGE);
throw Error("`triangular` has not overflowed its stack.");
} catch (exc) {
if (exc.message.includes("call stack")) {
console.log("`triangular` has overflowed its stack.")
} else {
throw exc;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment