Wikipedia mentions that "In any language which supports closures and proper tail calls, it is possible to write programs in continuation-passing style and manually implement call/cc."
How would one implement this function in for example in javascript? I know that javascript doesn't do tco, but assuming that stack space doesn't run out
On
synchronous call/cc
Other approaches use setTimeout or Promise and forces the caller to deal with asynchrony. Synchronous callcc can be implemented with try-catch. Let's first see the naive approach -
// naive
const callcc = f => {
try { return f(value => { throw value }) }
catch (e) { return e }
}
console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { throw Error("oh no!") }))35 ✅ 5 + 10 * 3
8 ✅ 5 + 3
15 ✅ 5 + 10
5Error: oh no! ❌ the thrown Error was treated as a return value
Wups! If we use throw for the continuation's return, how does catch know whether we called the continuation or a real error occurred? The important bit is that the continuation must "box" the return value and "unbox" it in catch to avoid swallowing real errors -
const callcc = f => {
class Box { constructor(v) { this.unbox = v } }
try { return f(value => { throw new Box(value) }) }
catch (e) { if (e instanceof Box) return e.unbox; throw e }
}
console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { exit(10); throw Error("test failed") }))
try {
console.log(5 + callcc(exit => { throw Error("test passed!") }))
}
catch (e) {
console.error(e)
}.as-console-wrapper { min-height: 100%; top: 0; }35 ✅ 5 + 10 * 3
8 ✅ 5 + 3
15 ✅ 5 + 10
15 ✅ 5 + 10
Error: test passed! ✅ Errors are not swallowed
short circuit
Given a list of numbers, let's multiply all of them. As humans we know if a single 0 is present, the product must be 0. callcc allows us to encode that same short-circuiting behavior. In the demo below mult(a,b) is used so we can see when actual work is happening. In a real program it could be replaced with a * b -
const callcc = f => {
class Box { constructor(v) { this.unbox = v } }
try { return f(value => { throw new Box(value) }) }
catch (e) { if (e instanceof Box) return e.unbox; throw e }
}
const apply = (x, f) => f(x)
const mult = (a, b) => {
console.log("multiplying", a, b)
return a * b
}
console.log("== without callcc ==")
console.log(
apply([1,2,3,0,4], function recur(a) {
if (a.length == 0) return 1
return mult(a[0], recur(a.slice(1)))
})
)
console.log("== with callcc ==")
console.log(
callcc(exit =>
apply([1,2,3,0,4], function recur(a) {
if (a.length == 0) return 1
if (a[0] == 0) exit(0) //
return mult(a[0], recur(a.slice(1)))
})
)
).as-console-wrapper { min-height: 100%; top: 0; }== without callcc ==
multiplying 4 1
multiplying 0 4 here we know the answer must be zero but recursion continues
multiplying 3 0
multiplying 2 0
multiplying 1 0
0
== with callcc ==
0 the answer is calculated without performing any unnecessary work
other implementations
Here we trade the Box class for a lightweight Symbol -
const callcc = f => {
const box = Symbol()
try { return f(unbox => { throw {box, unbox} }) }
catch (e) { if (e?.box == box) return e.unbox; throw e }
}
console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { exit(10); throw Error("test failed") }))
try {
console.log(5 + callcc(exit => { throw Error("test passed!") }))
}
catch (e) {
console.error(e)
}35 ✅ 5 + 10 * 3
8 ✅ 5 + 3
15 ✅ 5 + 10
15 ✅ 5 + 10
Error: test passed! ✅ Errors are not swallowed
caveat
In languages that support first-class continuations, you can return the continuation itself and call it at a later time. In JavaScript we cannot support this as the continuation is no longer run in the try-catch context. If you want to prevent the caller from misusing the continuation in this way, we can throw a specific error -
const callcc = f => {
const box = Symbol()
const exit = unbox => { throw {box, unbox} }
try {
const result = f(exit)
if (result === exit) throw Error("cannot return unbounded continuation")
return result
}
catch (e) {
if (e?.box == box) return e.unbox;
throw e
}
}
console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
try {
const cc = callcc(exit => exit) // ⚠️ returns continuation
cc("hello world") // ⚠️ calls continuation out of context
}
catch (e) {
console.error(e)
}.as-console-wrapper { min-height: 100%; top: 0; }35 ✅
8 ✅
15 ✅
Error: cannot return unbounded continuation! ✅
remarks
Transplanting features from one language to another is not strictly forbidden but I don't recommend this as a common practice. callcc is a utility that exists in other languages that are written to support goals a feature set that differs from JavaScript. JavaScript supports a wide variety of tools and patterns that are best for supporting JavaScript programs. Whatever you are trying to do with callcc probably has an appropriate JavaScript idiom you should be using instead.
On
Yes it is possible. See this question. This is how you would implement it:
Function.prototype.async = async;
function async() {
setTimeout.bind(null, this, 0).apply(null, arguments);
}
function callcc(f, cc) {
f.async(cc);
}
Then you may use it as follows:
pythagoras.async(3, 4, alert);
function pythagoras(x, y, cont) {
callcc.async(square.bind(null, x), function cc(x_squared) {
callcc.async(square.bind(null, y), function cc(y_squared) {
add.async(x_squared, y_squared, cont);
});
});
}
function square(x, cont) {
multiply.async(x, x, cont);
}
function multiply(x, y, cont) {
cont.async(x * y);
}
function add(x, y, cont) {
cont.async(x + y);
}
You may fiddle with the demo here: http://jsfiddle.net/brZrd/
On
it is possible
https://github.com/zaoqi/callcc.js/blob/master/callcc.js
async function callcc(f){
return await new Promise((resolve,reject)=>{
const resolve_packed=(v)=>{
resolve(v)
return new Promise((resolve,reject)=>{})
}
f(resolve_packed).then(resolve).catch(reject)
})
}
use it:
test('test1',()=>{
expect.assertions(1)
expect((()=>{
async function q(k,v){
console.log('testing1')
await k(v)
}
return callcc(async function(k){
console.log('testing0')
await q(k,133)
console.error('test error')
})
})()).resolves.toBe(133)
})
It is not possible to write a call/cc implementation in JavaScript:
JavaScript does not meet the requirement of "proper tail calls" (no additional stack creation). However, I believe that a form of continuations, such as that found in Jetty, using exceptions is possible. "CPS" is as easy as passing a function-object, although ultimately it runs into stack issues as well unless backed out occasionally.
Happy coding.