[kotlin deep/shallow/wide dive] deep - suspend가 정확히 뭐고 CPS는 뭐고 state machine이 뭐죠는 꼬리에 꼬리를 물고(2)

1편 : https://velog.io/@bernoyoun/kotlin-deepshallowwide-dive-deep-suspend-1

그러면 이제 state machine이 뭔지를 좀 알아보자.

혹시 state pattern(상태 패턴)이라는걸 design pattern 공부할때 본 적이 있는 사람이 있을 수 있다. 그래도 우리 같이 복습하는 의미로 다시 봐보자.

https://refactoring.guru/design-patterns/state

기본적으로는 FSM(finite-state machine)에서 컨셉을 상당히 가져온 것 같다.
간단히 요약해보면

• 각 상태에 대해서는 유한한 개수(finite)하게 존재함
• 각 상태에 따라서 행동이 달라지며 미리 결정됨
• 현재 상태에서 다른 상태로 전환을 할 수 있고 안할 수 도 있음

이 state의 transition을 관리하기 위해 state-machine이란게 존재함. 문제는 무작정 만들기 시작하면 무수한 if-else or switch-case 난타로 고통받을 수 있음. 그럴때 이 state pattern을 도입하면 숨을 좀 고를 수 있음.

이제 state-machine을 좀 봐보자.
https://developer.mozilla.org/en-US/docs/Glossary/State_machine
결과적으로 여기도 같은 말을 하고 있다.

상태에 대한 관리, transition에 대한 관리를 한다.

이제 coroutine state machine을 이해해보자.

https://kotlinlang.org/spec/asynchronous-programming-with-coroutines.html#coroutine-state-machine

약간 어질어질한 내용이 나온다.

Kotlin implements suspendable functions as state machines, since such implementation does not require specific runtime support. This dictates the explicit suspend marking (function colouring) of Kotlin coroutines: the compiler has to know which function can potentially suspend, to turn it into a state machine.

state-machine에서 관리를 하는게 아니라 suspendable function을 state machine으로 구현하고 runtime에서 뭔가 특별히 support할 필요가 없다고 한다. 지금 내가 상당히 편협한 생각을 가지고 있는가 해서 여러가지 문서들을 좀 찾아봤다.
https://github.com/Kotlin/KEEP/blob/master/proposals/coroutines.md#state-machines

여기를 보면

It is crucial to implement coroutines efficiently, i.e. create as few classes and objects as possible. Many languages implement them through state machines and Kotlin does the same. In the case of Kotlin this approach results in the compiler creating only one class per suspending lambda that may have an arbitrary number of suspension points in its body.
Main idea: a suspending function is compiled to a state machine, where states correspond to suspension points. Example: let's take a suspending block with two suspension points:

이런 내용이 있다.
즉 이게 메인 아이디어라는 건데..

• suspend 함수는 상태 머신으로 컴파일된다,
• 여기서 “상태(state)”는 각 suspension point를 의미한다.

이미 잘 정리된 글 처럼 보이지만 다시 하나 하나 정리를 해가면서 머리에 넣어보자.
예를 들어 아래와 같은 코드가 있다.

val a = a()
val y = foo(a).await() // suspension point #1
b()
val z = bar(a, y).await() // suspension point #2
c(z)

여기에는 3개의 상태가 존재한다:
1. 초기 상태 (아직 어떤 suspension도 발생하기 전)
2. 첫 번째 suspension point 이후
3. 두 번째 suspension point 이후
각 상태는 이 블록의 실행을 이어서 진행할 “continuation에 대한 진입점(entry point)”이다.

이후 컴파일 단계에서 위 코드는 '한 개의 anonymous class'로 컴파일된다.

class <anonymous_for_state_machine> extends SuspendLambda<...> {
    // The current state of the state machine
    int label = 0
    
    // local variables of the coroutine
    A a = null
    Y y = null
    
    void resumeWith(Object result) {
        if (label == 0) goto L0
        if (label == 1) goto L1
        if (label == 2) goto L2
        else throw IllegalStateException()
        
      L0:
        // result is expected to be `null` at this invocation
        a = a()
        label = 1
        result = foo(a).await(this) // 'this' is passed as a continuation 
        if (result == COROUTINE_SUSPENDED) return // return if await had suspended execution
      L1:
        // external code has resumed this coroutine passing the result of .await() 
        y = (Y) result
        b()
        label = 2
        result = bar(a, y).await(this) // 'this' is passed as a continuation
        if (result == COROUTINE_SUSPENDED) return // return if await had suspended execution
      L2:
        // external code has resumed this coroutine passing the result of .await()
        Z z = (Z) result
        c(z)
        label = -1 // No more steps are allowed
        return
    }          
}    

컴파일이 된 anonymous class는 다음을 포함한다:
• 상태 머신을 구현하는 메서드
• 현재 상태를 저장하는 필드 (label)
• suspension 사이에 공유되는 지역 변수들을 저장하는 필드들
• (필요하면) closure 캡처용 필드들, 여기는 없음
그리고 코루틴이 시작되면 이 state-machiine anonymous class는 아래와 같이 동작을 한다.
• 코루틴 시작 → resumeWith() 호출 → label = 0 → L0 실행
• L0에서 작업 수행 → label=1 → await 호출 → 만약 suspend되면 return
• 재개(resume)되면 다시 resumeWith() 호출 → label=1 → L1 실행
• L1에서 작업 수행 → label=2 → await 호출 → suspend되면 return
• 다시 재개되면 → label=2 → L2 실행 → 끝
즉, resumeWith()가 실행 재개 진입점이다.

그러면 만약 loop문 안에 suspension이 있다면?

var x = 0
while (x < 10) {
    x += nextNumber().await()
}

이런 코드가 있다.
컴파일 되면 단 하나의 state만 생성한다. 왜냐하면 because loops also work through (conditional) goto: -> 이미 loop문 자체가 compile단계에서 goto문으로 이루어지기 때문이다.

class <anonymous_for_state_machine> extends SuspendLambda<...> {
    // The current state of the state machine
    int label = 0
    
    // local variables of the coroutine
    int x
    
    void resumeWith(Object result) {
        if (label == 0) goto L0
        if (label == 1) goto L1
        else throw IllegalStateException()
        
      L0:
        x = 0
      LOOP:
        if (x >= 10) goto END
        label = 1
        result = nextNumber().await(this) // 'this' is passed as a continuation 
        if (result == COROUTINE_SUSPENDED) return // return if await had suspended execution
      L1:
        // external code has resumed this coroutine passing the result of .await()
        x += ((Integer) result).intValue()
        label = -1
        goto LOOP
      END:
        label = -1 // No more steps are allowed
        return 
    }          
}    

나는 여기까지만 하면 어느정도 될 줄 알았다. 근데 아래 이런 단락이 있다.
https://github.com/Kotlin/KEEP/blob/master/proposals/coroutines.md#compiling-suspending-functions

The compiled code for suspending function depends on how and when it invokes other suspending functions.

어? 좀 더 봐야겠다.

In the simplest case, a suspending function invokes other suspending functions only at tail positions making tail calls to them

이런 내용이 있다. tail position이 무엇인가? 말 그대로 맨 마지막에 호출되는 것을 말한다.
예를 들어

suspend fun g() {
... (더 이상 suspend function 호출이 없음)
}

suspend fun f() {
    ...
    return g()   <-- 마지막 호출
}

와 처럼 있을 때 return g() 부분이 tail position이다. 이러한 경우는 그냥 일반 함수처럼 compile된다고 한다. 단, CPS패턴에 의거하여 만들어진 continuation 파라미터를 그대로 다음 suspend함수에 넘긴다.(즉, state machine이 필요가 없다.)

이후 나오는 문장 중 non-tail position에 대한 내용이 나온다.

In a case when suspending invocations appear in non-tail positions, the compiler creates a state machine for the corresponding suspending function. An instance of the state machine object in created when suspending function is invoked and is discarded when it completes.

아까 우리가 봤던 state-machine으로 생성되는 패턴이다.

val a = qwer()   // qwer이 suspend function
println(a)
val b = poiu()   // poiu가 suspend function

이 경우 함수가 완료되면 state machine객체가 폐기된다(discarded로 되어있어서 직역했다)

Note: in the future versions this compilation strategy may be optimized to create an instance of a state machine only at the first suspension point

다행(?)스럽게도 나중에 최적화할 생각까지 가지고 계신다.

아까 state machine객체를 폐기한다고 했다. 그러면 어느정도 재사용할 여지가 있어야한다.

This state machine object instance is updated and reused when the function makes multiple invocations to other suspending functions.

진짜 재사용한다고 한다.
자랑스럽게 나오는 내용 중

Compare this to other asynchronous programming styles, where each subsequent step of asynchronous processing is typically implemented with a separate, freshly allocated, closure object.

요약 : 다른 언어는 계속 closure 객체 생성하지? 우리는 재사용해서 좋다.

즉 kotlin에서는

• 이는 다른 비동기 프로그래밍 스타일(예: callback-based)과 대비된다.
• 전통 방식에서는 각 비동기 단계마다 새로운 closure 객체를 계속 생성해야 한다.

이번 글 요약