Continuation Passing Style

In asynchronous programming, because we don’t have real-time results, we tend to set up callbacks to handle the results of execution.

fun doSomethingAsync(param1: Int, param2: Any, callback: (Any?) -> Unit) {
    // ...
    // when execution is done
    callback.invoke(result)
}
Copy the code

Suppose we agree on a programming specification that defines all functions in such a way that all functions return the result directly, but pass a callback function argument at the end of the argument list, and process the result through this callback when the function completes. This code Style is called Continuation Passing Style. The callback here is called a continuation. That is, the callback determines what the program will do next. The logic of the program is pieced together by successive continuations.

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. (from Wikipedia.)

The advantages of the CPS

We naturally implement asynchronous logic in a cpS-like manner because we do not know when to process the result of a method, so we pass control logic to the method to be called and let the method call itself after execution. We had to follow the sequentially executed control logic, but CPS gave us the opportunity to customize the control logic. So what can custom control logic do? Let’s look at an example.

Build a single-threaded event loop model

Let’s add a little rule: Every time a function is called and a callback is passed in, the callback is first converted to EventCallback. EventCallback puts the callback into a single-threaded thread pool to execute, as shown in the sample code below.

val singleThreadExecutor = Executors.newSingleThreadExecutor()

fun ((Any?) -> Unit).toEventCallback(): ((Any?) -> Unit) {
    return fun(result: Any?) {
        singleThreadExecutor.submit {
            this.invoke(result)
        }
    }
}

fun doSomething(param1: Any, callback: (Any?) -> Unit) {
    var result: Any? = null
    // ...
    // when execution is done
    callback.toEventCallback().invoke(result)
}
Copy the code

For some operations that require time to wait (such as IO operations), we can define some special functions, in which the specific logic is put into a specific thread pool to execute, and then return to the event thread after the operation is completed, so as to ensure that our event thread is not blocked.

val IOThreadPool = Executors.newCachedThreadPool()

fun doSomethingWithIO(param1: Any, callback: (Any?) -> Unit) {
    IOThreadPool.submit {
        var result: Any? = null
        // ...
        // when io operation is done
        callback.toEventCallback().invoke(result)
    }
}
Copy the code

In this way, we have actually established a single event loop + asynchronous IO execution model similar to Node.js. We can see that by using CPS, we can deal with the return value more flexibly, such as choosing the appropriate time or doing interception operation.

The disadvantage of the CPS

Callback Hell

In a normal execution model, if we need multiple presuppositions to compute a final result, we simply evaluate each value sequentially, and then evaluate each presupposition horizontally in the result, but in CPS, the order of execution is passed through callbacks. So we have to nest each value’s calculation as a Callback into another value’s calculation, which is called Callback Hell, and this code can be hard to read.

// Normal val a = calculateA() val b = calculateB() val c = calculateC() // ... val result = calculateResult(a, b, c/*, ... */) // CPS fun calculateResult(callback: (Any?) -> Unit) { calculateA(fun(a: Any?) { calculateB(fun(b: Any?) { calculateC(fun(c: Any?) {/ /... callback.invoke(calculate(a, b, c/*, ... */)}}}}Copy the code

Stack space usage problem

In languages such as C and Java, each function call allocates stack space for the function’s parameters, return values, and local variables, and then releases this space after the function returns. In the CPS model, we can see that the callback is called before the function is executed, so the stack space of the outside function is not released after entering the callback function, so the program is prone to the problem of stack space overflow.

CPS callbacks are special in that they are always executed as the last step of the function (instead of the return value in the normal process), so the value of the outer function is not accessed again, which is a manifestation of tail-recursive calls. In most functional languages, tail-recursion is optimized to reclaim stack space for outer functions. But there are no such optimizations in C and Java.

Kotlin coroutine

Kotlin Coroutine essentially uses CPS to control the process and solves some of the problems that arise when using CPS.

suspendThe keyword

The suspend function in Kotlin is written basically the same as a normal function, but the compiler does CPS on functions marked with the suspend keyword, which resolves the problem we mentioned with callback hell: We can still write the code in the normal order of the flow, and the compiler will automatically change it to the CPS equivalent.

In addition, to avoid the stack space problem, the Kotlin compiler does not actually convert the code into function callbacks, but instead leverages the state machine model. Kotlin called the suspend function a suspension point each time. During CPS transformation at compile time, each two Suspension points can be regarded as a state, and each time it enters the state machine, there is a current state. The code corresponding to that state is then executed, returning the result value if the program is finished, otherwise a special flag is returned indicating that it exits from the state and waits for the next entry. This is equivalent to implementing a reusable callback, using it each time and executing different code depending on the state.

Process control

As in our example of controlling callback execution above, Kotlin can also control the suspend function through the CoroutineContext class. A CoroutineContext is a structure similar to a one-way list. The system iterates through the list and controls the flow of the suspend function by each element. For example, we can use the Dispatcher class to control the thread on which the function executes, or use the Job class to cancel the current function execution. We can use Coroutine to rewrite the model we defined above:

class SingleLoopEnv: CoroutineScope {
		
override val coroutineContext: CoroutineContext = 
        Executors.newSingleThreadExecutor().asCoroutineDispatcher()

    suspend fun doSomething(param1: Any?): Any? {
        var result: Any? = null
        // ...
        // when execution is done
        return result
    }

    fun doSomethingWithIO(param1: Any?): Deferred<Any?> = 
            GlobalScope(Dispatchers.IO).async {
        var result: Any? = null
        // ...
        // when io operation is done
        return result
    }

    fun main() = launch {
        val result = doSomething(null)
        // handle result
        // ...

        val ioResult = doSomethingWithIO(null).await()
        // handle io result
        // ...
    }
}
Copy the code

conclusion

Coroutine is a syntactic sugar, as Kotlin offers several other mechanisms, but it is an advanced syntactic sugar that changes the execution logic of our code, allowing us to better leverage the idea of CPS functional programming to solve complex asynchronous programming problems.

Article by Orab