Skip to content

Instantly share code, notes, and snippets.

@hurryabit

hurryabit/stack_safe.js

Last active June 14, 2022 09:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save hurryabit/76a59348e9f4445f82d93fa75cba2582 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save hurryabit/76a59348e9f4445f82d93fa75cba2582 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. hurryabit revised this gist Nov 19, 2021. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions stack_safe.js
    View file
    Original file line number Diff line number Diff line change
    @@ -8,7 +8,7 @@ function triangular(n) {
    }
    }

    function recurse(f) {
    function trampoline(f) {
    function mu_f(arg) {
    const stack = [];
    let current = f(arg);
    @@ -34,7 +34,7 @@ function recurse(f) {
    return mu_f;
    }

    const triangular_safe = recurse(function* (n) {
    const triangular_safe = trampoline(function* (n) {
    if (n == 0) {
    return 0;
    } else {
  2. hurryabit created this gist Nov 17, 2021.
    63 changes: 63 additions & 0 deletions stack_safe.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    // 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 recurse(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 = recurse(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;
    }
    }