2010-03-21

F#は自分の中に眠る力を引き出すべく、Lisp長老に会いに行ったのだった。

Lisp like meta-programming ・・・!
いくつか例をあげてみよう。
（実行にはPowerPackが必要です）

階乗

open System
open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
open Microsoft.FSharp.Linq.QuotationEvaluation
open System.Runtime.Serialization.Formatters.Binary

// Expr の保存とロードを担当
type ExprManager() =
    static let formatter = new BinaryFormatter ()
    static member Save<'T> fileName (e : Expr<'T>) =
        formatter.Serialize ( System.IO.File.Create fileName, box e )
    static member Load<'T> fileName =
        formatter.Deserialize ( System.IO.File.OpenRead fileName ) |> unbox<'T Expr>

// 普通のfac
let rec fac = function
| 1 -> 1
| n -> n * fac (n - 1)

// 式を生成する再帰関数
let rec meta_fac = function
| 1 -> <@ 1 @>
| n -> <@ n * %(meta_fac (n - 1)) @>


let fac5 = meta_fac 5


// C++やCommon Lispのようにコンパイル時に展開できないので、事前に保存してやってもいいかもしれない
// しかしロードの方がコストがかかるかもしれない・・・
//let pre_fac3 () = ExprManager.Save "sample.txt" (meta_fac 3)

// ロード（似非プリプロセス）してやる
let fac3 = (ExprManager.Load<int> "sample.txt").Compile ()


[<STAThreadAttribute>]
do
    printfn "%A" <@ 5 * (4 * (3 * (2 * 1))) @> // これと同じになれば成功！
    printfn "%A" fac5
    printfn "\n"
    printfn "%d" <| fac 5
    printfn "%d" <| fac5.Eval ()
    printfn "%d" <| fac3 ()

Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

      [Value (5),

       Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

             [Value (4),

              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

                    [Value (3),

                     Call (None,

                           Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

                           [Value (2), Value (1)])])])])

Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

      [Value (5),

       Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

             [Value (4),

              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

                    [Value (3),

                     Call (None,

                           Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),

                           [Value (2), Value (1)])])])])


120

120

6

続行するには何かキーを押してください . . .

残念ながらパフォーマンスの面での期待はできなそうです。
コンパイル後の式はそこそこ速いものの、普通に書いた関数には及びませんでした。
色々オーバーヘッドがあるのかなぁ。
Lispではパフォーマンス向上のためにマクロを使って式を展開することもありますが、今の時代に気にするほどのことではないですね・・・。

and オペレータ

全てが真の場合のみ真を返すオペレータを書いてみよう。
先頭から見ていって、偽が見つかった時点で評価を中止する。

let (><) (a : Expr<bool>) (b : Expr<bool>) = <@ if %a then %b else false @>

let and_test = <@ true @> >< <@ false @> >< <@ 1 / 0 = 0 @>

[<STAThreadAttribute>]
do
    printfn "%A" <| <@ if (if 1 = 1 then 2 = 2 else false) then 3 = 3 else false @>
    printfn "%A" <| ( <@ 1 = 1 @> >< <@ 2 = 2 @> >< <@ 3 = 3 @> ) // 上と同じになるかな！？

    printfn "%A" <| and_test.Eval () // 例外は発生しない

IfThenElse (IfThenElse (Call (None, Boolean op_Equality[Int32](Int32, Int32),

                              [Value (1), Value (1)]),

                        Call (None, Boolean op_Equality[Int32](Int32, Int32),

                              [Value (2), Value (2)]), Value (false)),

            Call (None, Boolean op_Equality[Int32](Int32, Int32),

                  [Value (3), Value (3)]), Value (false))

IfThenElse (IfThenElse (Call (None, Boolean op_Equality[Int32](Int32, Int32),

                              [Value (1), Value (1)]),

                        Call (None, Boolean op_Equality[Int32](Int32, Int32),

                              [Value (2), Value (2)]), Value (false)),

            Call (None, Boolean op_Equality[Int32](Int32, Int32),

                  [Value (3), Value (3)]), Value (false))

false

続行するには何かキーを押してください . . .

Quoteしているため、遅延評価的な扱いになる。そのため 1 / 0 = 0 はその場では例外をスローしない。
普通の関数で定義してしまうと、必要のないものまで評価してしまうのでif系関数としてはよろしくない。*1

感想

Quotationは実行時に限るのでC++のテンプレートメタプログラミングなどとは毛色が違います。また、あらゆる式を記述できるわけではないので、柔軟性に欠けます。例えば型を定義できないしobject expressionなども使えない。

そのメタプログラミングの考え方はどちらかというとCommon Lispのように式を展開してゆくスタイルに近いけれども、強力さには雲泥の差があるように思います。Lispは式が単純な上に動的型付けであることも手伝って、自在に自身を記述することが出来る。おまけにコンパイル時・実行時・読み込み時（リードマクロ）など色々なタイミングで式を展開することも出来る。

パフォーマンス向上目的での利用もあまり意味がなさそうなので、独自のシンタックスシュガーを作るか、Linq to SQLのように式を解析して何かを生み出してやるか、などに利用範囲は限られそうです。ここぞ！というところで活きてくれるのを期待しているけど、現時点だとあまりアイディアが浮かばない・・・。

Computation ExpressionはQuotationでも利用可能みたいなので、その辺から何か面白い使い方でも出てくるのでは、と漠然と思っています。

*1:lazyで回避できますが

Nobuhisa's diary

Quotation で Meta-Programming !

階乗

and オペレータ

感想