F# RFC FS-1087 - 再開可能コード&状態機械をざっくり眺める（備忘録）
これはなに？
F# RFC FS-1087 - Resumable code and resumable state machinesを眺めたのをまとめた備忘録です．
注意
- 未リリースなので，将来変更される可能性がある．
- 私の理解（この文書）が間違っている可能性がある．
- 手元で実行していない．
- カテゴリはIdeaです．この文書のクオリティは低いです．読み飛ばして，ところどころ想像が入っているかもしれません．
RFCのサマリ
合成されたResumable code（State machine object）を静的に生成する機能をF#コンパイラに追加する．これによっていくつかのF#のコンピュテーション式がより効率の良い形で実装されるようになる．
RFCに書いてあるモチベーション
コンピュテーション式はアロケーションが起こりがちで，task! { ... }などのコンピュテーション式は，少ないアロケーションで動くことが望まれる．なので，F#では他の言語のコルーチンやHaskellのdo式よりも柔軟に書けるコンピュテーション式の良さを残しつつ，ハイパフォーマンスなコードを生成する術を手に入れたい．
RFCに書いてある設計の方針
- 新しいシンタックスは言語仕様に追加しない．コンパイラの機能にする．
- 静的に合成可能なResumable codeのみに焦点を当てる．
- F#のメタデータは変わらないようにする．
- コンパイル時に解決される．
- この機能はコンパイルの遅い段階に完全に型チェックされる．
- 高度なF#er向けである．
- コンピュテーション式に意味的な変更はない．
Resumable codeとは
Resumable codeは新しい低レベルでプリミティブ，合成可能でre-entrantなコードで，ハイパフォーマンスなコンピュテーション式の実装でのみ使われる．
type ResumableCode<'Data, 'T> = delegate of byref<ResumableStateMachine<'Data>> -> bool
Resumable codeは次のいずれか
- Resumable codeのコンビネータ（ResumableCode.Return, ResumableCode.Delay, ResumableCode.Combine などのFSharp.Coreにあるもの）
- 新しく書かれた低レベルな
ResumableCode<_,_>(fun sm -> <optional-resumable-expr>)デリゲートの実装．
<optional-resumable-expr>は，
if __useResumableCode then <resumable-expr> else <expr>
<resumable-expr>がコンパイル可能の時に，<resumable-expr>が使われ，そうでないときは，<expr>が普通に実行される．
こまごまとしたことは原文参照．
（これから，大事なところだけ書いていきます．）
task!{...}の実装を見てみよう
task!{...}の実装を見てみたい．しかし，これだけ見ても理解は大変なので，C#/VBの結果を参考にしてみてみよう．
簡単な例
C#/VBでAsync/Awaitを使ったらどうなるのか
Module Program
Async Function Fuga() As Task(Of Integer)
Await Task.Delay(100)
Return 0
End Function
End Module
このプログラムをコンパイルしてILSpyでasync/awaitのデコンパイルを無効化したうえで見てみた．（ILSpyがC#でしか出力できないんだから，C#で書くべきだった…）
まず，Fugaが生成した状態機械のためのクラスとFuga()は次の通りだ．（どうでもいい部分は消した）
private sealed class VB$StateMachine_0_Fuga : IAsyncStateMachine
{
public int $State;
public AsyncTaskMethodBuilder<int> $Builder;
internal TaskAwaiter $A0;
internal void MoveNext() { /* ... */ }
}
public static Task<int> Fuga()
{
VB$StateMachine_0_Fuga stateMachine = new VB$StateMachine_0_Fuga();
stateMachine.$State = -1;
stateMachine.$Builder = AsyncTaskMethodBuilder<int>.Create();
stateMachine.$Builder.Start(ref stateMachine);
return stateMachine.$Builder.Task;
}
$Stateはコードのどの場所まで行ったかを記憶する．$builderと$A0は，Asyncのために必要なものである．
メソッドFuga()は，状態機械を作り，その中の$Builderを初期化して，Start(ref TStateMachine)している．Startでは，$Builder.Taskを作ったのちに，VB$StateMachine_0_Fuga.MoveNext()を呼び出している．
VB$StateMachine_0_Fuga.MoveNext()は次の通りだ．（try-catchを消したのでインデントがおかしい）
internal void MoveNext()
{
int num = $State;
int result;
TaskAwaiter awaiter;
if (num != 0)
{
awaiter = Task.Delay(100).GetAwaiter();
if (!awaiter.IsCompleted)
{
num = ($State = 0);
$A0 = awaiter;
$Builder.AwaitUnsafeOnCompleted(ref awaiter, ref this);
return;
}
}
else { /* 後始末コード */ }
awaiter.GetResult();
awaiter = default(TaskAwaiter);
result = 0;
num = ($State = -2);
$Builder.SetResult(result);
}
Fuga()が呼ばれるとき，$Stateは-1から始まる．つまり，if分のthen節が実行される．そこでは，Await Task.Delay(100)があるので，awaiter = Task.Delay(100).GetAwaiter();で実行されていることが分かる．すぐ終わらなかった場合（awaiter.IsCompleted == false）は，$Stateを0にする（次MoveNextが呼ばれたときに後始末するようにする）．そして，$Builder.AwaitUnsafeOnCompletedを呼ぶ．これは，awaiterが完了したときに，this.MoveNext()が呼ばれるようになる．そして，returnしている．一方で次にMoveNext呼ばれた場合か，すぐに終わった場合，resultに0を設定後，$Builder.SetResult(result)（$Builder.Task.Resultの値を設定している．）とreturn分に書いた値を返しているのが分かる．
task!{ ... }はどうか
task!{ ... }の実装はここにある．
状態機械
[<Struct; NoComparison; NoEquality>]
type TaskStateMachineData<'TOverall> =
val mutable Result : 'TOverall
val mutable Awaiter: ICriticalNotifyCompletion
val mutable MethodBuilder : AsyncTaskMethodBuilder<'TOverall>
and TaskStateMachine<'TOverall> = ResumableStateMachine<TaskStateMachineData<'TOverall>>
and TaskResumptionFunc<'TOverall> = ResumptionFunc<TaskStateMachineData<'TOverall>>
and TaskResumptionDynamicInfo<'TOverall> = ResumptionDynamicInfo<TaskStateMachineData<'TOverall>>
and TaskCode<'TOverall, 'T> = ResumableCode<TaskStateMachineData<'TOverall>, 'T>
TaskStateMachineDataは状態機械のデータを持つ構造体で，先ほどの状態機械とメンバが非常に似ている．TaskStateMachineは状態機械なのだろうが，ResumableStateMachineのジェネリクスに適用したものとなっている．他もResumableほにゃららを使っている．
こいつらは，次のとおりである．
/// Acts as a template for struct state machines introduced by __stateMachine, and also as a reflective implementation
[<Struct; NoComparison; NoEquality>]
type ResumableStateMachine<'Data> =
val mutable Data: 'Data
val mutable ResumptionPoint: int
/// Represents the delegated runtime continuation of a resumable state machine created dynamically
val mutable ResumptionDynamicInfo: ResumptionDynamicInfo<'Data>
interface IResumableStateMachine<'Data> with
member sm.ResumptionPoint = sm.ResumptionPoint
member sm.Data with get() = sm.Data and set v = sm.Data <- v
interface IAsyncStateMachine with
// Used for dynamic execution. For "__stateMachine" it is replaced.
member sm.MoveNext() =
sm.ResumptionDynamicInfo.MoveNext(&sm)
// Used when dynamic execution. For "__stateMachine" it is replaced.
member sm.SetStateMachine(state) =
sm.ResumptionDynamicInfo.SetStateMachine(&sm, state)
and ResumptionFunc<'Data> = delegate of byref<ResumableStateMachine<'Data>> -> bool
and [<AbstractClass>]
ResumptionDynamicInfo<'Data>(initial: ResumptionFunc<'Data>) =
member val ResumptionFunc: ResumptionFunc<'Data> = initial with get, set
abstract MoveNext: machine: byref<ResumableStateMachine<'Data>> -> unit
abstract SetStateMachine: machine: byref<ResumableStateMachine<'Data>> * machineState: IAsyncStateMachine -> unit
type ResumableCode<'Data, 'T> = delegate of byref<ResumableStateMachine<'Data>> -> bool
これらは，コンピュテーション式を実装するうえで大変便利な型と関数のテンプレートになる．（すこし下の方に行くと，module ResumableCodeがある．そのモジュールにある関数らはTaskBuilderのWhileなどの関数がそのまま呼び出している．）
ResumableStateMachineは途中の値を持つData，VB/C#の$StateにあたるResumptionPointを持つ．ResumableDynamicInfoとはコンパイル時合成できなかった時のためのクラスである．
TaskBuilder.Run
実際に，TaskBuilder.Runを見てみよう．（言語仕様は変わらないので，ビルダーももちろんある．）
type TaskBuilder() =
member inline _.Run(code : TaskCode<'T, 'T>) : Task<'T> =
if __useResumableCode then
__stateMachine<TaskStateMachineData<'T>, Task<'T>>
(MoveNextMethodImpl<_>(fun sm ->
if __useResumableCode then
//-- RESUMABLE CODE START
__resumeAt sm.ResumptionPoint
try
let __stack_code_fin = code.Invoke(&sm)
if __stack_code_fin then
sm.Data.MethodBuilder.SetResult(sm.Data.Result)
with exn ->
sm.Data.MethodBuilder.SetException exn
//-- RESUMABLE CODE END
else
failwith "unreachable"))
(SetStateMachineMethodImpl<_>(fun sm state -> sm.Data.MethodBuilder.SetStateMachine(state)))
(AfterCode<_,_>(fun sm ->
sm.Data.MethodBuilder <- AsyncTaskMethodBuilder<'T>.Create()
sm.Data.MethodBuilder.Start(&sm)
sm.Data.MethodBuilder.Task))
else
TaskBuilder.RunDynamic(code)
__useResumableCodeで分岐しているのが分かるだろう．then節が合成される状態機械のコードであろう．
まず，__stateMachine関数にMoveNextMethodImpl，SetStateMachineMethodImpl，AfterCodeとなる関数を渡す．これら4つは，全てコンパイラに教えるための関数，ディレクティブみたいなもので，実装を見にいっても，（ResumableCodeと同じところにある．）failwithがあるだけで，何もない．MoveNextMethodImplはMoveNext()に相当する関数，SetStateMachineMethodImpl，AfterCodeは初期化に使われる関数である．SetStateMachine関数はAsyncTaskMethodBuilderに状態機械を紐づける関数である．AfterCodeは先ほどのFuga()関数と見比べると分かりやすいだろう．これから想像するに，task! { ... }を書いた箇所でそのまま実行されるのだろう．
MoveNextMethodImplの中身を見てみる．
__resumeAt sm.ResumptionPoint
try
let __stack_code_fin = code.Invoke(&sm)
if __stack_code_fin then
sm.Data.MethodBuilder.SetResult(sm.Data.Result)
with exn ->
sm.Data.MethodBuilder.SetException exn
__resumeAtは分からないので後回しにしよう．そのあと，__stack_code_finというlet定義があるが，__stackが付くと，スタック上に確保される（状態機械の状態にはならない）変数となる．渡されたResumable codeを実行して，trueならば結果を格納する．Resumable codeの戻り値は終わったか終わってないかを表しているのが分かるだろうか．
TaskBuilder.RunDynamicはすぐ上にあるが，TaskResumptionDynamicInfoが活躍している．TaskResumptionDynamicInfoは静的なコード生成が出来なかった時用であることがわかる．
TaskBuilder.ReturnFrom
次に，TaskBuilder.ReturnFromを見てみよう．
member inline _.ReturnFrom (task: Task<'T>) : TaskCode<'T, 'T> =
TaskCode<'T, _>(fun sm ->
if __useResumableCode then
//-- RESUMABLE CODE START
// This becomes a state machine variable
let mutable awaiter = task.GetAwaiter()
let mutable __stack_fin = true
if not task.IsCompleted then
// This will yield with __stack_yield_fin = false
// This will resume with __stack_yield_fin = true
let __stack_yield_fin = ResumableCode.Yield().Invoke(&sm)
__stack_fin <- __stack_yield_fin
if __stack_fin then
sm.Data.Result <- awaiter.GetResult()
true
else
sm.Data.MethodBuilder.AwaitUnsafeOnCompleted(&awaiter, &sm)
false
else
TaskBuilder.ReturnFromDynamic(&sm, task)
//-- RESUMABLE CODE END
)
awaiterは状態機械のメンバ変数になる変数で，先頭に__stack_が付いていない．そして，VB/C#と同様に，GetAwaiterを呼んでいる．もし，実行するtaskがすぐに終わったならば，真ん中のif文には引っかからずに，__stack_finがtrueとなり，すぐにGetResultされて，結果に代入される．一方で，終わらなかった場合，ResumableCode.Yield()を呼び出し，その結果によって条件分岐をしている．RFCを見ると，ResumableCode.Yieldはコードを中断するときにfalseを返し，コードが再開されるときにtrueを返す．つまり，呼び出した時にfalseを返す．この時，実行中のResumableCodeが終了して，また次に呼ばれるときに，ここから再開され，trueを返すようになる，ということだろうか．この関数は，次のように実装されている．
let inline Yield () : ResumableCode<'Data, unit> =
ResumableCode<'Data, unit>(fun sm ->
if __useResumableCode then
match __resumableEntry() with
| Some contID ->
sm.ResumptionPoint <- contID
false
| None ->
true
else
YieldDynamic(&sm))
RFCでは，match __resumableEntry() withの部分を特別扱いするような記述がある．ここから再開されそうな雰囲気がある．前述した変数awaiterは，記憶するようにしているので，それと合わせると納得がいく．
さて，このYieldのコードについて詳しく見ていこう．このmatch __resumableEntry() withについて，RFCに，
このような式が実行されるとき，最初は
Someの分岐の方が実行される．どんなに再開地点が設定されていても，もし再開が__resumeAtを用いて実行されるならば，Noneの分岐の方が実行される．
初回実行時は，Someの方を通り，ラベル番号を__resumableEntry()で取得し，後々gotoするために，sm.ResumptionPointに代入して記憶する．今度MoveNextが呼ばれたときに，__resumeAtでgotoして，Noneの方を通る，というわけであろう．
では，どこに__resumeAtがあるか，Runに書かれたMoveNextの実装を思い出してみると，
__resumeAt sm.ResumptionPoint
try
let __stack_code_fin = code.Invoke(&sm)
if __stack_code_fin then
sm.Data.MethodBuilder.SetResult(sm.Data.Result)
with exn ->
sm.Data.MethodBuilder.SetException exn
というわけで，match __resumableEntry with None ->の地点でgotoのラベルが入ってそうで，__resumeAtの地点でgotoしていそうである．（実際は後にcodeを呼び出しているので，ジャンプ先を指定して，呼び出した後にgotoしていそうである．）
結びとTODO
F#は面白いと思いました．（小並感）
手元で生成コード見ていないので，早い時期に答え合わせしたいと思います．（TODO）
Discussion