Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the interpreter he is
faced with is using applicative-order evaluation or normal-order evaluation. He defines
the following two procedures:
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
Then he evaluates the expression
(test 0 (p))
What behavior will Ben observe with an interpreter that uses applicative-order
evaluation? What behavior will he observe with an interpreter that uses normal-order
evaluation? Explain your answer. (Assume that the evaluation rule for the special form
if is the same whether the interpreter is using normal or applicative order: The predicate
expression is evaluated first, and the result determines whether to evaluate the consequent
or the alternative expression.)
A)
normal-order-evaluation 이라면 위의 식은 일단
(if (= 0 0) 0 (p)) 와 같이 펼쳐질 것이다.
그런데 주어진 식은 (test 0 (p)) 이기 때문에
(p)의 값을 계산하기 전에 (= 0 0) 이라는 조건에 맞기 때문에
결과로 0 이 나온다.
applicative order evaluation 라면 위의 식은 일단
인자로 들어온 (p)부터 계산해야 한다.
그런데 (p)를 구하면 그 결과로 (p)가 나오고 다시 (p)를 구해야 하기 때문에
무한루프를 돌아 결과가 나올 수 없다.
cf)scheme 은 applicative order evaluation 을 사용하는데, normal order evaluation 을 사용하는 언어로는 함수형 언어 heskell 이 있다고 한다.