shrink-stack.js

// This is an attempt to implement support for deep
// stacks without actually tracking the depth of the
// stack. Tracking the stack depth requires a fair
// amount of instrumentation. In contrast, this
// approach only requires inserting a single call
// to shrinkStack at the top of each function.
//
// This approach may involve more continuation
// capture than an approach that precisely tracks
// the stack depth. E.g., we would capture
// continuations in the following function, which
// is unnecessary:
//
//   function slower() {
//       function F() {
//       }
//       for (let i = 0; i < 20000; i++) {
//           F();
//       }
//   }
//
// However, we would have periodically suspend
// the function for responsiveness anyway, so we
// might as well combine the two behaviors using
// two counters:
// 1. An estimate of stack depth (which may be
//    higher than the actual depth)
// 2. The usual gas counter
//
// When the gas counter hits its limit, we can
// end the turn and reset both counters. When
// the stack depth counter hits its limit, we
// only reset the stack depth counter, and
// save+restore the continutation without
// ending the turn.

//
// Implementation
//

let depth = 0;
let maxDepth = 10000;
function shrinkStack() {
    if (depth === maxDepth) {
        depth = 0;
        return control(function(k) {
            return k(undefined);
        });
    }
    else {
        depth = depth + 1;
    }
}

//
// Demo
//

function sum(n) {
    shrinkStack();
    if (n === 0) {
        return 1;
    }
    else {
        return n + sum(n - 1);
    }
}

function odd(n) {
    shrinkStack();
    if (n === 0) {
        return false;
    }
    else {
        return even(n - 1);
    }
}

function even(n) {
    shrinkStack();
    if (n === 0) {
        return true;
    }
    else {
        return odd(n - 1);
    }
}

console.log(sum(19000));
console.log(even(19000));