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