04. Evaluation Strategies

1. Evaluation이란?

: 수학에서, 올바른 답을 얻기 위해 식(Expression)을 평가하는 방법은 중요한 이슈이다. λ Calculus에서도 마찬가지다.

 

 

2. 원칙과 전략

 

2-1. Evaluation Principle

: 식을 평가하기 위한 2가지 기본적인 원칙이 있는데, 각각 Eager Evaluation과 Lazy Evaluation이다.

 

Eager Evaluation

: 언제나 인자를 Evaluation하고, 함수를 인스턴스화(Instantiate) 한다.

 

Lazy Evaluation

: 인자가 필요한 시점에 Evaluation한다.

 

 

2-2. Evaluation Strategy

: 위의 기본적인 원칙에서 2개의 주요한 평가 전략(Evaluation Strategy)이 탄생하는데, 각각 Normal Order와 Applicative Order이다.

 

Normal Order(call by name으로도 알려져 있음)

: 언제나 맨 왼쪽의 것들부터 줄여나간다. 그리고 파라메터는 함수로 전달되기 전까지 평가하지 않는다.

 

Applicative Order(strict evaluation 또는 call by value로도 알려져 있음)

: 전달되었거나 대체된 파라메터를 먼저 평가한다.

 

 아래의 예제는, 각 Evaluation Strategy를 이해하는데에 도움이 될 것이다.

 

 

Example) 다음 식을 Normal Order, Applicative Order를 이용해서 평가(Evaluation)해보자.

 

(λ a.λ b.a)c((λ d.e)d)

 

 

Normal Order

: (λ a.λ b.a)c((λ d.e)d)  ->β  (λ b.a)[a＼c]c((λ d.e)d)  =  λ b.c((λ d.e)d)

->β  (c)[b＼((λ d.e)d)]  =  c

 

Applicative Order

: (λ a.λ b.a)c((λ d.e)d)  ->β  (λ a.λ b.a)c(e[d＼d])  =  (λ a.λ b.a)c(e)

->β  (λ b.a)[a＼c](e)  =  (λ b.c)(e)  ->β  c[b＼e]  =  c

 

 

※ 어떤 평가 전략을 쓰더라도 결과는 항상 같을까? 그렇지 않다. 위의 예와 같이, 다음 식을 평가해보자.

 

(λ x.a)((λ x.x x)(λ y.y y))

 

Normal Order

: (λ x.a)((λ x.x x)(λ y.y y))  ->β  a[x＼((λ x.x x)(λ y.y y))]  =  a

 

Applicative Order

: (λ x.a)((λ x.x x)(λ y.y y))  ->β  (λ x.a)(x x)[x＼(λ y. yy)]  =  (λ x.a)((λ y. yy)(λ y. yy))

->β  (λ x.a)(yy)[y＼(λ y. yy)]  =  (λ x.a)((λ y. yy)(λ y. yy)) - 무한 반복된다.

 

 

 각 평가 전략을 도입한 결과가 다르다. 따라서 어떤 평가 전략을 사용하느냐는 꽤 중요하다고 볼 수 있다. Church-Rosser 이론에 의하면, 식을 평가할 때 무한 반복되지 않고 끝날 수 있다면 Normal Order를 해당 식에 적용해도 끝날 수 있다. 그리고 똑같은 식에 두 평가 전략을 적용했을 때 모두 끝날 수 있다면, Alpha-conversion전까지 동일한 결과가 나온다.

 

 

3. Referrence

- λ Calculus tutorial