Skip to content

Instantly share code, notes, and snippets.

@yelouafi
Last active June 4, 2024 04:56
Show Gist options
  • Save yelouafi/44f5ed9bcdd1100b1902bcdb80aa32da to your computer and use it in GitHub Desktop.
Save yelouafi/44f5ed9bcdd1100b1902bcdb80aa32da to your computer and use it in GitHub Desktop.
delimited continuations using javascript generators
// 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment