AdaCore Blog

Coroutines in Ada, a Clean but Heavy Implementation

by Fabien Chouteau

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

  >>> def my_coroutine():
...     print("step 1")
...     yield
...     print("step 2")
...     yield
...     print("step 3")
...
>>> coro = my_coroutine()
>>> next(coro)
step 1
>>> next(coro)
step 2
>>> next(coro)
step 3

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:

  task type My_Coroutine is
   entry Continue;
end My_Coroutine;

task body My_Coroutine is
begin
   accept Continue;

   Ada.Text_IO.Put_Line ("Step 1");

   accept Continue;

   Ada.Text_IO.Put_Line ("Step 2");

   accept Continue;

   Ada.Text_IO.Put_Line ("Step 3");
end My_Coroutine;

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:

  declare
   Coro : My_Coroutine;
begin
   Coro.Continue;
   Coro.Continue;

This code will produce the following output:

  Step 1
Step 2
Step 3

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:

  declare
   Coro : My_Coroutine;
begin
   
   while Coro'Callable loop
      Ada.Text_IO.Put_Line ("Continue...");
      Coro.Continue;
   end loop;

This code will produce the following output:

  Step 1
Continue
Continue
Step 2
Step 3

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:

  type Coroutine is task interface;
   
procedure Continue (This : Coroutine) is abstract;

And a task that implements this interface:

  task type My_Coroutine is new Coroutine with
   entry Continue;
end My_Coroutine;

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

  type Any_Coroutine_Access is access all Coroutine’Class;

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:

  package Coroutine_List
is new Ada.Containers.Doubly_Linked_Lists (Any_Coroutine_Access);

And a couple of subprograms to manipulate the container:

  procedure Insert (This : in out Coroutine_List.List;
                  C    : not null Any_Coroutine_Access)
is
begin
   if not This.Contains (C) then
      This.Append (C);
   end if;
end Insert;

procedure Remove (This : in out Coroutine_List.List;
                  C    : not null Any_Coroutine_Access)
is
   Cur : Coroutine_List.Cursor;
begin
   if This.Contains (C) then
      Cur := This.Find (C);
      This.Delete (Cur);
   end if;
end Remove;
   
procedure Poll (This : in out Coroutine_List.List) is
begin
   for Elt of This loop
      if Elt.all'Callable then
         Elt.Continue;
      end if;
   end loop;
end Poll;

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:

  task type My_Generator (From, To : Integer) is
   entry Next (Value : out Integer);
end My_Generator;

task body My_Generator is
begin
   for X in From .. To loop
      accept Next (Value : out Integer) do
         Value := X;
      end Next;
   end loop;
end My_Generator;

And then use it like so:

  declare
   Gen : My_Generator (1, 10);
   Val : Integer;
begin
   while Gen'Callable loop
      Gen.Next (Val);
      Ada.Text_IO.Put_Line ("Task Gen:" & Val'Img);
   end loop;0

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:

  procedure My_Coroutine (Ctrl : in out Coroutine.Inner_Control'Class) is
begin
   Ada.Text_IO.Put_Line ("Step 1")
   Ctrl.Yield;
   Ada.Text_IO.Put_Line ("Step 2")
   Ctrl.Yield;
   Ada.Text_IO.Put_Line ("Step 3")
end My_Coroutine;

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:

  declare
   C : aliased Coroutine.Instance; -- Create a coroutine object
begin
   Ada.Text_IO.Put_Line ("Start the Coroutine");
   C.Start (My_Coroutine'Access); -- Start the coroutine

   --  At this point the Coroutine has begun its execution up to the first call to Ctrl.Yield
   loop
      Ada.Text_IO.Put_Line ("Poll");
      C.Poll; -- Let the Coroutine execute again (like next(coro)) in the Python example
      exit when C.Done; --  Check if the Coroutine has reached the end of its execution
   end loop;

This code will produce the following output:

  Start the Coroutine
Step 1
Poll
Step 2
Poll
Step 3

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:

  package Int_Generator is new Generator (Integer);

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

  procedure Gen_Positive (Ctrl : in out Int_Generator.Inner_Control'Class) is
begin
   for X in 1 .. 5 loop
      Ctrl.Yield (X); -- Yield a value
   end loop;
end Gen_Positive;

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:

  declare
   G : Int_Generator.Instance;
begin
   G.Start (Gen_Positive'Access);
   for Elt of G loop
      Ada.Text_IO.Put_Line ("Gen returned: " & Elt'Img);
   end loop;

This code will produce the following output:

  Gen returned: 1
Gen returned: 2
Gen returned: 3
Gen returned: 4
Gen returned: 5

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.

Posted in

About Fabien Chouteau

Fabien Chouteau

Fabien joined AdaCore in 2010 after his engineering degree at the EPITA (Paris). He is involved in real-time, embedded and hardware simulation technology. Maker/DIYer in his spare time, his projects include electronics, music and woodworking.