sicpマラソン5日目

sicp scheme

環境が復帰したので再開。

[メモ]
  • 最大公約数＝Euclidのアルゴリズム (1.2.5)
  • Lameの定理＝gcdの計算にkステップ必要な時、gcdの対の小さい方の数はk番目のFibonacci数以上 (1.2.5)
  • ifの評価＝述語式を最初に評価し、その結果から帰結式か代替式のどちらかを評価(演習問題1.5) (1.2.5)
  • Lameの定理の証明、チェックすること (1.2.5)
[演習問題]

1.20

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

正規順序で評価

(gcd 206 40)
==> (if (= 40 0)                              ;; if節 (= 40 0)==>#f を評価
        206
        (gcd 40 
             (% 206 40)))
==> (gcd 40 
         (% 206 40))
==> (if (= (% 206 40) 0)                      ;; if節 (= (% 206 40) 0)==>#fを評価、%の評価:+1回
        40
        (gcd (% 206 40)
             (% 40 (%206 40))))
==> (gcd (% 206 40) 
         (% 40 (% 206 40)))
==> (if (= (% 40 (% 206 40)) 0)               ;; if節 %の評価:+2回
        (% 206 40)
        (gcd (% 40 (% 206 40)) 
             (% (% 206 40) (% 40 (% 206 40))))))
==> (gcd (% 40 (% 206 40)) 
         (% (% 206 40) (% 40 (% 206 40)))))
==> (if (= (% (% 206 40) (% 40 (% 206 40))) 0)                          ;; if節 %の評価:+4回
        (% 40 (% 206 40))
        (gcd (% (% 206 40) (% 40 (% 206 40)))
             (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
==> (gcd (% (% 206 40) (% 40 (% 206 40)))
         (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
==> (if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) 0)   ;; if節 %の評価:+7回
        (% (% 206 40) (% 40 (% 206 40)))
        (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
             (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))))
==> (% (% 206 40) (% 40 (% 206 40)))                                   ;; %の評価:+4回
==> 2                                                                  ;; %の評価:合計18回

作用的順序で評価

(gcd 206 40)
==> (if (= 40 0)
        206
        (gcd 40 (% 206 40)))
==> (gcd 40 (% 206 40))        ;; %の評価:+1回
==> (gcd 40 6)
==> (if (= 6 0)
        40
        (gcd 6 (% 40 6)))
==> (gcd 6 (% 40 6))           ;; %の評価:+1回
==> (gcd 6 4)
==> (if (= 4 0)
        6
        (gcd 4 (% 6 4)))
==> (gcd 4 (% 6 4))            ;; %の評価:+1回
==> (gcd 4 2)
==> (if (= 2 0)
        4
        (gcd 2 (% 4 2)))
==> (gcd 2 (% 4 2))            ;; %の評価:+1回
==> (gcd 2 0)
==> (if (= 0 0)
        2
        (gcd 2 (% 2 0)))
==> 2                          ;; %の評価:合計4回