遅延評価ってなんなのさ
何なんでしょうね。分かりません。
自分の頭の中をとりあえず整理するためのエントリなので、あなたの頭を混乱させるだけになるかもしれません。
もし混乱してしまったら忘れてください。え、無理？忘れてください。
自分の考えを明確にしたので、こちらをどうぞ。
遅延評価いうなキャンペーンとかどうか - ぐるぐる～
これは遅延評価ですか？
関数を渡すだけ
// Scala def hoge(f: Unit => Int) = for (i <- 1 to 2) println(f())
(* F# *) let hoge f = for i in 1..2 do printfn "%d" (f())
この関数に渡す f は 2 回実行されます。そのため、f の中で画面出力をしていた場合、2 回出力されます。
これは遅延評価でしょうか？俺は違うと思います。
ここは多くの人で合意が取れると思ってます。
Scala の名前渡し
def hoge(x: => Int) = for (i <- 1 to 2) println(x)
この hoge に対して、
hoge { println("hoge"); 10 }
と呼び出すと、hoge が 2 回呼び出されます。
これは遅延評価でしょうか？俺は違うと思います。
が、これを遅延評価と呼ぶ人もいるかもしれません。
IEnumerable 的なもの
(* F# *) let hoge f = seq { for i in 1..10 -> f i } let xs = hoge (fun i -> printfn "hoge"; i) xs |> Seq.iter (printfn "%d") xs |> Seq.iter (printfn "%d")
// C# static IEnumerable<int> Hoge(Func<int, int> f) { for (int i = 0; i < 10; i++) yield return f(i); } // ... var xs = Hoge(x => { Console.WriteLine("hoge"); return x; }); foreach (var x in xs) Console.WriteLine(x); foreach (var x in xs) Console.WriteLine(x);
これを実行すると、10 回ではなく 20 回 hoge が出力されます。
これは遅延評価でしょうか？俺は違うと思います。
でも IEnumerable 的なものを遅延評価とする人は多いような気がします。
これを遅延評価と呼ぶ場合、何が遅延評価されているのでしょうか？
シーケンスの値である「関数」自体は渡すときにもう評価されているので違いますよね。
ではシーケンスの値として取り出す要素でしょうか？
でもそれを遅延評価と言ったら、一番最初の「関数を渡すだけの例」も遅延評価と呼ばないとおかしくありません？
F# の lazy
(* F# *) let hoge (Lazy x) = x |> ignore x hoge (lazy (printfn "hoge"; 10))
これを実行すると、hoge は 2 回ではなく 1 回しか出力されません。
これは遅延評価でしょうか？んー、このスタイルだと遅延評価と呼んでもいいような気もします。
では、こっちのスタイルはどうでしょうか？
(* F# *) let hoge (x: Lazy<'a>) = x.Force() |> ignore x.Force()
これ、上を書き換えただけでです。これははたして遅延評価・・・？
これは迷います。
lazy の自作
(* F# *) type MyLazy<'a> = { mutable Value: 'a option Source: unit -> 'a } with member x.Force() = if x.Value.IsNone then x.Value <- Some (x.Source()) x.Value.Value let myLazy f = { Value = None; Source = f } let hoge (x: MyLazy<'a>) = x.Force() |> ignore x.Force() hoge (myLazy (fun () -> printfn "hoge"; 10))
先ほどの例を自作した感じです。これは遅延評価でしょうか？ううむ、もはや遅延評価とは呼べないと思います。
これに Active Pattern を追加すると、
let (|MyLazy|) (x: MyLazy<'a>) = x.Force() let hoge (MyLazy x) = x |> ignore x hoge (myLazy (fun () -> printfn "hoge"; 10))
ぬーん。これなら遅延評価と呼べそうな気もするけど、これも違うと思います。
Scala の lazy val
lazy val hoge = { println("hoge") 10 } println(hoge) println(hoge)
これを実行すると、hoge は 1 回しか表示されません。
これを遅延評価じゃない、と言う人は少ない気がします。
遅延評価の条件とは？
ここまで色々と見てきました。
今の自分の中では、
- シーケンスの要素の場合、そもそも遅延評価と呼ばない (単に要素として考えることができるはずなのでシーケンスを特別扱いしない)
- 呼び出し元でラムダ式とかで関数に包む方式はその時点で遅延評価ではない
- 使う側で何か特別なこと (Force の呼び出しとか) が必要な場合、違う気もするがいいような気もする
くらいの線引きがあるような気がします。線引きと言いつつしっかりと線引かれて無いですね。
F# の lazy は遅延評価と呼んでいいような気がする、というのは lazy が構文として用意されているからです。
myLazy の場合、myLazy 自体は構文でも何でもなく、単に関数を受け取る関数なので、一番目の理由から遅延評価とは呼べない、としています。
あなたの線引き、定義も一度考えてみてください。
遅延評価関連のキーワード
- lazy evaluation
- Haskell 界隈の人が言う遅延評価は 100 % これでしょう。call-by-name も含めるかは意見の分かれるところ？
- delayed evaluation
- call-by-need と call-by-name を分けて考えたい人が使ったりします。lazy evaluation は call-by-need、delayed evaluation は call-by-name みたいに。でも、日本語に訳すとどちらも遅延評価となって混乱します。
- call-by-***
- 関数の引数の評価方法の話ででてきます。が、変数の評価方法を指していることもありそうな気がしてよく分かりません。
- call-by-name
- Scala の名前渡し引数で見たようなやつです。
- call-by-need
- call していませんが、Scala の lazy val でみたようなやつです。
- call-by-value
- ラムダ式で包んだり、MyLazy で包んだりしてるやつは実はこれですよね。関数とかインスタンスを値として渡してる。それを言ったら F# の lazy もこれですががが。
ぐーぐるせんせーに聞いてみた
ぐーぐるせんせーで「遅延評価」を検索してみました(2012/3/3)。pws=0を付けています。
上位 10 個を見てみましょう。
Wikipedia
一旦計算された値はキャッシュをすることが可能であり、遅延プロミスは最大で一度しか計算されないようにすることができる。ただし、Haskellの実装によっては、何度でも同じ計算を行う。
遅延評価 - Wikipedia
call-by-name も遅延評価という立場のようです。
IT Pro 本物のプログラマは Haskell を使う
遅延評価のための評価戦略としてよく説明されるのが，「名前呼び出し（call-by-name，名前渡し）」または「必要呼び出し（call-by-need，必要渡し）」です。実際のHaskellの処理系では必要呼び出しがよく使わます。
本物のプログラマはHaskellを使う - 第8回 遅延評価の仕組み：ITpro
こちらも Wikipedia と同じ立場ですね。
404 Blog Not Found
遅延評価(lazy evaluation)したいものを関数でくるんでしまえばいいのだ。こんな感じに。
var todo = function(){ return 1 };値を取り出したいときは、そのクロージャーを評価すればいい。JavaScriptなら、尻に()をつけるだけ。
todo(); // 1.厳密には、これは遅延評価ではない。クロージャーを作る部分というのは先行評価されている。しかしクロージャーを作ったら、そのクロージャーはすぐに返ってくる。「評価された値」はクロージャーそのものなのだ。中身はそのクロージャーを評価するまでおあずけってことに出来るわけだ。
404 Blog Not Found:λ Calculus - まずは遅延評価から
お、こちらは「厳密には違う」としていますね。
call-by-name は遅延評価とみなさない立場と取ってよさそうです。
ひらせチャンネル
int tarai(lazy int x, lazy int y, lazy int z) { if (x <= y) return y; return tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)); }ひらせチャンネル - 遅延評価って何だ？
D 言語だ・・・
ここでは、call-by-need を遅延評価と呼んでいますが、call-by-name については言及がありません。
はてなキーワード
最外簡約。引数よりも先に、外側の関数から評価を進めること。
遅延評価とは - はてなキーワード
簡約と評価は別物だ、って話を聞いたことがあるのですが、それは一旦おいておきましょう。
ここではキャッシュの話は出てきませんので、call-by-name も遅延評価と呼んでいるようです。
IBM developerWorks
このバージョンの calculate-statistics では、値が必要になるまで何も起こりません。そしてそれと同じく重要な点として、どれも 1 度しか計算されません。最初に分散が要求されたとすると、calculate-statistics が実行されて最初に平均が保存され、そして calculate-statistics が再度実行されて分散が保存されます。次に平均が要求されると、既に平均は計算されているため、calculate-statistics は単純に値を返します。
遅延プログラミングと遅延評価
call-by-need を遅延評価と呼んでいますが、call-by-name への言及がありません。
後ろの方で
しかし例えば Haskell など一部の言語では、通常の評価プロセスの一部として遅延機能を持っており、これは遅延評価と呼ばれています。遅延評価では、どのパラメーターも、必要になるまで評価されません。プログラムは基本的に最後から開始され、逆方向に実行されます。プログラムは、何を返すべきかを判断し、逆向きに動作を続けながら、どの値を返すべきなのかを判断します。基本的に、すべての関数が、各パラメーターへのプロミスを付けてコールされます。計算に値が必要になると、その計算はそのプロミスを実行します。値が必要な時しかコードは実行されないため、これは call-by-need (必要によるコール) と呼ばれます。従来のプログラミング言語では、プロミスではなく値が渡されるので、call-by-value (値によるコール) と呼ばれます。
遅延プログラミングと遅延評価
とあるように、call-by-value と call-by-need しかないように受け取れます。
call-by-reference とか、call-by-name どこいった。
Rubyist Magazine
「遅延評価」というのは、「その値が必要になるまで実際の計算を行わない評価方式」のことです。前もって評価した結果を利用するのではなく、それが必要になったときに初めて評価して結果を得る、ということです。
Rubyist Magazine - enumerable_lz による遅延評価のススメ
これだけではどういう考えかわかりませんが、実際に enumerable_lz を使ってみると、配列の代わりにシーケンスを返すだけのようです。
ぬぬぬ。
neue cc
hogeEnumerableに包まれている状態では、まだ何も実行は開始されていません。そう、遅延評価！
neue cc - LINQの仕組みと遅延評価の基礎知識
これも enumerable_lz と同じ感じですね。
Scheme 入門
全体的に遅延評価を取り入れた言語としては Haskell が有名ですが、 Scheme も部分的に遅延評価を取り入れています。
Scheme 入門 17. 遅延評価
Scheme の遅延評価について述べています。
つまり、call-by-need についての言及のみで、call-by-name への言及はありません。
@IT .NET 開発者 厳選ブログ記事
xxxEnumerable変数（＝前述の「selectEnumerable」／「takeEnumerable」などのIEnumerable
LINQの仕組み＆遅延評価の正しい基礎知識 − ＠ITオブジェクト）の中に包まれている状態では、まだ何も実行は開始されていません。そう、LINQは遅延評価されます！
これは上で登場した neue さんのブログ記事を加筆・修正したものなので、基本的には同じです。
さて・・・
うまい具合にばらばらですね。
call-by-name も遅延評価、という立場の人が検索結果の上位にいるのは意外でした。
結論？そんなものはないです。
でも一度個人個人で「自分はどれを遅延評価と呼び、どれを呼んでいないか」をはっきりさせてみてください。
