CIS194 6강 지연계산 내용 정리입니다.

하스켈 위키에서 Foldr Foldl Foldl’를 먼저 읽어보십시오.

미리 계산(strict evaluation)

지연 계산(lazy evaluation)에 대해 이야기하기 전에 그 반대인 미리계산에 대해 알아두면 좋다.

미리 계산 전략을 택하면 모든 함수 인자를 함수에 넘기기 전에 미리 계산한다. 예를 들어

f x y = x + 2

라는 함수가 있을 때, 미리계산 언어에서 f 5 (29^35792)라는 식을 계산하면 f에 인자를 넘기기 위해 먼저 5를 계산하고(이미 계산이 끝나있음), 29^35792를 계산한다(상당히 많은 계산을 수행해야 함).

하지만 이 특정 예제에서는 29^35792를 계산하는 것은 바보같은 짓이다. f가 y를 전혀 사용하지 않기 때문에 29^35792를 계산하기 위해 들인 모든 노력이 낭비된다. 이런 단점에도 불구하고 미리계산을 사용하고 싶어하는 이유가 있을까?

미리 계산의 잇점은 언제 어떤 일이 일어날지 예측하기 쉽다는 것이다. 미리 계산 언어는 보통 함수 인자를 어떤 순서로 평가할지(맨 왼쪽 인자부터 오른쪽 뱡항으로 차례로 평가할지, 맨 오른쪽 인자부터 왼쪽 방향으로 차례로 평가할지)까지도 정의해 놓곤 한다.

예를 들어 자바에서 다음과 같이 쓰면:

f (release_monkeys(), increment_counter())

원숭이를 풀어준 후 카운터가 증가되고, 그 후 그 두 함수의 결과가 f에 전달된다. 그리고 f가 그 두 결과를 사용하지 않더라도 원숭이를 풀어주는 일과 카운터 증가는 여전히 발생한다.

하지만 원숭이를 풀어주는 일과 카운터를 증가시키는 일이 서로 독립적으로 벌어질 수 있거나, 그렇지 않거나, 어느 한쪽이 다른 한쪽보다 먼저 일어나거나 하는 등의 조건이 f안에서 그 두 값을 언제 사용하느냐에 따라 달라진다면 혼동이 올 것이다. 이런 “부수효과(side effect)”가 있는 경우에는 미리 계산법을 택하는 것이 더 적합하다.

부수효과와 순수성

따라서 여기서 진짜 문제가 되는것은 부수 효과가 있는가 하는 것이다. “부수효과”라는 말은 식의 계산이 식 자체가 아닌 외부와 상호작용해 벌어지게 만드는 모든 것을 뜻한다. 이런 외부와의 상호 작용의 근본적인 문제는 상호 작용이 벌어지는 시점에 따라 결과가 달라질 수 있다는 점(time-sensitive)이다. 다음을 보자.

• 전역 변수를 갱신 - 전역변수의 값이 바뀌면 다른 식의 결과에 영향을 끼칠 수 있으므로, 갱신 시점에 따라 결과가 바뀐다
• 화면 출력 - 다른 화면 출력과 서로 뒤바뀌거나 뒤섞일 수 있으므로 출력 시점에 따라 결과가 바뀐다
• 파일이나 네트워크에서 데이터 읽기 - 파일의 내용이나 네트워크에서 들어오는 입력이 시간에 따라 다를 수 있다

앞에서 말한 것처럼 지연계산은 계산이 이뤄지는 시점을 정확히 추론하기 어렵다. 따라서 지연 계산 언어에 부수 효과를 포함시키는 것은 젼혀 직관적이지 않다. 역사적으로 하스켈이 순수 언어인 이유도 바로 그것이다. 하스켈 설계자들은 지연계산 언어를 바랐고, 부수효과를 금지하지 않으면 지연 계산을 전면 적용하는 것이 어려움을 금방 깨달았다.

하지만.. 부수 효과가 전혀 없는 언어는 유용하지 않다. 그런 언어로 할 수 있는 일은 프로그램을 인터프리터에 적재해 실행하고 식을 계산하는 것 뿐이다(음.. 뭔가 자주 들어본 말 아닌가?). 사용자 입력을 받을 수 없고, 결과를 출력할 수 없으며, 파일을 읽을 수도 없다. 하스켈 설계자들이 맞딱뜨린 문제는 바로 이런 부수 효과를 언어 자체의 순수성을 훼손시키지 않으면서 잘 정리된, 제한이 가해진 방식으로 처리하는 방법을 찾는 것이었다. 마침내 그들은 그 방법을 찾아냈는데, 그에 대해서는 나중에 설명한다(IO 모나드).

지연 계산

미리 계산을 이해했으므로 지연 계산이 어떻게 돌아가는지 살펴보자. 지연 계산 전략을 택하면 함수 인자 계산은 가능한 미뤄진다. 즉, 인자들은 그 값이 진짜 필요할 때까지 계산이 미뤄진다. 어떤 식을 함수의 인자로 넘기면 그 식의 결과를 계산하는 대신 식 자체를 평가되지 않은 식(unevaluated expression)으로 감싸서 전달한다(이를 썽크(thunk)라고 부른다).

예를 들어 f 5 (29^35792)에서 두번째 인자는 계산되지 않고 그냥 썽크에 들어가고 f가 호출된다. f가 이 두번째 인자 값을 사용하지 않으면 쓰레기 수집기는 썽크를 수집해 해제해 버린다.

패턴 매칭이 계산을 이끌어냄

그렇다면 언제 식을 계산하는 것이 “필요해질”까? 위 예에서는 함수가 자신의 인자를 사용하는 것에 촛점을 맞췄지만, 실제로는 그것이 가장 중요한 구분은 아니다. 다음 예를 보자.

f1 :: Maybe a -> [Maybe a]
f1 m = [m,m]

f2 :: Maybe a -> [a]
f2 Nothing  = []
f2 (Just x) = [x]

f1과 f2는 모두 인자를 사용한다. 하지만 이 둘 사이엔 차이가 있다. f1은 인자인 m을 사용하기는 하지만 실제로 m의 값이 무엇인지 알 필요는 전혀 없다. 여전히 m을 평가되지 않은 상태로 남겨둬도 문제가 없다. 단지 리스트에 그 평가되지 않은 식을 넣어두면 된다. 다른 말로 하면 f1 e라는 함수 호출에서 f1의 결과는 e가 어떤 값인지와는 전혀 관계가 없다.

반면 f2가 계속 진행하려면 인자에 대해 알아야만 한다. 인자가 Nothing으로 만들어졌는가, 아니면 Just로 만들어졌는가? 즉, f2 e를 계산하려면 f2의 결과가 e의 모양에 따라 바뀌기 때문에, 먼저 e를 계산해서 그 결과를 봐야 한다.

알아둬야 할 중요한 내용 한가지는 썽크는 패턴매칭을 진행하기 충분한 정도만 평가되지 더도 덜도 평가되지 않는다는 점이다! 예를 들어 f2 (safeHead [3^500, 49])를 계산한다면, f2는 safeHead [3^500, 49]를 호출하게 만들 것이다. 이 호출의 결과는 Just (3^500)이다. 여기서 3^500은 아직 계산이 이뤄지지 않았음에 유의하라. safeHead가 Just의 내부를 볼 필요가 없고, f2도 마찬가지로 Just의 내부를 알 필요는 없다. 따라서 3^500은 f2의 결과를 가져가 사용하는 쪽에서 Just에 들어있는 값을 쓸 때가 되서야 평가된다.

여기서 기억할 슬로건은 “패턴 매칭이 계산을 이끌어낸다”이다. 중요한 점을 다시 한번 반복한다.

• 식은 패턴 매칭이 일어날 때만 평가된다.
• … 이떄 식의 평가는 패턴 매치를 진행하기에 충분한 정도까지만 이뤄지고, 그보다 더 평가를 진행하거나 덜 평가를 진행하는 일은 없다!

이제 더 재미있는 예를 하나 살펴보자. take 3 (repeat 7)을 계산하려 한다. 다음은 repeat와 take의 정의다.

repeat :: a -> [a]
repeat x = x : repeat x

take :: Int -> [a] -> [a]
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs

평가 과정을 순서대로 나열하면 다음과 같다.

  take 3 (repeat 7)
      { 3 <= 0이 False이므로 두번째 절로 진행한다
    두번째 인자를 평가해야 두번째 절을 매치시킬 수 있다.
    따라서 repeat 7을 한번 펼친다. }
= take 3 (7 : repeat 7)
      { 두번째 절이 매치되지는 않았지만, 세번째 절은 매치된다.
      여기서 (3-1)은 아직 평가되지 않았음에 유의하라! }
= 7 : take (3-1) (repeat 7)
      { 첫번째 절을 결정하기 위해 (3-1) <= 0인지 검사해야 한다.
      따라서 (3-1)을 계산해야만 한다. }
= 7 : take 2 (repeat 7)
      { 2 <= 0은 False이므로 `repeat 7`을 다시 확장해야 한다.}
= 7 : take 2 (7 : repeat 7)
      { 앞의 (3-1)에서와 비슷한 로직을 따름 }
= 7 : 7 : take (2-1) (repeat 7)
= 7 : 7 : take 1 (repeat 7)
= 7 : 7 : take 1 (7 : repeat 7)
= 7 : 7 : 7 : take (1-1) (repeat 7)
= 7 : 7 : 7 : take 0 (repeat 7)
= 7 : 7 : 7 : []

(주의: 실제 함수 평가가 위 예제같은 순서로 일어날 수도 있지만, 하스켈 컴파일러들은 대부분 좀 더 복잡한 방식을 사용한다. 예를 들어 GHC는 그래프 축약(graph reduction)을 사용한다. 이는 평가할 식을 그래프로 표현하면서 식에서 공통되는 하위식을 포인터를 사용해 공유하는 방식이다. 이런 경우 불필요하게 하위식을 중복 계산하는 일이 없다. 예를 들어 f x = [x, x]라면 f (1+1)을 계산할 떄 덧셈을 단 한번만 수행한다. 리스트에 두번 나타나는 ‘x’는 서로 공유되기 때문에 (1+1)이라는 하위식은 한번만 계산된다)

결과

지연계산은 흥미롭지만 명백하게 알기는 어려운 결과를 하스켈 전반에 가져온다. 몇가지를 살펴보자.

순수성

지금까지 본 것처럼 지연 계산을 사용하려면 순수성을 사용할 수 밖에 없다.

공간 사용량 예측

지연계산이 모든 면에서 좋은 것만은 아니다. 단점 중 하나는 프로그램이 메모리를 얼마나 사용할지 예측하기 어렵운 경우가 생긴다는 점이다. (겉보기엔 문제 없어보이는) 다음을 보자.

-- 표준 foldl 함수
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl (+) 0 [1,2,3]를 계산하면 어떤 단계를 거쳐 계산이 끝날까?

  foldl (+) 0 [1,2,3]
= foldl (+) (0+1) [2,3]
= foldl (+) ((0+1)+2) [3]
= foldl (+) (((0+1)+2)+3) []
= (((0+1)+2)+3)
= ((1+2)+3)
= (3+3)
= 6

여기서 리스트 끝까지 진행하기 전까지는 누적 함수(+)의 결과를 사용하지 않는다. 따라서, 중간에 생기는 청크는 (((0+1)+2)+3)이라는 큰 덩어리가 된다. 이 청크가 맨 마지막에 6이라는 값으로 줄어든다. 여기서 적어도 두가지 문제가 있다. 첫번째는 이 과정이 그냥 효율적이지 못하다는 점이다. 중간에 보면 리스트를 굳이 다시 리스트와 유사한 어떤 것(누적함수의 청크)로 변환하는 것을 알 수 있다. 두번째 문제가 더 큰 문제고 알아채기도 어려운데, 바로 (((0+1)+2)+3)를 계산하려면 3과 2를 스택에 넣고 (0+1)을 계산해야 한다는 점이다. 그 후 다시 스택을 줄여가면서(unwinding) 덧셈을 쭉 수행해야 한다. 리스트 크기가 작은 이런 예제에서야 별 문제가 아니지만, 크기가 커지면 큰 문제가 된다. 보통 스택 공간은 크기가 그리 크지 않기 때문에 이런 경우 스택 넘침이 발생한다.

해법은 foldl 대신 약간 미리계산 성질을 가미한 foldl'을 사용하는 것이다. 특히 foldl'은 더 진행하기 전에 두번쨰 인자(누적함수)를 계산하게 만든다. 따라서 청크가 커지는 일이 없다.

  foldl' (+) 0 [1,2,3]
= foldl' (+) (0+1) [2,3]
= foldl' (+) 1 [2,3]
= foldl' (+) (1+2) [3]
= foldl' (+) 3 [3]
= foldl' (+) (3+3) []
= foldl' (+) 6 []
= 6

예를 보면 foldl'에서는 리스트를 축약하면서 바로바로 (+)를 계산함을 알 수 있다. 하지만 이 경우 약간 덜 지연계산을 수행한다는 사실을 알아야 할 것이다.

(foldl'이 어떻게 돌아가는지 관심이 있는 독자는 하스켈 위키의 seq부분을 보라)

쇼트서킷(short-circuit) 연산자

언어에 따라 &&나 ||등의 연산에서 쇼트 서킷을 지원하는 경우가 있다. 예를 들어 &&(논리곱, AND)에서는 첫번째 인자가 거짓이면 두번쨰 인자를 계산하지 않고 바로 거짓을 반환할 수 있다. 하지만 자바나 C++같은 언어에서는 이런 쇼트서킷 연산이 언어에서 특별한 경우로 정해져 있다. 일반적으로 미리계산 언어에서 함수의 인자는 함수를 수행하기 전에 계산이 끝난다. 따라서 &&나 ||에 대한 쇼트 서킷은 언어 의미에서 특별한 예외를 정의한 것이다.

하지만 하스켈에서는 예외 없이 쇼트 서킷을 구현할 수 있다. 예를 들어 (&&)나 (||)는 모두 단순한 라이브러리 함수일 뿐이다! 다음은 (&&)의 정의다.

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

여기서 (&&)가 두번쨰 인자에 대해서는 패턴 매칭을 하지 않음에 유의하라. 게다가 첫번째 인자가 False면 두번째 인자는 아예 무시된다. 결과적으로 (&&)는 자바나 C++의 && 연산자와 마찬가지로 쇼트 서킷을 지원한다.

물론 (&&)를 다음처럼 정의할 수도 있었을 것이다.

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

이 버전도 (&&)와 결과가 같지만, 동작 방식은 다르다. 예를 들어 다음을 생각해보자.

False &&  (34^9784346 > 34987345)
False &&! (34^9784346 > 34987345)

이들은 모두 False지만 두번째 식은 시간이 훨씬 많이 걸린다! 또는 다음을 생각해 보라.

False &&  (head [] == 'x')
False &&! (head [] == 'x')

첫번째 것은 다시 False이지만, 두번째 것은 예외가 발생하며 죽는다. 시도해 보라.

여기서 알아둘 것은 함수를 정의할 때는 지연계산과 관련해 흥미로운 문제들이 있다는 점이다.

사용자 정의 제어 구조

쇼트서킷 연산자에 사용했던 아이디어를 한 단계 더 깊이 적용하면 여러분 자신만의 제어 구조(control structure)를 만들 수 있다.

대부분의 언어는 내장 if 구문을 제공한다. 어떤 사람들은 if가 쇼트 서킷과 비슷하게 작동하기 때문에 그런 구조가 필요하다고 이야기한다. 조건식의 계산 결과에 따라 if문은 두 가지 중 오직 하나만을 실행한다. if문을 실행할 때마다 두 가지 모두 실행된다면 원래 목적에 반한 것이다!

하지만 하스켈에서는 if를 라이브러리 함수로 만들 수 있다!

if' :: Bool -> a -> a -> a
if' True x _ = x
if' False _ y = y

물론 하스켈에는 내장 if식이 있다. 하지만 나는 왜 그게 있어야 하는지 모르겠다. 하스켈에서 if는 그다지 많이 쓰이지 않는다. 보통은 패턴매칭이나 가드를 더 많이 사용한다.

무한 데이터 구조

지연 계산은 무한한 데이터 구조(infinite data structure)를 다룰 수 있다는 뜻이기도 하다. repeat 7과 같은 예를 이미 봤다. 이런 무한 데이터 구조를 만들어도 청크만 만들어지고, 이는 나중에 더 자라날 수 있는 데이터 구조의 “씨앗”을 심는 것과 비슷하다.

다른 유용한 구조로는 게임 상태 공간처럼 “실질적으론 무한인(effectively infinite)” 데이터 구조가 있다. 이는 이론상으론 유한이지만 실제로는 너무 커서 메모리에 다 들어갈 수 없는 데이터 구조를 말한다. 하스켈을 쓰면 모든 가능한 수를 정의할 수 있고, 필요할 때 상태 공간 트리를 검색할 수 있다.

파이프라이닝/통밀 프로그래밍

큰 데이터 구조를 “파이프라인”을 통해 차례로 변환하는 방식으로 코딩을 하면, 지연 계산으로 인해 각 변환이 마치 단계적 진행을 강제하는 장치처럼 작동한다. 실제 결과가 필요할 때는 각 단계의 결과과 차례로 파이프라인의 다음 단계로 전달된다.

동적 프로그래밍(dynamic programming, 동적계획법이라고도 부름)

동적 프로그래밍은 보통 복잡한 문제를 적절한 순서로 행렬을 채워넣어가면서 해결하는 방식이다. 행렬의 각 셀을 처리할 떄는 이미 이전에 계산된 다른 셀을 참조해 처리한다. 이때 계산 순서를 잘못 정의하면 쓸모없는 결과를 얻는다.

하지만 지연 계산을 사용하면 하스켈 런타임이 알아서 올바른 계산 순서를 정해준다. 예를 들어 0-1 배낭문제(knapsack problem)은 (무게나 부피가) 정해진 물건들을 (최대로 집어넣을 수 있는 무게나 부피가 정해진) 가방에 넣되 물건 전체의 가치가 최대가 되게 하는 물건들의 조합을 찾는 문제다. 그냥 배열 m을 그 자신에 대한 표준적인 재귀를 사용해 정의하면, 지연 계산이 셀을 계산하기에 적당한 순서를 알아서 찾아준다.

import Data.Array

knapsack01 :: [Double]   -- values 
           -> [Integer]  -- nonnegative weights
           -> Integer    -- knapsack size
           -> Double     -- max possible value
knapsack01 vs ws maxW = m!(numItems-1, maxW)
  where numItems = length vs
        m = array ((-1,0), (numItems-1, maxW)) $
              [((-1,w), 0) | w <- [0 .. maxW]] ++
              [((i,0), 0) | i <- [0 .. numItems-1]] ++
              [((i,w), best) 
                  | i <- [0 .. numItems-1]
                  , w <- [1 .. maxW]
                  , let best
                          | ws!!i > w  = m!(i-1, w)
                          | otherwise = max (m!(i-1, w)) 
                                            (m!(i-1, w - ws!!i) + vs!!i)
              ]

example = knapsack01 [3,4,5,8,10] [2,3,4,5,9] 20