delimited continuations using javascript generators

delimited-continuations.js

// We model the call stack using a linked list of Generators
// Each Generator has a _return field pointing back to its parent

function stepGen(gen, arg) {
    const {done, value} = gen.next(arg)
    if(done) {        
        if(gen._return) {
            stepGen(gen._return, value)
        }
    } else if(typeof value === 'function') {
        // example:  
        //     yield gen => setTimeout(() => stepGen(gen, null), 1000)
        value(gen)
    } else if(typeof value.next === 'function') {
        // or yield a child Generator        
        value._return = gen
        value._reset = gen._reset
        stepGen(value, null)
    }
}

// reset is used to delimit the continuation
// eventually captured by shift
function reset(f) {
    return gen => {
        const genReset = f()
        genReset._return = gen
        genReset._reset = genReset  
        stepGen(genReset, null)
    }
}


// shift captures the current continuation up
// to the innermost enclosing reset
function shift(f) {
    return gen => {
        const genReset = gen._reset
        const genShift = f(v => genK => {
            genReset._return = genK
            stepGen(gen, v)
        })
        genShift._return = genReset._return
        stepGen(genShift, null)
    }
}


function* test1() {
    const x = yield reset(function*() {
        // no shift; reset returns as a normal function
        return 2
    })
    console.log('test1: ', x)
}

stepGen(test1())
// => test1: 2

function* test2() {
    const x = yield reset(function*() {
        const a = 2
        const b = yield shift(function*(k) {
            // shift doesnt invoke the continuation k
            // this will be the result of the whole reset block
            return 3
        })
        return a + b  
    })
    console.log('test2: ', x)
}

stepGen(test2())
// => test2: 3

function* test3() {
    const x = yield reset(function*() {
        const a = 10
        const b = yield shift(function*(k) {
            // shifts invokes the continuation k
            // here k is equivalent to a function 
            //        v => a * v
            // so the argument 2 is returned to b and the execution
            // of k will resume from the line following the shift up to 
            // the innermost enclosing reset, the result returned by this
            // continuation (return a * b ie 10 * 2) is bound to c
            // and shift continue the execution as normal
            // finally the return value of shift block is also the return
            // value of the whole reset block (c + 3 = 20 + 3)
            // it's as if shift swallow the entire surrounding up to reset
            // becoming the main expression of the reset block
            const c = yield k(2)
            return c + 3
        })
        return a * b  
    })
    console.log('test3: ', x)
}

stepGen(test3())
// => test3: 23

// Our implementation doesnt allow mulitple invocations of the
// captured continuation inside a shift
// But we can have multiple shifts inside the same reset
function* test4() {
    const x = yield reset(function*() {        
        yield  shift(function*(k) {
            return [1, ...yield k()]
        })
        yield  shift(function*(k) {
            return [2, ...yield k()]
        })
        return []
    })
    console.log('test4', x)
}

stepGen(test4())
// => test4: [1,2]