This is the final part of a series about Algebraic Effects and Handlers.
- Part 1 : continuations and control transfer
- Part 2 : Capturing continuations with Generators
- Part 3 : Delimited continuations
- Part 4 : Implementing Algebraic Effects and handlers
So we've come to the core topic. The reality is that we've already covered most of it in the previous parts. Especially, in the third part, where we saw delimited continuations at work.
In this part, we'll see that the mechanism of Algebraic Effects isn't much different from that of delimited continuations. But first, let's approach the topic from a more familiar perspective. We'll exploit the similarity with JavaScript Error handling to introduce the concept.
From Exceptions to Algebraic Effects
Below a simple example of Error handling. Don't pay much attention to the program logic, all we're interested on are the mechanics of the Call Stack.
function main(n) {
return handler(n);
}
function handler(n) {
try {
unsafeOperation(n);
} catch (e) {
return 0;
}
}
function unsafeOperation(n) {
const x = oneMoreIndirection(n);
return x * 2;
}
function oneMoreIndirection(n) {
if (n < 0) {
throw "cant be under zero!";
}
return n + 1;
}
main(-1);
// => 0
Once we reach the oneMoreIndirection
, the Call Stack looks like:
main(-1) -> handler(-1) -> unsafeOperation(-1) -> oneMoreIndirection(-1)
When oneMoreIndirection
throws, the exception bubbles up to the closest try
/catch
block, which in this case is located in handler
. All stack frames below that handler (oneMoreIndirection(-1) -> unsafeOperation(-1)
) are discarded. So the Call Stack becomes like:
main() -> handler()
Now, let's envision what those discarded frames represent concretely. If we were to resume after throw "can't be a zero!"
, then we should
-
return n + 1
fromoneMoreIndirection
- then
return x * 2
fromunsafeOperation
- then return to ...hmmm
Where should we return after? It must be somewhere inside handler
but where exactly? The control is now inside catch
but it may not be obvious where our continuation would fit. But remember, exceptions work through a double decision
- control is transferred to the most recent enclosing handler
- the stack frames from the throwing function up to the handler are discarded
So what happens if we keep decision (1) but change (2): the stack frames aren't discarded but reified as a function (a delimited continuation), which is provided as argument to the handler? In an hypothetical JavaScript, this would look like:
function handler() {
try {
unsafeOperation(0);
} catch (e, /**/resume/**/) {
// ...
return 0;
}
}
Now it may not be obvious what should we do with resume
. After all, it doesn't make much sense to resume a function that has already aborted. But that's only if we consider non-local control transfer as exclusively meant to signal exceptions. What if we could use it in a more general way, as a sort of interaction between a (maybe deeply nested) function and an enclosing handler?
The function can throw a request, and the handler interprets the request then resumes the function using the provided continuation. As with exceptions, the function doesn't need to know anything about the handler or how the request is fullfilled. And, that's the core idea of Algebraic Effects.
I'm not going to discuss the motivation behind throwing effects vs executing them right away inside a function. The question just translates to why we should separate pure and impure computations, which is a whole subject ont its own.
The thing I want to mention here, is that many discussions I saw on this subject lack the required context. Many arguments that are valid in a language like Haskell aren't necessarily transposable to a language like JavaScript. In the former, things like purity makes it easier to give a mathemtical interpretation to a program, which can be exploited by the compiler to prove many properties about the program at compile time. This isn't the case in JavaScript, which doesn't have the same mathematical formalism underline (for example I see no reason to forbid mutation of local varibales in JavaSript). On the other hand, I do beleive some other properties, like Compositionality, are equally important in any programming language.
So back to our earlier example, here's how the whole example may look like in our hypothetical JavaScript:
function main() {
return handler();
}
function handler() {
try {
operation();
} catch (e, resume) {
return resume("Yassine");
}
}
function operation() {
return oneMoreIndirection();
}
function oneMoreIndirection() {
const name = throw "Your name, please?";
return `Hi ${name}`;
}
If you ever worked with libraries like redux-saga
it's the same idea but on streoids. Here, you have full control over the effects (while in libs like redux-saga
the interpretation of effects is hard coded in the library). As we'll see, you have even control over the return value of the handled computation.
Ok, having seen what could be JavaScript in a parallel universe, let's go back to reality. While we'll, probably, never see the catch
clause taking a continuation argument some day, we can use our old freinds, Generators, as a decent consolation.
Implementing Algebraic Effects with Generators
We're going to do this in two steps.
- First, we'll implement just the exception like part: transfer the control to the closest handler
- Then we'll add the code to capture the delimited continuation up to the handler
We'll base our implementation on this version from the last post
function isGenerator(x) {
return x != null && typeof x.next === "function";
}
function runGenerator(gen, arg) {
const { value, done } = gen.next(arg);
if (done) {
const _return = gen._return;
if (isGenerator(_return)) {
runGenerator(_return, value);
} else if (typeof _return === "function") {
_return(value);
}
} else {
if (isGenerator(value)) {
value._return = gen;
runGenerator(value, null);
} else if (typeof value === "function") {
value(gen);
}
}
}
function start(gen, onDone) {
gen._return = onDone;
runGenerator(gen, null);
}
Quick remainder, the code relies on a _return
field on the Generator, which points to the parent Generator. Inside a Generator, we can either yield a call to a child Generator (in which case we set its _return
to the current one), or yield a suspended computation (just a fancy name for a function taking the current Generator).
First, let's add the equivalent of our try/catch
clause.
function withHandler(handler, gen) {
function* withHandlerFrame() {
const result = yield gen;
// eventually handles the return value
if (handler.return != null) {
return yield handler.return(result);
}
return result;
}
const withHandlerGen = withHandlerFrame();
withHandlerGen._handler = handler;
return withHandlerGen;
}
- First thing we need is to run
withHandler
in its own Generator, this way it'll have its own stack frame - We save the provided handler in a
_handler
field inwithHandler
's own Generator - Inside this Generator, we run the provided computation
- The handler may eventually handle the return value of the computation, we'll see later how it can be useful
For example:
const abortHandler = {
//optional, handles the return value
*return(result) {
// ...
},
*abort(msg) {
console.error(msg);
return 0;
}
};
function* main() {
yield withHandler(abortHandler, someFunc());
}
We set abortHandler
as a handler for all abort
effects thrown from inside someFunc()
. The function, or one of its children, can use perform("abort", msg)
to throw an exception that will bubbles up to the handler.
Below our first implementation of perform
(note we don't capture the continuation)
function perform(type, data) {
return performGen => {
// finds the closest handler for effect `type`
let withHandlerGen = performGen;
while (
withHandlerGen._handler == null ||
!withHandlerGen._handler.hasOwnProperty(type)
) {
if (withHandlerGen._return == null) break;
withHandlerGen = withHandlerGen._return;
}
if (
withHandlerGen._handler == null ||
!withHandlerGen._handler.hasOwnProperty(type)
) {
throw new Error(`Unhandled Effect ${type}!`);
}
// found a handler, get the withHandler Generator
const handlerFunc = withHandlerGen._handler[type];
const handlerGen = handlerFunc(data);
// will return to the parent of withHandler
handlerGen._return = withHandlerGen._return;
runGenerator(handlerGen, null);
};
}
The function returns a suspended computation that does the following
- lookup for the closest handler that can handle
type
like effects - if we can't find a suitable handler, we throw (for real this time) an error
- if a matching handler is found, we instantiate its function with the effect data
- set the
_return
address of the handler's Generator to the parent ofwithHandler
clause - run the handler's Generator
Note the last step means we're purely ignoring performGen
, which corresponds to how catch
discards the throwing function.
Let's see how it works with the earlier error handling example adapted to Generators
const abort = {
*abort(msg) {
console.error(msg);
return 0;
}
};
function* main(n) {
return yield handler(n);
}
function* handler(n) {
return yield withHandler(abort, unsafeOperation(n));
}
function* unsafeOperation(n) {
const x = yield oneMoreIndirection(n);
return x * 2;
}
function* oneMoreIndirection(n) {
if (n < 0) {
// throw
yield perform("abort", "can't be under zero!");
}
return n + 1;
}
start(main(2), console.log);
// => 6
start(main(-1), console.log);
// => can't be under zero!
// => 0
Let's take a closer look to how perform
/withHandler
work together in this case.
Since withHandler
doesn't change the Call Stack, but just wraps the given Generator and sets a special _handler
field, when we reach the oneMoreIndirection(-1)
the stack looks like this:
main(-1) -> handler(-1) -> withHandler({abort}) -> unsafeOperation(-1) -> oneMoreIndirection(-1)
yield perform("abort", msg)
finds the closest handler, which becomes the direct child for the parent of withHandler
clause:
main(-1) -> handler(-1) -> abort(msg)
Notice how this is similar to shift
/reset
we saw in the previous post. When shift
doesn't use the captured continuation, it effectively discards all the stack frames up to, and including, the reset
block. shift
repalces, then, the whole surrounding reset
block and becomes the main expression of reset
's parent. In fact, shift
/reset
presents much more similaralities with perform
/withHanndler
as we'll see in a moment.
Capturing the delimited continuation
We shall, now, generalize our exception like handling by providing the handler with a delimited continuation that represents the previously discarded stack frames. This time, however, we'll proceed differently. Before jumping into the code, we'll start with a usage example, analyze how things should work in this example, then show the implementation.
The example uses a read
effect to get a value from the surrounding environment. For our purpose, the handler will interpret the effect with a constant value.
// define the `read` handler
const constRead = {
*read(_, resume) {
const result = yield resume("Stranger");
return result;
}
};
function* main() {
return yield withHandler(constRead, greet());
}
function* greet() {
const name = yield withCivility();
return `Hi, ${name}`;
}
function* withCivility() {
// throw the `read` effect
const name = yield perform("read");
return `M. ${name}`;
}
start(main(), console.log);
// => Hi, M.Stranger;
Assuming we have a working perform
implementation, let's envision how the example should manipulate the Call Stack. As always, nothing happens until we reach withCivility()
main() -> withHandler({read}) -> greet() -> withCivility()
When performing the read
effect, we know from the previous example that the handler will become the direct child of main()
. However, the intermediate frames, previously discarded, will now become the delimited continuation provided to the read
handler
main() -> read(_, <<withHandler({read}) -> greet() -> withCivility()>>)
We should point to an important thing here. The captured continuation is still wrapped by withHandler({read})
, this is essential because we still want to handle further read
effects from the rest of the computation. Notice, also, that the read
handler runs outside withHandler({read})
scope, this is also important, this handler may, itself, forward read
effects (or any other effect) to an upstream handler. This makes it possible to compose different handlers. Each handler in the chain may perform some preprocessing then delegate the same (or another) effect to a parent handler.
So, now when read
's handler resumes the delimited continuation the stack becomes
main() -> read(_, <<>>) -> withHandler({read}) -> greet() -> withCivility()
Note our continuations can only be invoked once (one shot). This is repersented by setting the second argument of read
to <<>>
.
In the case withCivility
performs a second read
effect, it will be trapped again by the surrounding withHandler
and a new handler instance will be created and inserted into the stack. The parent of the new handler will be withHandler({rad})
's parent, which in this case the former read
handler.
Ok, having seen an example of how perform
should manipulate the Call Stack. Let's put it into actual code
function perform(type, data) {
return performGen => {
// finds the closest handler for effect `type`
let withHandlerGen = performGen;
while (
withHandlerGen._handler == null ||
!withHandlerGen._handler.hasOwnProperty(type)
) {
if (withHandlerGen._return == null) break;
withHandlerGen = withHandlerGen._return;
}
if (
withHandlerGen._handler == null ||
!withHandlerGen._handler.hasOwnProperty(type)
) {
throw new Error(`Unhandled Effect ${type}!`);
}
// found a handler, get the withHandler Generator
const handlerFunc = withHandlerGen._handler[type];
const handlerGen = handlerFunc(data, function resume(value) {
return currentGen => {
withHandlerGen._return = currentGen;
runGenerator(performGen, value);
};
});
// will return to the parent of withHandler
handlerGen._return = withHandlerGen._return;
runGenerator(handlerGen, null);
};
}
The key code is
function resume(value) {
return currentGen => {
withHandlerGen._return = currentGen;
runGenerator(performGen, value);
};
}
It gives its meaning to the line const result = yield resume("Stranger")
in the handler code. Especially, withHandlerGen._return = currentGen
delimits the continuation starting from performGen
(the Generator that performed the effect) to currentGen
(the Generator that executed yield resume(...)
).
You may have noticed how the implementation of withHandler
/perform
looks similar to shift
/reset
from the previous post:
-
reset
puts a special mark on a satck frame withHandler
installs a handler on a stack frameshift
finds the closestreset
and becomes the direct child ofreset
's parentperform
finds the closest & matchingwithHandler
, the matching handler becomes the direct child ofwithHandler
's parentshift
captures all the intermediate frames and reifies them into an argument to its computationperform
captures all the intermediate frames and reifies them into an argument to the matching handler
In fact, Algebraic Effects can be seen as a more structured alternative to delimited continuations.
Voilà, that's all mechanics of Algebraic Effects in action. In the remaining of this post, we'll see some more examples.
Example 1: reverse logging
Our first example will be a log
handler that prints the logged messages in the reverse order. It may look a little fancy, but should give us a more firm understanding of the mechanics.
function log(msg) {
return perform("log", msg);
}
const reverseLog = {
*log(msg, resume) {
yield resume();
console.log(msg);
}
};
function* main() {
return yield withHandler(reverseLog, parent());
}
function* parent() {
yield child();
}
function* child() {
yield log("A");
yield log("B");
yield log("C");
}
Let's see the Call stack before performing the first log
effect
main() -> withHandler({reverseLog}) -> parent() -> child()
After yield log("A")
main() -> log("A", <<withHandler({reverseLog}) -> parent() -> child()>>)
The handler invokes the continuation before logging the message so
main() -> log("A", <<>>) -> withHandler({reverseLog}) -> parent() -> child()
After yield log("B")
main() -> log("A", <<>>) -> log("B", <<withHandler({reverseLog}) -> parent() -> child()>>)
Again the second handler instance invokes the continuation before logging, so
main() -> log("A", <<>>) -> log("B", <<>>) -> withHandler({reverseLog}) -> parent() -> child()
After yield log("C")
main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<withHandler({reverseLog}) -> parent() -> child()>>)
After the third handler instance invokes the continuation
main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({reverseLog}) -> parent() -> child()
child()
, parent()
, withHandler({reverseLog})
terminate successively, which results in the following Call Stack
main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>)
The logs will now resume starting from rightmost stack frame, which prints the messages in the reverse order.
Example 2: collecting logs
This one collects the logs in an array instead of logging them
const collectLogs = {
return(x) {
return [x, ""];
},
*log(msg, resume) {
const [x, acc] = yield resume();
return [x, `${msg} {acc}`];
}
};
function* main() {
return yield withHandler(collectLogs, parent());
}
function* parent() {
return yield child();
}
function* child() {
yield log("A");
yield log("B");
yield log("C");
return 10;
}
start(main(), console.log);
// => [10, "A B C "]
After the third handler instance invokes the continuation, we endup with
main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({collectLogs}) -> parent() -> child()
child()
returns 10
to parent()
, which returns the same value to withHandler({collectLogs})
main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({collectLogs})
Since collectLogs
has defined a return
clause, the value will be processed by the matching handler, which results in withHandler({collectLogs})
returning [10, ""]
to its parent log("C")
. This one concats ""
(acc
) with "C"
(msg
) and returns [10, "C "]
to log("B")
. The whole process results in [10, "A B C "]
being returned
Combining handlers
Here we compose the two precedent handlers
const reverseLog = {
*log(msg, resume) {
yield resume();
console.log(msg);
yield log(msg);
}
};
const collectLogs = {
return(x) {
return [x, ""];
},
*log(msg, resume) {
const [x, acc] = yield resume();
return [x, `${msg} ${acc}`];
}
};
function* main() {
return yield withHandler(collectLogs, withHandler(reverseLog, parent()));
}
// ... rest unmodified
start(main(), console.log);
// => C
// => B
// => A
// => [undefined, "C B A "]
The first handler prints the message in the reverse order, then forwards the log
effect to collectLogs
, since the logs are forwarded in the reverse order, they endup collected also in the reverse order.
Conclusion
There are many other examples (state, async, ...). Some simple ones could be found here. If you feel more adventurous, you can consult this collection of ocaml examples (not all of them would be applicable in JavaScript).
This concludes our series about Algebraic Effects & Handlers. Hope it wasn't too booring, and thanks again for being a patient reader!
Some references
- An Introduction to Algebraic Effects and Handlers using Eff language
- A talk about Algebraic Effects using the language Koka
-
What's algebraic about Algebraic Effects, if you feel more adventurous. (hint: In programming world, the arity of an algebraic operation isn't the number of params but the number of the possible outcomes, the interpretation
I^A -> I
can be translated into(A -> I) -> I
(function == exponential) which is also the siganture of a CPS function that invokes its continuation(A -> I)
with a value of typeA
, the same siganture of a handler, example: a boolean type has 2 possible outcomesBool -> I -> I
can be seen asI^2 -> I
; please don't ask me more!)
Top comments (5)
I think in Javascript it should be the goal to be explicit about which portion of the code is impure and to separate it from the "pure portion" on the temporal rather then the spacial axis (separate the code).
We can achieve this temporal separation by deferring the evaluation of impure code through thunks. However, we don't want thunks flying around throughout our code, so we wrap them in an object type and define some operators to be able to lift normal functions into this type and to chain operations on this type.
Now we can compose eventually-impure with pure code and unleash the effects later explicitly by calling e.g.
Sounds like the main idea behind
redux-saga
library.Huge thank for the amazing series!
In the Example 2: the
return
handler should be a generator, so, you missed a '*'?