coroutines instead of closures

With coroutines being so core to the execution engine of STZ it does make me wonder - do we really need closures too?

There's actually two kinds of closures. The first kind is passed on the stack and dies when the stack frame that defined it no longer needs it. These are meant to be cheap, quick things that are used as code blocks:

height > 50 then: [ stdout write: "I'm in a closure" ]

A pointer to the captured variables and where the code block is are passed as a parameter to then then: method. At some point the then: method evokes the closure - or doesn't. Then then: returns and the closure is no longer needed. All of this information can sit on the stack and cost us basically nothing.

The second kind of closure is the expensive one though:

person fancyPrint: [ stdout write: `name: [person name]` ]

It's not so much that the closure captures person but that the closure is being assigned to person which means it is escaping this stack frame. When we know it can escape we have to elevate it in to an object. Freeing that object is now the responsibility of the programmer. This is where garbage collection makes everything easier because you can set and forget. However, we'd be pretending there was no cost here, yet there clearly is.

Part of this can be mitigated by the creation of free methods that free any variable in the person structure that is owned - in this case fancyPrint could be owned. Sending free to person would therefore also free the closure if there is one.

Now we add coroutines in to the mix. Coroutines are re-entrant. They also have their own stack. They are, in short, more expensive. You don't know how long the coroutine will run for or how deep its call tree will be. We could make basic coroutines cheap by checking what their stack depth would be and calculating how big its stack needs to be. But that'd be a heuristic that paints over the problem.

The better solution is to have a smarter stack - one that grows automatically. The virtual stack proposed by minicoro might fit the bill - they worn it is slower though because it has to set up the stack space. Good news though - we can re-use that allocation if it's "done with" - whenever we know that the coroutine is no longer in scope we can put that stack space back in to a pool to be reused.

Sure, we might waste some memory if that stack had to grow a lot first. But there's still a limit on growth size - 2mb. Worst case scenario is hundreds of thousands of coroutines all growing to 2mb. The pool itself has a size limit though so we'd never end up with hundreds of thousands of coroutines recycling. The majority of it will get deallocated.

So let's figure out what the coding experience would be in stz if we have coroutines.

// evaluating a closure block:
the-block evaluate: arguments

// evaluating an escaped closure block:
the-block evaluate: arguments

// escalate the block in to a coroutine by invoking the magic 'yield'
the-coroutine = [ n: int | 1 to: 10 do: [ i | context yield: n + i ] ]
the-coroutine evaluate: 100 // returns 101, 102, 103, etc... every time we send evaluate: 100 until it ends

Note that a closure cannot be a coroutine unless it is assigned to a variable - or passed as a parameter to another method. That's not strictly true - but if it's not assigned to a variable or parameter it can only ever yield once. That is the same as doing a return.

Speaking of doing a return. What if we dropped context yield: and instead simply used the return syntax of ^ ?

coro = [ n: int | 1 to: 10 do: [ i | ^n + i ] ]

Neat. But problem. There's two blocks there and the inner one is doing the yield/return thing. That means the one passed to to:do: is the coroutine, not the one assigned to coro.

What we'd need is the ability to specify what the coroutine is. Perhaps some new syntax could do this. Perhaps a return type could do this. The problem is worse than that too. That return statement - is it to return from to:do: or is it to return from coro or is it to return from the method containing coro?

The Smalltalk answer is that it returns from coro ... but why would anyone looking at that code be able to assume that? to:do: is like a for loop in which case you treat the code block there as local. But what if it's not? there's a lot of assumptions the programmer has to make.

We need a better way to return and we need a better way to specify a coroutine. So let's do that then. Let's name the return variable and use that.

coro = [ n: int → return: yield |
  1 to: 10 do: [ i → ø |
    return = n + i ] ]

Now we're talking. It's explicit what we're doing. It's a little weird that we use assignment to return from something though. Perhaps we'd be better off by using an arrow as we do in the type syntax, something like this ← or → ... now the ← appeals to me because it's the opposite of the → in the type declaration. But using → to mean 'the same thing as return and the return type' has an appeal to it. It also indicates we 'continue on from here'.

coro = [ n: int -> r: yield |
  1 to: 10 do: [ i -> ø | r -> n + i ] ]

We lose the ability to anonymously reference the return value. It takes us farther away from Smalltalk-80. But is that really so bad? for a coroutine that is only ever called once it behaves just like a return. For a coroutine that is evaluated many times it behaves just like a yield.

This is cool for code blocks. But what about methods? methods use a slightly different parameter declaration:

[ self coro: n | int -> yield |
  1 to: 10 do: [ i -> ø | ??? -> n + i ] ]

One solution I have been eyeballing is to make things more explicit in the parameters of a method. Instead of using 'the order' of parameters in the signature, we instead break away from that ordering and name them again. It's slightly more typing but it is more explicit about what's going on - and it's the same syntax for a code block:

[ self coro: n | n: int -> r: yield |
  1 to: 10 do: [ i -> ø | r -> n + i ] ]

There's a problem here though - what does it mean for a method to be a coroutine? A code block sure makes sense but a method? You can't "capture" a method like you can a code block. You can assign a method to a variable - and I suppose invoke it just like you can with a code block. Is that enough? and if so isn't that just a code block that has a signature you're not using?

One approach might be to state that having a return type of yield on a method does turn it in a coroutine - one that will keep evaluating as a coroutine for the entire life of the program. It might be thread local, in fact a way we could state that is to declare the type of r to be r: thread_local yield instead.

This could be very useful. A random number generator, once made, never need be made again. This could also not be useful. Is it a confusing concept that will get in the way? What we gain is the ability to use a coroutine over and over again without having to call evaluate:.

For now I'm going to leave this in the ??? column and state that it's intended to be part of the STZ but may or may not be in the first cut.

And gosh I did not expect to change the way returns are done at this late stage in the design!