読者です 読者をやめる 読者になる 読者になる

眠気と戦う日々

眠気と戦いながらプログラミングについていろいろと書くブログ

コンピュテーション式の変形後を覗き見る #FsAdvent

FSharp

はじめに

この記事はF# Advent Calendar 2014の10日目の記事です。
前日はbleisさんの「クラスのコンストラクタ呼び出し時にプロパティも同時に初期化する」でした。

本日はTipsからちょっと外れてネタをご紹介します。
タイトルにもある通り、コンピュテーション式のお話です。

コンピュテーション式とは何ぞや

式変形により、言語の提供する構文の意味を変更することのできる強力な機能です。
その辺りの細かいことなどを知りたい場合は言語仕様を読みましょう。
さて、今回はその「式変形」に着目してみました。

本題

式変形という素敵ワードを聞き、そこで湧き上がる疑問があります。
すなわち「式変形するって言うけど、それって本当に言語仕様通りなの? 同じように動作するだけで、実は違ったりしない?
当然、気になりますよね? 気にならないわけないですよね?
気にならない人も気になってきたかと思います。
はい。
てことで、コンピュテーション式の式変形を追いかけて行きましょう。
具体的には手を動かして変換した結果と、コンピュテーション式を変換したあとの式木を表示する感じです。

題材

とは言ったものの、複雑なコンピュテーション式を手で変換するのは骨が折れます。
なので今回は極端に単純な例でいきます。
具体的には以下の様な感じで。

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

let simple = SimpleBuilder ()

とりあえずこれだけあれば、以下の様なコンピュテーション式を書くことができます。

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

今回はこれを考えていきましょう。

手動での変形

それでは早速行きましょう。
まずもっとも「外側」の部分の規則は以下です。

builder-expr { cexpr }

これが以下のようになります。

let b = builder-expr in {| cexpr |}

そして、変換規則はbleisさんの過去記事「詳説コンピュテーション式」にある以下の規則を用います。
今回はカスタムオペレータについては考慮しませんし、題材となるコンピュテーション式ではとりあえずこれで十分だからです。

{| cexpr |}T (cexpr, fun v -> v)

これで前準備は十分ですね。それでは本格的に変換していきます。

letを変換する

はい、それではまずは一番最初に出てくるlet x = 10の変換から行きましょう。
letの変換規則は以下のようになっています。

T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))

これに従って変換します。

(* 元の形 *)
let ret = simple {
  let x = 10
  return x
}

(* 全体の変形 *)
let ret =
  let b = simple
  {| let x = 10 in return x |}

(* {| cexpr |} 形式を T(e, C) の形に変換 *)
let ret =
  let b = simple
  T(let x = 10 in return x, fun v -> v)

(* letの変換規則に従って変換 *)
let ret =
  let b = simple
  T(return x, fun v -> (let x = 10 in v))

はい、letの変換はここまでです。
それでは次はreturnの変換です。

returnを変換する

returnの変換規則は以下のようになっています。

T(return e, C) = C(b.Return(e))

これに従って、letを変換した結果をさらに変換してみましょう。

(* letの変換規則に従った変換結果 *)
let ret =
  let b = simple
  T(return x, fun v -> (let x = 10 in v))

(* returnの変換規則に従って変換 *)
let ret =
  let b = simple
  (fun v -> (let x = 10 in v)) (b.Return(x))

(* 簡約 *)
let ret =
  let b = simple
  let x = 10 in (b.Return(x))

はい、これにて手動変換終了です。

自動変形を覗き見る

それでは次に自動の方を見て行きましょう。
自動での変換結果を覗き見るために必要なのはRunとQuoteです。
Quoteがあると、Runの引数として式木が与えられます
これを覗き見るため、とりあえず以下のように書き換えます。

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

  member this.Quote(x) = x
  member this.Run(expr) =
    Console.WriteLine(expr.ToString())

はい、とりあえずまずは式木をそのまま表示する感じですね。
これを実行すると、以下の様な結果が得られます。

Let (x, Value (10), Call (Some (Value (Program+SimpleBuilder)), Return, [x]))

これをこちらの資料に従って、読みやすいように変えてみましょう。

Letの読み替え

まず最初に登場するのはLetです。
Letはlet式のことですね。
この資料に従って、以下のようにします。

Let (var, expr1, expr2) = let var = expr1 in expr2

これを行う関数を定義します。
とりあえず今回は表示が目的ですし、式木を受け取って文字列を返却する感じでいいでしょう。
てことでこんな感じです。

let rec evaluate = function
  | Let (var, expr1, expr2) ->
    sprintf "let %s = (%s) in (%s)" (var.ToString()) (evaluate expr1) (evaluate expr2)

それでは次、expr1に当たる箇所で出てくるValueの読み替えを実装していきます。

Valueの読み替え

Valueは定数値を表しています。 こちらの資料に従って以下のようにしましょう。

Value (obj * Type) = obj

objはその定数値、Typeはその型を表していますので、今回はobjのみを文字列に変換してみましょう。

let rec evaluate = function
  | Let (var, expr1, expr2) ->
    sprintf "let %s = (%s) in (%s)" (var.ToString()) (evaluate expr1) (evaluate expr2)
  | Value (obj, _) ->
      obj.ToString()

まだまだ行きます。 次はCallです。

Callの読み替え

Callは関数呼び出しのことです。 こちらの資料に従って以下のような感じにします。

Call (Some instance, methodInfo, arguments) = instance.methodInfo(arguments)

Some instanceはインスタンスメソッドの呼び出しの場合にのみ入るインスタンスの式木です。 methodInfoはそのままですね。呼び出す対象となるメソッドです。 argumentsはその引数です。 これらを踏まえ、以下のように実装します。

let rec evaluate = function
  | Let (var, expr1, expr2) ->
    sprintf "let %s = (%s) in (%s)" (var.ToString()) (evaluate expr1) (evaluate expr2)
  | Value (obj, _) ->
      obj.ToString()
  | Call (Some instanceExpr, methodInfo, arguments) ->
    let args = List.map evaluate arguments
    sprintf "(%s).%s(%s)" (evaluate instanceExpr) (methodInfo.Name) (List.reduce (sprintf "%s, %s") args)

そろそろ終わりが見えてきました。

その他の解釈

さて、それでは残りです。
残りは単純に引数の値を文字列化しちゃいましょう。
ということで、evaluate関数の最終形はこちらです。

let rec evaluate expr =
  match expr with
  | Let (var, expr1, expr2) ->
    sprintf "let %s = (%s) in (%s)" (var.ToString()) (evaluate expr1) (evaluate expr2)
  | Value (obj, _) ->
      obj.ToString()
  | Call (Some instanceExpr, methodInfo, arguments) ->
    let args = List.map evaluate arguments
    sprintf "(%s).%s(%s)" (evaluate instanceExpr) (methodInfo.Name) (List.reduce (sprintf "%s, %s") args)
  | _ ->
    expr.ToString()

それではこれを使い、コンピュテーション式の変形後を覗きこんでみましょう。

自動変形の結果

以前定義していたSimpleBuilderは以下の様な感じでした。

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

  member this.Quote(x) = x
  member this.Run(expr) =
    Console.WriteLine(expr.ToString())

これのRunでevaluate関数を実行し、中身を表示します。

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

  member this.Quote(x) = x
  member this.Run(expr) =
    Console.WriteLine(evaluate expr)

そして実行します。 結果は下のような感じです。

let x = (10) in ((Program+SimpleBuilder).Return(x))

Program+SimpleBuilderの部分はインスタンスを表しているので、これを以下のように読み替えてしまいましょう。

let b = simple
let x = (10) in (b.Return(x))

そして、Runの結果がコンピュテーション式の結果となるので、以下のようにします。

let ret =
  let b = simple
  let x = (10) in (b.Return(x))

はい、これにて完了です。

結果比較

それでは2つの結果が出揃いましたので、比較してみましょう。
まず手動です。

let ret =
  let b = simple
  let x = 10 in (b.Return(x))

次に自動です。

let ret =
  let b = simple
  let x = (10) in (b.Return(x))

()は単なる表示用なので無視すると完全に一致しますね。

まとめ

このレベルのシンプルなコンピュテーション式であれば仕様通りということがわかりました。
ところでこの記事、一番の収穫はQuoteを定義するとRunで式木が得られるというTipsだと思うんですが、どうでしょう。
次点で資料リンク。

ということで本日は以上です。
明日はgab_kmさんです。楽しみですね!

追記・あわせて読みたい

本エントリに対するツッコミをbleisさん、pocketberserkerさんが書いてくださいました。
既存のコンピュテーションビルダーに対してRun/Quoteを追加するより良い方法など、素晴らしいTipsを紹介してくださっています。
エントリはこちらです。

ありがとうございました!