2010-10-27

問題1.20

Common Lispでは、

(defun gcd (a b)
  (if (zerop b)
      a
      (gcd b (remainder a b))))

実行されるremainderを#|→|#で示す。正規順序評価では、

(gcd 206 40)

(if (zerop 40)
    206
    (gcd 40 (remainder 206 40)))

(gcd 40 (remainder 206 40))

(if (zerop #|→|#(remainder 206 40))
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

;; 1st remainder call

(if (zerop 6)
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

(gcd (remainder 206 40)
     (remainder 40 (remainder 206 40)))

(if (zerop (remainder 40 #|→|#(remainder 206 40)))
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

;; 2nd remainder call

(if (zerop #|→|#(remainder 40 6))
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

;; 3rd remainder call

(if (zerop 4)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

(if (zerop (remainder (remainder 206 40)
                      (remainder 40 #|→|#(remainder 206 40))))
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

;; 4th remainder call

(if (zerop (remainder #|→|#(remainder 206 40) #|→|#(remainder 40 6)))
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

;; 5th and 6th remainder calls

(if (zerop #|→|#(remainder 6 4))
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

;; 7th remainder call

(if (zerop 2)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
                           (remainder 40 (remainder 206 40)))))

(if (zerop (remainder (remainder 40 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40 #|→|#(remainder 206 40)))))
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

;; 8th remainder call

(if (zerop (remainder (remainder 40 #|→|#(remainder 206 40))
                      (remainder #|→|#(remainder 206 40)
                                 #|→|#(remainder 40 6))))
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

;; 9th, 10th and 11th remainder calls

(if (zerop (remainder #|→|#(remainder 40 6) #|→|#(remainder 6 4)))
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

;; 12th and 13th remainder calls

(if (zerop #|→|#(remainder 4 2))
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

;; 14th remainder call

(if (zerop 0)
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

(remainder (remainder 206 40) (remainder 40 #|→|#(remainder 206 40)))

;; 15th remainder call

(remainder #|→|#(remainder 206 40) #|→|#(remainder 40 6))

;; 16th and 17th remainder calls

#|→|#(remainder 6 4)

;; 18th remainder call

2

となり、18回実行される。作用的順序では、

(gcd 206 40)

(if (zerop 40)
    206
    (gcd 40 (remainder 206 40)))

(gcd 40 #|→|#(remainder 206 40))

;; 1st remainder call

(gcd 40 6)

(if (zerop 6)
    40
    (gcd 6 (remainder 40 6)))

(gcd 6 #|→|#(remainder 40 6))

;; 2nd remainder call

(gcd 6 4)

(if (zerop 4)
    6
    (gcd 4 (remainder 6 4)))

(gcd 4 #|→|#(remainder 6 4))

;; 3rd remainder call

(gcd 4 2)

(if (zerop 2)
    4
    (gcd 2 (remainder 4 2)))

(gcd 2 #|→|#(remainder 4 2))

;; 4th remainder call

(gcd 2 0)

(if (zerop 0)
    2
    (gcd 0 (remainder 2 0)))

2

となり、4回実行される。

投稿者 時刻:
ラベル:

1 件のコメント:

  1. llibra2010/10/27 6:24:00

    正規順序評価の定義を、もうちょっと詳しく書いて欲しかった。(f (+ 1 1) (+ 1 (+ 1 1)))のとき、どれから評価するか、とか。細かいことはどうでもいいのかもしれないけど、モヤモヤする。

    返信削除

登録: コメントの投稿 (Atom)