Language that allows composition of coroutines

[WiseIndian]

Inspired by http://storm-enroute.com/coroutines/docs/0.6/composition/index.html

This would allow code such as (found in storm en route tests)

def foo(i: Int) = coroutine[Int] { 
        yieldval(i)
        if (i > 0) {
          foo(i - 1)
          foo(i - 1)
        }
      }

Hence code such as

coroutine[X] {
   ...
   co
   ...
}

would be synctactic sugar for:

coroutine[X] {
  ...
  while(true) {
    co.continue() match {
      case Some(yielded) => yieldval(yielded)
      case None => break
    }
  }
 ...
}

Hence, when we encounter some statement in a block of type Coroutine, we would map this statement to the previous code. After that mapping we would transform the whole block as we did before.

I think an important limitation is that we have to verify that the nested corountine (like co in the previous exemple) has to yield elements that are subtypes of the enclosing coroutine's yield type. So we would have to add something to the current checker.

[liufengyun]

This is stackful coroutines. As it's semantically important, we should introduce a special syntax to it, like what we do for yieldval e.

To be more systematic, I'd suggest to start from syntax, semantics, and types, and finally implementation details. There could be many implementations, as long as they conform to semantics, it's fine.

[WiseIndian]

This is augmenting of the following language: https://gist.github.com/liufengyun/b2eafffbe9b925270d48523cdc7b551d

The following is a way to handle pattern matching:

this transformation will prove to be useful in the proposed implementation of stackful coroutines (c.f. the end of this comment).

We would have to update the language specification.

e ::= L | x | e.f | e.f[T](e, .., e) | if(e) e else e | { S*; e } | new p.C(e, .., e)  | (x: T) => e | TryCatch
Z ::= yield e | if(e) Z* else Z* | e | { Z* } | e | x = e | e.f = e | while(e) Z* | x match {  case e => Z*; case e => Z*; ...  case e => Z* }

The transformation for pattern matching is very similar to the if/else case.

〚 x match {  case e1 => Z₁*; case e2 => Z₂*; ...  case en => Zn* } 〛(c)  becomes 
'{
    val next = () => ${c()}
    x match {
    case e1 =>  ${〚Z₁*〛{ () => '{ next()} } }
    case e2 => ${〚Z₂*〛〛{ () => '{next()} } }
    ...
    case en => ${〚Zn*〛〛{ () => '{next()} } }
    }
}

Stackful coroutines:

About the syntax: Since stackful coroutines are an important element of coroutines we are going to add a special "keyword" call to make them stand out.

we simply update Z to add call(co) to it Z ::= yield e | if(e) Z* else Z* | e | { Z* } | e | x = e | e.f = e | while(e) Z* | x match { case e => Z*; case e => Z*; ... case e => Z* } | *call(co)*

Here co must be a coroutine instance. We will enforce this property by later introducing typing rules.

About the semantic of the call keyword:

semantic coroutines can be paused and resumed for any later execution. This means that coroutines within coroutines can be paused and resumed too. The meaning of adding a call(coroutine_instance), where coroutine_instance is an instance of the class Coroutine_implementation <: Coroutine, within a coroutine body definition can be interpreted as replacing call(coroutine_instance) by the body of the Coroutine_implementation continue's method body.

Parenthesis on the proposal for an implementation of yield and call: Their untransformed implementation could throw an exception saying they are situated outside of a coroutine body. 〚 yield(e) 〛(c) would then be as before. 〚call(co) 〛(c) will be described later.

About typing rules for coroutines:

for all yield(arg) in coroutineBody we have: arg Ⱶ T1 and T1 <: T AND for all call(co) in Z* we have: co Ⱶ Coroutine[T2] where T2 <: T __________________________________________________________________________________ coroutine[T] { coroutineBody} Ⱶ Coroutine[T]

Proposal for implementations of call(co):

Given this code one could try inlining the body of the continue method of the class from which co was instantiated. But this might cause problems when in presence of mutual reference of coroutines. Indeed we would infintely generate code in this case. Imagine this simple case:

val c1 = coroutine {
    e1
    call(c2)
    e2
}

val c2 = coroutine {
    e3
    call(c1)
    e4
}

It's transformation would never finish with a rule simple as: 〚call(co) 〛(c) = 〚body of co's continue method 〛(c)

indeed after a first recursion this code would get transformed to

val c1 = coroutine {
    e1
   〚 e3
    call(c1)
    e4
    〛(c)
    e2
}

val c2 = coroutine {
    e3
   〚e1
    call(c2)
    e2
    〛(c)
    e4
}

This is a story that never ends because call(c2) in c2 would make call(c1) appear again and vice versa.

Hence a more sensible idea could be this one:

〚call(co) 〛(c) =
    〚 
        while(true) {
            co.continue() match {
                case Some(yielded) => yieldval(yielded)
                case None => break
            }
        }
    〛(c)

The second transformation call to 〚.〛(c) would take care of actually transforming the while and yieldval within the code.

[liufengyun]

Nice analysis @LeDevDuDimanche 👍

Regarding the syntax, what about join co? I find join is more intuitive than call.

Regarding the implementation, what about just chain the next function, something like this.next = () => co.next()? This seems more efficient. Of course, some tweaking is needed to make it work.

[WiseIndian]

Yeah I like the idea of the join. Its a good name for that operation. Thanks for the tip, I'll think about how to do the tweaking :)

[WiseIndian]

Dear Fengyun I found a solution that might closer to what you suggested:

〚join(co) 〛(c) =

    this.next = () => {
      val subresult = co.next()
      if (subResult.isDefined)
        return subResult

      this.next = () => ${c()}
      this.next()
    }

A small simplified example how what a transformation will look like with that transformation. In this exemple a subcoroutine yields 1. And its "parent" coroutine yields 0, then joins this subcoroutine and then yields2:

abstract class Coroutine {
  var next: () => Option[Int]
}

    val sub = new Coroutine() {
      //yield 1
      var next: () => Option[Int] = () => {
        this.next = () => {
          None
        }
        Some(1)
      }
    }

    val co = new Coroutine() {
      //yield 0
      //join sub
      //yield 2
      var next: () => Option[Int] = () => {
        this.next = () => {
          val subResult = sub.next()
          if (subResult.isDefined) {
            subResult
          } else {
            this.next = () => {
              this.next = () => None
              Some(2)
            }
            this.next()
          }
        }

        Some(0)
      }
    }

[liufengyun]

Nice design @LeDevDuDimanche 👍

One minor comment: avoid using return, and try to test the design with simple examples and improve the sketch.

[WiseIndian]

Thank you :) Ok i'll fall back to an if/else and create tests. I should create a checker for the stackful coroutines too that would check subtyping and whether join is out of its place.

[WiseIndian]

d6542f8