Lazy Evaluation、怠け者評価、遅延評価の話題

Lazy Evaluation 怠け者評価(遅延評価)って？

子供の頃(今でも？)、「他人にやれと言われる前に自分から、さっさとやりなさい。」などと言われませんでしたか？一般社会では、普通に会社や組織に所属して他人に雇用されているときには、これが常識でしょう。

コンピュータプログラムの世界でも同じで、計算はできるだけ前もって済ませておくというのが普通らしいです。関数に渡すにもまず、ちゃんと値を計算して渡す。根がまじめで人がいいので、渡した値が実は使われないかもしれないなんて、疑ったりはしないのね。

でもね、Haskellでは、評価は必要になって、尻をたたかれないかぎり、やりません。前もってやっておくなんて「信〜じられな〜い」。これをLazy Evaluationといったりします。

いわれて始めて仕事を始めるというやつですね。しかも、いわれた分だけしかやらないというやつですね。

Haskellでプログラムを書き、それを走らせることができています。ということは、どこかで、最初に要求を出すやつがいて、そいつが要求を出して、計算がはじまり、それが連鎖して、計算が継続され、最初の要求に答えたら計算が終るということがおこっていると考えられますね。

Haskell の Lazy Evaluation を追いかける

Haskellのプログラムは、どのような契機で評価が開始され、どのように評価が進み、どこまで評価が到達するのでしょう？

単純な計算で、遅延評価を追いかけてみましょう。

Hugs の対話型インタープリタを起動しましょう。

% hugs
Prelude>

対話型のインタープリタにプロンプトが出たましたね。このとき、インタープリタは何か要求されるのを待っている状態です。さて、今、1 + 1 の結果が知りたいとしましょう。

Prelude> 1 + 1
2
Prelude>

答の 2 が表示されましたね。なにが起こったのか詳細に考えていきましょう。

1 + 1 とタイプして、リターンキーを押した

これは、インタープリタに対する「1 + 1 の結果を印字(PRINT)せよ」という要求です。処理系は、この要求を理解するために、準備処理をします。いまは、この準備処理については詳しく考えません(要するに、1 + 2 というデータを、内部的なプログラムの表現に変換します。その際、入力が Haskell のプログラムとして正しいかどうかをチェックします)。

次に、インタープリタは

印字ルーチン print に入力渡して、結果を印字するように要求

で print は、文字列を出力するルーチン putStr を使って、印字を実行するのですが、putStr は文字列しか扱えません。文字列を完全に使える状態にして出力がおこなわれます。データを文字列に変換する関数は show です。

show (1 + 1)

を「評価をする」というのが出発点です。

一般には Int型に対する show の定義はちょっと複雑ですが、以下のような定義と同等と、今は、考えてください(ここの説明では、 1 + 2 の結果がInt 型であることを暗黙の前提としています)。

show = \ i ->  case i of
                 0  -> "0"
                 1  -> "1" 
                 2  -> "2"
                 ...

さて、

show (1 + 1)

の評価ですが、どこまで評価するかというと、 WHNF になったら評価がおわります。WHNF というのは、乱暴にいうと一番外側(の一番左)にデータコンストラクタが出てきた形、または、 λが出てきた形です。

さて、show (1 + 1) は WHNF でしょうか？違いますね。関数適用ですね。関数適用を評価するには、まず関数部分を評価します。そして出てきた、λ式の body 部にある仮引数を、実引数で置き換えます。

show を評価
==> \ i -> case i of 
              0 -> "0"
              1 -> "1"
              2 -> "2"
              ...

いちばん外の左に、λがでてきましたね。ですから、show の評価はこれでおしまい。出てきた、λ式の body 部にある仮引数を、実引数で置き換えます。

仮引数を実引数でおきかえる

==> case (1 + 1) of 
      0 -> "0"
      1 -> "1"
      2 -> "2"
      ...

で、ここで、case 式の簡約ですが、

case expr of
  pat1 -> expr1
  pat2 -> expr2
  ...

とある場合、この式は pat_n で照合ができるようになるまで、 expr を評価し、適合したパターンの後にある式に簡約されます。もし、expr が pat_2 と適合したら、この case 式全体は、expr2 に簡約されます。

そこで、次に、1 + 1 の評価を行います。

Int 型に対する + は通常、組込みです。 (x + y)という式を評価すると + は x 、y を共に評価してから、足し算をして、その結果を返します。

仮想的には以下のように定義されていると思ってください。

(+) :: Int -> Int -> Int
(+) = \ i -> \ j -> case i of
                      0 -> j
                      1 -> case j of 
                             0 -> 1
                             1 -> 2
                             ...
                      ...

というわけで、1 + 1 の評価結果は 2 です。さて、show の計算のとことで、 (1 + 1) が評価されて 2 になったので show のなかの case 式のパターンマッチ

   2 → "2"

によって、show (1 + 1) の値として、“2” が選択されます。これが putStr に渡って、2 が印字されるというわけです。

これで、インタープリタが 1 + 1 を評価する時の動きを追いかけられました

要点は、

最初の部分は特別だか、それ以外では評価は WHNF が要求されると行なわれる
WHNF を要求するのは、case 式のパターンマッチだ
Lazy Evaluation をまじめに追跡するのは難しい

ということです。

ちょっといたずら

インタープリタに、1 + (error “hoge”) というのを評価させてみましょう。 (Hugs のシステムには評価のようすをトレースする機能がないので、手でなにかに書きながら追い掛けます。)

Prelude> 1 + (error "hoge")

Program error: hoge

error “hoge” は評価されるとエラーを起します。これはどの段階でエラーを起したのでしょう。これは、

show (1 + (error "hoge"))

==> (\ i -> case i of 
              0 -> "0"
              1 -> "1"
              ...)
    (1 + (error "hoge"))
==> case (1 + (error "hoge")) of
      0 -> "0"
      1 -> "1"
      ...

パターンマッチのために、1 + (error “hoge”) を簡約

  ==> (\ i -> \ j -> case i of
                       0 -> j
                       1 -> case j of 
                              0 -> 1
                              1 -> 2
                              ...
                       ...
       ) 1 (error "hoge")
  ==> case 1 of
        0 -> j
        1 -> case (error "hoge") of
               0 -> 1
               1 -> 2
               ...
        ...

最初のパターンマッチを行うために、1 が評価され、パターンマッチの結果

  ==> case (error "hoge") of
        0 -> 1
        1 -> 2
        ...

となる。このパターンマッチを行うために、error “hoge” が評価するところでエラーが起きます。

もっといたずら

上のエラーの契機は、show (1 + (error “hoge”)) の評価を行うときに (1 + (error “hoge”) の評価を行う際に、ありました。 + が引数を2つとも必ず評価する関数だからですね。

では、+ のかわりに、次のように定義された k という関数をつかってみましょう。

k :: Int -> Int -> Int
k = \ x -> \ y -> x + 1

こんなふうに定義して、hoge.hs にセーブしたものを読み込んで、 1 `k` (error “hoge”) を評価してみましょう。

Prelude> :load hoge.hs
Main> 1 `k` (error "hoge")
2

今度はエラーが起りませんね。つまり、error “hoge” は評価されていないわけです。追いかけてみましょう。

show (1 `k` (error "hoge"))

==> (\ i -> case i of
              0 -> "0"
              1 -> "1"
              2 -> "2"
              ...
    ) (1 `k` (error "hoge"))
==> case (1 `k` (error "hoge")) of
      0 -> "0"
      1 -> "1"
      2 -> "2"
      ...

パターンマッチのために、1 `k` (error “hoge”) を評価

==> (\ x -> y -> x + 1) 1 (error "hoge")
==> 1 + 1
==> 2

というわけで、(error “hoge”)は評価されなかったわけで、エラーは起きないというわけですね。

究極(?)のいたずら (2004/11/12)

対話型のインタープリタ内で、プロンプトに対して式 exp を入力すると、その式の入力の値を印字しようとして、評価が進むといいましたよね。印字のルーチン (print)内で、show exp が返す値を完全に評価された文字列にしようとすることで、評価が進みます。では、show が完全な文字列をつくるのに exp を評価しなくてもいいことになっていればどうでしょう。ちょっと解りにくいですが、とりあえず実験してみましょう。

hugs98-Nov2003 をソースからデフォルトの設定のまま(すなわち、configure スクリプトをオプションなしで)インストールしたと仮定して説明します。この場合、/usr/local/lib/hugs/libraries/Hugs/ に、Prelude.hs がインストールされています。これの 299行目あたり

instance Show Int where
    showsPrec   = primShowsInt

となっているところを

instance Show Int where
--    showsPrec   = primShowsInt
    showsPrec _ _ _ = "<Int>"

と書き換えてください。これは何をやったかというと、Int 型の値を文字列 (String型)の値に変換する関数を定義を、与えられた Int 型の値にかかわらず(つまり評価することなく)単に、“<Int>”とという文字列を返すように変更を施しています。

さて、これで、hugs インタープリタを起動して、実験です。まず、プロンプトから length [1,2,3] を入力してみましょう。まずは、予想をして、何が印字されるでしょう。

length [1,2,4] を評価すると 3 になるはずですよね。

Prelude> length [1,2,4]
"<Int>"

length の型は、[a] -> Int なので、lenght [1,2,4] の値は Int 型です。先程の変更が効果を発揮して、<Int> が印字されています。

では、length [1,2,4] は評価されたのでしょうか。これだけではわかりませんね。どうしたら解るでしょう？ length [1,2,4] が評価されたとすると、 length の定義から、引数のリストを最後まで辿って、要素の数を特定しているはずですね。そこで最後まで辿りきれない無限リスト[1..] を length に渡してみましょう。

Prelude> length [1..]
<Int>

ちゃんとプロンプトが返ってきますね。つまり、lenght [1..] は評価されていないのです。

なぜでしょう。それは、Int型に対する show 関数がその引数の値を使っていないからです。すなわち、Int型を印字するのに、Int型の値を必要としないように書換えてしまったからです。length [1..] の値が Int 型であることを知るのに length [1..] を評価する必要がないことを思い出してください。

length [1,2,4] + error “hoge” をプロンプトから入力してみましょう。

Prelude> length [1,2,4] + error "hoge"
<Int>

これもエラーは発生しません。さらに、

Prelude> error "hoge" :: Int
<Int>

これでさえ大丈夫です。もちろん、ちゃんと length [1..] を評価するとそれは停止しません。確かめてみましょう。

Prelude> take (length [1,2,4]) "The Haskell Language"
"The"
Prelude> take (length [1..]) "The Haskell Language"
"{Interrupted!}

“{Interrupted!} は実行を Ctrl-C で止めたときに出たものです。 length [1,2,4] + error”hoge" はちゃんと評価すると、もちろんエラーになります。

Prelude> take (length [1,2,4] + error "hoge") "The Haskell Language"
"
Program error: hoge

究極の実験の後始末を忘れないようにしましょう。無茶な変更を加えたところを元にもどしておきましょう。忘れると変なところで、ワケワカなことになりますからね。

samefringe problem

Uuutokudaの日記(2005-11-15)より

Haskell なら単に fringe を比べればいいだけだよーん．

data Tree a = Leaf a | Branch [Tree a]

fringe :: Tree a -> [a]
fringe (Leaf x)    = [x]
fringe (Branch cs) = foldr ((++) . fringe) [] cs

samefringe :: Eq a => Tree a -> Tree a -> Bool
samefringe t u = fringe t == fringe u

Last modified : 2006/11/22 22:35:38 JST