A few months ago I was reading this article about coroutines in game development and how they are great tools for writing scripts (as in movie scripts) in the same language as the game engine. Until then I heard about coroutines but never really gave them a thought, this piqued my curiosity.

A coroutine is a kind of subprogram that can be paused and then resumed later on.

Let’s take a look at an example from Python

As you can see the execution of the function “my_coroutine” is paused and resumed at “yield”.

Lightweight, fast, easy to use coroutines usually require some kind of language, compiler, run-time support because a second call stack is required as well as context switching at the right places.

In the article, Emil Ernerfeldt presents an implementation of C++ coroutines based only on cooperatives threads. The coroutine is executed in a separate thread (“inner”) and communicates with the “outer” thread so that only one is executing at a time. For instance, the equivalent of Python’s “yield” is the inner thread resuming outer thread and suspending itself.

This way of seeing coroutines as collaborative threads is actually very close to the original definition provided by Donald Knuth in The Art Of Computer Programming (Volume 1):

Subroutines are special cases of more general program components, called coroutines. In contrast to the unsymmetric relationship between a main routine and a subroutine, there is complete symmetry between coroutines, which call on each other.

My immediate thought was that it should be fairly easy to do the same with Ada tasks. I was actually quite right about this. But it is only after I implemented a somewhat over-engineered solution, that my colleague Ben Brosgol made me realize there is an even more clean way to implement coroutines in Ada.

So I will first cover the simplest and cleanest solutions and then the over-engineered one.

Coroutines with Rendezvous

The easiest way to implement coroutines in Ada is to use a type of task synchronization called rendezvous. If you first want to know more about rendezvous, you can have a look at the dedicated chapter on learn.adacore.com.

Let’s define a coroutine “inner” task with an entry:

The task will run until it reaches an accept statement and then waits for some other task to synchronize with it, and so on.

On the “outer” side we instantiate the coroutine and call the "Continue" entry:

This code will produce the following output:

As you can see it is quite simple.

Now we can even go further and call the entry in a loop using the “`Callable” attribute:

This code will produce the following output:

This is not completely what we expected, right? Why are there two consecutive “Continue” lines? Well contrary to the schema shown above, the outer task is not instantly suspended when the coroutine task is released, so it will loop and print the second “Continue” line before being suspended again.

Going One Step Further with Task Interfaces

Ada provides task polymorphism through task interfaces. We can define what it means for a task to be a coroutine task like so:

And a task that implements this interface:

We can also define an access type for any task that implement the interface:

The point here is that we can now manipulate a pool of different coroutines in a unified way. Going back to the video example of the beginning, we might have several coroutine scripts running at the same time in a video game engine.

We need a container to hold our accesses to coroutines:

And a couple of subprograms to manipulate the container:

Note that in the Poll procedure here, all the coroutines might run in parallel as the outer task is not waiting for a previously released coroutine to suspend before releasing the next one.

What About Generators?

Generators are a special kind of coroutines that can produce values. We can also make generators using the same idea of collaborative Ada tasks and entries. Let’s see another little example:

And then use it like so:

The (Maybe) Over-Engineered Task Based Coroutines

As I said in the introduction, my first approach was not based on task rendezvous. I implemented an Ada library that provides coroutine features using tasks and suspension objects. It is available here https://github.com/Fabien-Chouteau/task_coroutines or as a crate in the Alire ecosystem: https://alire.ada.dev/crates/task_corounties.html

The implementation is more involved than the rendezvous based presented above. However this is under the hood, and using the library is quite simple. Also the behavior is closer to what one would expect, with only one of the collaborating tasks being executed at a given time. Let's see how to use it.

First we define our Coroutine procedure:

As you can see, it takes an "Inner_Control" object as an argument. This object provides the interfaces to synchronize with the outer task. "Ctrl.Yield" is the equivalent of the "yield" keyword in Python. When the coroutine calls "Ctrl.Yield", its execution is suspended and the outer task execution resumed.

Speaking of the outer task, here is how to create and run the coroutine:

This code will produce the following output:

Generators

I also implemented generators in the same way. The package is generic, it has to be instantiated with the type of data that we want to generate:

The definition of the generator sub-program goes like this:

We have the same concept with the "Inner_Control" type and its "Yield" subprogram, except in this case it takes an argument. This is the value that is returned to the outer task.

The "Int_Generator.Instance" type implements the iterator interface, so we can use it in a “for of” loop like so:

This code will produce the following output:

Pros and Cons

I presented several solutions for coroutines and generators in this post. The common advantage across all of them is that they rely on standard Ada features, and therefore should be portable on any platform with Ada tasking available. On the other hand, spawning a task is a relatively costly operation both in terms of time and memory usage, so these coroutines are not lightweight.

Alternative

A few years ago, my colleague Pierre-Marie de Rodat made a prototype implementation of coroutines and generators based on the Portable Coroutine Library (PCL). It might provide better performance at the cost of relying on an external dependency. The project is hosted here: https://github.com/pmderodat/a...

What about Ravenscar and embedded?

The rendezvous based approach is not compatible with the restrictions of the Ravenscar profile, primarily because task entries are not allowed. And the current implementation of the “task_coroutines” library relies on features that are not available in the Ravenscar profile (entry select), so it is also incompatible as is. I think it could be doable with a different API, but then there is the question of the usefulness of this kind of coroutines when tasks cannot be created dynamically at run-time.

At some point I would like to investigate another approach to coroutines for embedded systems, like the one presented here for the GameBoy Advance. Dealing with the GNAT secondary stack might be a problem though, we’ll see.