SICP 연습문제 1.9 친절한 풀이

문제

다음 두 프로시저는 모두 0보다 큰 정수 두 개를 더하는 일을 하는데, 인자에 1을 더하는 inc 프로시저와 인자에서 1을 빼는 dec 프로시저를 가져다 쓴다.

(define (+ a b)
  (if (= a 0)
    b
    (inc (+ (dec a) b))))
  
(define (+ a b)
  (if (= a 0)
    b
    (+ (dec a) (inc b))))

맞바꿈 계산법에 따라 두 프로시저가 (+ 4 5)를 계산하는 과정을 밝혀라 이 프로세스는 반복하는가? 아니면 되도는가?

문제로 부터 얻은 것

반복하는 프로세스는 계산을 거듭해도 식이 늘어나지 않는 프로세스를 말합니다. 반복하는 프로세스를 설계함으로써 메모리를 아낄 수 있습니다. 또한 이 문제를 풀어 본다면, 설계한 프로시저가 반복하는 프로세스인지 되도는 프로세스인지 판단할 수 있는 방법을 알 수 있습니다.

문제풀이

아쉽게도 Dr.Racket으로는 +식을 프로시저로 다시 정의하지 못합니다. 때문에 이론적으로 문제를 풀어보겠습니다. 앞부분의 내용을 이해하신 분이라면, 두 프로시저 중 어느 것이 되도는 프로세스이고 반복하는 프로세스인지 눈치챌 수 있을 것입니다. 각각의 프로시저의 실행되는 과정을 맞바꿈 계산법으로 나타내면 다음과 같습니다.
if식을 따로 과정에 넣지는 않겠습니다.

a. 1번 프로시저

(+ 4 5)
(inc (+ (dec 4) 5))   
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5))        
(inc (inc (+ 2 5))     
(inc (inc (inc (+ (dec 2) 5))))        
(inc (inc (inc (+ 1 5))))  
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

b. 2번 프로시저

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8
(+ (dec 1) (inc 8))
(+ 0 9)
9

되도는 프로세스는 프로세스가 진행함에 따라 계산을 뒤로 미루는 탓에 식이 길게 늘어지는 특징이 있습니다.^{교재 44p} 반대로 반복하는 프로세스는 프로세스가 진행하면서 식의 길이가 늘거나 줄어들지 않습니다. 따라서 1번 프로시저는 되도는 프로세스이고, 2번 프로시저는 반복하는 프로세스입니다.

이 문제의 풀이과정 중에서 왜 (dec (dec (dec (dec 5))))와 같은 식으로 표현하지 않는지 궁금하신 분들도 계실것입니다. 맞바꿈 계산법은 정의대로 계산법과는 다릅니다. 정의대로 계산법으로 계산한다면, 끝까지 dec계산을 넘기기 때문에 (dec (dec (dec (dec 5))))같은 모습이 나오지만, 맞바꿈 계산법은 (dec 4)를 3으로 바꾸어서 계산하기 때문에 위와 같은 결과가 도출됩니다.

읽어주셔서 감사합니다.