NoSyu의 주저리주저리 :: SICP Exercise 연습문제 4.2

이 문제는 eval 프로시저를 개선하는 아이디어를 냈을 때 생기는 문제점에 관한 얘기입니다. 책에 나오는 eval 프로시저는 다음과 같습니다.

   1: (define (eval exp env)

   2:   (cond ((self-evaluating? exp) exp)

   3:         ((variable? exp) (lookup-variable-value exp env))

   4:         ((quoted? exp) (text-of-quotation exp))

   5:         ((assignment? exp) (eval-assignment exp env))

   6:         ((definition? exp) (eval-definition exp env))

   7:         ((if? exp) (eval-if exp env))

   8:         ((lambda? exp)

   9:          (make-procedure (lambda-parameters exp)

  10:                          (lambda-body exp)

  11:                          env))

  12:         ((begin? exp)

  13:          (eval-sequence (begin-actions exp) env))

  14:         ((cond? exp) (eval (cond->if exp) env))

  15:         ((application? exp)

  16:          (apply (eval (operator exp) env)

  17:                 (list-of-values (operands exp) env)))

  18:         (else

  19:          (error "Unknown expression type -- EVAL" exp))))

이를 Louis reasoner는 procedure application이 더 많이 호출되기에 cond 밑보다는 위에 두는 것이 조금 더 효과적이라는 제안을 하였습니다. 왜냐하면 cond 구문은 if가 중첩된 것과 같기 때문입니다.

   1: (cond ((> x 0) x)

   2:       ((= x 0) (display 'zero) 0)

   3:       (else (- x)))

   1: (if (> x 0)

   2:     x

   3:     (if (= x 0)

   4:         (begin (display 'zero)

   5:                0)

   6:         (- x)))

위의 두 코드는 같은 코드입니다.

a. 이 계획의 잘못된 점은 다음과 같습니다.

Louis reasoner가 제시한 방법대로 eval 프로시저를 고친다면 다음과 같습니다.

   1: (define (eval exp env)

   2:   (cond ((self-evaluating? exp) exp)

   3:         ((variable? exp) (lookup-variable-value exp env))

   4:         ((quoted? exp) (text-of-quotation exp))

   5:         ; order changed

   6:         ((application? exp)

   7:          (apply (eval (operator exp) env)

   8:                 (list-of-values (operands exp) env)))

   9:         ((assignment? exp) (eval-assignment exp env))

  10:         ((definition? exp) (eval-definition exp env))

  11:         ((if? exp) (eval-if exp env))

  12:         ((lambda? exp)

  13:          (make-procedure (lambda-parameters exp)

  14:                          (lambda-body exp)

  15:                          env))

  16:         ((begin? exp)

  17:          (eval-sequence (begin-actions exp) env))

  18:         ((cond? exp) (eval (cond->if exp) env))

  19:         (else

  20:          (error "Unknown expression type -- EVAL" exp))))

즉, exp가 application임을 확인하는 코드가 assignment임을 확인하는 코드보다 위에 있어 먼저 실행이 될 것입니다. 그럼 여기서 어떤 문제가 발생하느냐?

바로 application? 프로시저에 문제점이 있습니다. 책에 나오는 해당 프로시저의 코드는 다음과 같습니다.

   1: (define (application? exp) (pair? exp))

즉, pair라면 true를 보내기에 assignment, definition 등의 것들도 모두 application? 프로시저를 실행하면 true가 나오게 될 것입니다. 따라서 eval 프로시저의 assignment?와 definition? 코드를 실행하지 못하고 무조건 application? 코드를 실행할 것입니다. 이렇게 되면 eval 프로시저의 코드 낭비일 뿐만 아니라 간단히 처리할 수 있는 것도 application으로 보아 복잡하게 처리해야 하는 단점이 있습니다.

b. 사실 이 문제에서 어떻게 도와줘야 한다는 것인지 이해가 되지 않았습니다.

Louis에게 도움이 되도록 언어 문법을 바꾸어서 프로시저 적용 식이 언제나 call로 시작되게 하자. 보기를 들어, (factorial 3)은 (call factorial 3)으로, (+ 1 2)는 (call + 1 2)로 된다.

라고 적혀있습니다. 그럼 나는 도대체 무엇을 해야 하는지 이해가 되지 않았습니다. make-begin 프로시저처럼 (cons 'call seq)라는 body를 수행하는 프로시저를 만들어야 한다는 뜻인지, application? 프로시저를 (pair? exp)에서 (tagged-list? exp 'call)로 바꿔야 한다는 것인지 잘 모르겠습니다. 영문판에는 이렇게 적혀있습니다.

Help him by changing the syntax of the evaluated language so that procedure applications start with call. For example, instead of (factorial 3) we will now have to write (call factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).

we will have to write라는 말은 이제부터 (+ 1 2)를 (call + 1 2)라고 쓸 것이라 해석했습니다. 따라서 Louis는 거기에 맞게 무엇인가를 수정해서 자신이 원래 계획했던 application? 프로시저 코드를 eval 프로시저 안의 cond에 위에 두자는 계획이 비효율적이지 않게 만들 수 있을 것입니다. 그럼 최종적으로 저는 Louis가 수정해야 하는 무엇인가를 찾는 문제로 해석하였습니다.

따라서 해당 문제의 답으로 application? 프로시저를 바꾸었습니다.