SICP 연습문제 1.20 친절한 풀이

문제

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

문제로 부터 얻은 것

정의대로 계산법을 사용하게 되면
if식 안에서의 계산과 밖에서의 계산이 분리되어서 훨씬 더 많은 계산을 하게될 수도 있다는 것을 알았습니다.

문제풀이

참고-GCD 알고리즘 증명

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

a. 정의대로 계산법

이 문제에서 주의할 점은,
if식의 술어의 참 거짓을 확인할 때는 remainder를 사용하여 b값을 구하지만 계산된 결과가 다음 단계로 넘어가지는 않는다는 것입니다.
if식 안에서 remainder를 실행하고 밖에서도 한번 더 실행한다.

그 시점까지 실행된 remainder의 총 수를 뒤에 표시하겠습니다.

(gcd 206 40)

(gcd 40 (remainder 206 40))

(if (= (remainder 206 40) 0)) <-------------------------------------------------------1번 실행 총 1번

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

(if (= (remainder 40 (remainder 206 40) 0))) <-----------------------------------------2번 실행 총 3번

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

(if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0)) <------------4번 실행 총 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)))))

(if (= (remainder (remainder 40 (remainder 206 40)) 
                  (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))  <-------7번 실행 총 14번 
   0))    


(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))              <----------4번 실행 총 18번

총 18번 실행되는 것을 볼 수 있습니다.
혹시 이해가 안되시는 분들은, 마지막 줄을 처리하기 전까지는 if식의 술어부분만 계산한다는 것을 생각해주시기 바랍니다.

b. 인자먼저 계산법

(gcd 206 40)
(gcd 40 (remainder 206 40)) <------1번 실행 총 1번
(gcd 40 6)
(gcd 6 (remainder 40 6))    <------1번 실행 총 2번
(gcd 6 4)
(gcd 4 (remainder 6 4))     <------1번 실행 총 3번
(gcd 4 2)
(gcd 2 (remainder 4 2))     <------1번 실행 총 4번
(gcd 2 0)
0

총 4번 실행되는 것을 볼 수 있습니다.

c. 결론

정의대로 계산법을 사용하게 되면, if식 안에서의 계산과 밖에서의 계산이 분리되어서 훨씬 더 많은 계산을 하게될 수도 있습니다.

읽어주셔서 감사합니다.