.NET 5.0 が発表されて F# 5.0 の機運も高まってきた今日この頃ですが，型クラスの orphan instances が作れるようになるやつとか，applicative functors 用のシンタックスとか，ジェネリック等価判定・比較の高速化とか，どれも便利で面白そうだけど最近あんまり動きが見られないなあ，と思いながら Candidate for F# vNext を眺めていたところ，そんなアンニュ〜イな気分を根底から吹き飛ばすヤバい機能が実装されつつあることが先日判明し，わたしは今，冷静さを欠いています．
その機能とは，これです．
[WIP, RFC FS-1072] task and state machine support by dsyme
This inserts a heavily modified (but semantically almost completely compatible) version of TaskBuilder.fs into FSharp.Core and adds a general state machine compilation mechanism for F# computation expressions.
(注: 強調はわたしによる)
私訳: この PR は TaskBuilder.fs1 に大きな変更を加えた（ただし，記法の面ではほぼ完璧な互換性がある）ものを FSharp.Core2 に追加し，さらに computation expressions をステートマシンとしてコンパイルするための汎用的な機構を実装するものである．
これは，大変なことです．何が大変なのか？これによって具体的に何ができるようになって，それがどのくらい凄いことで，そして一体どのような意味を持つのか？書きます3．
1 前提知識・背景の整理
1.1 Computation Expressions とは
まず computation expressions とはどのような機能なのか？
むかしちょろっと解説したような気もするし，多分ググれば詳しくわかるので，簡単なおさらいに留める．
Computation expressions とは，
- 特殊な文脈を持った計算 を書くための
- DSL を
- ライブラリとして提供する
ための仕組みである．
特殊な文脈を持った計算というのは例えば，
- 非同期計算 (async/await, Future, Promise, Goroutine など)
- コルーチン (ジェネレータ，イテレータなど）
- エラーハンドリング (null，例外，Either，Result，Maybe，Optionなど）
などが該当する．それを書くための DSL とは，（普段意識することは少ないかも知れないが）それらの機能のために用意された専用の糖衣構文のことである．例えば，C# の
public static IEnumerable<int> Numbers(int i)
{
while(true)
{
yield return i;
i++;
}
}
というのはイテレータを作るための糖衣構文であって，普通のメソッドとは全く違う機構を使ってコンパイルされる．同様に，
public static async Task<string> DownloadTextAsync(string url)
{
var httpClient = new HttpClient();
var text = await httpClient.GetStringAsync(url);
return text;
}
というのは非同期コードを生成するための DSL で，これもコンパイル時に非同期メソッド専用のコード変形が行われる．
そして DSL をライブラリとして提供するというのは，これらの専用構文をコンパイラが直接サポートするのではなく，プログラマが F# コード中で自由に構文を定義して使用・配布することができる，ということだ．上と同様のコードを F# で書けば以下のようになる：
let rec numbers i : seq<int> =
seq {
yield i
yield! nums (i+1)
}
let downloadTextAsync (url: string) : Async<string> =
async {
let client = new HttpClient()
let! text =
client.GetStringAsync url |> Async.AwaitTask
return text
}
ここで seq { .. } や async { .. } といった糖衣構文はコンパイラ組み込みのものではなく，computation-expression builders (以下 builder(s)) と呼ばれる特定の形をしたオブジェクトを定義することで，誰でも自作の構文を使えるようになっている．例えば async builder は概ね次のように定義されている：
// https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/control.fs より抜粋・改変
type AsyncBuilder() =
// let! x = computation in body
// ( binder := fun x -> body )
member b.Bind(computation: Async<'a>, binder: 'a -> Async<'b>) : Async<'b> =
AsyncBuilderImpl.bindA computation binder
// return value
member b.Return(value: 'a) : Async<'a> =
AsyncBuilderImpl.resultA(value)
let async = AsyncBuilder() // builder インスタンスの作成
b.Bind(computation, binder) というメソッドは let! x = fooAsync()4 という構文糖に，b.Return(value) というメソッドは return x という構文糖にそれぞれ対応する．
1.2 Async<'T> vs Task<'T> - 歴史的事情
ところで，C# と F# は同じ .NET Framework で動く言語である．しかし先程のコードを見ていて気づいたかも知れないが，両者は非同期計算を表現するためにそれぞれ異なる型を使っている．
C# は Task<'T> を使う：
public static async Task<string> DownloadTextAsync(string url)
{
var httpClient = new HttpClient();
var text = await httpClient.GetStringAsync(url);
return text;
}
一方 F# は Async<'T> を使う：
let downloadTextAsync (url: string) : Async<string> =
async {
let client = new HttpClient()
let! text =
client.GetStringAsync url |> Async.AwaitTask
return text
}
そして Async.AwaitTask は C# の Task<'T> を F# の Async<'T> に変換するための関数である．
違うのは名前だけではなく：
-
Task<'T>は非同期メソッドが呼ばれた時点で処理が開始される5が，Async<'T>メソッドが返すのはまだ実行されてない処理を表すオブジェクトで，明示的に開始するまで実行されない． -
Async<'T>のほうが設計に一貫性があって composability に優れ，F# idiomatic である．Async<'T>は「非同期計算の結果を受け取るためのオブジェクト」ではなく「非同期実行される計算自体を表すオブジェクト」である．これにより計算同士を合成したり，ある計算が終わるのを待ってから別の計算を始めるなどの処理を簡単に書くことができ，明示的な開始によって実行方法を安全に制御することができる． -
Task<'T>のほうがはるかに高速である．Async<'T>よりも低レベルの言語機能を使って実装されているため，余計なアロケーションなどが抑えられている．Async.AwaitTaskによるTask<'T>からAsync<'T>への変換はそれだけでオーバーヘッドを生んでしまう． - そして一番重要なのが，
Task<'T>用の builder は F# の標準ライブラリには存在していない．自前で実装しようとしても，低レベルの最適化が必要なため，C# と同じパフォーマンスを出すことができない．なお上で Don の言及している TaskBuilder.fs とは，まさにTask<'T>用の builder を提供するサードパーティーライブラリである．
もう分かるであろうが，F# は async { .. } 構文だけでは現状不十分で，C# の async/await と同じ挙動・パフォーマンスで， C# 製の非同期ライブラリの性能を最大限に活かせる task { .. } 構文が必要なのだ6．
しかしそれを実現するためには F# コード内で builder として実装することが不可能な様々な低レベルの最適化が必要なため，今まで標準ライブラリには取り込まれてこなかったのだ．
Don はそれを今やろうと言っている（そしてやっている）のだ．しかしそれだけでは，まだそんなにすごい話でもない．なぜか？
単に特定の構文に対して最適化を施すだけのことなら，既に一度やったことがあるからだ．
2 Computation Expressions の最適化手法
2.1 既存の事例 - seq<'T>
ここでみなさんにひとつ謝らなければならないことがあって，私は 1.1 節でひとつ都合の良い嘘をついた．
みなさんは，seq { .. } と同じものを自力で実装し直すことはできない．
なぜか？それは，F# コンパイラは内部で seq { .. } 式をステートマシンへ変換するからだ．つまり，実際 seq { .. } はコンパイラ組み込みの構文なのだ．
例えば，先ほどの例の
let rec numbers i : seq<int> =
seq {
yield i
yield! nums (i+1)
}
は概ね次のようにコンパイルされる7：
type internal numbersClass(i, pc, current) =
let mutable i = i // 元の関数内の変数 i
let mutable pc = pc // プログラム・カウンタ
let mutable current = current // イテレータの現在の値
// 別のイテレータに処理を移すかどうか
let mutable redirect = false
// 次に実行するイテレータ
let mutable redirectTo : numbersClass = Unchecked.defaultof<_> x
// イテレータの実行を1ステップ進めて,
// 実行する処理が残っているかどうかを返す.
member __.MoveNext() : bool =
// 次に実行するイテレータがあるならそちらを実行
if redirect then redirectTo.MoveNext()
else
// プログラム・カウンタの値を元に実行する処理を決める．
// 便宜上パターンマッチで表現しているが，実際は goto 命令を用いて直接ジャンプする．
match pc with
| 1 -> // 再帰呼び出しを yield! しているとき
pc <- 2
// i を 1 増やして新しいイテレータを作り，そちらに処理を移す
redirectTo <- new numbersClass(i + 1, 0, 0)
redirect <- true
redirectTo.MoveNext()
| 2 -> // それ以外のとき（永遠に来ない）
current <- 0
false
| _ (* 0 *) -> // 値を yield しているとき
pc <- 1
current <- i
true
// イテレータの現在の値.
member __.Current = if redirect then redirectTo.Current else current
let numbers i = new numbersClass(i, 0, 0)
seq { .. } 構文から生成されるステートマシンは，プログラム・カウンタを用いてステートマシンの状態を表し，破壊的再代入で状態を上書きし，ジャンプテーブルを引いて特定のラベルに goto することで処理を再開するなどの，かなり低レイヤの言語機能を用いている．しかし，命令的なプログラミング言語ではよく使われるこれらの機能は，F# の宣言的なプログラミングスタイルと相性が悪い．では，なぜコンパイラ側で特別なサポートをしてまで，"F# らしくない" 構造のステートマシンを生成する必要があるのか？
2.2 なぜステートマシンを，なぜコンパイラ側で？
特殊な文脈の付いた計算を OCaml や Haskell や F# のような言語で自然に実装しようとするときは，大抵の場合「文脈を表現するデータ型」を作り，また「文脈特有のアクション8の後に実行する処理」を関数オブジェクトとして表し，それを複数個合成することでひとつの計算をつくる9．そしてアクションの結果に応じて，次の処理をどのように実行するか決める．
例えば，seq を素直に実装すると次のようになるだろう:
type 'a myseq =
| Cons of 'a * 'a myseq
| Delay of (unit -> 'a myseq)
| Nil
let rec numbers i =
Cons (i,
Delay (fun () ->
numbers (i+1)
))
これを computation expression にすることで，「アクション後の処理」を「アクション結果の変数束縛 (ex. do-notation)」もしくは「複文 (ex. イテレータ)」として書けるようになる．
type MySeqBuilder() =
member __.Yield x = Cons (x, Nil) // yield
member __.YieldFrom xs = xs // yield!
member __.Delay thunk = Delay thunk // 計算の遅延
member __.Combine (xs, ys) = // 複文の連結
let rec combine xs ys =
match xs with
| Nil -> ys
| Delay f -> Delay (fun () -> f() |> combine <| ys)
| Cons (a, xs') -> Cons (a, combine xs' ys)
combine xs ys
let myseq = MySeqBuilder() // builder インスタンスの作成
let rec numbers2 i =
myseq {
yield i
yield! numbers2 (i+1)
}
この方法では，様々なパフォーマンス上の問題が発生する．
まず，アクションが発生するたびにその後の処理を関数オブジェクトにしなければならず，そのアロケーションコストがパフォーマンスを悪化させる．これは 'a option などのフラットな構造をしている文脈の場合，インライン展開などを駆使してある程度は軽減することができる．
しかしさらに問題になるのは，seq のように処理の実行順序(の制御)自体が文脈に含まれている場合，文脈を表すデータ型自体に「次の処理」を格納しなければならないことだ．この場合インライン展開は望み薄になる上，新たなパフォーマンス悪化の要因が発生する．
処理の順番を考慮すると，再帰的なデータ構造の外側には先に行われる処理，内側には後に行われる処理を格納することになるが，これは「アクションの結果を使う処理」や「最後のアクションの次」を新しく追加しようとするたびに．データ構造の一番内側まで辿らなければならないことを意味する．seq の例で言えば，2つのイテレータを連結する処理は上にもあるように
let rec combine xs ys =
match xs with
| Nil -> ys
| Delay f -> Delay (fun () -> combine (f()) ys)
| Cons (a, xs') -> Cons (a, combine xs' ys)
のようになる．イテレータを合成すればするほど Delay 内部の関数に combine の呼び出しが追加されていき，関数オブジェクトのアロケーションと列挙時に発生する関数呼び出しの数が更に増える10．
These tend to allocate continuations and other values like crazy.
- dsyme
そして，このような関数やデータ型を使った定義から goto やジャンプテーブルを用いた実装に変換するのが相当難しい，もしくはほぼ不可能であることは想像に難くない．それゆえ，コンパイラ側でのステートマシン生成のサポートがどうしても必要なのだ．
しかしそれでは，特殊な文脈を持つ計算を扱う言語機能を新しく追加するたびに，コンパイラに手を入れて専用のステートマシン生成機能を実装するか，さもなければパフォーマンスの最適化を諦めなければならない．
Don は，この状況を変えようとしている．
2.3 Don のやろうとしていること
computation expressions をステートマシンとしてコンパイルするための汎用的な機構を実装する
冒頭のこの一文の持つ意味がもうお分かりであろう．これからは新しい monadic な言語機能を実装するときに，汎用的な機構を使ってステートマシンへの変換を定義すれば，コンパイラがよしなにやってくれて，実行時のパフォーマンスが最適化される．そして，ユーザ側からは普通の computation expression と同じように使えるのだ．
しかも，それだけでは終わらない．Don はこう続けている．
In this mechanism we allow the specification of new varieties of generated state machines in library code, normally as part of the implementation of a computation-expression builder.
(注: 強調は原文ママ)私訳: この機構においては，新しい種類のステートマシンを生成する方法を，通常は computation-expression builder の実装の一部分として，（コンパイラのソースコードではなく）ライブラリのソースコード中で定義できるようにする．
つまり，パフォーマンスが最適化された monadic な言語機能を，コンパイラを弄ることなく，パッケージとして提供できるようになるのだ．
このことは，単に F# でより効率的なプログラムを書けるようになるだけにとどまらず，F# の開発体制自体に対しても大きな影響をもたらすことになるだろう．
3 汎用ステートマシン生成機構による直接的な利益
3.1 C# の新機能のサポートが容易に
C# の言語開発のスピードは異常に速い．どれくらい異常かというと，2〜3年ごとにメジャーバージョンが1つ上がる11．
F# 開発陣は常日頃から F# に追加したい機能と C# に追従しなければならない機能の板挟みになっており，開発速度が下がる原因になっている．
しかしステートマシン生成機構を使えば，言語に新しく monadic な計算と専用構文を追加するのは，C# よりもむしろ楽になる．実際，C# 7.0 で追加された ValueTask<'T> などの task-like types や C# 8.0 で追加予定の IAsyncEnumerable<'T> はこの機構を使って実装される予定だ．
3.2 標準ライブラリの Computation Expressions の大幅な高速化
Async<'T> にこの機構を用いるのは性質上難しいが，F# に標準で用意されている computation expression は他にもあり，それらを再実装することで高速化を見込める．
前述の seq { .. } だけでなく，リスト内包表記 [ .. ] と配列内包表記 [| .. |] も実質的には computation expression のようなもので，特にリスト内包表記については，ステートマシン生成機構で実装し直すことで約 1.5 倍高速になることが既に確認されている12．
3.3 自作の computation expressions のパフォーマンス最適化が可能に
例えば Unity では，C# の IEnumerable<T> でのステートマシン生成を用いてコルーチンを実現している．しかし，遅延リストとしての機能が過剰であることが多く，また IEnumerable<T> の実装上の問題で T を値型で具体化すると boxing コストが発生する問題などがある．
そのため，F# でコルーチンとして理想的な computation expression を作るモチベーションが発生するが，今までは前述の理由で IEnumerable<T> のパフォーマンスには決して届かなかった．しかし，これからは違う．
汎用的なステートマシン生成機構によって，ユーザ側が各々のニーズに応じた computation expression を，パフォーマンスを犠牲にすることなく実装することが可能になる．
実はこれは，わたしのような言語オタクにとってかなり衝撃的なことなのだ．ここから先の節には趣味や妄想が多分に含まれるが，同士の方はぜひこのまま読み進めていただきたい．F# の新機能の紹介記事として言うべきことは全て言い尽くしたので，ここで読むのをやめてもいいです．
4 The Mother of all Monads
4.1 Filinski はかく語りき
継続というのはモナドより強い言語機能で，任意の純粋なモナドは限定継続で表現できることが， Filinski により明らかになっている．
We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations".
- Andrzej Filinski. 1994. Representing monads. In Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '94). ACM, New York, NY, USA, 446-457. DOI=http://dx.doi.org/10.1145/174675.178047
私訳: unit (訳注: return のこと) と extension (訳注: bind のこと) の操作が純粋関数型の項として表現可能な任意のモナドは，"composable continuation" (訳注: 限定継続，delimited continuation とも呼ばれる) をサポートする値呼びの言語に埋め込むことができることを示す．
Filinski は限定継続が通常の継続と状態を用いて表現可能であることも示している．ところでステートマシンというのはまさに継続そのもので，計算をあるところで区切って，残りの処理を関数として取り出す機能を提供する．F# は当然状態を扱うことができるので，ステートマシン生成機構のサポートは first-class な限定継続サポートと等価になり14，よって全ての純粋なモナドを first-class にサポートできるようになるのだ．
つまり，F# vNext はモナドを一番うまく扱える言語になるのだ．15
4.2 DSL から言語拡張へ
モナドは特殊な文脈を持つ計算を抽象化するための機構であるが16，実行コストの高い言語機能を使って機能をシミュレートする（ことでしかうまく実装できない）場合が多く、それゆえパフォーマンスをある程度は諦めざるを得なかった。そして do-notation (computation expressions を含む) は、それをあたかも組み込み構文であるかのように直観的に書けるようにするための DSL に過ぎなかった．
F# vNext はそれを変える．モナドは実行に最適化された言語機能として実装できるようになり，そこでは computation expressions は単なる DSL ではなく言語拡張になる．
上でも述べたように，例えばゲームに使うコルーチンモナドをステートマシン生成を用いて実装すれば，プログラマにとっての使いやすさと実行時の効率を両立することができる．これは言語自体にゲームスクリプティング用の拡張を実装したのと同じことになる．
また LINQ to SQL / Entity Framework 的な思想をもっと押し進めて，データベースアクセスに最適化されたコードをステートマシンを用いて実装することで，F# に効率的なデータベースアクセス専用の言語拡張を追加することもできるだろう．
そして，F# はコンパイラ自体がライブラリとして利用でき，ツールチェインはそれを利用しているため，独自に追加された computation expressions は全てコンパイラや IDE による支援を受けることができる．Computation expressions の内部で補完を効かせることもできるし，Don いわくデバッグ ("stack, breakpoints, stepping") も C# 同様に IDE を使ってできるようになるらしい．
そのとき，F# は一体 "なに用" の言語になるのだろう？
4.3 すべてが F# になる
"汎用プログラム言語" は一般に なんでもできる (TM) 言語を指すが，特殊な文脈を持つ計算専用に設計された言語に比べると，記法やパフォーマンスの面で譲ることが多い．それゆえに並列・非同期計算に特化した言語や，スクリプトとして他言語に埋め込むための言語などが開発され，生き残っている．
F# はもはや汎用プログラム言語としての枠に収まらなくなる．ステートマシン生成機構を使えば様々な目的に特化させられるからだ．しかし F# は依然として F# というひとつの言語である．コンパイラを fork することなく独自の拡張を追加でき，それを単なるライブラリとして配布できるからだ．
気合の入った computation expression ライブラリがあれば F# はすべてになることができ，やがてすべてが F# になるのだ．
もちろん，F# ユーザが増えなければ，ライブラリ作者が足らないままなのだが…………17
ところで，わたしはちょっと前から 株式会社ぺあのしすてむ様 でアルバイトとして働かせていただいております．ぺあのしすてむで一緒に F# を書きませんか？
-
サードパーティ製の computation expression builder ライブラリ ↩
-
F# の標準ライブラリ ↩
-
以下 "である調" でお送りします．いきなり語調が変わりますがびっくりしないでね ↩
-
C# で言うところの
var x = await FooAsync();↩ -
実際はまだ開始されていない
Task<'T>オブジェクトを作ることもできなくはないが，C# コンパイラは非同期メソッドを呼んだ際に自動的に処理を開始するようにコンパイルする． ↩ -
もちろん，
async { .. }は要らないとかそういう話ではない．Async<'T>のTask<'T>に対する利点は上で説明したとおり． ↩ -
記事に収まるようにかなり簡略化していて，実際とはだいぶ異なるが ↩
-
エラーハンドリングならエラーチェック，非同期処理なら別の非同期処理の結果の待機，コルーチンなら処理の中断・再開． ↩
-
要するにモナド． ↩
-
これで開発者が息も絶え絶えにならないのは，.NET が後方互換性を異常なほど気にするランタイムでもあるからで，既存の C# コードはメジャーバージョンが上がったくらいではまず死なない．仮にソースコードレベルで破壊的変更が入ったとしても，パッケージをバイナリ形式で配布する文化のお陰で，使ってるライブラリが全部即死ということにはまずならない．その上 C# は言語バージョンとランタイムバージョンが独立しており，必要な機能をランタイムがサポートする限り，新しい言語バージョンから古いランタイム用バイナリへのコンパイルや，その逆ができる（最新コンパイラでも昔の言語バージョンをサポートする）．F# も後方互換性をかなり重視する言語で，最新コンパイラでも古いランタイムへのコンパイルができるが，
さすがに最新の言語バージョンしかサポートしていない．F# 4.6以降のバージョンはサポートされるようになった． ↩ -
なお Don は mutate-tail-cons-cell trick を使ってもっと速くできると言っている ↩
-
ほんとか？ここらへん自信ないので詳しい人マサカリお願いします． ↩
-
例えば Scheme は継続を first-class でサポートしている上に強力なマクロ機能があるのでおそらく同等のことができるが，F# では monadic なプログラミングスタイルが既に文化として確立されていてコンパイラやエディタによるサポートがしっかりしており，またステートマシンとしてコンパイルされてバイトコードまで落ちてくるために恐らく実行効率が高いので，個人的には "どちらがモナドをうまく扱えるか" は F# のほうに軍配を挙げたい． ↩
-
Codensity みたいな "モナドのためのモナド" もあるんだけど，そういうのは除く． ↩
-
次回予告！「F# はなぜ流行らないのか」乞うご期待！ ↩