14,637,446 members
Articles » General Programming » Algorithms & Recipes » Algorithms
Article
Posted 25 Mar 2020

4.4K views
4 bookmarked

# Inspired by codewitch's "What is a Coroutine?"

Rate this:
25 Mar 2020CPOL
Abstracting codewitch's article into a cooperative worker implementation
Specify multiple workers that manage their own state and abstract out the stepper method and execute the work step using an enumerator.

## Introduction

This article was inspired by honey the codewitch's article, What is a Coroutine, so if you're going to vote, I'd suggest you actually vote on her article!

What struck me about what codewitch presented was two things:

1. The work is defined in the `IEnumerable` coroutine itself.
2. The implementation with the `yield` doesn't handle general purpose cooperative multitasking of multiple work items.

## Abstraction, Iteration 1

I decided to look at how the concept could be abstracted to address the two issues above.

### Separate the Work

My first iteration was an attempt to separate out the work. This required three changes:

1. The worker state needs to be specified in its own container.
2. The work itself is a separate method.
3. The `Coroutine` method is changed to take a `Func`, which it executes and returns the result.

To manage the state, we have a formal state class now:

```public class UpDownCounterState
{
public bool IsDone => Value == 1 && CountDirection == Direction.Down;
public int StateValue => Value;

public int Value { get; set; } = 0;
public Direction CountDirection { get; set; } = Direction.Up;
}```

And the worker method is defined separately (for brevity, I changed to this to count from `1` to `7` and back to `1`):

```static (int ret, bool done) Counter(UpDownCounterState currentState)
{
currentState.Value += 1 * (int)currentState.CountDirection;   // A cheat!
bool done = currentState.IsDone;
currentState.CountDirection = currentState.Value == 7 ?
Direction.Down : currentState.CountDirection;

return (currentState.Value, done);
}```

Which yields the following implementation for the Coroutine:

```static IEnumerable<R> Coroutine<R, Q>(Q state, Func<Q, (R ret, bool done)> fnc)
{
bool done = false;

while (!done)
{
var result = fnc(state);
yield return result.ret;
done = result.done;
}
}```

Using this is straightforward - we pass in the initial state and worker method and let the Coroutine do the work of calling and returning the result of each step:

```using (var cr = Coroutine(new UpDownCounterState(), Counter).GetEnumerator())
{
while (cr.MoveNext())
{
Console.Write(cr.Current + " ");
}
}```

And we see:

1 2 3 4 5 6 7 6 5 4 3 2 1

Note that the `code>Coroutine` has been "generified" so that the return can be whatever the worker method returns.

### Multiple Workers

The above achieves a certain degree of abstraction and can be expanded to support multiple workers, let's say we want a multiplier as well. So we have a class to handle the multiplier state:

```static (int ret, bool done) Multiplier(UpDownMultiplierState currentState)
{
currentState.StateValue += 1 * (int)currentState.CountDirection;
bool done = currentState.IsDone;
currentState.CountDirection = currentState.StateValue == 5 ?
Direction.Down : currentState.CountDirection;

return (currentState.StateValue * currentState.Multiplier, done);
}```

And a `Coroutine` implementation that takes a list of workers which loops until all the work is done:

```static IEnumerable<R> Coroutiners<Q, R>(List<(Q state, Func<Q, (R ret, bool done)> fnc)> fncs)
{
List<bool> doners = Enumerable.Repeat(false, fncs.Count).ToList();
int n = 0;

while (!doners.All(done => done))
{
if (!doners[n])
{
var result = fncs[n].fnc(fncs[n].state);
doners[n] = result.done;
yield return result.ret;
}

n = (n == fncs.Count - 1) ? 0 : n + 1;
}
}```

And we can initiate the cooperative coroutine workers like this:

```using (var cr = Coroutiners(
new List<(IState, Func<IState, (int, bool)>)>()
{
(new UpDownCounterState(), Counter),
(new UpDownMultiplierState(), Multiplier)
}).GetEnumerator())
{
while (cr.MoveNext())
{
Console.Write(cr.Current + " ");
}
}```

Given that the multiplier worker goes from 1 to 5 and back to 1 (and the counter goes from 1 to 7 and back to 1), we see:

1 10 2 20 3 30 4 40 5 50 6 40 7 30 6 20 5 10 4 3 2 1

which illustrates the cooperative "multitasking" of each worker.

#### Problems

There are three major problems with this implementation:

1. All workers must return the same type.
2. The abstraction `IState` is required and forces each worker to cast to the concrete state type.
3. The state and the worker is decoupled: `(new UpDownCounterState(), Counter)` such that the programmer could easily apply the wrong state to the worker function.

To illustrate #2, the state containers must be derived from `IState`:

```public interface IState { }

public class UpDownCounterState : IState
{
public bool IsDone => Value == 1 && CountDirection == Direction.Down;
public int StateValue => Value;

public int Value { get; set; } = 0;
public Direction CountDirection { get; set; } = Direction.Up;
}

public class UpDownMultiplierState : IState
{
public bool IsDone => Counter == 1 && CountDirection == Direction.Down;

public int Counter { get; set; } = 0;
public int Multiplier { get; set; } = 10;
public Direction CountDirection { get; set; } = Direction.Up;
}```

To illustrate #3, the workers must cast `IState` to the expected state container:

```static (int ret, bool done) Counter(IState state)
{
UpDownCounterState currentState = state as UpDownCounterState;
currentState.Value += 1 * (int)currentState.CountDirection;
bool done = currentState.IsDone;
currentState.CountDirection = currentState.Value == 7 ?
Direction.Down : currentState.CountDirection;

return (currentState.Value, done);
}

static (int ret, bool done) Multiplier(IState state)
{
UpDownMultiplierState currentState = state as UpDownMultiplierState;
currentState.Counter += 1 * (int)currentState.CountDirection;
bool done = currentState.IsDone;
currentState.CountDirection = currentState.Counter == 5 ?
Direction.Down : currentState.CountDirection;

return (currentState.Counter * currentState.Multiplier, done);
}```

## Abstraction, Iteration 2

The solution to address the problems described above is that each worker must be abstracted out into its own container class which manages its own state:

```public interface ICoroutine
{
bool IsDone { get; }
void Step();
}```

And the worker containers look like this:

```public class UpDownCounter : ICoroutine
{
public bool IsDone => State.IsDone;

protected UpDownCounterState State { get; set; }

public UpDownCounter()
{
State = new UpDownCounterState();
}

public void Step()
{
State.Value += 1 * (int)State.CountDirection;
State.CountDirection = State.Value == 7 ? Direction.Down : State.CountDirection;
}

public override string ToString()
{
return State.Value.ToString();
}
}

public class UpDownMultiplier : ICoroutine
{
public bool IsDone => State.IsDone;

protected UpDownMultiplierState State { get; set; }

public UpDownMultiplier()
{
State = new UpDownMultiplierState();
}

public void Step()
{
State.Counter += 1 * (int)State.CountDirection;
State.Value = State.Counter * State.Multiplier;
State.CountDirection = State.Counter == 5 ? Direction.Down : State.CountDirection;
}

public override string ToString()
{
return State.Value.ToString();
}
}```

Note that the worker initializes its own state! Yes, the programmer can still mess that up, but it's less likely, in my opinion.

Next, the `Coroutines` method signature is actually simpler:

```static IEnumerable<Q> Coroutines<Q>(List<Q> fncs) where Q : ICoroutine
{
int n = 0;

while (!fncs.All(f => f.IsDone))
{
if (!fncs[n].IsDone)
{
fncs[n].Step();
yield return fncs[n];
}

n = n == (fncs.Count - 1) ? 0 : n + 1;
}
}```

But look! We are no longer returning the value of the worker step, we are returning the worker itself! We've also eliminated the need for the `IState` interface.

Its usage is easier to define:

```using (var cr2 = Coroutines(new List<ICoroutine>()
{
new UpDownCounter(),
new UpDownMultiplier()
}).GetEnumerator())
{
while (cr2.MoveNext())
{
Console.Write(cr2.Current.ToString() + " ");
}
}```

And again we see:

1 10 2 20 3 30 4 40 5 50 6 40 7 30 6 20 5 10 4 3 2 1

Here, `ToString` is overridden in the worker so that it returns the worker's current step value, but it should be pointed out that most likely, workers will just do something and we don't care about their internal state, so we can write the cooperative multitasking work simply as:

```foreach (var _ in Coroutines(new List<ICoroutine>()
{
new UpDownCounter(),
new UpDownMultiplier()
}));```

This is an unusual syntax as the `foreach` doesn't have a body! One would hope that the compiler doesn't optimize this into a "this loop does nothing" and throws out the code!

## Conclusion

Inspired by codewitch, we've abstracted the concept of coroutines to support multiple workers and in the process solved a variety of problems. Some ideas: the code here can now be extended to:

• Handle exceptions that a worker might throw without necessarily disrupting the other workers.
• Implement a "stop all" option that any worker can set.
• Include a worker that simply has a "stop all" flag that could be set asynchronously.

Have fun!

## History

• 25th March, 2020: Initial version

## Share

 Architect Interacx United States
Blog: https://marcclifton.wordpress.com/
Research: http://www.higherorderprogramming.com/
GitHub: https://github.com/cliftonm

All my life I have been passionate about architecture / software design, as this is the cornerstone to a maintainable and extensible application. As such, I have enjoyed exploring some crazy ideas and discovering that they are not so crazy after all. I also love writing about my ideas and seeing the community response. As a consultant, I've enjoyed working in a wide range of industries such as aerospace, boatyard management, remote sensing, emergency services / data management, and casino operations. I've done a variety of pro-bono work non-profit organizations related to nature conservancy, drug recovery and women's health.

 First Prev Next
 Coroutines with their own separate call stacks Qwertie8-Apr-20 8:39 Qwertie 8-Apr-20 8:39
 You might find the `Co` type interesting... it's a technique for giving each `yield`-based coroutine its own call stack.
 Couldn't this be simplified? George Swan29-Mar-20 9:38 George Swan 29-Mar-20 9:38
 Re: Couldn't this be simplified? Marc Clifton30-Mar-20 3:00 Marc Clifton 30-Mar-20 3:00
 Coroutine - Routine that caught the coronovirus... mldisibio26-Mar-20 12:48 mldisibio 26-Mar-20 12:48
 Re: Coroutine - Routine that caught the coronovirus... Marc Clifton28-Mar-20 2:08 Marc Clifton 28-Mar-20 2:08
 Encapsulation of routine Niemand2526-Mar-20 0:08 Niemand25 26-Mar-20 0:08
 Re: Encapsulation of routine Marc Clifton26-Mar-20 2:56 Marc Clifton 26-Mar-20 2:56
 Re: Encapsulation of routine Niemand2526-Mar-20 3:18 Niemand25 26-Mar-20 3:18
 Cool! honey the codewitch25-Mar-20 7:39 honey the codewitch 25-Mar-20 7:39
 Re: Cool! Marc Clifton25-Mar-20 7:49 Marc Clifton 25-Mar-20 7:49
 Last Visit: 22-Sep-20 15:21     Last Update: 22-Sep-20 15:21 Refresh 1