Most implementations of coroutines are based on some kind of runtime yield primitive. However, kotlin does not have this kind of lower-level support, and still implements coroutines based on CPS transformations on jvm, which does not have yield instruction support.

It’s actually quite impressive, and I’d like to know how it’s done.

CPS Transformation

CPS stands for Continuation Passing Style, which is basically code that looks like this.

1
2
3
4
5

function auth(token, resourceName) {
  let userId = loginUser(token)
  let ok = checkPermission(userId, resourceName)
  return ok ? 'success': 'failed'
}

Convert to this style.

1
2
3
4
5
6
7

function auth(token, resourceName, callback) {
  loginUser(token, function(userId) {
    checkPermission(userId, resourceName, function(ok) {
      callback(ok ? 'success': 'failed')
    })
  })
}

This is also known as “callback hell”, a style that was once popularized in node js. Roughly speaking, the value that should be returned by the function is returned by the callback function in the argument. The word “continuation” is obscure, but it is actually a synonym for “callback”.

The flow is roughly as follows

  1. the asynchronous method is called and the callback function is registered to the io loop.
  2. the io loop acknowledges the io event (e.g., receives a server-side response) and calls back the callback function registered in the io loop, passing the result of the asynchronous return in the arguments and, if there is an exception, also in the arguments to the callback function.
  3. the callback function continues to call other callback functions, registering new callback functions to the io loop when a new asynchronous method is called.

It is the io loop, the scheduler, that really drives the entire control flow.

The problem with callback functions is that they lack structure, and every asynchronous call necessarily involves an exception handling process, which makes the code unreadable; Future / Promise could improve the structure a bit by standardizing the wrapping of onSuccess(result) and onError(err), which would make the code structure a bit nicer.

1
2
3
4
5
6
7

function Promise auth(token, resourceName) {
  loginUser(token)
    .then(userId => checkPermission(userId, resourceName))
    .then(ok => ok ? 'success': 'failed')
    .catch(err => console.log(err))
  })
}

There is one more step in the evolution of async / await style syntax, and that is yield. The difference between the async / await style asynchronous methods is that the async / await mode registers the point at which the function was last executed as the callback entry to the io loop. io loop scheduler finds a response, finds the corresponding function, and presses resume( result) to drive the subsequent execution.

But jvm obviously doesn’t have yield support, so how does kotlin do this?

CPS in kotlin

The asynchronous method is marked in kotlin by adding the suspend keyword.

1
2
3
4
5

suspend fun auth(token: String, resourceName: String): String {
  val userId = loginUser(token)  // suspending fun
  val ok = checkPermission(userId, resourceName)  // suspending fun
  return ok ? 'success': 'failed'
}

At compile time, the suspend method will be converted to CPS approximately, adding a cont parameter to call back the return value or an exception:

1
2
3

suspend fun auth(token: String, resourceName: String, cont: Continuation<Any?>) {
  ...
}

The Continuation is a Promise/Future-like interface.

1
2
3
4
5

public interface Continuation<in T> {
  public val context: CoroutineContext
  public fun resume(value: T)
  public fun resumeWithException(exception: Throwable)
}

The context represents the concurrent context, which is omitted here. resume and resumeWithException are identical to the then() and catch() of Promise in js. All that’s missing here is an alternative to yield.

The context represents the concurrent context, which is omitted here. resume and resumeWithException are identical to the then() and catch() of Promise in js. All that’s missing here is an alternative to yield.

StateMachine

The alternative to yield is the StateMachine, which does two things: 1. suspends and remembers the execution point; and 2. remembers the context of the local variables at the moment the function is suspended.

Each suspend function generates an internal class StateMachine that holds the function’s local variables and execution points.

How to record execution points?

First of all, all suspend points are necessarily the points where the suspend function is called. kotlin does something interesting here by using a switch case, where each suspend execution position corresponds to a label, and the next time execution resumes, the next execution position is found by the incrementing label. The approximate pseudo-code would look like this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

suspend fun auth(token: String, resourceName: String, cont: Continuation<Any?>) {
  val sm = cont as? AuthSM ?: AuthSM(cont)

  when (sm.label) {
    0 -> {
      sm.cont = cont
      sm.label = 1
      loginUser(token, sm)
      return
    }
    1 -> {
      throwOnFailure(sm.result)
      sm.userId = sm.result as Int
      sm.label = 2
      checkPermission(sm.userId, sm)
      return
    }
    2 -> {
      throwOnFailure(sm.result)
      sm.ok = sm.result as boolean
      sm.cont.resume(sm.ok ? "success": "failed")
    }
    else -> throw IllegalStateException(...)
  }
}

Each StateMachine object is also an implementation of the Continuation interface. Whenever the suspend function reaches the suspend point, it will actually exit execution and the execution context of the function will be fully recorded in the StateMachine. The execution of the resume method is equivalent to executing the function again using the context recorded in the StateMachine as an argument.

Draw a diagram to organize the general process.

image

Summary

  • kotlin’s concurrent support is about two parts, CPS transformation and StateMachine. CPS transformation makes synchronous code asynchronous, adding additional Continuation type parameters for function result value return.
  • The switch / case with label to do execution point recording and suspend.
  • Each suspend method generates an internal StateMachine class. The StateMachine class contains all local variables of the function, as well as the return value and exception value of the suspend point, and plays the function of the yield statement, i.e., suspend the execution of the function, for which the current context of the local variables and the execution point of the function need to be recorded.
  • Resuming the execution of the suspended function is equivalent to taking the context of the local variables and the point of execution of the function as arguments. The function is called once again.