how lazy evaluation works in haskell

Lazy evaluation이 동작하는 방식

게으른 평가(lazy evaluation)는 하스켈 프로그램이 실행될 때 광범위하게 사용된다. 게으른 평가의 적용은 코드를 보다 단순하게 만들어줄 수 있지만, 초보자에게는 종종 메모리 사용과 관련된 함정이 되기도 한다. 예를 들어 foldl (+) 0 [1..10^8] 이라는 간단한 표현식은 계산에 있어 수기가바이트의 메모리를 요구한다.

게으른 평가는 일종의 트레이드 오프이다. 이는 코드를 단순하게 만들어주지만 그것이 튺정한 프로그램에서 실제로 어떻게 평가하는지 완전히 이해할 수는 없게 된다. (케바케라서…)

그래프 축약

하스켈 프로그램은 표현식을 평가하는 것으로 실행된다. 다음 함수를 예로 들어보자.

square x = x * x

그리고 다음 표현식을 평가해보자.

square (1 + 2)

이 식은 square라는 함수의 인자를 (1+2)라는 표현식으로 대체하여 다음과 같은 표현식으로 치환된다.

square (1+2)
=> (1+2)*(1+2)

그리고 (+), (*) 함수가 계속해서 평가된다.

(1+2) * (1+2)
=> 3 * (1 + 2)
=> 3 * 3
=> 9

다시 처음의 식을 그래프로 표현해보자.

square _
       |
       + _ _
         | |
         1 2

각각의 라인은 함수의 적용이다. 맨 앞은 함수의 이름, 그 뒤 언더스코어로 표시한 빈 칸들은 각각의 인자가 된다. 이러한 그래프는 마치 컴파일러가 메모리 포인터를 이용해서 표현식을 나타내는 방식과도 많이 닮아 있다.

프로그래머가 작성하는 모든 함수들은 축약법칙을 따르는데, 이는 함수 적용이 결국 우변의 표현식으로 대체된다는 의미이다.

square _  ==>  * _ _
       |         \ |
       x            x

위 그래프에서 x는 함수의 인자이고, 표현식일 수 있기 때문에 서브 그래프를 함축한 표현이된다. 이 때 (*) 함수의 두 인자가 동일한 그래프를 가리키고 있는 점에 유의하자. (하스켈의 모든 것은 함수이므로, 같은 이름은 같은 포인터라 봐도 무방하다.)

어떤 그래프가 축약 가능한 경우 이를 reducible expression이라고 하고 줄여서 redex (여기서는 리딕스라 하겠다.)라 부른다.

square _
       |
       + _ _
         | |
         1 2

위 그래프에서 1행과 2행의 그래프는 각각 리딕스이다. 각각의 리딕스를 위에서부터 순차적으로 축약해 나가보면

square _ (r)        ==> * _  _         ==> * _ _ (r) ==> 9
       |                  ㄴ |                \|
       + _ _                 + _ _ (r)         3
         | |                   | |
         1 2                   1 2

위와 같이 축약을 거듭해 나가는 것으로 최종 값이 산출된다. 최종값 9는 더 이상 축약될 수 없는 데 이러한 모양의 그래프를 normal form이라 하다. 노멀폼에는 이러한 단위 숫자만 올 수 있는게 아니라 특정한 콘크리트 타입의 상수(중 일부)가 올 수 있다. 이를테면 리스트 말이다.

: _  _
  |  |
  1  : _  _
       |  |
       2  : _  _
            |  |
            3  []

위 그래프는 리스트 1:2:3:[]을 나타낸다. 이 리스트는 하나의 데이터타입에 대한 값이므로 더 이상 축약될 수 없고, 따라서 노멀폼이다. 즉, 어떤 그래프의 최상위 노드가 컨스트럭터일 때 해당 그래프는 (항상은 아니다) 노멀폼이된다.

노멀폼이 되는 조건이 두 가지 있는데, 하나는 유한해야 한다는 것과 다른 하나는 순환이 없어야 한다는 것이다. 다음 식을 보자.

ones = 1 : ones

이 식은 그래프로 표현하면


┌───────┐ : _ _ │ | │ │ 1 └─┘

위와 같이 순환하는 구조가 된다. 이 그래프는 리딕스가 아니다. 그러면서도 순환이 발생하기 때문에 노멀폼도 아니다. 리스트의 꼬리는 재귀적으로 자기자신을 가리키면서 결과적으로 무한리스트가 된다. 이와 같이 노멀폼을 가지지 않으면서 무한 루프에 대응하게 되는 표현식들이 존재할 수 있다.

하스켈에서는 실질적으로 표현식 평가가 바로 노멀폼으로 이어지지는 않는다. 보통은 그래프를 축약해나가다가 weak head normal form을 만나면 일단 평가를 멈추게 된다. (약어로 WHNF라 한다) 우선 그래프의 탑노드가 컨스트럭터라면 WHNF라 말할 수 있는데, 예를 들어 (7+12):[] 은 다음과 같이 WHNF가 된다.

:  _   _
   |    \
  + _ _  []
    |  \
    7  12

위 그래프는 노멀폼은 아니지만, 최상위 노드가 :이므로 WHNF이다. 반면, WHNF가 아닌 형태의 그래프는 청크 혹은 미평가식이라한다. 위 그래프에서 최상위 노드는 컨스트럭터이지만, 첫번째 인자는 미평가된 식이다.

이러한 WHNF에서 흥미로운 점은 위에서 언급한 ones이다. 이 그래프의 탑노드는 컨스트럭터이므로, 하스켈에서는 무한 리스트를 표현하고 다룰 수 있다. 이런 점은 코드를 보다 모듈단위가 될 수 있게 해준다.

평가 순서, 게으른 평가

하나의 표현식이 여러 리딕스를 포함하는 일은 흔하다. 이 때 이들을 축약하는 순서가 중요할까?

eager evaluation라 불리는 축약방법은 함수 파라미터를 적용하기 전에 먼저 축약한다. 따라서 함수가 실제로 평가되기 전에 파라미터들이 모두 평가된다. 대부분의 언어가 이런 방식을 적용한다.

하지만 하스켈 컴파일러는 좀 더 다른 방식을 적용한다. 이른바 게으른 평가인데, 상위 노드를 먼저 평가하려 한다.

&& 연산자가 평가되는 방식을 살펴보자. 다음의 식을 생각해보자.

('H' == 'i') && ('a' == 'm')

이 연산식은 아래와 같은 그래프로 구성된다.


(&&) _ _ :1 │ │ │ └ (==) _ _ :3 │ │ \ │ 'a' 'm' (==) _ _ :2 │ \ 'H' 'i'

위 그래프에서 :2, :3은 축약 가능한 리딕스인데 그 중 먼저 계산되는 것은 :2이다. (==) 'H' 'i'False로 축약된다. 축약된 식은 (&&) False x 가 되는데, 하스켈은 이 때 탑노드를 평가하려고 시도한다. &&의 정의에 따라,

(&&) :: Bool -> Bool -> Bool
True && x = x
False && x = False

이는 두 번째 파라미터가 노멀폼이 되든 안되든 탑 노드가 리딕스가 된다. 그리고 축약하면 False가 된다.

이를 수식형태로 다시 표현하면 다음과 같다.

('H' == 'i') && ('a' == 'm')
=> False && ('a' == 'm')
=> False

위에서 계산했던 square 의 식을 써보면

square (1 + 2)
=> let x = (1 + 2) in x * x
=> let x = 3 in x * x
=> 9

시간복잡도와 공간복잡도

시간

표현식을 평가하는데 얼마나 많은 단계가 필요할까? “급한 평가”에서 이는 간단하다. 모든 함수 평가에 대해서 각 파라미터를 평가하는데 걸리는 시간의 총 합과 함수를 계산하는데 드는 시간을 더하면 된다. 하지만 느린 평가에서는? 게으른 평가는 가능한 평가를 뒤로 미룬다 뿐이지 실제로 급한 평가보다 계산을 더 많이 하지는 않는다. 대신 위에서 본 바와 같이 운이 좋다면 미평가식을 포함한 계산식은 리딕스가 될 수가 있고 이 경우에는 급한 평가에 비해서 적은 단계로 계산이 수행될 수 있다.

공간

게으른 평가는 시간과 공간의 트레이드 오프이다. 게으른 평가는 시간에 있어서는 이익을 볼 수 있지만 공간에 대해서는 손해를 볼 수도 있다. 계산에 필요한 메모리의 크기는 미평가식의 크기만큼이나 쓰이기 때문에 노멀폼에 비해서 엄청나게 큰 용량의 메모리를 쓸 경우가 있다.

특히 리스트를 접는 foldl 함수의 경우 느리게 평가되면서 단순히 연속된 자연수의 합을 구하는 계산이 수십기가바이트의 메모리를 요구하는 경우가 있을 수 있다.