コンピュテーション式の変形後を覗き見るを改良する

さてさて、気になるネタがまた増えたようです。コンピュテーション式の変形後を覗き見るというエントリがF# Advent Calendar 2014の10日目の記事として公開されました。 Quoteを差し込んで、Runで表示する、というのは面白いアイディアですね。

だが俺の前でコンピュテーション式の変換を扱ったのが運の尽きだ！添削をくらうがいい！

・・・同僚だからってやりたい放題ですね。

変換に必要なメソッド

変換対象が

let ret = simple {
  let x = 10
  return x
}

程度であれば、必要なメソッドはReturnだけです。 BindもReturnFromも不要です。

ですが、消してしまってはあまりにも単純なので、 Bindを使う例を扱えるようにしましょう！

変換対象はこうなります。

let res = simple {
  let! x = 10
  return x
}

このコードがコンパイルできるようにするために必要なコンピュテーションビルダーの定義はこれです。

type SimpleBuilder () =
  member __.Return(x) = x
  member __.Bind(x, f) = f x

let simple = SimpleBuilder ()

手動で変換する

では、このコードを変換していきます。

let res = simple {
  let! x = 10
  return x
}

一番外側はいいでしょう。

let res =
  let b = simple in
  {| let! x = 10 in return x |}

let!の変換

{|と|}に挟まれた部分(cexpr)がlet! ...という形をしているので、 let!の変換規則を最初に適用します。

let b = simple in
T(return x, fun v -> C(b.Bind(10, fun x -> v)))

Bindの呼び出しが出てきました。

returnの変換

Tの最初の引数(変換対象)がreturn xという形をしているので、 returnの変換規則を適用します。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

Returnの呼び出しが出てきました。これ以上変換すべき個所はありませんので、手動変換はここまでです。ビルダーにはBindもReturnも適切に定義されているため、コンパイル可能です。

変換を出力する

さて、元の記事ではSimpleBuilderを弄って変換の様子を出力するようにしていました。同じ方法だと面白くないので、この記事では別の方法を取ってみることにします。その前に、Quoteについて突っ込んでおきます。

Quote変換

Quoteは元記事でも使っていますが、その定義は

member this.Quote(x) = x

と、あたかも式木がxとして渡されてそれをそのまま返しているように見えます。しかし、実際はQuoteメソッドは呼び出されることはありません。ただ単に、Quoteという名前で定義されてさえいればいいのです。そのため、紛らわしさを無くす意味でもQuoteの実装は、

member __.Quote() = ()

としておいた方がいいと思います。

コンピュテーションビルダーに機能を後付けする

さて、コンピュテーションビルダーに対する機能の追加ですが、方法としては以下のものがあるでしょう。

コンピュテーションビルダーの書き換え
既存のコンピュテーションビルダーを継承して機能を追加
型拡張として機能を追加
拡張メソッドとして機能を追加

1つ目の方法が元記事のやり方です。一番シンプルですが、コードがない場合にはこの方法は選べません。

2つ目の方法は、面倒ですしそれほど説明すべき点もないので省略します。

3つ目と4つ目の方法を今回紹介します。

型拡張として機能を追加

コンピュテーション式の変換は、コードの表現しか見ておらず、実現方法は問題にしていません*1。そのため、ビルダーに対してメソッドを呼び出せるようになっていれば、コンピュテーションビルダーにメソッドが定義されている必要はありません。

型拡張でQuote機能を追加する例を見てみましょう。

open FSharp.Quotations.Evaluator

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

この型拡張を適当なモジュールに入れ、そのモジュールをopenするかどうかでexprを出力するかどうかを切り替えれるようになります。しかし、ビルダーにQuoteメソッドを追加してRunの引数の型をExpr<_>型にしてしまい、 Runメソッドの中で引数をそのまま返してしまうと、コンピュテーション式利用側はExpr<_>を受け取ることになってしまいます。これでは、元のコードをコンパイルできなくなってしまいます。

そこで、FSharp.Quotations.Evaluatorというライブラリを使います。このライブラリは、F#のコードクォートを実行するためのライブラリです。 Runメソッドの最後でEvaluateを呼び出し、 QuoteでExpr<_>にしたものをまた戻します*2。

拡張メソッドとして機能を追加

型拡張ではなく、もちろん拡張メソッドとして定義することもできます。

open System.Runtime.CompilerServices
open FSharp.Quotations.Evaluator

[<Extension>]
type SimpleBuilderExtension private () =
  [<Extension>]
  static member Quote (_: SimpleBuilder) = ()
  [<Extension>]
  static member Run(_: SimpleBuilder, expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

少々面倒なので、型拡張でいいですね。一応、できるということで。

exprを出力するコード

少し改良していますが、基本的には元の記事と同じです。

open Microsoft.FSharp.Quotations.Patterns
open System.Collections.Generic

module Printer =
  let mutable private i = 0
  let private valueMap = Dictionary<obj, string>()
  let printKnownVar obj =
    if obj = box simple then
      "simple"
    else
      "unknown_var"
  let printValues () =
    valueMap
    |> Seq.sortBy (fun kv -> kv.Value.Substring(2) |> int)
    |> Seq.map (fun kv -> sprintf "let %s: %s = %s" kv.Value (kv.Key.GetType().Name) (printKnownVar kv.Key))
  let rec print (expr: Quotations.Expr) =
    match expr with
    | Call (Some receiver, m, args) ->
        (* インスタンスメソッド呼び出しを文字列化 *)
        let receiver = print receiver
        let args = List.map print args |> String.concat ", " (* reduceじゃなくてconcatでOK *)
        sprintf "%s.%s(%s)" receiver m.Name args
    | Value (obj, typ) ->
        (* 値を文字列化 *)
        if typ = typeof<SimpleBuilder> then
          (* 値が辞書にあったらそれを変数として扱うように変更 *)
          match valueMap.TryGetValue(obj) with
          | true, name -> name
          | false, _ ->
              let name = sprintf "$b%d" i
              i <- i + 1
              valueMap.Add(obj, name)
              name
        else
          string obj
    | Lambda (arg, Let(var, value, body)) when arg.Name = print value ->
        (* 単純なラムダ式を文字列化 *)
        (* Expr<_>の表現力の問題によって、Lambdaではラムダ式すべてを表現できない。
           例えば、ラムダ式の引数部分でパターンマッチできるが、
           Expr<_>のLambdaはargがVarなので、Letと組み合わせることでこれを再現している模様。 *)
        let arg = var.Name
        let body = print body
        sprintf "(fun %s -> %s)" arg body
    | Var v ->
        (* 変数を文字列化 *)
        v.Name
    | _ ->
        (* 対応できない式木はエラーにするように変更 *)
        failwithf "%A is not supported." expr

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    let exprStr = Printer.print expr
    let values = Printer.printValues ()
    values |> Seq.iter (printfn "%s")
    printfn "%s" exprStr
    expr.Evaluate()

改良した点としては、

変数を出力するようにした
実装を洗練
Runの結果を変えないように、式木を実行するようにした

というところです。

実行してみる

拡張を施したモジュールをopenすると、既存のコンピュテーション式の挙動が変わり、 Printer.printの結果が出力されるようになります。

let res = simple {
  let! x = 10
  return x
}

このコードを実行してみると、このような出力が得られます。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

結果比較

手動変換した結果はこうでした。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

そして、QuoteによってExpr<_>にしたものを文字列化したのがこれです。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

完全に一致！！！

まとめ

コンピュテーション式がどんな風に変換されるのか見るために、 Quoteで式木化してF#コードに文字列化するのはいいアイディアでした。この記事では、以下のことをやりました。

Bindを必要な例に変更
既存のコンピュテーションビルダーに機能を追加する方法
出力されるコードに何も手を加えなくても手動変換の結果とほとんど同じになるようなExpr<_>の出力

Expr<_>の限界*3はありますが、これを推し進めれば、かなり良い感じに色々なコンピュテーション式の変換結果を出力できるようになりそうです。

今年もF# Advent Calendarは豊作ですね！素晴らしいです。

*1:ダックタイピング的、とも言えるでしょう。

*2:Delayを定義している場合は、更にユニットを渡す必要があります。

*3:match式がIfThenElseに落ちるなど