Hatena::Groupcsnagoya-sicp

gabuchanの日記

2008-11-10

問題1.20

| 16:29

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(gcd 206 40)

こんな最大公約数を求める手続きがあったとして、「正規順序評価と作用的順序評価で remainder 演算がそれぞれ何回実行されるか。」という問題。

手動デバッグが面倒なのでプロファイルを使いました。

$ gosh -ptime 1.20.scm | grep remainder
remainder                                                4  0.0000     0(  0%)

作用的順序で評価する Gauche では4回だそうです。つまり、作用的順序評価では4回。

正規順序といえば・・・やっぱり Haskell ですよね。

main = print $ Main.gcd 206 40

gcd :: Integer -> Integer -> Integer
gcd a 0 = a
gcd a b = Main.gcd b $ remainder a b

remainder :: Integer -> Integer -> Integer
remainder a b = a `rem` b

組み込みで gcd 関数があるので、明示的にMain.を追加しています。remainder 手続きは rem 関数があるのですが、組み込み(?)関数はプロファイルに上がってこないので、ユーザ定義でラッパーを作りました。

プロファイルを有効にしてコンパイル

$ ghc -prof -auto-all -o haskell_gcd 1.20.hs

プロファイルを有効にして実行

$ ./haskell_gcd +RTS -p

プログラム名.prof というファイルが作られるので見ます。

$ less haskell_gcd.prof
        Mon Nov 10 15:10 2008 Time and Allocation Profiling Report  (Final)

           haskell_gcd +RTS -p -RTS

        total time  =        0.00 secs   (0 ticks @ 20 ms)
        total alloc =      17,832 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

CAF                            GHC.Handle             0.0   48.3
CAF                            Main                   0.0   50.5


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0     0.0  100.0
 CAF                     Main                                                 152           3   0.0   50.5     0.0   51.7
  main                   Main                                                 158           1   0.0    0.1     0.0    1.2
   gcd                   Main                                                 159           5   0.0    0.9     0.0    1.0
    remainder            Main                                                 160           4   0.0    0.2     0.0    0.2
 CAF                     GHC.Handle                                           104           4   0.0   48.3     0.0   48.3

remainder関数は4回。正規順序でも4回か。