I try to implement the continuation monad in Javascript to handle continuation passing style and asynchronous control flows. Here is my continuation monad for learning:
// auxiliary functions
const log = prefix => x => console.log(prefix, x);
const addk = x => y => k => setTimeout((x, y) => k(x + y), 0, x, y);
const inck = x => k => setTimeout(x => k(x + 1), 0, x);
const sqr = x => x * x;
// continuation monad
const cont = {
of: x => k => k(x),
map: ftor => f => k => ftor(x => k(f(x))),
ap: ftor => gtor => k => ftor(x => gtor(f => k(f(x)))),
chain: ftor => mf => k => ftor(x => mf(x) (k)),
callcc: f => k => f(x => () => k(x)) (k)
};
// map a normal, unary function with an asynchronous function:
cont.map(inck(9)) (sqr) (log("map"));
// chain two asynchronous CPS computations with an asynchronous binary CPS function
const comp1 = cont.map(inck(4)) (sqr);
const comp2 = cont.map(inck(9)) (sqr);
cont.chain(comp1) (x => cont.chain(comp2) (y => addk(x) (y))) (log("chain"));Apart from cont.ap, whose benefit doesn't reveal itself to me, everything works fine.
Now I'd like to mimic the throw/catch mechanism of synchronous control flows in Javascript. callcc seems to fit, because it provides an escape continuation mechanism for use with continuation monads, as stated on http://hackage.haskell.org/.
But I can't figure out how to apply callcc and I haven't found any suitable source that describes such an application.
Continuations are a powerful abstraction. Let me emphasize that. Continuations are an immensely powerful abstraction. Why are continuations so powerful? It's because a continuation is simply a function[1] and “functions have a dangerous property of being invokable.” More on that later.
Yes, a continuation is just a function. However, what makes a continuation so special is what it represents. A continuation represents the “rest of the computation” (a.k.a. the computation context). For example, consider the following Scheme expression:
(add1 (* 3 x))
; |_____|
; |
; computation
(add1 [])
; |_______|
; |
; context
Here the computation (* 3 x) has the context (add1 []) where the [] represents a hole. The hole can be plugged with the result of a computation. This is written as (add1 [result]) for some result. A continuation is just a representation of a context. For example, the function (lambda (result) (add1 result)) represents the context (add1 []).
On the other hand, the computation (* 3 x) can also be represented as a function. It's represented as the function (lambda (context) (context (* 3 x))) where context is a continuation representing the context of the computation. In should be noted that the Cont type in Haskell represents the computation itself, not its context.
As I said before, a continuation is simply a function and “functions have a dangerous property of being invokable.” In particular, a function may be invoked not only once but also arbitrarily many times or even never at all. This is what makes continuations so powerful.
For example, consider the aforementioned computation (* 3 x) represented as a function:
(lambda (context)
(context (* 3 x)))
What if we applied context more than once? We could use it to double the result as follows:
(lambda (context)
(+
(context (* 3 x))
(context (* 3 x))))
If the given context is add1 then this will produce the answer (* 2 (add1 (* 3 x))).
On the other hand, what if we never applied context? We could short-circuit the evaluation:
(lambda (context)
(* 3 x))
This is precisely what call/cc does. It short-circuits the evaluation by ignoring the context and simply returning an answer. For example, consider:
(call/cc (lambda (short-circuit)
(add1 (short-circuit (* 3 x)))))
Here, the computation (* 3 x) has the context add1. However, we short-circuited the computation by applying the context of call/cc (i.e. short-circuit) to the result of the computation. Hence, we ignored the original context (i.e. add1) and returned an answer.
call/cc implemented?Now that we understand continuations let's look at the definition of callCC in Haskell:
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
-- |___________________________|
-- |
-- f
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k
-- __|___ |______________________|
-- | | |
-- (a -> r) short-circuit
It should be noted that k is the current continuation (i.e. the continuation of the entire expression). The function f is the only input to callCC. It returns a Cont r a which represents the entire computation to be performed. We apply it to k to get the result of the computation.
However, inside the computation we can call short-circuit whenever we want to short-circuit the evaluation. This function takes a result and returns a computation that ignores its context and applies the current continuation k to the result, thereby short-circuiting the evaluation.
We understood what continuations are in Scheme. We understood how callCC works in Haskell. Let's use our newfound knowledge to implement continuations and callCC in JavaScript:
var Cont = defclass({
constructor: function (runCont) {
this.runCont = runCont;
},
map: function (f) {
return new Cont(k => this.runCont(x => k(f(x))));
},
apply: function (g) {
return new Cont(k => this.runCont(f => g.runCont(x => k(f(x)))));
},
bind: function (f) {
return new Cont(k => this.runCont(x => f(x).runCont(k)));
}
});
Cont.of = x => new Cont(k => k(x));
var callCC = f => new Cont(k => f(x => new Cont(_ => k(x))).runCont(k));
var log = prefix => x => console.log(prefix, x);
var add1 = x => Cont.of(x + 1);
callCC(short_circuit => short_circuit(15).bind(add1)).runCont(log("short"));
callCC(short_circuit => Cont.of(15).bind(add1)).runCont(log("no short"));
function defclass(prototype) {
var constructor = prototype.constructor;
constructor.prototype = prototype;
return constructor;
}callCC can be used to implement goto.The power of callCC allows you to create arbitrary control flow structures like throw, coroutines and even goto as can be seen here:
var Cont = defclass({
constructor: function (runCont) {
this.runCont = runCont;
},
map: function (f) {
return new Cont(k => this.runCont(x => k(f(x))));
},
apply: function (g) {
return new Cont(k => this.runCont(f => g.runCont(x => k(f(x)))));
},
bind: function (f) {
return new Cont(k => this.runCont(x => f(x).runCont(k)));
}
});
Cont.of = x => new Cont(k => k(x));
var callCC = f => new Cont(k => f(x => new Cont(_ => k(x))).runCont(k));
var log = (x, ms) => new Cont(k => setTimeout(_ => k(console.log(x)), ms));
var omega = x => x(x); // This is a very dangerous function. Run `omega(omega)`.
callCC(omega).bind(cc => log("loop", 1000).bind(_ => cc(cc))).runCont(x => x);
function defclass(prototype) {
var constructor = prototype.constructor;
constructor.prototype = prototype;
return constructor;
}This code is equivalent to:
forever:
delay(1000);
print("loop");
goto forever;
Hence, you should be careful when working with continuations.
[1] Continuations are usually implemented using first-class functions. However, in languages with first-class continuations like Scheme there's a distinction between continuations and functions. Nevertheless, even if a continuation is not a function it's still like a function in that it's invokable.