Zenn
⚒️

F# RFC FS-1087 - 再開可能コード&状態機械をざっくり眺める（備忘録）

2021/05/15に公開
.NET
F#
idea

これはなに？

F# RFC FS-1087 - Resumable code and resumable state machinesを眺めたのをまとめた備忘録です．
https://github.com/fsharp/fslang-design/blob/main/FSharp-6.0/FS-1087-resumable-code.md

注意

  • 私の理解（この文書）が間違っている可能性がある．
  • カテゴリはIdeaです．この文書のクオリティは低いです．読み飛ばして，ところどころ想像が入っているかもしれません．

こまごまとしたことは原文参照です．
（これから，大事なところだけ書いていきます．）

RFCのサマリ

静的に生成されたResumable code（State machine object）のための低レベルで一般的な能力をF#コンパイラに追加する．これによって，taskやtaskSeqを含むいくつかのF#のコンピュテーション式がより効率の良い形で実装されるようになる．F#コンパイラに最初に実装されたシーケンス式の実装に似ている．

モチベーション

F#はとても一般化されたコンピュテーションを扱うためのメカニズムであるコンピュテーション式を持つ．（例: seq { ... }, task { ... }, async { ... }, asyncSeq { ... }, option { ... }, etc）

task { ... } のようなコンピュテーション式は，少ないアロケーションで実行されることが要求される．（他にも，シーケンス式と非同期シーケンス式など）既存のTaskBuilder.fsや，Plyといったものはアロケーションのオーバーヘッドが存在する．
F#のコンピュテーション式の，様々なコンピュテーションを表現できるという良さを残しつつ，ハイパフォーマンスなコードを生成する術を手に入れたい．

設計の方針

  • 新しいシンタックスは言語仕様に追加しない．
  • 静的に合成可能なResumable codeのみに焦点を当てる．Resumable codeのすべては一つのResumable state machineに結合される．
  • F#のメタデータは変わらないようにする．（nameof，あるいはほかの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>) デリゲートの実装．

Resumable codeをきっちり定義する理由は，MoveNextメソッドを実装するためである．

Resumable codeのコンビネータ

ほとんどのResumable codeの関数はResumableCode.*であり，Resumable codeとなる関数はすべてインライン化される．例：

let inline printThenYield () =
    ResumableCode.Combine(
        ResumableCode.Delay(fun () -> printfn "hello"; ResumableCode.Zero()),
        ResumableCode.Yield()
    )

ResumableCode.Yield

再開地点は``ResumableCode.Yield`の呼び出しで作られる：

ResumableCode.Yield()

すなわち，低レベルなResumable codeの中では：

let __stack_yield_complete = ResumableCode.Yield().Invoke(&sm)

この__stack_yield_completeは（一時停止すればfalse，再開すればtrueを返す．
ResumableCode.Yieldは次の定義を持つ．

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))

ResumableCode.Combine

Resumable codeの連続実行を示す．

ResumableCode.Combine(<resumable-code>, <resumable-code>)

再開可能なコードを持つことから，<resumable-code>は0か1つ以上の再開可能地点を持つ．これは，最初の<resumable-code>が次の<resumable-code>よりも実行されることが保証されないことを意味する．

ResumableCode.TryWith

try/with セマンティクス

ResumableCode.TryWith(<resumable-code>, <resumable-code>)

ResumableCode.TryFinally, ResumableCode.TryFinallyAsync

try/finally セマンティクス

ResumableCode.TryFinally(<resumable-code>, <compensation>)
ResumableCode.TryFinallyAsync(<resumable-code>, <resumable-code>)

これらコンビネータは.NET ILのtry/finallyブロックを用いず，try/withを用いる．

ResumableCode.While

反復のセマンティクス

ResumableCode.While((fun () -> expr), <resumable-code>)

再開可能なコードを持つことから，<resumable-code>は0か1つ以上の再開可能地点を持つ．
しかし，ガードは再開可能ではない．非同期なwhileループ，非同期なwhileの条件が非同期であるループは，ガードのためのResumable codeを別な場所に配置する．

低レベルなResumable codeとは

低レベルなResumable codeはResumableCode，__stateMachine，MoveNextMethodImplというデリゲートの実装を持つ．ResumableCodeの戻り値は完了(true)またはyielded(false)を示す．

ResumableCode<_,_>(fun sm -> <optional-resumable-expr>) 
MoveNextMethodImpl(fun sm -> <resumable-expr>)

例えば，

ResumableCode<_,_>(fun sm -> printfn "hello"; true)

<optional-resumable-expr>は：

if __useResumableCode then <resumable-expr> else <expr>

または

<resumable-expr>

である．もし，Resumable codeがコンパイル可能である状態機械は<resumable-expr>が用いられ，そうでない場合は<expr>が用いられる．

<resumable-expr>

<resumable-expr>は：

__resumableEntryで作る再開可能ポイント

match __resumableEntry() with
| Some contId -> <resumable-expr>
| None -> <resumable-expr>

式が実行されると，最初のSomeの分岐が実行される．__resumeAtを用いて再開が実行されると，None分岐が実行される．

Some分岐は普通は，__resumeAtの実行をメソッドの実行時に行うと，のちの利用のためのcontIDを状態機械に保存することで一時停止する．
例として：

let inline returnFrom (task: Task<'T>) =
    let mutable awaiter = task.GetAwaiter()
    match __resumableEntry() with 
    | Some contID ->
        sm.ResumptionPoint <- contID
        sm.MethodBuilder.AwaitUnsafeOnCompleted(&awaiter, &sm)
        false
    | None ->
        sm.Result <- awaiter.GetResult()
        true

注意：再開可能な式は結果を返すことができる．上の例では，taskが終了したかどうかを返している．

__resumeAt式

__resumeAt <expr>

実行時，__resumeAt contIdはNone分岐（対応するmatch式の）に直接ジャンプする．
スコープにあるすべての__stack_*のローカル変数は再開時にゼロ初期化される．

スタックに保存され，再開時にゼロ初期化されるlet式

let __stack_var = ... in <resumable-expr>

Resumable codeの中では，__stack_*という名前はスタックに保存され，再開時に初期値になる．

再開可能なtry/finally式

try <resumable-expr> finally <expr>

F#での注意：.NET ILはtry/withのコードブロックへの直接のジャンプは禁止されている．そのため，F#ではジャンプは再配置される．

再開可能なwhileループ

while <expr> do <resumable-expr>

ガードは再開可能な式ではない．

Resumable codeの並び

<resumable-stmt>; <resumable-stmt>

ResumableCodeデリゲートの呼び出し

e.g.

code arg
code.Invoke(&sm)
(code arg).Invoke(&sm)

再開可能なmatch式

match <expr> with
| ...  -> <resumable-expr>
| ...  -> <resumable-expr>

そのほかのF#式

<expr>

Resumable codeを持つ再開可能な状態機械の構造体

再開可能な状態機械は__stateMachineによって区別される．Resumable codeはコンパイラによって生成されるResumableStateMachineを基にした構造体にホストされる．

__stateMachine<_, _>
    (MoveNextMethod(fun sm -> <resumable-code>))
    (SetMachineStateMethod(fun sm state -> ...))
    (AfterMethod(fun sm -> ...))

コンパイル時，__stateMachineはResumableStateMachineにしたがって，F#コンパイラによってクロージャにキャプチャされたフィールドが追加された新しい構造体が生成される．MoveNextMethod，SetMachineStateMethod，AfterMethodはこの構造体に書き換えされる．'関数'はIAsymcStateMachineインターフェースを実装するのにつかわれる．AfterMethodメソッドは実行され，ヒープ利用を削減するための状態機械の削除に使われる．それの返す型はResumableStateMachineには含まれない．

[<Struct; NoComparison; NoEquality>]
type ResumableStateMachine<'Data> =
    val mutable Data: 'Data
    val mutable ResumptionPoint: int
    val mutable ResumptionDynamicInfo: ResumptionDynamicInfo<'Data>
    interface IResumableStateMachine<'Data>
    interface IAsyncStateMachine

注意：

  1. 3つのデリゲートの引数はMoveNext，SetMachineStateメソッドの実装を特定する．また，Afterコードブロックは状態機械の上で生成後すぐに実行される．デリゲートは状態機械のアドレスを受け取ることができる．
  2. 生成するたびに，ResumableStateMachine構造体は新しい構造体にコピーされる．つまり，Resumableなコンピュテーション式を使うたびに構造体が定義されるということ？
  3. MoveNextメソッドはResumable codeである可能性がある．

状態機械のコンパイル可能性

ステートマシンがコンパイル可能でないとは，次の条件のいずれかを満たすことを言う．

  1. Resumable codeが__resumableEntryの場所をボディとする整数によるforループにならない．
  2. Resumable codeがlet recになる．
  3. Resumable codeがunreducedなResumableCodeのパラメータを利用している．
  4. Resumable codeが__resumableEntryの地点でtry/finallyが用いられている．
  5. Resumable codeがtry/withでwithブロックに__resumableEntryがある．

状態機械の実行

状態機械の実行では，いくつかの項は直接.NETの処理に変換される．たとえば，__resumeAtからgotoなど．
もしResumableCode式が正しいResumable codeである場合，次のように変換される．
　1. すべての実装は__useResumableCodeがtrueの時，インライン化される．
　2. すべての再開地点match __resumableEntry() with Some contId -> <stmt1> | None -> <stmt2>はユニークな整数contIDのための静的な構造に変換される．<stmt1>は最初に実行される．<stmt2>はcontIDに対応するジャンプが起きたときに実行される．（ジャンプテーブルのターゲットとなる．）
　3. すべての__stack_*はメソッドのローカル変数に変換され，ゼロ初期化される．
　4. すべての__stack_*でない変数はオブジェクトのメンバ変数となる．
　5. __resumeAt <expr>はジャンプテーブルを呼ぶ．もし，静的に<expr>が決まるならば，効率の良いgoto文に置き換わる． そうでない場合，関数の最初に戻る．<expr>が実行時に正しい再開地点を指定できない場合，__resumeAtの後の文を実行する．

正式リリース後：task{...}の実装を見てみよう

task{...}の実装を見てみよう．まずはC#の結果を参考にしてみる．

簡単な例

コンパイルしてみる

C#にて，

public static async ValueTask<int> Fuga() {
    await Task.Delay(1000);
    return 0;
}

このプログラムをコンパイルしてILSpyでC#4.0として見てみた．（少し整形した）

private sealed class <Fuga>d__0 : IAsyncStateMachine {
  public int <>1__state;
  public AsyncTaskMethodBuilder<int> <>t__builder;
  private TaskAwaiter <>u__1;
  private void MoveNext()　{
    int num = <>1__state;
    int result;
    TaskAwaiter awaiter;
    if (num != 0)　{
      awaiter = Task.Delay(1000).GetAwaiter();
      if (!awaiter.IsCompleted)　{
        num = (<>1__state = 0);
        <>u__1 = awaiter;
        <Fuga>d__0 stateMachine = this;
        <>t__builder.AwaitUnsafeOnCompleted(ref awaiter, ref stateMachine);
        return;
      }
    }　else　{
      awaiter = <>u__1;
      <>u__1 = default(TaskAwaiter);
      num = (<>1__state = -1);
    }
    awaiter.GetResult();
    result = 0;
    <>1__state = -2;
    <>t__builder.SetResult(result);
  }

  void IAsyncStateMachine.MoveNext() => this.MoveNext();
  void IAsyncStateMachine.SetStateMachine(IAsyncStateMachine stateMachine) =>
    this.SetStateMachine(stateMachine);
}
public static Task<int> Fuga() {
  <Fuga>d__0 stateMachine = new <Fuga>d__0();
  stateMachine.<>t__builder = AsyncTaskMethodBuilder<int>.Create();
  stateMachine.<>1__state = -1;
  stateMachine.<>t__builder.Start(ref stateMachine);
  return stateMachine.<>t__builder.Task;
}

今度はF#のコードである．

let fuga () =
  task {
    do! Task.Delay(1000)
    return 0
  }

↓

[SpecialName]
[StructLayout(LayoutKind.Auto, CharSet = CharSet.Auto)]
internal struct fuga@17 : IAsyncStateMachine, IResumableStateMachine<TaskStateMachineData<int>>
{
  public TaskStateMachineData<int> Data;
  public int ResumptionPoint;
  public TaskAwaiter awaiter;
  public override void MoveNext()  {
    int resumptionPoint = ResumptionPoint;
    switch (resumptionPoint){}
    bool flag;
    int num;
    bool flag2;
    switch (resumptionPoint) {
    default: {
      Task task = Task.Delay(1000);
      awaiter = task.GetAwaiter();
      flag = true;
      if (awaiter.IsCompleted)
        break;
      if (false)
        goto case 1;
      ResumptionPoint = 1;
      num = 0;
      goto IL_0064;
    }
    case 1:
      num = 1;
      goto IL_0064;
      IL_0064:
      flag2 = (byte)num != 0;
      flag = flag2;
      break;
    }
    int num2;
    if (flag) {
      awaiter.GetResult();
      @null @null = null;
      @null null2 = null;
      int result = 0;
      Data.Result = result;
      num2 = 1;
    } else {
      Data.MethodBuilder.AwaitUnsafeOnCompleted(ref awaiter, ref this);
      num2 = 0;
    }
    int num3;
    if (num2 != 0) {
      TaskAwaiter taskAwaiter = default(TaskAwaiter);
      awaiter = taskAwaiter;
      num3 = 1;
    } else
      num3 = 0;
    if (num3 != 0)
      Data.MethodBuilder.SetResult(Data.Result);
  }

  void IAsyncStateMachine.MoveNext() => this.MoveNext();
  public override void SetStateMachine(IAsyncStateMachine state) =>
    Data.MethodBuilder.SetStateMachine(state);
  void IAsyncStateMachine.SetStateMachine(IAsyncStateMachine state) => this.SetStateMachine(state);
  public override int get_ResumptionPoint() => ResumptionPoint;
  int IResumableStateMachine<TaskStateMachineData<int>>.get_ResumptionPoint() =>
    this.get_ResumptionPoint();

  public override TaskStateMachineData<int> get_Data() => Data;
  TaskStateMachineData<int> IResumableStateMachine<TaskStateMachineData<int>>.get_Data() =>
    this.get_Data();

  public override void set_Data(TaskStateMachineData<int> value) => Data = value;

  void IResumableStateMachine<TaskStateMachineData<int>>.set_Data(TaskStateMachineData<int> value) => this.set_Data(value);
}

public static Task<int> fuga() {
  fuga@17 stateMachine = default(fuga@17);
  stateMachine.Data.MethodBuilder = AsyncTaskMethodBuilder<int>.Create();
  stateMachine.Data.MethodBuilder.Start(ref stateMachine);
  return stateMachine.Data.MethodBuilder.Task;
}

Microsoft.FSharp.Control.TaskStateMachineData<T>とは次のように定義されている．

[<Struct; NoComparison; NoEquality>]
type TaskStateMachineData<'T> =
    [<DefaultValue(false)>]
    val mutable Result: 'T
    [<DefaultValue(false)>]
    val mutable MethodBuilder: AsyncTaskMethodBuilder<'T>
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>

つまり，AsyncTaskMethodBuilderと結果の一時保存場所である．

TaskBuilder.Runを見てみる

まずはRunメソッドである．

member inline _.Run(code: TaskCode<'T, 'T>) : Task<'T> =
  if __useResumableCode then
    __stateMachine<TaskStateMachineData<'T>, Task<'T>>
    (MoveNextMethodImpl<_>(fun sm ->
      //-- RESUMABLE CODE START
      __resumeAt sm.ResumptionPoint
      let __stack_code_fin = code.Invoke(&sm)
      if __stack_code_fin then
        sm.Data.MethodBuilder.SetResult(sm.Data.Result)
              //-- RESUMABLE CODE END
     ))
     (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)

もし，Resumable codeが利用できるならば，__useResumableCodeがtrueとなり，__stateMachineが処理される．
まず，AfterCodeは，関数fugaに出力されていたコードがそのまま記述されている．
そして，本丸となるMoveNextMethodImplである．最初の__resumeAtで処理を再開している．これは，出力されたコードの最初にあるswitch文がそれにあたると考えられる．そして，code.Invoke(&sm)を実行している．これはコード本文の実行を意味する．そのコード本文の実行が終われば，AsyncTaskMethodBuilder.SetResultを呼び出して，Resultに格納された結果を返している．

ちなみに，DynamicRunは，

static member RunDynamic(code: TaskCode<'T, 'T>) : Task<'T> =
  let mutable sm = TaskStateMachine<'T>()
  let initialResumptionFunc = TaskResumptionFunc<'T>(fun sm -> code.Invoke(&sm))
  let resumptionInfo =
    { new TaskResumptionDynamicInfo<'T>(initialResumptionFunc) with
        member info.MoveNext(sm) =
          let mutable savedExn = null

          sm.ResumptionDynamicInfo.ResumptionData <- null
          let step = info.ResumptionFunc.Invoke(&sm)

          if step then
            sm.Data.MethodBuilder.SetResult(sm.Data.Result)
          else
            let mutable awaiter = sm.ResumptionDynamicInfo.ResumptionData :?> ICriticalNotifyCompletion
            sm.Data.MethodBuilder.AwaitUnsafeOnCompleted(&awaiter, &sm)
        member _.SetStateMachine(sm, state) =
          sm.Data.MethodBuilder.SetStateMachine(state)
      }
  sm.ResumptionDynamicInfo <- resumptionInfo
  sm.Data.MethodBuilder <- AsyncTaskMethodBuilder<'T>.Create ()
  sm.Data.MethodBuilder.Start(&sm)
  sm.Data.MethodBuilder.Task

となる．ここで，ResumptionDynamicInfo<'T>が役に立つ．初期の再開後メソッドはコード本文として，ResumptionDynamicInfoを作成している．MoveNextが呼び出されると，ResumptionDynamicInfo.ResumptionDataを呼び出す．stepがtrue，つまり，完了したならばAsyncTaskMethodBuilder.SetResultを呼び出して結果を返す．falseならば，ResumptionDynamicInfo.ResumptionDataを完了後に実行されるICriticalNotifyCompletionとして指定している．このメンバはobjと型付けされている．（！）

Doを見てみる

member inline _.Combine
  (
    task1: TaskCode<'TOverall, unit>,
    task2: TaskCode<'TOverall, 'T>
  ) : TaskCode<'TOverall, 'T> =
  ResumableCode.Combine(task1, task2)

こんなことになっているので，ResumableCode.Combineを見てみる．
ResumableCodeは，

let __stack_fin = code1.Invoke(&sm)
if __stack_fin then
  code2.Invoke(&sm)
else
  false

かえってシンプルである．一方，CombineDynamicは，

if code1.Invoke(&sm) then
  code2.Invoke(&sm)
else
  let rec resume (mf: ResumptionFunc<'Data>) = ResumptionFunc<'Data>(fun sm ->
    if mf.Invoke(&sm) then
      code2.Invoke(&sm)
    else
      sm.ResumptionDynamicInfo.ResumptionFunc <- (resume (GetResumptionFunc &sm))
      false)
  sm.ResumptionDynamicInfo.ResumptionFunc <- (resume (GetResumptionFunc &sm))
  false

code1が素直に終わる（Task.IsCompletedがすぐにtrueになる）ならば，code2を実行している．一方で終わらなかった場合，再開後のメソッドをresumeを代入している．再開後のコードを実行してみて，終了すればcode2を実行し，そうでなければ，同じようにresumeを実行する．そのままGetResumptionFunc &smを代入しないのは，そのまま終了すると，code2が実行されずに結果を返してしまうためである．

Returnを見てみる

Returnは非常に簡単である．

member inline _.Return(value: 'T) : TaskCode<'T, 'T> =
  TaskCode<'T, _>(fun sm ->
    sm.Data.Result <- value
    true)

Data.Resultに値を代入してtrueを返す．そうすれば，AfterCodeでSetResultを読んでくれるので，結果を返すことができる．

Bindを見てみる．

let inline _. Bind (task : ^TaskLike, continuation: ('TResult1 -> TaskCode<'TOverall, 'TResult2>))
TaskCode<'TOverall, _>(fun sm ->
  if __useResumableCode then
    //-- RESUMABLE CODE START
    // Get an awaiter from the awaitable
    let mutable awaiter = (^TaskLike: (member GetAwaiter: unit -> ^Awaiter) (task))
    let mutable __stack_fin = true

    if not (^Awaiter: (member get_IsCompleted: unit -> bool) (awaiter)) 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
	let result = (^Awaiter: (member GetResult: unit -> 'TResult1) (awaiter))
	(continuation result).Invoke(&sm)
    else
	sm.Data.MethodBuilder.AwaitUnsafeOnCompleted(&awaiter, &sm)
	false
  else
    TaskBuilderBase.BindDynamic< ^TaskLike, 'TResult1, 'TResult2, ^Awaiter, 'TOverall>(
	&sm,
	task,
	continuation
    )
  //-- RESUMABLE CODE END
)

もし，Task.IsCompletedがすぐにtrueにならなかったら（終わらなかったら），ResumableCode.Yield()を用いている．
一方で，すぐに終わった場合は，Task.Awaiter.GetResult()で値を取得し，継続を呼び出している．

詳しく，ResumableCode.Yieldを見てみよう．

//-- RESUMABLE CODE START
match __resumableEntry () with
| Some contID ->
  sm.ResumptionPoint <- contID
  //if verbose then printfn $"[{sm.Id}] Yield: returning false to indicate yield, contID = {contID}"
  false
| None ->
  //if verbose then printfn $"[{sm.Id}] Yield: returning true to indicate post-yield"
  true

ここでは，再開点を挿入している．
つまり，1回目通る時はResumableCode.Yield.Invoke(&sm)は，falseを返す．__stack_finはfalseになるので，AwaitUnsafeOnCompletedが呼ばれる．awaiterの実行が終了すれば，MoveNextが再度呼ばれ，Runの最初の__resumeAtが呼ばれる．すると，None分岐にジャンプし，trueをResumableCode.Yield.Invoke(&sm)が返すこととなる．__stack_finはtrueになるので，GetResultなどが呼ばれることとなる．

BindDynamicは次のとおりである．

let mutable awaiter = (^TaskLike: (member GetAwaiter: unit -> ^Awaiter) (task))
let cont =
  (TaskResumptionFunc<'TOverall>(fun sm ->
    let result = (^Awaiter: (member GetResult: unit -> 'TResult1) (awaiter))
    (continuation result).Invoke(&sm)))

// shortcut to continue immediately
if (^Awaiter: (member get_IsCompleted: unit -> bool) (awaiter)) then
  cont.Invoke(&sm)
else
  sm.ResumptionDynamicInfo.ResumptionData <- (awaiter :> ICriticalNotifyCompletion)
  sm.ResumptionDynamicInfo.ResumptionFunc <- cont
  false

すぐに終了したならば，contが実行される．その一方で，終わらなかった場合，ResumptionDataにawaiter，ResumptionFuncにcontが代入される．
RunDynamicに戻ると，このawaiterがAwaitUnsafeOnCompletedに渡され，contが次回呼び出される．

正式リリース前：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!{ ... }の実装はここにある．

状態機械

https://github.com/dotnet/fsharp/blob/086b3c6a3e35be0f6b3449f0eb5f17306fb1c674/src/fsharp/FSharp.Core/tasks.fs#L29

[<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ほにゃららを使っている．
こいつらは，次のとおりである．
https://github.com/dotnet/fsharp/blob/086b3c6a3e35be0f6b3449f0eb5f17306fb1c674/src/fsharp/FSharp.Core/resumable.fs#L34

/// 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していそうである．）

結び

非常に簡単にアロケーションの少ないコード生成ができるなぁという印象でした．
驚くべきことが，C#/VBのステートマシンはclassなのに対し，F#はstructで生成されています．どうせボックス化されるので，微妙な気もしますが，F#の仕組みは汎用ということで，ハイパフォーマンスなコンピュテーション式を作ることができるようにということなのでしょう．

Discussion