C# yield return and Scala Continuations

The Scala Collection API and the .NET Collection API are very similar as we could observe in my previous post, yet C# has some constructs that Scala lacks of. However, in Scala we can implement the same features but just in a different way. Let’s take a look at them.

Scala Built-in Missing Feature

When implementing an Iterable in Scala we need to implement the abstract method iterator. This method basically returns an Iterator instance that describes how we can get the elements out from our collection.

Let’s take a look at an example

class AIterable extends Iterable[Int] {
  val items = Seq(1,2,3,4,5) // some kind of data structure
  
  override def iterator: Iterator[Int] = new Iterator[Int] {
    var i = 0

    override def hasNext: Boolean = i < items.length

    override def next(): Int = {
      val a = items(i)
      i += 1

      return a
    }
  }
}

We can see how we need to implement hasNext and next. These methods are required by the Iterator class. It does look simple, but the C# implementation is even simpler.

class ACollection : IEnumerable<int>
{
    private int[] items = { 1, 2, 3, 4, 5 };
        
    public override IEnumerator<int> GetEnumerator()
    {
        foreach (int i in items)
        {
            yield return i;
        }
     }
}

Note that both implementations are conceptually the same, yet they work very different. The key is the yield return construct from C#, missing in Scala.

C# yield return

The the previous example, yield return works in two ways.

First, the compiler generates an IEnumerator class, as the one we saw in Scala, for us. We don’t have to write these classes anymore which releases us of this tedious job.

Second, yield return is a continuation features that C# offers. Yes, it is a continuation mechanism. Once the yield return statement is hit, the expression after it is returned and the execution is suspended. The rest of the computation can be invoked in another time. This is especially useful if we want to iterate our collection lazily. Every time we call MoveNext() (next in Scala Iterator) the rest of the continuation is executed.

Can we do the same in Scala? Indeed we can, but it could get a little more complicated.

The Continuation Model

So, what is all that about continuations?

In computer science and computer programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state.

The best way to look at this, is in my opinion, is through an example.

void Factorial(int n, Action<int> next)
{
  if (n <= 1)
  {
    next(1);
  }
  else
  {
    Factorial(n - 1, x => next(x * n)); 
  }
}

Here we implemented the factorial function, but instead of returning its value, we passed it to the function next (our continuation). In order to call this function, we do:

Factorial(5, x => Console.WriteLine(x));

Now, we want to implement something like yield return to return, lazily, the items from our collection in Scala. The solution is based in the continuation model of computation.

Creating an Iterator in Scala with Continuations

The computation model we just saw is extensively using in Scala. The concept itself is not hard to understand, but sometimes it takes time to crack its details.

Let’s implement the same Iterator as before using continuations, and then walk through each of its parts.

class TList[A](items: Seq[A]) extends Iterable[A] {

  private val xs = items.toList

  override def iterator: Iterator[A] = new Iterator[A] {
    var i = -1

    override def hasNext: Boolean = i < xs.length - 1
    override def next(): A =  reset {
      shift {
        k: (A => A) => {
          k()         

          xs(i)
        }
      }
      x += 1
    }
  }
}

Here, we are changing the Iterator so it uses the Scala continuation features. However, we still need to define the Iterator class that yield return, in C#, generates for us.

The reset marks the scope of the continuation while shift marks the continuation itself. It is basically the same as we did in C#, but expressed in a different way. Note that the function k is the continuation, and x + 1 is the body of the continuation.

Even though in Scala we can suspend the generation of items in our Iterator using continuations, there is no way to replace the Iterator completely as in C#. However, Scala continuations are very useful in other contexts and yield return in C# is bind to the concept of collection generation.

Ending

We just saw we can use continuations in Scala to generate a collection of items while in C# we can use the built-in yield return construct.

Both, C# and Scala offer continuation features. The first one by the use of yield return and async/await. The second one, by using reset and shift.

The C# iterators are now replaced by the continuation created using yield return, but in Scala we still to implement our owns.

I hope these small examples should show how yield return works and the continuations behind it. Also, it should help new people in Scala, coming from C#, to understand better the continuation model.