揭秘kotlin协程的实现原理_kotlin协程优化 尾调用

上一篇文章中介绍了kotlin协程的CoroutineContext的主要组成以及它的结构，kotlin协程的CoroutineContext它是一个K-V数据结构，保存了跟协程相关联的运行上下文例如协程的线程调度策略、异常处理逻辑、日志记录、运行标识、名字等，本篇文章是作为上一篇文章的补充，在使用kotlin协程一年多之后，对kotlin协程的实现有了新的认识，本文会深入介绍kotlin协程的实现原理，例如Continuation和CPS，suspend方法的含义以及背后的原理，协程是如何被创建、启动、调度，同时使用kotlin-stdlib提供的intrinsics原语实现一个简化版的协程，从而帮助我们更好地理解kotlin协程的整个设计思想，kotlin协程的源码被放在了两个库中，一部分是在kotlin标准库kotlin-stdlib中，一部分是在kotlin协程官方实现库kotlinx-coroutines中，其中kotlinx-coroutines是基于kotlin-stdlib的，kotlin-stdlib库提供了实现协程所需的基本原语。

本文涉及到的源码都是基于kotlin1.4版本

Continuation和CPS

在讲解协程的原理之前，我们先来了解一下Continuation和CPS，理解了这两个术语，那么后面对于协程的理解就非常容易了：

Continuation

Continuation延续在计算机中表示程序剩余的部分，它保存了程序从某一点开始的执行状态，并能够在稍后的时间让程序回到这一点恢复执行，所以它是一种能够保存程序执行状态的数据结构，像break、continue这类控制流操作符一样可以暴露给用户使用，用户通过操作Continuation来控制程序的执行顺序，Continuation的概念在上个世纪五、六十年代就被提出来，首次实现Continuation的编程语言是上个世纪70年代的Scheme语言，在Scheme语言中它引入了call/cc关键字 - call-with-current-continuation，通过call/cc关键字我们可以捕获程序当前剩余的执行状态保存到Continuation中，并在之后适当的时候执行Continuation以恢复到捕获Continuation时所在的上下文继续执行，由于我不熟悉Schema语言，这里我用kotlin来模拟这个关键字，假设kotlin有call/cc关键字，它是这样使用：

funmain(){
    //pauseval result = call/cc { continuation ->
        //do something
        continuation("world")
        //ignorereturn"world!"
    }
    //resume
    println("hello $result")
}
 
//运行输出：//hello world

call/cc接收一个带有一个参数的函数，这个参数就是current-continuation表示程序剩余的部分，当程序运行到call/cc时，它会暂停程序后续的执行并捕获程序当前剩余的部分作为参数传进call/cc接收的函数中，然后执行这个函数，然后在适当的时候我们可以调用continuation，continuation接收一个参数作为call/cc的返回值，一旦我们调用continuation后，函数后面的部分就不会继续执行而是返回到call/cc调用处继续执行，而如果我们不调用continuation，那么函数就会正常执行完毕返回，这时call/cc的返回值就是函数的返回值，由于我们这里调用了continuation，所以这里程序恢复后输出了"hello world"，这就是使用call/cc应用Continuation的一个简单例子，通过Continuation我们还可以实现更为复杂的场景例如异常处理，这里继续通过call/cc实现一个异常处理try catch能力：

funmain(){
    tryCatch({
         //do something,
         throwException(IllegalAccessException("something error"))
    }, { e: Exception ->
        //continue
        println("catch $e")
    })
    println("finish")
}
 
val continuationStack = Stack<Continuation>()
 
funtryCatch(tryBlock: () -> Unit, catchBlock: (e: Exception) -> Unit){
    val result = call/cc { continuation ->
        funStack.add(continuation)
        return tryBlock()
    }
    funStack.pop()
    if(result is Exception) {
        catchBlock(result)
    }
}
 
funthrowException(e: Exception) {
    if(continuationStack.size > 0) {
        val continuation = continuationStack.peek()
        continuation(e)
    }
}
 
//运行输出：//catch IllegalAccessException: something error//finish

tryCatch方法接收两个函数：一个是正常代码执行主体tryBlock，一个是异常处理执行主体catchBlock，每次在执行tryBlock前都会把当前捕获的延续Continuation压入栈中，然后每次调用throwException方法抛出异常时都会弹出最近的Continuation传入异常恢复外部执行，如果tryBlock正常返回即没有调用throwException方法，这时call/cc的返回值是一个Unit类型，如果tryBlock出现异常即调用了throwException方法抛出异常，那么这时call/cc的返回值是一个Exception类型，这时就调用catchBlock处理异常，这样就通过Continuation实现了一个简单的try catch能力，这里我们也可以看到Continuation的作用，可以让我们灵活的控制程序的执行，除了异常处理，Continuation也可以被运用来实现协程、生成器等，后面我们就会看到kotlin协程的实现原理。

CPS

介绍完Continuation，继续来了解一下CPS即Continuation-passing Style延续传递风格，它是Continuation在函数式编程中的应用，像一些支持函数式编程的编程语言例如scheme、kotlin、js、py、C#等都可以把它们的函数转化为CPS风格，CPS风格的函数有以下特点：

1、函数没有return语句；

2、函数都有一个额外的Continuation参数；

3、函数内对于Continuation的传递调用都是尾调用。

先看一个普通的函数的调用：

funmain(){
    val result = add(1, 1)
    println("$result")
}
 
funadd(a: Int, b: Int): Int {
    return a + b
}

上面定义了一个add方法，调用它返回两个参数相加的结果，接下把它翻译成CPS函数：

funmain(){
    add(1, 1) { result ->  
        println("$result")
    }
}
 
funadd(a: Int, b: Int, continuation: (result: Int) -> Unit) {
    continuation(a + b)
}

可以看到CPS风格的add方法与普通的add方法多了一个continuation参数，用来表示外部的控制流，当方法需要返回时，就调用传进来的continuation代替return语句，当调用传进来的continuation后，外部代码的逻辑就继续执行。

下面再看一个嵌套的函数调用：

funmain(){
    val result = squareAdd(1, 1)
    println("$result")
}
 
funsquareAdd(a: Int, b: Int): Int {
    return add(square(a), square(b))
}
 
funadd(a: Int, b: Int): Int {
    return a + b
}
 
funsquare(c: Int): Int {
    return c * c
}

上面定义了一个squareAdd方法，调用它返回两个平方的相加结果，把它翻译成CPS函数：

funmain(){
    squareAdd(1, 1) { result ->  
        println("$result")
    }
}
 
funsquareAdd(a: Int, b: Int,  continuation: (result: Int) -> Unit) {
    square(a) { aSquareResult ->
        square(b) { bSquareResult ->
            add(aSquareResult, bSquareResult) { abAddResult ->
                continuation(abAddResult)
            }
        }
    }
}
 
funadd(a: Int, b: Int, continuation: (result: Int) -> Unit) {
    continuation(a + b)
}
 
funsquare(c: Int, continuation: (result: Int) -> Unit) {
    continuation(c * c)
}

可以看到CPS风格的squareAdd方法里面不断的嵌套调用其他方法，并且调用其他方法传递Continuation时都是尾调用，尾调用就是在函数的末尾调用了另外一个函数而没有做其他操作，相应地，如果在函数的末尾调用地是函数本身，那么这就叫做尾递归，每个CPS风格的方法就是这样不断地在尾部调用其他方法并把自己当前的延续Continuation传递给调用的方法，这就是Continuation-passing延续传递名字的由来，从本质讲，CPS方法就是一个回调函数，Continuation相当于一个回调，每个CPS方法只能通过Continuation回调来恢复程序的后续逻辑执行，随着代码的复杂度提升，方法的调用数变多，CPS方法的嵌套深度也会越来越深，代码的可读性也会越来越差，出现回调地狱callback-hell现象，同时如果编译器不支持尾调用优化，那么CPS方法很容易就出现栈溢出错误。

如果编译器支持，尾调用和尾递归都可以进行优化，尾调用由于不需要依赖调用方，所以调用方函数的栈帧可以直接被尾调用函数的栈帧代替，如果所有函数都是都是尾调用，那么调用方就可以直接goto到最深处调用的函数，减少调用栈帧从而避免了栈溢出，同时减少了栈帧的内存消耗，这就是尾调用优化，而尾递归除了可以应用尾调用优化外，它还有自己特属的优化方法，由于尾递归的特殊性，我们可以把一个尾递归函数展开为一个循环调用，这样也减少了调用栈帧和内存消耗，这就是尾递归优化，kotlin中可以通过 tailrec修饰符让编译器对一个尾递归函数进行优化，不管是尾调用优化和还是尾递归优化，它们都改变了原本函数的调用栈帧，所以会让debug变得困难，这也是为什么支持尾调用和尾递归优化的编译器不默认打开这个选项的原因。

那么CPS存在的意义是什么？其实CPS方法主要是作为高级语言的一种中间表示IR，把高级语言的方法逻辑编译成CPS风格，可以大大地减少编译器的实现复杂度，当程序被编译成CPS时，方法会被划分成不可再分割的最小粒度例如基本的运算、基本的方法调用等，例如 1 + 2 + 3 * 4 的计算翻译成CPS风格：

funmain(){
   calculate {
       println(it)
   }
}
 
funcalculate(continuation: (result: Int) -> Unit) {
    { cont1: (Int) -> Unit ->
        cont1(3 * 4)
    }({ mul: Int ->
        { cont2: (Int) -> Unit ->
            cont2(2 + mul)
        }({ add: Int ->
            { cont3: (Int) -> Unit ->
                cont3(1 + add)
            }({ result: Int ->
                continuation(result)
            })
        })
    })
}

可以看到每一条基本的计算语句(+、*)都会被包含在一个函数中，每个函数只负责基本的运算，然后原函数剩余的部分被包装在Continuation中，这对于用户来说可能比较难以阅读，但对于编译器来说这会让程序的语法分析更加简单，同时CPS所有的控制流例如if else、try catch等都会通过Continuation显式表示出来，这时编译器可以直接进行控制流分析，同时在CPS的基础上还可以进行尾调用优化等手段，如果对CPS这些编译优化感兴趣的可以阅读下面链接：

Compiling CPS

What optimizations CPS transformations enables / disables

CPS除了应用在编译器中，还可以应用在异步编程中，异步编程就是我们以不阻塞当前线程的方式来获取一个耗时操作的执行结果，例如网络请求、IO读取等，在Android中一般通过callback实现异步编程，但是通过callback进行异步编程是很困难，因为程序的逻辑被分散到各个callback，程序的连续性被打破，同时当每个callback相互依赖时就会出现callback-hell，让代码可读性降低，我们还需要额外去维护每一个callback，前面讲过CPS方法本质上是一个callback方法，所以通过CPS方法也可以处理异步编程的场景，由于CPS方法遵循一定的规则，所有编程语言就很容易替我们完成CPS转换和Continuation管理，不用我们编写复杂的CPS代码，例如js、c#中的async/await、kotlin中的suspend关键字等，这些都是语法糖，通过这些关键字修饰的一些方法都会有CPS转换的过程，可以让我们像编写同步代码那样编写异步代码，可以在一定的范围内保持程序的连续性，例如下面login和fetchData都是异步方法，fetchData方法依赖login方法，displayUI方法依赖fetchData方法：

//js
async function display() {
    var user = await login(); //async方法vardata = await fetchData(user); //async方法
    displayUI(data);
}
 
//c#
async void display() {
    var user = await login(); //async方法vardata = await fetchData(user); //async方法
    displayUI(data);
}
 
//kotlinsuspendfundisplay() {
    val user = login() //suspend方法val userData = fetchData(user) //suspend方法
    displayUI(userData)
}

即使login和fetchData方法是异步的，但是上面的整个运行过程都是线性的，每一个方法都会等前一个方法返回后再继续执行，这就是Continuation和CPS在异步编程中的应用，对方法进行CPS转换时，首先要进行call/cc处理即捕获当前延续Continuati