It's been a while since my last post, but I'm back with more thoughts on managing execution control flow. How do programming languages control the flow or processing of instructions? We are going to be talking about tools far more interesting than control structures such as loops, conditional statements, functions, and exceptions. Not every language has them built in, but most of them could be emulated. As such, this part 1 article discusses the use of continuations, coroutines, and fibers for managing control flow in software programs. It explores the benefits and differences of each mechanism and provides examples of their implementation.
Intro
As software developers, we need to ensure that our programs execute correctly and efficiently. With complex operations, things can get out of control quickly, making it challenging to manage the execution flow. However, with the right tools and techniques, we can make things more reliable. The tools we are going to be talking about are at our fingertips every day. They exist in many programming languages (maybe not all, and not fully), yet trying to describe them in a simple, formal way represents a challenge of not knowing audience's experience level. So we'll start wih the basics ...
Continuations
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on. Wikipedia
There you have it. Simple, right? Something tells me, "Not really"...
Let's start with the basics.
Every program is a bunch of computations performed in a some sort of manner (sequently, parallel, etc.) Every computation is executed in a context (basically all the things it can interact with and all the things that can influence it). It turns out that context could be preserved and the computation could be continued later with the preserver context. Why is it useful? Not all computations are created equal. Not all of them can run at the same time, not all of them should run at the same time. There are many reasons to preserve the context so it could be restored and accessed later (in continuation).
Continuation is a general concept that refers to the state of a computation at any point in time. Think of them as a way of capturing the current state of a program's execution and saving it for later. Continuations are commonly used in programming languages and compilers to implement control flow constructs like exceptions, loops, and function calls. They allow us to save current execution context, including the call stack and local variables, and then resume execution from that context at a later time.
So the question is: How do we capture the context, store it and reuse later? One strait forward answer would be a function that captures its environment, is passed through the program execution and is invoked where needed accessing preserved context. How specifically the context is captured might be different for different languages. But principles are the same.
For example, in JavaScript, continuations can be implemented using closures and higher-order functions.
function withCatch(f, handler) {
return function () {
try {
f.apply(null, arguments);
} catch (ex) {
handler(ex);
}
};
}
function divide(x, y, continuation) {
if (y === 0) {
throw new Error("Division by zero");
} else {
continuation(x / y);
}
}
const handler = function (ex) {
console.log(`Exception: ${ex.message}`);
};
const continuation = function (result) {
console.log(`Result: ${result}`);
};
const divideWithCatch = withCatch(divide, handler);
divideWithCatch(6, 0, continuation); // "Exception: Division by zero"
divideWithCatch(6, 2, continuation); // "Result: 3"
Continuations make us define execution control as their explicit parameters. Reminds you of something? Yep, the callbacks. But not general purpose callbacks. There are some explicit rules around continuations and computations the are part of.
- Continuation is always the last parameter of a computation (function).
- Computation is not allowed to control its flow independently of the continuation (no
returnstatement whatsoever). - Every computation passes control to the continuation explicitly by calling it with the final result as a parameter.
Following these rules strictly we get the style of composing a program that is called continuation-passing style.
In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. Wikipedia
According to the rules, our previous example is not strictly CPS. Let's fix that by treating exceptions like a special case continuations.
function divide(x, y, result, error) {
if (y === 0) {
error(new Error("Division by zero"));
} else {
result(x / y);
}
}
const handler = function (ex, c) {
c(`Exception: ${ex.message}`);
};
const continuation = function (result, c) {
c(`Result: ${result}`);
};
const messages = [];
const logger = (message, c) => {
messages.push(message);
c(messages);
}
divide(10, 0,
(r) => continuation(r, (v) => logger(v, console.log)),
(e) => handler(e, (v) => logger(v, console.log))
);
As we can see, in JavaScript CPS style functions do not compose, forcing us to use callbacks. Callbacks are OK if you have only one or two layers of nesting. But in general, the code with callbacks grows with every next developer simply adding one more to the pyramid also known as callback hell. The problem is solvable. But, as usual, different people went different paths of solving it.
Stack shifting
To some extent a more classical method of removing callbacks is to introduce on-demand stack shifting, also know as Call With Current Continuation (call/cc)
And it works by saving a reference to the current continuation and executing it later outside of the callback. The question is how to get out of the callback. For languages with call/cc native implementation, compiler takes care of it. In JavaScript we are going to use a well known way of breaking out of a function/lambda - throw an exception. And the execution flow would look like this:
- Throw some sort of custom exception with the continuation parameter.
- Catch that custom exception.
- Reuse stored value where needed.
const wrapIt = (value, symbol) => ({
value,
isWrapper: s => s == symbol
});
const callCC = f => {
const id = Symbol();
try {
return f(value => { throw wrapIt(value, id); })
}
catch(ex){
if(ex?.isWrapper(id)) {
return ex.value;
}
throw ex;
}
}
function divide(x, y, c) {
if (y === 0) {
c({
success: false,
value: new Error("Division by zero")
});
} else {
c({
success: true,
value: result(x / y)
});
}
}
const handler = function (ex, c) {
c(`Exception: ${ex.message}`);
};
const continuation = function (result, c) {
c(`Result: ${result}`);
};
const result1 = callCC(done => divide(10, 0, done));
const result2 = callCC(done =>
result1.success ?
continuation(result1.value, done) :
handler(result1.value, done)
);
_ = callCC(_ => console.log(result2))
Composition
Composing functions for the sake of removing callbacks is probably the simplest way of dealing with them. Here is how:
function compose(...fns) {
return (...args) =>
fns.reduceRight((res, fn) => [fn.call(null, ...res)], args)[0]
}
const divide = (x, y, result, error) => {
if (y === 0) {
error(new Error("Division by zero"));
} else {
result(x / y);
}
}
const handler = ex => c => {
c(`Exception: ${ex.message}`);
};
const continuation = result => c => {
c(`Result: ${result}`);
};
const flip = f => y => x => f(x)(y)
compose(
([c, h]) => divide(10, 0, c, h),
x => [flip(continuation)(x), flip(handler)(x)])
(console.log)
Looking at divide parameters result and error, one might think they have seen this pattern of passing two continuations - one for positive and another for negative scenarios before. That is not a coincidence. Here is what happens when we refactor divide further:
const result = (value) => {
if(value?.then) {
return value;
}
return {
then: f => result(f(value)),
catch: _ => error(value)
};
}
const error = (value) => {
if(value?.catch) {
return value;
}
return {
then: f => result(f(value)),
catch: f => error(f(value))
};
}
const divide = (x, y, result, error) =>
y === 0 ?
error(new Error("Division by zero")) :
result(x/y);
const handler = ex => c => c(`Exception: ${ex.message}`);
const continuation = result => c => c(`Result: ${result}`);
divide(10, 0, result, error)
.catch(e => handler(e)(result))
.then(value => continuation(value)(result))
.then(console.log)
Promises, promises (not a proper implementation, but you get the point)...
Generators
Another method of implementing continuations using generators is a bit controversial in a way that it might introduce more complexity to the solution. Nevertheless, when we start thinking about callbacks as if they are generator steps returned by the yield operator, it all starts to make sense. What we are missing is a facility that would run any particular generator until it is exhausted and feed generated returns to the next one and so on.
const isGenerator = g => g?.constructor?.name === 'GeneratorFunction';
function run(generator, ...args) {
let iterator = generator(...args);
let currentValue = null;
let result = iterator.next(currentValue);
currentValue = result.value;
while (!result.done) {
result = iterator.next(currentValue);
if(isGenerator(result.value)) {
iterator = result.value(currentValue);
result = iterator.next(currentValue);
}
if(!result.done) {
const prevValue = currentValue;
currentValue = result.value;
if(isGenerator(currentValue)) {
iterator = currentValue(prevValue);
}
}
}
return currentValue;
}
const divide = (x, y) => function* (next) {
if (y === 0) {
yield new Error("Division by zero");
} else {
yield x / y;
}
yield next
}
const handler = (next) => function* (ex){
if(ex instanceof Error){
yield `Exception: ${ex.message}`;
} else {
yield next
}
};
function* continuation(result) {
yield `Result: ${result}`;
}
const div = divide(10, 0);
const handle = handler(continuation);
const result = run(div, handle);
console.log(result)
Coroutines
For our last example, generators were used to pause and resume computation execution. Surprisingly enough, that is exactly what coroutines are for.
Generators, also known as semicoroutines, are a subset of coroutines. Specifically, while both can yield multiple times, suspending their execution and allowing re-entry at multiple entry points, they differ in coroutines' ability to control where execution continues immediately after they yield, while generators cannot, instead transferring control back to the generator's caller. That is, since generators are primarily used to simplify the writing of iterators, the yield statement in a generator does not specify a coroutine to jump to, but rather passes a value back to a parent routine. Wikipedia
Generator is a fancy way of creating an iterator. Coroutine implements a contract of communication between the caller and the callee in a way that the caller can pause/resume execution but the callee decides on exact points within its execution where it should pause.
Seems like I made things more confusing.
A generator is a function that returns an iterator object, which can be used to iterate over a sequence of values. When a generator is called, it returns an iterator object that can be used to step through the sequence.
A coroutine, on the other hand, is a more general concept that includes generators but also allows for more complex interactions between the coroutine and its caller. Coroutines can use the yield keyword to both produce and consume values. In addition, coroutines can be resumed from where they left off, allowing them to save state and carry out complex operations over multiple calls.
Wait a minute, but wasn't the continuations example with generators implemented in a similar fashion? We did have a generator in there (several generators), and we were passing values between both sides of those generators. So does it mean continuations are coroutines? No exactly ...
Coroutines vs continuations
Coroutines and continuations are both related to control flow, but they have some differences.
A continuation is a function that represents the rest of a computation after a certain point. A continuation can be passed as an argument to another function, which can then invoke it to resume the computation. Continuations can be
one-shot- can be invoked only oncemulti-shot- can be invoked multiple times.
A coroutine is a function that can pause and resume its execution multiple times. A coroutine can suspend its execution and return control to another coroutine or the caller. Coroutines can be
symmetric- transfer control explicitlyasymmetric- transfer control implicitly.
Full coroutines, which are stackful, are similar to one-shot continuations, could be suspended from within a nested stackframe. They can implement control flow features like generators and exception handling using continuations.
However, not all coroutines are full. Some coroutines are stackless, which means only the top-level routine may be suspended (effectively the are compiler synthesized state machines).
Another way to compare coroutines and continuations is by their usability and efficiency. Continuations abort the current computation and jump to another point in the program. Continuations also require copying the captured continuation before modifying it if they are multi-shot.
Coroutines involve pausing and resuming computations without aborting them. Coroutines also avoid copying overhead by using separate stacks for each coroutine.
function coroutine(f) {
const iterator = f();
iterator.next(); // run till first yield
return function(x) {
return iterator.next(x).value;
}
}
function* divide() {
let [x, y] = yield;
while(y === 0){
y = yield new Error("Division by zero");
}
yield (x / y);
}
function* error(){
while(true){
const ex = yield
if(ex instanceof Error){
yield `Exception: ${ex.message}`;
}
}
};
function* result() {
while(true){
const result = yield
yield `Result: ${result}`
}
}
const div = coroutine(divide)
const handler = coroutine(error);
const continuation = coroutine(result)
let value = div([10,0]);
value = handler(value)
console.log(value)
value = div(1);
value = continuation(value)
console.log(value)
Can a coroutine be implemented with no usage of generators? Yes, it can. Let's think what a coroutine actually is. It's a mechanism of dealing with a given computation in chunks. In case of a generator, chunks are divided by a yield keyword. We can mimic all of that by introducing a task queue with a sequential execution. And for the asynchronous part - promises to the rescue.
const Coroutine = () => {
const tasks = [];
let promise = Promise.resolve();
const coroutine = {
add(task) {
tasks.push(task);
},
run(value) {
if(tasks.length <= 0){
return;
}
const task = tasks[0];
promise = promise
.then(() => task(value))
.catch(data => data)
.then(data => {
tasks.shift();
coroutine.run(data);
});
}
}
return coroutine;
};
const divide = (x, y) => () => {
if(y === 0){
throw new Error("Division by zero");
} else {
return x / y;
}
}
const handler = (continueWith) => (ex) =>
ex instanceof Error ? `Exception: ${ex.message}` : continueWith(ex);
const continuation = (result) =>`Result: ${result}`;
const coroutine = Coroutine();
coroutine.add(divide(10, 0))
coroutine.add(handler(continuation));
coroutine.add(console.log);
coroutine.run();
Fibers
We saw how continuations are similar to coroutines when implemented using same language tools like generators. Another construct that is similar to a coroutine is a Fiber.
In computer science, a fiber is a particularly lightweight thread of execution. Like threads, fibers share address space. However, fibers use cooperative multitasking while threads use preemptive multitasking. Threads often depend on the kernel's thread scheduler to preempt a busy thread and resume another thread; fibers yield themselves to run another fiber while executing. Wikipedia
Cooperative scheduling is the concept of fibers yielding to each other, where the switching of execution contexts occurs in the process rather than kernel. This makes context switches an integral part of computation. As a result, many of the overheads associated with context switching can be completely eliminated while allowing for a surplus of execution threads, in the form of fibers.
Because fibers are implemented at the user-level, they can be used in environments where traditional threads are not available or feasible, such as in embedded systems or on platforms that do not support multi-threading. Additionally, because fibers are managed by the program itself, they can be more finely tuned to the specific needs of the program, allowing for more efficient use of resources.
We've seen computational constructs yielding to each other already - coroutines. So fibers are coroutines? No, they are control flow concepts with the different design decisions. Even though fibers are lightweight threads not managed by the kernel directly, the concept ot the scheduler is still in place. Fibers are controlled by a scheduler.
When a coroutine yields, it passes control directly to its caller (or, in the case of symmetric coroutines, a designated other coroutine). When a fiber blocks, it implicitly passes control to the fiber scheduler. Coroutines have no scheduler because they need no scheduler. Distinguishing coroutines and fibers
How do we go about implementing fibers? We are gong to need a few things.
fiber- a primitive that encapsulates the idea itself.coroutine- it gives the ability to yield control. (used as a tool to not to implement things from scratch).scheduler- something that controls when/whether fibers interact.
function Fiber(coroutine) {
const iterator = coroutine();
let data;
return {
moveNext(props) {
if(props){
data = props;
}
const result = iterator.next(data);
if (result.done) {
return false;
}
if(Array.isArray(result.value) && result.value.length > 0){
const [next, p] = result.value;
next.moveNext(p);
}
return true;
}
}
}
const scheduler = () => {
const fiber1 = (x,y) => (next) => Fiber(function* () {
if(y === 0){
yield [next, new Error("Division by zero")];
} else {
yield [next, (x / y)];
}
yield next;
});
const fiber2 = (next) => Fiber(function* () {
let result;
while(!result){
result = yield []; // wait
}
if(result instanceof Error){
yield [next, `Exception: ${result.message}`];
} else {
yield [next, `Result: ${result}`];
}
});
const fiber3 = Fiber(function* () {
let result;
while(!result){
result = yield []; // wait
}
console.log(result);
});
return {
run(x, y) {
const f3 = fiber3;
const f2 = fiber2(f3);
const f1 = fiber1(x, y)(f2);
while (f1.moveNext() || f2.moveNext() || f3.moveNext()) {
console.log("Main thread doing other work...");
}
}
}
};
scheduler()
.run(10, 0)
This code is an example of a simple implementation of cooperative multitasking using fibers in JavaScript. It creates 3 fibers and specifies interactions between them. Every fiber is crested with the Fiber function that wraps corresponding coroutine. Fiber instance is used as a driving force for the coroutine tasks.
The scheduler function creates fiber instances and connects them together. Scheduler also operates on its own mimicking personal execution flow. This is just one example how fibers could be connected by a scheduler waiting to execute their main logic when appropriate parameters are passed from one fiber to another.
In general, fiber is a pretty flexible data structure that could be used to solve different problems. Here is a list of some of them:
- Managing asynchronous I/O: Fibers can be used to manage asynchronous I/O operations, allowing to write code that appears to be synchronous, but is actually executing asynchronously behind the scenes. This can make it easier to write code that performs I/O-bound operations without blocking the main thread.
- Coordinating multiple tasks: Fibers can be used to coordinate multiple tasks or operations, allowing to switch between them in a lightweight manner. This can be useful for scenarios where multiple operations should run parallel but with no usage of the heavy overhead of threads or tasks.
- Managing state in long-running operations: Fibers can be used to manage state in long-running operations, allowing you to pause and resume execution at any time. This can be useful for scenarios where a long-running operation can be interrupted and resume later.
- Implementing coroutines.
- Building custom schedulers: Fibers can be used to build custom schedulers, allowing to control the execution of tasks and operations in a fine-grained manner. This can be useful for scenarios where we need to prioritize certain tasks over others, or where we need to implement complex scheduling algorithms.
Conclusion
Continuations, coroutines and fibers are all related concepts of the software execution control flow, but they have different characteristics and applications.
Continuations: A continuation is a way of capturing the current state of a program's execution and saving it for later. Continuations are commonly used in programming languages and compilers to implement control flow constructs like exceptions, loops, and function calls. Continuations allow you to save the current execution context, including the call stack and local variables, and then resume execution from that context at a later time.
Coroutines: A coroutine is a cooperative multitasking construct that allows multiple execution contexts to run in a single thread of control. Coroutines enable you to write code that can yield control to another coroutine and then resume execution from where it left off. Coroutines are often used in asynchronous programming and event-driven systems, where you need to handle multiple events simultaneously without blocking the main thread.
Fibers: A fiber is similar to a coroutine, but it provides more fine-grained control over the execution context. Fibers allow you to create lightweight threads of execution that can be scheduled and managed independently of the main thread. Fibers are often used in systems programming and operating systems to implement user-level threads and cooperative multitasking.