Old/sampou.org/Lazy

Lazy


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 型の値にかかわら ず(つまり評価することなく)単に、“”とという文字列を返すように変更 を施しています。

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

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

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

length の型は、[a] -> Int なので、lenght [1,2,4] の値は 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