SICP 연습문제 1.5 풀이

연습문제 1.5

아래와 같이 두 프로시저를 정의하였다.

(define (p) (p))

(define (test x y)
    (if (= x 0)
        0
        y))

그런 다음 아래 식의 값을 구해볼 때, applicatve-order evalutaion을 따르는 경우와 normal-order evaluation을 따르는 경우에 대해 각각 구해보자.

(test 0 (p))

해설

Applicative-order evaluation

책의 내용에 따르면 Applicative-order evaluation은 연산자와 피연산자를 먼저 계산하고서, 연산자 프로시저를 연산할 인자에 맞춘다. 따라서 test, 0과 (p)의 값을 먼저 구해야 하는데, test와 0은 문제 없지만 (p)를 구하려면 무한 루프에 빠지게 된다.

개인적으로 이해하기론 python에서는 이러한 모양새인 것 같다.

def p():
    return p()
p()

실제로 이를 실행시켜보면 무한 루프에 빠져 maximum recursion depth exceeded 에러를 만나게 된다.

Normal-order evaluation

Normal-order evaluation은 primitive operator로만 이루어진 식이 나올 때 까지 피연산자의 계산을 미루고, 더 이상 펼치지 못하는 식을 얻을 때 그 식의 값을 구하는 방법이다. 이에 따라 (test 0 (0)) 를 primitive operator만 남을 때 까지 펼쳐보면 아래와 같다.

(if (= 0 0)
    0
    (p))

따라서 이 식의 값은 0이다.

Note: 영어 해설의 내용이 더 와닿았다.

When an interpreter uses normal-order evaluation, it will “fully expand and then reduce”. In this model, the interpreter will not evaluate the operands until their values are actually needed. In that case,

참고

• https://sicp-solutions.net/post/sicp-solution-exercise-1-5/