[연습문제] - 1.20

Study/SICP 2008. 4. 1. 23:49

문제)프로시저가 만들어 내는 프로세스는 마땅히 실행기의 계산 규칙에서 영향을 받는다. 앞서 나온 gcd프로시저를 보기 삼아서, 이런 문제를 살펴보자. 먼저 이번에는 (1.1.5절에서 선보인) normal-order evaluation을 따른다고 하자. (if를 normal-order evaluation방법은 연습문제 1.5에 있다.) substitution으로 (gcd 206 40)를 (normal-order)구하는 프로세스를 보이고, remainder 연산을 어디에서 쓰는지 표시하자. 프로세스가 끝날 때까지 remainder 연산을 얼마나 쓰는가? applicative-order evaluation하는 경우라면 또 어떠한가?


풀이)

normal-order로 구하는 프로세스는 따로 정의 할 필요 없을듯 해서 앞에서 나온 gcd프로시저를 그대로 사용

(define (gcd a b)

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

(remainder a b) 는 a를b로 나눈 수의 나머지를 취하는 프로시저다.. c언어에서의 %연산이라 생각하면됨.


normal-order evaluation 일때 remainder연산의 사용횟수 = 'rmd' 라 두고!!

(gcd 206 40)

    (if (= 40 0)  206  (gcd 40 (remainder 206 40)))       40 = 0 아니므로 뒤의 결과를 취함 rmd = 0

-> (gcd 40 (remainder 206 40)                                                                               rmd = 0

-> (if (= (remainder 206 40) 0)

        40

        (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))                          rmd = 0

-> (if (= 6 0)

        40

        (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))                          rmd = 1

-> (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))                                rmd = 1

-> (if (= (remainder 40 (remainder 206 40)) 0)

        (remainder 206 40)

        (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))         rmd = 1

-> (if (= 4 0)

         (remainder 206 40)

        (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))         rmd = 3

-> (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))          rmd = 3

-> (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0)

        (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))))))

                                                                                                                           rmd = 3

-> (if (= 2 0)

          (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))))))

                                                                                                                           rmd = 7

-> (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)))))

                                                                                                                           rmd = 7

-> (if (= (remainder (remainder 40 (remainder 206 40))

                            (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 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)))))))

                                                                                                                           rmd = 7

-> (if (= 0 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)))))))

                                                                                                                           rmd = 14

-> (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))                       rmd = 14

-> 2                                                                                                                      rmd = 18

normal-order evaluation 하는 경우에는

프로세스가 끝날때 까지 사용한 remainder연산은 18번 이다.



applicative-order evaluation 일때 .... 마찬가지로 remainder연산을 rmd로 두고....

(gcd 206 40)

-> (if (= 40 0)

         206

         (gcd 40 (remainder 206 40))                                                                          rmd = 0

-> (gcd 40 (remainder 206 40))                                                                               rmd = 0

-> (gcd 40 6)                                                                                                         rmd = 1

-> (if (= 6 0)

        40

        (gcd 6 (remainder 40 6)))                                                                               rmd = 1

-> (gcd 6 (remainder 40 6))                                                                                    rmd = 1

-> (gcd 6 4)                                                                                                           rmd = 2

-> (if (= 4 0)

         6

         (gcd 4 (remainder 6 4)))                                                                                rmd = 2

-> (gcd 4 (remainder 6 4))                                                                                       rmd = 2

-> (gcd 4 2)                                                                                                           rmd = 3

-> (if (= 2 0)

         4

         (gcd 2 (remainder 4 2)))                                                                                 rmd = 3

-> (gcd 2 (remainder 4 2))                                                                                       rmd = 3

-> (gcd 2 0)                                                                                                            rmd = 4

-> (if (= 0 0)

         2

         (gcd 0 (remainder 2 0)))                                                                                 rmd = 4

-> 2

applicative-order evaluation 하는 경우에는

프로세스가 끝날때 까지 사용한 remainder 연산은 4번이다.

Posted by hazeyun
,