青木日記

■ RHG 読書会

今日は RHG 読書会 #3 です。5 章のコンパクションのところからだっけ。

■ RHG 読書会 /3

読書会 #3 行ってきました。参加者のみなさんお疲れさまでした。

今回は 5 章 GC のコンパクションの話から 10 章のパーサ／スキャナでした。 もうちょっと時間はあったんですが、難関の 11 章 (状態付きスキャナ) を前にして日和りです。 第一部の山場のクラスと GC の章もほぼ終わってましたし、 今回は様子見と言うか嵐の前の静けさと言うか谷間の回ですね。 トピックは明日起きたら RWiki に書いときます。

今回も非常に楽しかったです。 読書会後の rhg-tokyo Haskell 分科会も有意義でした (笑)。

ちなみに、なんで Haskell Haskellって言ってるかと言うと、 Haskell という言語から何がしかを得たいと思うからです。 別に必ずしも Haskell が凄くいいとは思ってないんです。

ただ、Haskell は ML とか Scheme と比べてもより関数型っぽいので、 関数型の特徴がより鮮明に見えるだろうとは期待してます。 たとえば正格 (strict) なところとか、ML のような抜け道がないとことか。

■ たらいまわし関数

どういう経緯で話が出たんだかすっかり忘れましたが、 「たらいまわし関数」というのがあるそうです。 処理の様子が「たらいまわし」らしい。

− Haskell 版
　
main :: IO ()
main = print (tarai 12 6 0)
　
tarai :: Int -> Int -> Int -> Int
tarai x y z
    | x <= y    = y
    | otherwise = tarai (tarai (x-1) y z)
                        (tarai (y-1) z x)
                        (tarai (z-1) x y)
# Ruby 版
def tarai( x, y, z )
  if x <= y
  then y
  else tarai(tarai(x-1, y, z),
             tarai(y-1, z, x),
             tarai(z-1, x, y))
  end
end
　
puts tarai(12, 6, 0)

この関数はけっこう有名な竹内関数 (tak) の本来の姿で、 遅延評価のある処理系だと高速に評価できるそうな。 本当かどうか、Ruby と Haskell (hugs) の両方で計測してみました。

~/c/test/haskell % time runhugs tarai.hs                         aamine@harmony
12
runhugs tarai.hs  0.13s user 0.01s system 101% cpu 0.138 total
~/c/test/haskell % time ruby tarai.rb                            aamine@harmony
12
ruby tarai.rb  24.65s user 0.00s system 100% cpu 24.604 total

200 倍速ッ？！ こ、これはすごい。

よーし、ついでに C でも書いてみよー！

~/c/test/haskell % gcc -O6 -Wall tarai.c -otarai                 aamine@harmony
~/c/test/haskell % time ./tarai                                  aamine@harmony
12
./tarai  0.29s user 0.00s system 118% cpu 0.246 total

C 言語が Haskell インタプリタに負けた……。 計算量って偉大だ。

■ アッカーマン関数

次はヤッターマン関数じゃなくてアッカーマン関数。 こっちの関数は評価方法に関らず計算量が死ぬほど多いらしいです。

module Main (main) where
　
main :: IO ()
main = print (ack 3 1)
　
ack n m
    | n == 0    = m+1
    | m == 0    = ack (n-1) 1
    | otherwise = ack (n-1) (ack n (m-1))

ack 3 3 くらいまでならすぐに結果が返ってきますが、 うっかり ack 4 4 とか計算させてしまうととてつもないことになります。

っていうか、終わるの？ これ。