예제로 이해해보는 모나드 – 파서구현하기

Applicative Functor가 Functor를 확장하는 것처럼, 모나드도 Applicative의 차원을 확장한 것이라 할 수 있습니다. 하지만 그것은 단순한 기술적인 설명일 뿐이며 모나드에서는 그 모나드가 가지는 계산적 맥락이 어떤 특성을 갖는지를 이해하는 것이 중요합니다. (그리고 이것은 매우 추상적이라 쉽지 않습니다.)

이런 경우 구체적인 예를 들어가며 살펴보는 것이 좋은데, 모나드의 경우 흔히 파서(Parser)를 예로 듭니다. 파서란 어떤 해석기 같은것을 만들 때, 가장 앞단에 위치하는 부분으로 (주로) 문자열로 이루어진 데이터를 정해진 문법적 규칙(리터럴)에 맞게 토큰으로 분리하고, 각 토큰이 갖는 논리적 관계에 맞게 트리를 만들어내는 논리장치입니다. 어떠한 데이터, 특히 코드를 해석하는 모든 프로그램은 파서를 가지고 있습니다. 모든 언어의 컴파일러나 인터프리터는 기본적으로 해석기 이므로 파서가 필요합니다. 웹브라우저는 HTML 코드를 읽고 그 문법적 구조를 이해해야 하기 때문에 HTML 코드를 잘라내는 파서를 가지고 있습니다.

실질적으로 유용하고 의미있는 작업을 하는 파서를 만드는 것은 사실 매우 어렵고 복잡한 일입니다. 여기서는 단지 파서를 핑계로 모나드를 이해하는데 도움을 주려하기 때문에 아주 단순하면서도 쓸모없는 간단한 파서의 타입을 정의해보겠습니다.

예제로 이해해보는 모나드 – 파서구현하기 더보기

하스켈에서 메모이제이션 구현하기

하스켈의 메모이제이션

하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 f와 그 인자 x가 있을 때 최초 f(x)가 계산되고 나면 그 이후에 f(x)가 필요한 경우에 불필요한 반복 계산이 필요하지 않은 것 처럼 들린다. (왜냐면 f(x)는 이미 이전에 계산되어 값으로 축약되었고, 그 사이에 어떤 일이 있었든지 간에 같은 인자에 대해서는 하스켈의 함수는 같은 결과를 내놓을 것이기 때문이다.)

하지만 이것은 다른 문제이다. 이는 하스켈이 기본적으로 모든 함수 적용 연산에 대해 그 결과를 캐싱한다는 이야기인데, 실제로 이런 일은 일어나지 않는다. 당연하게도 프로그램의 생애 주기가 얼마나 될지 알 수 없기 때문에 캐싱에 무한정 리소스를 소모할 수도 없기 때문이다. (그외에도 몇 가지 이유가 더 있겠지만…)

따라서 메모이제이션이 필요하다면 이는 프로그래머가 직접 수행하도록 코드를 작성해야 한다. 다른 언어에서 메모이제이션은 키-값 쌍으로 이루어지는 맵 구조를 이용해서 한 번 계산된 결과를 이 맵내에서 업데이트하는 식으로 처리한다. 예를 들어 파이썬의 메모이제이션은 다음과 같이 이루어진다.

memo = {}
def memoized_func(n):
  if n in memo:
    return memo[n]
  result = ..... 
  memo[n] = result
  return result

그런데 하스켈에서는 어떨까? 하스켈에서는 이러한 방식을 사용할 수 없다. 이 동작은 함수가 호출되었을 때 함수 외부의 값을 변경하는 부수효과를 동반하는데, 순수함수형 언어에서는 이런 동작이 허용되지 않는다.

그렇다고 방법이 없는 것은 아니다. 메모이제이션의 기본적인 아이디어는 이미 계산된 값을 어딘가 저장하고 있는 것이다. 따라서 “함수를 값으로 변환한다”는 대담한 발상을 기반으로 다음과 같이 처리할 수 있다. 대신에 우리가 염두에 두는 메모이제이션을 적용할 함수는 Int -> a 타입의 함수라고 하자.

  1. 메모이제이션을 위해서는 Inta 타입의 값을 각각 짝지어놓을 수 있는 어떤 자료 구조가 필요하다.
  2. List 타입을 생각해보면 (!!)를 이용해서 인덱스(Int)로 값(a)을 액세스할 수 있다.
  3. 따라서 함수호출은 함수를 사상한 리스트에 대한 원소 접근으로 환원해볼 수 있다.

실제로 이 아이디어가 가능한지 시험해보자.

테스트 1

기본적으로 적당히 오래 걸리는 함수 하나를 생각해보자. 소수 판별 검사가 좋겠다. 하스켈에서의 소수 판별 검사 함수는 적당히 느리게 작성하면 아래와 같이 쓸 수 있다.

isPrime :: Int -> Bool
isPrime n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]

엄청 간단하다. 2보다 작은 경우 그리고 2와 3인 경우를 제외하면 임의의 자연수 N에 대해서 2…N-1 까지 자연수로 N을 나눠서 나누어 떨어지는 경우가 한 번도 없으면 소수가 되는 것이다.

그러면 이 함수의 메모이제이션 버전은 어떨까? 하스켈의 느긋한 연산을 활용할 수 있다.

isPrimeMemo :: Int -> Bool
isPrimeMemo = ((map f [0..]) !!) where
            --  ~~~~~~~~~~~ 소수판별결과를 리스트로 만들어서 N 번째 값을 구한다.
      f n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]

무척이나 이상하게 생겼다. 만약 isPrimeMemo 173을 호출하면 어떤 일이 생길까?

  1. isPrimeMemo 173은 기본적으로 (!!) 173 . map f $[0..]이다. 따라서 0부터 시작하는 무한리스트를 f로 맵핑한 결과에서 173번째 원소를 찾는다.
  2. fisPrime과 동일한 내용으로 정의되어 있다.
  3. 다시 isPrimeMemo 173이 호출되었다. 이때 문제의 리스트 (함수 f의 적용 결과가 모여있는)에서 최소한 173번째 원소까지는 맵핑이 완료된 상황이기 때문에 계산을 거치지 않고 그 값을 찾아서 리턴하게 된다.

실제로 두 번 이후의 호출부터는 빨라지는지 확인해보자. 이를 위해 함수 호출의 시간을 계산하는 timeIt 함수를 사용한다. 이 함수는 timeit이라는 패키지에 포함되어 있는데, 기본적으로 설치되어 있지 않으니 cabal을 이용해서 설치해야 한다.

테스트는 1에서 1만까지의 소수를 찾아서 그 합을 계산해서 출력하는 것을 4회 시행해본다.

import Control.Monad
import System.TimeIt

isPrimeMemo :: Int -> Bool
isPrimeMemo = ((map f [0..]) !!) where
      f n | n < 2     = False
          | n < 4     = True
          | otherwise = all ((/= 0).(n `mod`)) [2..(n-1)]
          
main = do
    print "START"
    forM_ [1..4] $ \_ -> timeIt . print . sum . filter isPrimeMemo $ [1..10000]

결과는 다음과 같다.

"START"                  
5736396                  
CPU time:   2.42s        # 최초 실행시
5736396                  
CPU time:   0.27s        # 이후부터는 매우 빠르게 실행된다.
5736396                  
CPU time:   0.28s        
5736396                  
CPU time:   0.28s        

근데 가만보면 메모아이즈된 함수의 꼴이 원래 외부에 정의한 함수 모양과 완전히 똑같다. 따라서 일반적인 Int -> a 타입의 함수를 메모아이즈 할 수 있는 형태로 함수를 만들어 볼 수 있을 것이다.

memoize :: (Int -> a) -> Int -> a
memoize fBody = ((map fBody [0..]) !!)

isPrimeMemo = memoize isPrime

이렇게 정의한 뒤 테스트해보아도 같은 결과를 얻을 수 있다.

테스트 2

메모이제이션이나 수행속도 최적화에 관련해서 소수 판별 검사보다도 더 유명한 문제가 있으니 바로 피보나치 수열의 일반항을 구하는 것이다. 사실 피보나치 수열의 일반항은 하스켈에서는 메모이제이션 보다는 무한 리스트를 느긋한 방식으로 다루는 식으로 매우 우아하고 효율적으로 계산할 수 있는데, 여기서는 그게 목적이 아니므로 교과서의 정의를 충실히 따라 보도록 하자.

fibo :: Int -> Integer
fibo n | n < 3     = toInteger $ n - 1
       | otherwise = fibo (n-1) + fibo (n-2)
       
fiboMemo = memoize fibo

-- 35정도면 적당히 느릴 것으로 보여진다.
main = do
    print "START"
    forM_ [1..4] $ \_ -> timeIt . print . fiboMemo $ 35

결과는 다음과 같다. 뭔가 예상했던 것과는 다르다.

"START"           
5702887           
CPU time:  17.95s 
5702887           
CPU time:   0.00s 
5702887           
CPU time:   0.00s 
5702887           
CPU time:   0.00s 

2차 이후의 시행은 매우 빠르게 캐싱된 값을 성공적으로 사용했다는 것을 알겠다. 그런데 첫 시행이 너무 오래 걸렸다. 왜 이런 문제가 생길까? 그것은 fibo 함수가 isPrime과는 달리 재귀적으로 자신을 호출하기 때문이다. fiboMemo의 호출과정을 따라가보면

  1. fiboMemo 35가 호출되면 (map fibo [0..]) !! 35가 호출된다.
  2. 이 때 fibo 35를 평가하게되고, 이는 fibo 34 + fibo 33 이런식으로 계산해야 하는 양이 폭발하기 시작한다. 그런데 메모아이즈 된 함수는 fiboMemo이지 fibo가 아니다. 최종적으로 fiboMemo 35의 값은 캐싱이 되지만, 그 중간과정에 쓰인 fib는 그렇지 못하기 때문에 반복 계산을 엄청나게 많이 한다.

이와 비슷한 문제가 Swift에서도 있었다. WWDC에 소개된 예제에서는 그야말로 mind-blowing한 방법을 동원해서[^1] 이 문제를 해결했다. 하스켈에서의 해법도 이와 거의 유사하다.

fibo2 :: Int -> Integer
fibo2 n | n < 3     = toInteger $ n - 1
        | otherwise = fiboMemo2 (n-1) + fiboMemo2 (n-2)

fiboMemo2 = memoize fibo2

main = do
  print "START"
  forM_ [1..4] $ \_ -> timeIt . print . fiboMemo2 $ 35

절차형 언어에 익숙한 사람이라면 이해가 가지 않을 수 있다. 저 두 함수는 뭔가 정의의 순서 자체가 꼬인게 아닌가? 싶은데, 하스켈은 “느긋하게” 계산하고, 또 “순수함수”이기 때문에 정의의 순서나 계산의 순서가 별로 중요하지 않다. 코드 앞쪽에 언급된 함수 정의나 표현식은 필요할 때가 되어서야 평가되며, 순수함수는 지금 계산하나 나중에 계산하나 그 값이 다를리가 없기 때문에 문제가 되지 않는다.

약간의 트릭을 활용하면 조금 더 와닿는 형태로 정의할 수 있을지 모르겠다.

fastFibo = memoize body
           where
           body n
             | n < 3     = n - 1
             | otherwise = fastFibo (n-1) + fastFibo (n-2)  

어쨌거나 fiboMemo2fastFibo를 이용해서 계산하면 우리가 기대했던 대로 올바른 동작을 하는 것을 확인할 수 있다.

"START"
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s
5702887
CPU time:   0.00s

그외 논의 사항

피보나치 수열의 경우, 지수적 시간 복잡도를 가지는 문제를 리니어한 시간대로 끌어내렸다. 하지만 리스트를 탐색해야 하는 한계가 있기 때문에 이러한 메모이제이션이 만능 탄환으로 작동하지는 못할 것이다. (당장 소수 검사의 문제만 해도 숫자가 커지면 되려 느려질 수도 있다.) 따라서 이진 탐색 트리와 같이 보다 빠르게 요소를 찾을 수 있는 자료구조의 도입이 필요하다.

또한 함수를 리스트로 변환하는 과정의 한계 때문에 Int 타입 인자 함수에만 유효하다. 이는 다른 타입을 정수로 해시할 수 있다면 극복가능할 것으로 보인다.

fix 함수(참고: Data.Function)에 대한 논의가 있다. fix 함수는 fix x = lef x = f x in x라는 알쏭달쏭한 함수인데 지금으로서는 도무지 이해가 안된다. 좀 더 연구해볼 필요가 있을 것 같다.

Tail 과 꼬리재귀(Tail Recursion) – Swift

꼬리재귀

Natasha ElementTypehe Robot에 꼬리재귀에 대한 글이 올라오고 Digg에서 많은 digg을 얻었는데, 좀 이상해서 내용을 정리해본다. 링크한 글의 저자는 꼬리재귀와, 함수형 언어의 자료 구조인 리스트의 head, tail을 혼동하고 있는 듯 하다. 우선 꼬리재귀에 대해서 먼저 이야기하겠다. 꼬리 재귀는 재귀의 특별한 한 형태이다. 꼬리 재귀를 설명하기 전에 먼저 재귀(recursion)에 대해 알아보자.

재귀는 어떤 함수의 내부에서 스스로를 다시 호출하는 것을 말한다. 예를 들어서 1에서 10 까지의 자연수의 합을 구하는 과정을 재귀적인 처리를 통해서 구한다고 생각해보자.

  1. 계산은 1 + 2 + 3 + 4 + … + 10 으로 이루어지고, 편의상 이걸 +(1~10) 이라고 표현하기로 약속한다.
  2. 이 때 10까지의 합과 9까지의 합은 10만큼 차이난다, 즉 +(1~10)+(1~9) + 10 인 셈이다.
  3. +(1~n)+(1~(n-1)) + n 이 된다.

이 관계를 이용하면 1에서 n 까지의 자연수의 합을 구하는 함수를 다음과 같이 작성할 수 있다.

func sumUpto(n: Int) -> Int {
  guard n > 0 else { return 0 }
  return n + sumUpto(n: n - 1)
}

재귀함수의 기술적 한계

재귀함수는 1) 어디까지 계산할 것인가와 2) 한 단계의 계산과 다음 단계의 계산의 관계만을 생각하는 것으로 전체 계산 알고리듬을 매우 간결하게 정리할 수 있는 장점이 있다. 문제는 기술적인 한계때문에 재귀의 단계는 일정한 범위 이상으로 커질 수가 없다는 점이다. 그것은 재귀함수가 자신을 호출하는 것에 대해서 시스템은 부가적인 리소스를 더 많이 소모해야 한다는 것이다.

프로그램 흐름에서 함수의 호출은 메인 루틴에서 별도의 서브 루틴으로 흐름이 이행되는 것을 의미한다. 함수 내부로 실행 흐름이 들어가게 되면 함수 내부에는 전달된 인자와 함수 내부에서 선언된 지역 변수, 상수들이 존재하며 이것은 메인 루틴의 스코프와는 개별적인 값들이 된다. 또한 함수의 실행이 끝나면 실행 흐름은 메인 루틴에서 함수를 호출했던 위치로 돌아가야 하고, 이 때 실행 흐름이 액세스할 수 있는 변수들은 원래의 스코프의 값들이 되어야 한다. 이러한 리소스 제어를 위해서 함수가 호출되면 시스템은 메모리 영역의 끝단에 별도의 스택을 만들고 여기에 인자값과 함수의 지역 변수들을 복사한다. 그리고 함수의 실행이 끝나면 스택 영역을 파괴하여 리소스를 회수하는 식으로 동작한다.

함수의 재귀 호출은 함수는 하나지만, 함수가 매번 재귀 호출 될 때마다 별도의 독립적인 컨텍스트가 요구되기 때문에 재귀 호출을 반복하면 반복할 수록 스택영역을 계속해서 추가적으로 사용해 나가야 한다. 하지만 당연하게도 시스템의 메모리 자원은 한정되어 있기 때문에 스택 영역의 크기는 제한된다. 통상 몇 천~몇 만 단위의 횟수 내에서 스택이 중첩될 수 있고 (이것은 언어나 컴파일러마다 다르다.) 따라서 재귀의 깊이 역시 제한된다.

그런 이유에서 위의 sumUpto(n:) 함수는 몇 만 단위의 n 값에 대해서는 값을 계산하지 못하고 프로그램이 터지게 된다. 또한 시스템 입장에서 스택 영역을 할당하고 파괴하는 작업은 상당히 비싼 작업이다. 따라서 그만큼 성능 측면에서도 불리하다.

꼬리재귀 최적화

그런데 재귀 함수의 특정한 패턴 중에는 꼬리재귀(tail recursion)라는 것이 있다. 꼬리 재귀는 함수가 자신을 재귀호출한 결과를 바로 리턴하는 것을 의미한다. 꼬리 재귀가 특별한 이유는 다음과 같다.

  1. 꼬리 재귀에서 재귀의 결과는 그대로 리턴되므로 재귀의 결과에 대한 추가적인 연산이 불필요하다.
  2. 재귀 결과에 추가적인 연산이 불필요하다는 점은, 재귀 결과를 받은 시점에 해당 함수 내의 컨텍스트를 더 이상 참조하지 않는다는 의미이다.
  3. 그렇다면 재귀 호출에 진입하는 시점에서, 해당 레벨의 컨텍스트가 필요하지 않다는 것을 의미한다.
  4. 재귀 호출되었을 때 새로 생성해야 할 컨텍스트는 사실상 현재 컨텍스트와 동일하다.

이 말이 무엇을 의미하는가? 꼬리 재귀에서는 재귀 호출로 새로운 스택을 만들고 새 함수 컨텍스트로 실행 흐름을 옮기는 대신에, 현재 함수의 맨 처음으로 실행 흐름이 점프하면 된다는 의미이다. 즉 꼬리 재귀는 그 흐름이 루프로 치환된다는 것이다. 게다가 꼬리 재귀를 판단하는 것도 매우 간단해서 return 문에 재귀 호출구문이 있고 그외의 표현식이 없으면 된다. 따라서 컴파일러는 이러한 꼬리 재귀 패턴을 간단하게 루프로 치환할 수 있고, 그렇게 하여 스택 생성과 파괴에 따른 메모리 및 성능 낭비를 막을 수 있다. 이것을 꼬리 재귀 최적화라고 한다.

앞서 sumUpto(n:)은 재귀 호출 결과에 n을 더한 후에 리턴하기 때문에, 재귀 호출한 결과를 다시 가공하여 호출하고 있기에 꼬리 재귀가 아니라 하였다. 왜냐하면 재귀의 결과에 다른 값을 누적해서 더해야하기 때문이다. 따라서 누적값을 인자로 넘겨서 이러한 형태를 꼬리 재귀로 변경할 수 있다.

func sumUptoByTailRecursion(n: Int, _ acc: Int = 0) -> Int {
  guard n > 0 else { return acc }
  return sumUptoByTailRecursion(n: n - 1, acc + n) // 위로부터 누적하여 아래로 내려보낸다.
}

이렇게 변경된 형태는 꼬리 재귀이고, 이제 동일한 연산에 대해서 컴파일러가 최적화 할 수 있게 되었다.

Swift 컴파일러는 꼬리 재귀 최적화를 수행하는 것으로 보이지만, 실제로는 최적화가 적용되지 않는 경우가 있다. 그것은 ARC때문에, 컴파일러가 최적화를 수행하는 이전 단계에서 메모리 관리 코드를 여기 저기에 삽입할 수 있기 때문이다. 따라서 소스 코드 원안에서 꼬리 재귀 형태였던 것이 ARC에 의해서 모양이 바뀔 수 있다. 이러한 문제를 피하기 위해서 트램폴린이라는 기법을 사용할 수 있다. (트램폴린 기법은 명시적으로 재귀를 루프로 바꿀 수 있기 때문에 최적화가 훨씬 쉬우며, 심지어 꼬리 재귀 최적화를 지원하는 다른 언어에서도 문법적으로 구현이 가능하다면 실제 꼬리 재귀보다 좋은 성능을 보인다.)

리스트의 꼬리에 관하여

나타샤가 헷갈려한 tail은 무엇일까? 그것은 리스트라는 함수형 언어에서의 주력 데이터 타입에서 사용되는 용어이다. 그러려면 “리스트”라는 타입에 대해서 살펴보아야겠다. 리스트는 배열처럼 여러 개의 개별 원소값이 일렬로 나열된 순서가 정해진 집합을 나타낼 때 사용한다. 그럼 “연결리스트(linked list)”하고 비슷한 것인가라고 생각할 수 있는데, 연결리스트와는 다르다. 연결리스트는 원소값을 감싸는 노드가 자신의 다음 노드에 대한 참조를 가지고 있는 것인데, 리스트는 다음 원소와의 연결이 “연산자”에 의해 고정된다.

하스켈에서 리스트를 만드는 빌딩 블럭으로는 두 개의 표현이 사용되는데,

  1. [ ] 은 빈 리스트를 의미한다.
  2.  : 연산자는 원소:리스트 의 형태로 어떤 리스트의 앞에 하나의 원소를 결합하는 작용을 한다.

위 표현을 활용하면 얼마든지 긴 리스트를 만들 수 있다. 예를 들어 [1] 이라는 1개 원소를 가지는 리스트는 빈 리스트에 1이라는 원소를 붙인 것이므로 1:[ ] 로 표현할 수 있다. 그럼 [1, 2]는? 1:(2:[])가 된다. 이런 식으로 1:(2:(3:(4:(5:[]))))와 같이 표현되는 것을 (으아 괄호지옥이다!!!) 문법적으로 쓰기 편하게 [1,2,3,4,5]라고 표현하는 것이다.

리스트는 결국 맨 앞의 원소 하나와 그걸 제외한 나머지 리스트가 붙어있는 재귀적인 꼴로 정의된다. 여기서 맨 앞의 원소를 head, 나머지를 tail이라고 한다. 그렇다면 tail에 대한 재귀적인 처리를 tail recursion이라고 할까? 아니다. 리스트의 본질은 그 자체가 재귀적인 데이터 타입이기 때문에 리스트에 대한 거의 대부분의 연산이 재귀적으로 이루어진다. 리스트의 합을 구하는 sum 이라는 함수를 정의한다고 하면 하스켈에서는 다음과 같이 정의할 수 있다.

sum :: Integral a => [a] -> a
sum [] = 0
sum (x:xs) = x + (sum xs)

하스켈은 선언적인 함수이기 때문에 변수라는 개념이 없다. x = 1 과 같은 식으로 값에 이름을 붙일 수 있지만 이것은 엄밀하게 1 이라는 항등함수 x를 의미하는 것이다. 따라서 각 원소의 누적값을 더해나갈 임시 변수같은 것이 존재하지 않기 때문에 리스트에 대해서 루프를 통한 연속적인 연산은 불가능하며, 리스트의 재귀적인 성질에 의존하는 재귀적인 처리만이 가능하다. 그리고 (x + sum xs라는 표현 자체는 꼬리 재귀의 모양도 아니다.)

참고로 하스켈의 리스트는 Swift에서도 구현할 수 있다. 열거체는 indirect 변경자를 사용해서 재귀적으로 정의가능하다.

enum List<T> {
  case empty
  case list(T, List<T>)
}

// 빈 리스트
let anEmptyList: List<Int> = .empty
// [1]
let one: List<Int> = .list(1, .empty)
// [1,2,3,4,5]
let oneToFive: List<Int> = .list(1, .list(2, .list(3, .list(4, .list(5, .empty)))))

// 그리고 합계를 구하는 함수
func sum(list: List<Int>) -> Int {
  switch list {
  case .empty: return 0
  case .list(let x, let xs): x + sum(list:xs)
  }
}

접기

다시 원글에서 나타샤는 reduce에 대한 이야기를 하고 있다. 리스트를 하나의 값으로 축약하는 행위는 엄밀하게 말하면 재귀적인 특성이 아니라 항등원을 갖는 이원연산과, 그 연산의 항등원에 관한 성질 때문이다. 이러한 연산은 두 개의 값을 하나로 합칠 수 있고, 하나의 값이 있을 때에는 항등원을 이용해서 연산을 적용할 수 있다. 이러한 연산과 항등원을 모노이드라고 하는데, 모노이드로부터 Foldable이라는 특성을 규정한다. 따라서 재귀와 아무런 관련이 없는 배열이나, 옵셔널등도 모노이드의 성질을 가지며 reduceflatMap과 같은 연산을 적용받을 수 있다.