この記事は、「F# Advent Calendar 2016」の23日目の記事です。やっばいギリギリ。
英語版はこちら (For English post: https://www.kekyo.net/2016/12/23/6305)
前日は、ぜくるさんのTypeProviderのお話です。
今私は、「F#のコンパイラの代替え品」を作っています。とは言っても、一からF#のコンパイラを自作できるような技量はあるはずがなく、「F# Compiler Service」をバックエンドとして使っています。
F# Compiler Serviceは、C#でいう所のRoslynに相当して、F#ソースコードをパースして構文木（Abstract Syntax Tree）を取得し、さらにそれを使って実際にコンパイル（つまりMSILを生成してPEを出力する）ところまでをプログラマブルに実行できるライブラリです（他にも、fsiに相当するInteractive interpreterのエンジンも持っています）。
何故、代替えとなるコンパイラを作ろうとしているのかとか、背景についての紹介をしたいと思います。
Expandable F# Compiler project (fscx)
Expandable F# Compiler (fscx)は、GitHubで公開しています。ちなみに現在のバージョンは0.6.14、まだ正式リリースには至っていません。仕様は予告なく変更される可能性があります :)
fscxは、標準のF#コンパイラ（fsc.exe）の代わりに使用します。目的とかポイントは以下の通りです:
- コンパイル時に「ソースコードの自動変形」を可能にしたい – これは、ソースコードのテキストベースの置換（例えば正規表現などを使って）するのではなく、F# Compiler Serviceで構文木を取得した後、その構文木に直接手を入れて変形させることを目指しています。テキストベースの置換では、明らかに不正な変形を行ってしまう危険性がありますが、構文木ベースであればそのような問題は発生しません（実際には非常に難しいのですが）。
- この自動変形を行う処理を「フィルタライブラリ」と呼び、フィルタライブラリは自由に拡張出来るようにする – 例えば、当初想定しているのは、目的となるメソッドの呼び出しコードの前後に、自動的に追加コードを（構文木ベースで）挿入するフィルタライブラリです。しかし、これに限らず、様々な変形をプラガブルに実現できるようにします。
- 導入が簡単である事 – コンパイラパスの手動構成やVSIXではなく、「NuGetパッケージ」として公開し、NuGetインストールするだけでfscxを使用するようにできる事。これは、以前「NuGetでビルドプロセスに介入するパッケージを作る」で書いた通り、MSBuildのスクリプトを書くことで実現できました。
使用者から見た構造
fscxの使用者は、fscx自体を直接扱うわけではありません。目的別に作られた「フィルタライブラリ」がNuGetで導入できるようになるため、これを導入することで、依存関係によりfscxが導入されて、標準のfsc.exeを置き換えます。
この図では、「sample-filter.nupkg」というNuGetのパッケージがあり、これを自分のF#プロジェクトに導入すると、fscx（実際には”FSharp.Expandable.Compiler.Build”）も一緒に導入され、fsc.exeではなく、fscxを使ってコンパイルを行うようになります。そして、sample-filter.nupkgに含まれるフィルタライブラリを使って構文木を変形し、バイナリを生成します。
例えば、以下のようなコードを書いていたとします:
module SampleModule =
let format (a: int) (b: int) (c: string) =
System.String.Format("{0} = {1}", a + b, c)
もし、sample-filterが「関数（メソッド）の呼び出し時にログ出力を挿入する」フィルタライブラリだったとすると:
module SampleModule =
let format (a: int) (b: int) (c: string) =
// 以下のコードが自動的に挿入される
System.Diagnostics.Trace.WriteLine("Log: format {0} {1} {2}", a, b, c)
System.String.Format("{0} = {1}", a + b, c)
のような変形を「コンパイル時」に実現します。もちろん、ソースコードファイル自体に一切変更は加えません。そして、使用者はsample-filter.nupkgを導入するだけでこれが実現できるようになります。
使用者がフィルタの詳細に関与することなく、フィルタパッケージの導入だけで実現する – このようなツールセットが透過的に振る舞う必要があると言う点で、非常に重要だと考えています。
フィルタライブラリ開発者から見た構造
フィルタライブラリ側は、やや複雑です。
まず、フィルタ処理はF# Compiler Serviceの構文木を使うため、必ずF# Compiler Serviceへの参照が必要になります。また、fscxの中核となるライブラリも参照が必要です。fscxは”FSharp.Expandable.Compiler.Core”で公開されているので、自分のフィルタライブラリプロジェクトに導入しておきます。
そして、実際にフィルタコードを書けばよいのです…が…
フィルタコードの実装手段
フィルタライブラリを作る際に、2通りの方法を選択することが出来ます:
- 構文木に対して、レガシーなビジターパターンを使う – これは、.NET LINQで使われている「ExpressionVisitorクラス」と同じようなクラスを使って、いわゆるOOPベースのビジターパターンで構文木の変形を行う方法です。なぜExpressionVisitorクラスをそのまま使わないのか？と思うかもしれません。これはF# Compiler ServiceやRoslynを使ったことがある方ならわかると思いますが、構文木の構造は言語毎に大きく異なるのです。同じRoslynでも、実はC#とVisual Basicが似て異なる構文木クラス群を使うように、F#も全く異なる構文木型を使います。つまり、既存のVisitorクラスはどれも流用出来ないため、専用の基底Visitorクラスを用意しています。
- F# Compiler Serviceは、ビジターパターンを適用できる標準的なインフラを用意していません – 何故なら、関数プログラミングとパターンマッチングを使うと、わざわざ基底Visitorクラスのようなものを用意しなくても、簡単にビジターパターンを適用できるからです。とは言っても、再帰的な探索のうち、構文木のリストなどは式で書くと煩雑になりがちです。そこで、関数プログラミングスタイルで使用できる、再帰探索の実装を簡略化可能な補助ライブラリを用意しました。
例えば、基底Visitorクラスを使うと、以下のようにコードを書くことが出来ます:
type InsertLoggingVisitor() =
inherit AstInheritableVisitor()
override __.VisitExpr_Quote(context, operator, isRaw, quoteSynExpr, isFromQueryExpression, range) =
// DEBUG
printfn "%A" operator
base.VisitExpr_Quote(context, operator, isRaw, quoteSynExpr, isFromQueryExpression, range)
override this.VisitExpr_App(context, exprAtomicFlag, isInfix, funcExpr, argExpr, range) =
match funcExpr with
// ...
関数ビジターパターンのための補助ライブラリを使った場合:
let outerVisitor
(defaultVisitor: (NoContext * SynExpr -> SynExpr),
context: NoContext, // (Non custom context type)
expr: SynExpr) : SynExpr option =
match expr with
| SynExpr.Quote(operator, _, _, _, _) ->
// DEBUG
printfn "%A" operator
None // (None is default visiting)
| SynExpr.App(exprAtomicFlag, isInfix, funcExpr, argExpr, range) ->
match funcExpr with
// ...
| _ ->
None // (None is default visiting)
どちらが望ましいかは、一長一短あります。基底Visitorクラスを使う場合は、すべての構文木ノードをビジターの対象に出来ますが、ネストした構文木の解析は煩雑です。関数ビジターパターンは解析の自由度が高く、パターンマッチングを使用して容易に構文木を特定できますが、ビジターの対象はSynExprのみです。
これらの補助ライブラリは、fscx自身に直接依存しないため、「FSharp.Compiler.Service.Visitors」という独立したパッケージにしてあります。そのため、fscxを使わないとしても、このライブラリだけで、F# Compiler Serviceのビジターパターンの実装に流用することもできます。
# このライブラリは0.7.1で大体固まった感があるので、正式リリースまで大きく変わらないと思います。
構文木変形の難しさ
構文木の変形には、一種のロマンがあります（たぶん ;)
しかし、実際には「死ぬほど大変」です。この記事を読んでいる人は、おそらくF# Compiler ServiceやRoslynを日常的に触っていると思う :) ので、それがいかに大変かおわかりいただけると思います。LINQのExpressionTreeも大概ですが、あれが更に複雑になったものと思ってもらえれば良いと思います。
# なお、ExpressionTreeについては、Advent LINQの後半の記事や、Final LINQ Extensions IIIが参考になると思います。
前述のsample-filterで示したような変形を実現するには、狙った場所に対応する構文木がどのような構造で現れ、それをどのように変形すれば目的を達成できるのかを、慎重に検討しなければなりません。
構文木は再帰構造で定義されます。そのため、いい加減な判定を行うと、意図しない箇所を変形してしまう可能性があります。また、ソースコード上では些細な違いでも、構文木上ではドラスティックに変わってしまったりすることもあります。
例えば、以下のようなコードを考えます:
// 一般的な.NETのメソッド（タプル形式）
let output1 (a: int, b: string, c: double) =
System.Console.WriteLine("output1: {0}:{1}:{2}", a, b, c)
// F#関数（カリー化可能形式）
let output2 (a: int) (b: string) (c: double) =
System.Console.WriteLine("output2: {0}:{1}:{2}", a, b, c)
output1は、典型的な.NET標準のメソッドと呼べるでしょう。しかし、output2はF#らしい「関数」です。このoutput2を呼び出すコードを書いたとします:
// 一般的な.NETのメソッド呼び出し（タプル形式）
// (int * string * double) -> unit
output1 (123, "ABC", 456.789)
// F#関数の呼び出し（カリー化可能形式）
// int -> string -> double -> unit
output2 123 "ABC" 456.789
.NETメソッド形式は、以下のF#関数と区別して「タプル形式」と呼んでいます。構文木上でも、引数部分が「タプル」のように見え、一つのタプル値を引数に渡しているかのように解釈されます。F#関数は「カリー化可能形式」です。カリー化可能の場合の関数呼び出しは、部分適用された関数が連続的に適用されていくような感じに解釈されます。そして、構文木上もネストされた関数呼び出し（Appノード）で表現されます。
構文木が可視化できないと、ここら辺の検討が絶望的に大変なので、小さなツールですが構文木をF#コードっぽくダンプするツールを作りました（可視化が目的だったので、完成度は高くありません）。これを使うと、以下のような出力が得られます:
// 以下がoutput1の呼び出し
Ast.SynExpr.App( (* expr1 *) // App - output1(...)
ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
false (* isInfix *),
Ast.SynExpr.Ident( (* funcExpr *)
output1 (* Item *)),
Ast.SynExpr.Paren( (* argExpr *) // Paren --> Tuple : タプル形式の引数
Ast.SynExpr.Tuple( (* expr *)
[ (* exprs *) // タプルの中身をリストで表現
Ast.SynExpr.Const( (* [0] *)
Ast.SynConst.Int32( (* constant *)
123 (* Item *)));
Ast.SynExpr.Const( (* [1] *)
Ast.SynConst.String( (* constant *)
"ABC" (* text *)));
Ast.SynExpr.Const( (* [2] *)
Ast.SynConst.Double( (* constant *)
456.789 (* Item *)))],
[ (* commaRanges *)]),
range>.Some( (* rightParenRange *)))),
// 以下がoutput2の呼び出し
Ast.SynExpr.App( (* expr2 *) // App - 456.789の適用
ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
false (* isInfix *),
Ast.SynExpr.App( (* funcExpr *) // App - "ABC"の適用
ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
false (* isInfix *),
Ast.SynExpr.App( (* funcExpr *) // App - output2に対して123の適用
ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
false (* isInfix *),
Ast.SynExpr.Ident( (* funcExpr *)
output2 (* Item *)),
Ast.SynExpr.Const( (* argExpr *)
Ast.SynConst.Int32( (* constant *)
123 (* Item *)))),
Ast.SynExpr.Const( (* argExpr *)
Ast.SynConst.String( (* constant *)
"ABC" (* text *)))),
Ast.SynExpr.Const( (* argExpr *)
Ast.SynConst.Double( (* constant *)
456.789 (* Item *))))),
出力が冗長で見難いのですが、output1とoutput2では、引数がリストで表現されているか、ネストされた関数として表現されているかで全く構造が異なることが分かります。カリー化可能形式とは、実は以下のような呼び出しであることが分かります:
// F#関数の呼び出し（カリー化可能形式）
// int -> string -> double -> unit
output2 123 "ABC" 456.789
// 実はこういう事:
((output2 123) "ABC") 456.789
// さらに分解すると:
let f1 = output2 123 // f1は高階関数
let f2 = f1 "ABC" // f2は高階関数
f2 456.789
ソースコードの些細な違いが、構文木上で大幅に異なる表現となる場合があるため、ビジターパターンで探索する場合に注意が必要です。実際のところ非常に難しい…
# 余談ですが、構文木の解析が非常に大変だった経験から、先日のNGK2016BのLTネタ: 「You will be assimilated. Resistance is futile.」が生み出された、みたいな背景があります。Roslynなので、fscxとは全然関係ないのですが :)
フィルタのミドルウェア
このように、フィルタライブラリの独自実装自体は、構文木の扱いが非常に複雑であるため、特に想定されるシナリオのために、ミドルウェアとなる補助ライブラリ”FSharp.Expandable.Compiler.Aspect”を用意しています。
これは、「AOP（アスペクト志向パラダイム: Aspect-Oriented-Paradigm）」で知られているような、任意の処理の直前と直後に、安全に処理を挿入できる機構を持った手法と同じことを、fscx上で実現させるための補助ライブラリです。
フィルタライブラリを開発する際に、一からフィルタライブラリを実装するのではなく、この補助ライブラリを使うと、fsprojのプロパティに指定した情報と「アスペクトクラス」を指定して、構文木の操作を一切実装することなく、安全にAOPを実現できます。
例えば、以下のようなコードを用意しておきます:
// コンテキストクラス（関数を抜ける際に実行するメソッドを定義）
type SampleAspectContext internal (body: string) =
// Finish aspect (trigger are leaved method with return value)
member __.Leave(result: 'T) : 'T =
Console.WriteLine("Leave: " + body)
result
// Finish aspect (trigger are leaved method with exception)
member __.Caught(ex: exn) : unit =
Console.WriteLine("Caught: " + body + ": " + ex.ToString())
// 関数を呼び出す際に呼び出されるメソッドを定義
type SampleAspect() =
// Start aspect (trigger are entered method)
static member Enter(methodName: string, fileName: string, line: int, column: int, args: obj[]) =
let body =
String.Format
("{0}({1}, {2}): {3}({4})",
fileName,
line,
column,
methodName,
String.Join(", ", args |> Seq.map (sprintf "%A")))
Console.WriteLine("Enter: " + body)
new SampleAspectContext(body)
このアスペクトコードは、関数の入り口と出口で、自動的にコンソールにログを出力します。SampleAspect.Enterが関数の入り口で呼び出され、関数名やソースコードの位置、そして渡された引数を入手できます。この情報をもとに、ログを出力しています。
また、Enterが返すクラスのインスタンスが「アスペクトコンテキスト」として扱われ、LeaveまたはCaughtが関数の出口で呼び出されます。命名の通り、正常に抜ける場合にはLeaveが、例外で抜ける場合にはCaughtが呼び出されます。それぞれ、戻り値と例外のインスタンスが引数で指定されるので、これを元にログを出力しています。
これらのクラスや関数とその引数は、完全なダックタイピングです。特定のクラスやインターフェイスの実装は不要で認識されます。本当はインターフェイスで縛ったりしたいのですが、そうすると余計なアセンブリ参照が増え、最終的にはNuGetのパッケージングで非常に苦労することになるからです。
これで、アスペクトを「SampleAspect」として定義できたので、FSharp.Expandable.Compiler.Aspectに認識させるために、以下のコードを定義しておきます:
// SampleAspectクラスをアスペクトとして使用するフィルタを定義する
[<Sealed>]
type SampleAspectLoggerDeclaration() =
// 依存関係を増やさないために、クラス名を文字列で指定
inherit DeclareFscxInjectAspectVisitor("SampleAspectLogger.SampleAspect")
アスペクトコード自体とこの定義型の実装は、C#でも記述できるように、型の要求を緩くしてあります。
この定義がフィルタライブラリに含まれていると、fscxによって以下の操作が行われます:
- 対象の関数の入り口に、SampleAspect.Enterを呼び出すコードを、構文木の挿入で実現する。
- 対象の関数の出口に、SampleAspectContext.LeaveまたはCaughtを呼び出すコードを、構文木の挿入で実現する。Leaveは正常終了した際の戻り値を、Caughtはtry-withブロックによってキャッチした例外を伴って呼び出す。
このようなコードが:
let f11 (a: int, b: string, c: int) =
output1(a + c, b, 123.456)
fscxによってこのように変形されます:
let f11 (a: int, b: string, c: int) =
let __arg_0 = a + c
let __arg_1 = b
let __arg_2 = 123.456
let __context =
SampleAspectLogger.SampleAspect.Enter
("f11", "SampleCode.fs", 2, 3, [|__arg_0, __arg_1, __arg_2|])
try
__context.Leave(output1(__arg_0, __arg_1, __arg_2))
with
| ex ->
__context.Caught(ex)
reraise()
ここでは、タプル形式のメソッドを呼び出していますが、当然カリー化可能形式にも対応しています。
アスペクトクラス（SampleAspect, SampleAspectContext）と、アスペクトクラスを定義する型（SampleAspectLoggerDeclaration）以外に、構文木を操作するためのコードは一切不要であることに注目してください。
なお、現在FSharp.Expandable.Compiler.Aspectは実装を行っている最中で、特にどの関数を変形のターゲットとするかという指定方法を詰めている所です。
まとめ
このように、fscxはこれを土台として、FSharp.Expandable.Compiler.Aspectを使えばAOPを簡単に実現させることも出来、それ以上の変形も（難易度は高いですが）自在に可能でかつ、これをフィルタライブラリとして配布・再利用可能にします。
例えば、F#でOOPをやるのは非常にダルい説があります。何故なら関数プログラミングスタイルになれると、クラスとかインターフェイスを定義したり使ったりするのが面倒なためです（人によるかも知れませんが）。
そのようなわけで、F#でUIプログラミングをやるために、INotifyPropertyChangedのハンドリングとかも面倒この上ないのですが、fscxがあれば、インターフェイスの自動実装を行う変形フィルタライブラリを作ったりとかも出来るのです（しかも、コンパイル時に変形するのでランタイムコストがありません）。そういうライブラリがあれば、普通にコードを書いて、フィルタライブラリのパッケージをNuGetで導入するだけで、即自動実装させることが出来ます。
正式リリースまでには、まだいくつか詰める必要があるのですが、着地点は見えてきた感じです。
謝辞: 株式会社オンザロードさんと、ぶれいすさんに、このプロジェクトの協力を頂いています。ありがとうございます。
今年も残すところあとわずかですね。それではまた！
Hello world的な最初のトライがInt32の計算だったので、まずはInt64を扱うことで、どのような差異が生まれるのかを確認しました。
迷走の始まりです :)
前回から引き続き、フロー解析のアルゴリズムの検討です。
