콘텐츠로 건너뛰기
Home » 예제로 이해해보는 모나드 – 파서구현하기

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

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

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

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

파서의 타입

그렇다면 파서가 어떤 타입을 가져야할지부터 생각해보겠습니다. 파서가 하는 일은 문자열을 받아서 임의의 의미있는 트리를 만들어낸다고 했습니다. 그런데 실제로 어떤 파서가 처리할 수 있는 데이터는 문자열 데이터의 일부분일 것입니다. 어떤 작은 파서가 문자열의 일부분을 처리했다면, 그 결과와 더불어 남아있는 문자열 데이터도 같이 반환하여야 합니다. 따라서 대략의 타입은 다음과 같이 정의해볼 수 있습니다.

Parser :: String -> (Tree, String)

직관적으로 바로 떠올리기는 힘들지만, 파서가 데이터를 처리할 때 결과가 한 가지 이상이 될 수 있는 경우가 있습니다. (혹은 없을 수도 있죠) 따라서 파서의 리턴타입은 (Tree, String) 보다는 [(Tree, String)]이 되는 것이 좀 더 자연스럽게됩니다.

또한 트리의 타입은 파서마다 달라질 수 있으니 타입 파라미터를 추가해서 조금 더 범용적으로 파서의 타입을 정의하면 이렇게 됩니다.

Parser a :: String -> [(a, String)]

자 그럼 타입을 정했으니, 아주 간단하고 쓸모없는 파서를 하나 만들어보겠습니다. 이 파서는 문자열을 파싱하여, Char 타입 데이터를 얻어냅니다. 즉 첫글자를 따내는 파서입니다. 문자열이 비어있다면 빈 리스트를, 그렇지 않다면 (첫글자, 나머지)로 구성된 튜플의 싱글톤(원소가 1개만 있는 집합)을 리턴합니다. 이름은 item 으로 하겠습니다.

item :: Parser Char     -- 1
item []     = []        -- 2
item (x:xs) = [(x, xs)] -- 3
  1. 먼저 item 은 Char 값을 분리해내는 파서입니다.
  2. 빈 문자열을 받으면 파싱에 실패하고 그 결과는 빈 리스트입니다.
  3. 그렇지 않은 경우, 첫번째 글자와 나머지 글자를 분리하여 튜플로 만들고 그 것을 담은 리스트를 리턴합니다.

파서가 함수로 정의되어 있지만 item “hello” 라고 써서 사용하는 것은 왠지 어색해보입니다. 따라서 당장은 별 쓸데는 없어보이지만 파서에 문자열을 넣어서 실행하는 함수 runParser를 작성해보겠습니다. 이 함수는 의외로 매우 유용한데, item "hello" 라고 쓸 것을 runParser item "hello" 라고 쓸 수 있게 해줍니다… 아, 이런…😒

runParser :: Parser a -> String -> [(a, String)]
runParser p xs = p xs

사실 속으로 저도 이게 뭔 헛짓인가 싶습니다. 어쨌든 이런 생각이 들었다면 잘 따라오고 있는 중이니 계속해서 나가보겠습니다.

Failure

이번에는 조금 특별한 파서를 만들겠습니다. 이 파서는 주어진 입력이 무엇이든 항상 실패하는 파서입니다. 왠지 이번에도 runParser만큼이나 유용(?😌?)할 것 같은데, 그 이름은 failure로 하겠습니다. 실패한 파서는 이후에 남아있는 문자열이 무엇이든 상관없이 빈 리스트를 리턴합니다.

failure :: Parser a
failure _ = []

뭔가 대환장 파티라도 할 기세이지만, 이부분이 나중에 킬링포인트…

Return

이번에는 failure와는 반대로 항상 뭔가를 파싱해내는 파서에 대해서 생각해봅시다. 논리적으로 항상 뭔가를 파싱해낸다는 말은 입력에 상관없이 어떤 상수값을 파싱한다는 이야기입니다. 그런데 그 상수값을 알지 못한다면 이러한 파서를 처음부터 정의하는 것은 불가능하기 때문에, “상수값을 받으면” 그 상수를 항상 파싱하는 파서를 만드는 함수를 만들어보겠습니다.

일단 그 이름은 return으로 하겠습니다. 모나드의 요구사항으로 주어지는 함수인 return과 이름이 같은 걸 봐선, 여기 어떤 흑막이 있을것으로 예상됩니다. 자, 그런데 중요한 차이점이 있으니 잊지 맙시다. 조금 전 만든 failure는 그 자체로 파서였습니다. 하지만 return은 파서가 아닙니다. ‘파서를 만드는 함수’라는 점에 유의하세요.

return :: a -> Parser a
return v = \str -> [(v, str)]

return 함수가 만들어내는 파서는 문자열의 어떤 부분도 소모하지 않습니다. 단지 v 라는 값을 상수값을 항상 파싱한 것처럼 보내줍니다.

파서를 조합하기

갑자기 일반적인 논의로 돌아와서, 그런데 어떤 데이터를 파싱할 때 쓰이는 파서는 사실 그 속에 여러 다양한 파서가 결합되어 있는 형태입니다. 프로그래밍 언어 해석기를 생각해보죠. 숫자값이나 문자열 값은 그 리터럴이 다르기 때문에 서로 다른 규칙을 이용해서 파싱해야 할 것입니다. 숫자값에서도 실수와 정수는 표기법이 다르죠. 이러한 각각의 데이터 형에 대한 리터럴은 그에 맞는 파서를 써서 해석해야 합니다. 그외에 미리 지정된 키워드를 구분해내는 파서도 필요합니다. 웹브라우저는 또 어떨까요? 태그와 태그로 둘러싸인 텍스트 데이터를 구분해서 파싱해야 하고, 또 태그 내의 각 속성과 그 값을 파싱해야 합니다. 즉 하나의 파서는 저마다 자기가 요구하는 문자열의 생김새를 알고 있는 작은 파서들의 결합체라고 볼 수 있겠습니다.

이 때, 큰 파서 덩어리에서는 주어진 코드 문자열이 정수인지, 실수인지, 문자열인지를 알아야 각 표기에 어울리는 파서를 쓸 수 있을 것입니다. 그럼 이 구분을 어떻게 해야할까요? 네? 정규식이요?

굳이 그럴 필요가 없습니다. 여러 파서를 순차적으로 시험하고 그 결과를 결합해보면 됩니다. 어 떤 문자열이 있을 때, 예를 들어 “1.23”이 있다고 합시다. 여기에 정수 파서를 먼저 적용합니다. 정수 표기에 해당하는 문자가 없다면 파싱에 실패할 것이고, 있다면 정수값을 파싱해내겠죠. (이 경우에는 .23이 이어지기 때문에 파싱에 실패합니다.) 결과가 없는 경우에 다시 실수 파서를 적용합니다. 이번에도 실패했다면 문자열을 파싱하고… 이런식으로 여러 종류의 파서를 줄 세워서 파싱 가능한 값이 처음 나올때까지 파싱을 하는 것입니다. 😨이런 이거 어디선가 본 거 같은 패턴인데… 여튼 계속 살펴보겠습니다.

파서를 이런식으로 결합하기 위해 +++ 라는 결합 함수 혹은 연산자를 만들어보겠습니다. 하는 일은 앞서 설명한 것과 똑같습니다. 파서와 파서를 결합하여 새로운 파서를 만드는데, 이 새로운 파서는 두 파서를 각각 적용하여 그 첫 결과를 사용합니다. 중요하니까 한 번 더 말하자면 파서와 파서를 결합하여 새로운 파서를 만듭니다.

새로운 파서를 만드는 함수로 앞에 만든 return 이 있었습니다. 다만 이 녀석은 인자를 필요로 한다는 점만 다르죠.

(+++) :: Parser a -> Parser a -> Parser a
f (+++) g = \xs -> case runParser f xs of
                         []            -> runParser g xs
                         [(y, ys)]     -> [(y, ys)]

아직 어떻게 구현할지는 모르지만 숫자를 파싱하는 파서(numParser :: Parser Char)와 연산자를 파싱하는 파서 (opParser :: Parser Char)가 있다고 할 때 numParser +++ opParser 는 주어진 문자열의 첫글자가 숫자이면 숫자로, 연산자 문자이면 연산자문자로서 파싱하고, 둘 다 아니라면 실패할 것입니다. (어? 이게 진짜 되네?)

+++ 함수(연산자)는 파서 자체를 함수로 봤을 때, 일종의 함수 조합과 비슷합니다.

조금 더 나아가서 +++ 외에 다른 연산자를 만들 수 있을지 생각해봅시다. +++ 연산자는 파싱가능한 타입을 알 수 없는 값을 파싱하기 위해서 f, g, h… 등 임의의 파서를 결합하여 순서대로 파싱가능한 케이스와 그 때의 결과를 얻는 파서가 되었습니다. 그 외에 연속적으로 값을 처리하고 그 결과를 한 번에 리스트로 묶어서 받아내거나 하는 파서도 만들어낼 수 있을지 모릅니다.(이건 뒤에 가서 만들어볼겁니다.) 기본적인 패턴을 알았으니 좀 더 발전시켜 나가는 것은 그렇게 어렵지 않을지도요.

모나드

여기서 잠깐 파서가 하는 일을 다시 되짚어 봅시다. 파서는 기본적으로 문자열을 입력으로 받아서, “일부를 사용해버리고” 남은 문자열을 돌려주는 함수라고 했습니다. 이 때 “사용된 일부”를 통해 해석된 값이 발생하고 그것을 남은 문자열과 함께 돌려줍니다. 어떤 부수적인 효과(사용된 첫 글자를 처리한 결과)가 단순한 첫글자 자르기와 더불어 발생한 셈입니다. 즉 파서는 순수한 문자열 입력을 받아서 부수효과 + 순수한 출력(역시 문자열)을 만들어내는 함수입니다. 말장난 같지만 이것은 출력의 관점에서 ‘부수효과’라는 맥락이 들어있는 컨테이너라 볼 수 있습니다.

사실은 모나드가 주로 사용되는 곳이 이러한 부수효과와 관련되는 부분입니다. 부수 효과에 집중할 때, 모나드의 필수 구성 요소인 바인드가 이와 관련됩니다. 바인드는 모나드와 모나딕 함수를 연결하여 새로운 모나드를 만드는 연산인데, 이 때 각각의 모나드를 액션이라 하며, 액션 내부에서 발생하는 부수효과는 바인드 연산을 따라 흐르는 파이프라인 혹은 액션의 체인 내에서는 계속 유지가 됩니다.

모나딕함수: 모나드가 아닌 값 a를 받아서 어떤 모나드를 만드는 함수. 앞서 간단히 구현해본 return 같은 함수가 모나딕 함수입니다.

우리는 흔히 IO 모나드를 do 블럭 내에서 사용합니다. 이 때 각 라인에는 모나드 함수가 사용되는데, 이때 각각의 라인을 특별히 액션이라 부릅니다. 각 액션의 결과는 do 블럭 내에서는 마치 다음 라인으로 이어져서 참조가 가능한 것처럼 보입니다. 즉 모나드 액션의 부수효과가 do 블럭 내에서는 유지되는 것처럼 보이는 것이죠.

그럼 파서를 모나드로 보고, 바인드 함수를 작성해보겠습니다. 바인드는 모나드 m a 와 모나딕 함수인 a -> m b 타입의 함수를 연결하여 m b 모나드를 만드는 연산입니다. 예를 들어 item 과 같은 Parser Char 파서에 Char -> Parser (Char, Char) 와 같은 타입의 함수를 바인드하면 Parser (Char, Char)를 만들 수 있겠죠. 파서(모나드) f의 결과 값 중 트리값을 함수 g 에 전달하여 만들어지는 제 3의 파서에, f를 거친 후 남은 문자열을 전달해주면 되는 것입니다.

이 과정에서 흥미로운 것은 모나드를 계속 바인드하는 체인을 거치는 동안 문자열은 점점 짧아질 것이지만, 표면적으로 매 단계를 거친 후의 나머지 문자열이 다음 연쇄로 전달되는 과정이 보이지 않을 것이라는 점입니다. 왜냐하면 그 과정은 바인드 연산 내부에 있기 때문이죠. 파서 타입에 대한 바인드 연산의 구현은 다음과 같습니다.

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
f >>= g = \xs -> let [(y, ys)] = f xs
                 in  runparser (g y) ys

그러면 Char -> Parser (Char, Char) 타입이 되는 함수를 하나 생각해봅니다. 가장 간단한 예는 첫 문자를 복제하는 거죠, 간단하게 return 함수를 사용해서 twice라는 파서 생성 함수를 작성할 수 있겠습니다.

이 때 twice는 파서, 그러니까 모나드를 출력하는 함수입니다. return 처럼 말이죠. 이러한 함수를 모나딕 함수라고 합니다. 모든 모나드인 타입에 대해서 return 함수는 가장 기본이 되는 모나딕 함수인 셈입니다. 어떤 문자를 하나 받아서 그걸 두 개로 만드는 건 \a -> (a, a) 와 같이 쓸 수 있습니다. 하지만 여기서 결과는 모나드가 되어야 하므로 (a, a)를 return에 넘겨주면 되겠네요. 따라서 twice 함수는 아래와 같이 쓰여집니다.

twice :: Char -> Parser (Char, Char)
twice = \v -> return (v, v)

앞서서 만든 음흉한 return 함수가 잘 사용되었습니다. 자 이제 문자열의 첫 글자를 (x , x) 형식으로 파싱해내는 itemTwice 함수는 지금껏 작성해온 요소들을 조합하여 만들 수 있게 됩니다. 이해가 되나요? (모나드 >>= 모나딕함수 = 모나드)

itemTwice :: Parser (Char, Char)
itemTwice = item >>= twice

파서를 실제 모나드로 정의해보기

모나드와 모나딕 함수를 바인드로 연결하여 새로이 조합된 모나드를 만들 수 있다는 감을 잡았습니다. 이번에는 Parser를 모나드로 만들기 위해서 코드를 좀 정리해보겠습니다. 파서 자체의 실제 타입은 함수((->)r)이므로, 클래스 적용을 위해 newtype으로 재선언할 필요가 있습니다.

그리고 GHC 7.2 이상에서는 특정한 타입을 Monad로 만들기 위해서는 반드시 Functor, Applicative로 만들도록 강제됩니다. (인터넷상의 많은 자료가 그 이전 GHC를 기준으로 하기 때문에, 거의 대부분의 자료는 최신 버전의 GHCi에서는 제대로 돌아가지 않습니다.)

모나드로서의 파서는 앞서 작성했던 String -> [(a, String]) 함수를 생성자 Parser에 결합합니다. 그리고 runParser 함수를 통해서 파서 함수에 문자열을 전달할 수 있도록 레코드 필드로 선언합니다.

이렇게 정의되는 파서모나드에 대해서 runParser 함수를 통해서 Parser 로 감싸진 함수를 꺼낼 수 있습니다. 참고로 여기서 runParser는 구축자 뒤에 오는 함수식을 참조하는 함수이기 때문에, 아래와 같이 파서를 newtype으로 정의한다면 기존에 runParser의 구현은 필요가 없습니다.

newtype Parser a = Parser{ runParser :: String -> [(a, String)] }

이런식으로 단순한 함수였던 파서를 새 타입으로 정의합니다. newtype 으로 정의하면 원래 타입과 달리 새로운 타입 클래스를 지정할 수 있습니다. 모나드를 만들기 전에 먼저 Functor로 만들어보겠습니다.

-- Functor
instance Functor Parser where
  fmap f p = Parser $ \str ->
         case runParser p str of
              []        -> []
              [(y, ys)] -> [(f y, ys)]

Fuctor가 되기 위해서는 fmap 함수를 작성해야 하고, 여기서는 부수효과인 트리에 주어지는 함수 f 를 사상합니다. 즉 파서는 fmap을 통해서 트리를 조작하는 함수와 결합할 수 있습니다.

다음은 Applicative 구현입니다. 이건 좀 복잡해 보일 수 있는데, 함수가 들어있는 컨테이너와 값이 들어있는 컨테이너를 결합하는 <*> 연산자를 주의 깊게 구현하면 됩니다. runParser의 결과가 비어있거나, 그렇지 않거나 하는 경우를 잘 따라가면 그리 어렵지 않습니다.

-- Applicative
-- needs pure, <*>
instance Applicative Parser where
  pure x = Parser $ \str -> [(x, str)]
  -- pure x는  return과 동일하다는 것을 알 수 있습니다.
  p <*> q = Parser $ \str ->
    -- p : Parser (a -> b)
    -- q : Parser a
    case (runParser p str) of
         -- p로 파싱할 수 없다면 결과가 없을 것이고
         -- p로 파싱할 수 있다면 다시 q로 파싱된 결과를 여기에 '적용'합니다.
         []                -> []
         [(f, str')]       ->
               case runParser q str' of
                    []        -> []
                    [(x, xs)] -> [(f x, xs)]

Applicative의 구현에는 pure, <*> 두 개의 함수 구현이 필요합니다. pure는 return과 사실상 동일합니다. <*>는 함수를 내장하는 파서와 값을 내장하는 파서를 결합합니다. 그래서 좌변의 부수효과인 함수에 우변의 부수효과인 트리를 대입하여 최종 결과를 만듭니다. 사실 기계적인 구현이라 딱히 덧붙일 설명이 없네요.

이번에는 모나드로 만들기

다음은 모나드 구현입니다. 사실상 return 과 바인드 구현은 앞에서 해봤기 때문에 역시 간단하게 쓸 수 있습니다.

instance Monad Parser where
  return x = Parser $ \s -> [(x, s)]
  p >>= q = Parser $ \str ->
            case runParser p str of
                 [] -> []
                 [(v, str')] -> runParser (q v) str'

앞서 만들었던 (+++), failure 함수 역시 파서의 구축자인 Parser를 붙여서 다음과 같이 수정합니다.

(+++) :: Parser a -> Parser a -> Parser a
f +++ g = Parser $ \xs ->
    case runParser f xs of
          []       -> runParser g str
          [(v,ys)] -> [(v, ys)]
failure :: Parser a
failure = Parser $ \_ -> []

item 파서도 약간 수정이 필요합니다. Parser 구축자가 앞에 붙어야 하기 때문이죠. 이 item이 앞으로 만들 몇 가지 추가적인 파서의 기본형이 됩니다.

item :: Parser Char
item = Parser $ \s ->
    case s of
      [] -> []
      (x:xs) -> [(x, xs)]

잠깐, 모나드 공리에 대해

어떤 타입을 모나드의 인스턴스로 정의하려면 >>= 연산과 return 함수에 대한 구현이 필요합니다. 모나드로 정의된 많은 종류의 파서가 있을 수 있고, 파서가 아닌 다른 모나드들도 많이 있습니다. 하지만 모든 모나드는 >>= 연산자와 return 함수를 사용할 수 있어야 합니다. 이 때 두 함수가 반드시 지켜야 하는 몇 가지 성질이 있는데, 이를 모나드의 공리라 부르며 다음과 같은 성질이 요구됩니다.

  1. m >>= return == m
  2. return x >>= f = f x
  3. (m >>= f) >>= g = m >>= (\x -> f x >>= g)

아마도 제대로 작성된 모나드라면 이 성질을 만족할 것입니다. 하지만 >>=, return의 구현에 대해서 항상 이 성질을 만족하지 못할지도 모릅니다. 하스켈 컴파일러는 이러한 관계까지 자동으로 검증하지는 못합니다.

모나드에서 중요한 점은 바인드를 연쇄적으로 처리하는 과정에서, 내부에 발생하는 모든 부수효과(혹은 부가정보)가 그 체인이 종료될 때 까지는 내부에 유지된다는 점입니다. 이 성질을 잘 이용하면 부수 효과를 모나드 내부에 가두면서 전체적으로는 순수한 연산으로 만드는 것이 가능하다는 이야기입니다. 부수효과와 관련되는 가장 대표적인 분야가 입출력인데, 하스켈은 IO 모나드를 사용해서 입출력을 처리하며, 순수한 함수 연산과 IO 동작을 잘 조화시킬 수 있습니다.

모나드의 중요한 이 성질을 설명하는 부분에서 많이 놓치기 쉬운 점 중 하나가, 부수효과가 아닌 연산 그 자체에 관한 것입니다. 부수효과가 유지되는 처리과정은 바인드 함수를 통해서 연결되는 모나드와 모나드 생성 함수(모나딕 함수라 하겠습니다.)의 연쇄로 이루어집니다. 이 말은 곧 어떤 모나드 객체는 모나딕 함수를 한 번 이상 연결하여 새로운 연산으로 만들 수 있다는 것입니다.

앞서 간단히 언급한 numParser +++ opParser 는 두 개의 모나드를 연결해서 새로운 모나드를 만드는 작은 예시였습니다. 그러면 모나드에 모다닉 함수를 연결하여 새로운 모나드를 어떻게 조합하는지 살펴보겠습니다.

이번에도 시작은 쓸모없는 예제로 시작하겠습니다. 만약 Char -> Parser (Char, Char) 타입의 함수가 있다면 Parser Char 모나드에 연결, Parser (Char, Char) 모나드를 만들 수 있음을 이미 보았습니다.

itemTwo :: Parser (Char, Char)
itemTwo = item >>= \c -> item >>= \c' -> return (c, c')

이 정의 어디에도 직접적으로 ‘잔여 문자열’을 넘기는 표현은 없지만(사실 바인드 연산자 내부에 있으므로), 이는 우리가 의도하는 동작을 정확하게 수행합니다. 이때 바인드의 구현을 상기해봅시다.

  1. 첫번째 item 은 문자열의 첫 글자를 떼어냅니다.
  2. 첫번째 바인드 연산자의 우변에서 \c -> 로 시작하는 함수는 Char를 받아서 또다른 파서를 리턴하는 함수입니다. 이 함수는 형식을 볼 때 Char를 받는 것처럼 보이지만, 사실은 첫번째 item의 리턴값 전체가 넘겨지고 있습니다. 즉 이 함수 내부에 있을 파서의 입력으로 나머지 문자열이 전달됩니다.
  3. 같은 방법으로 두 번째 item을 사용하여 두 번째 결과를 만듭니다.
  4. 최종적으로 앞에서 때어낸 첫 두 글자를 묶어서 (c, c’)의 튜플로 만듭니다. 이를 return 하기 때문에 최종 파서는 앞 두 글자를 떼어낸 나머지 문자열을 같이 돌려주는 파서로 만들어집니다.

위 과정에서는 두 개의 익명함수가 겹쳐져서(nested) 사용되었습니다. 바인드 연산자의 우변으로 갈 수록 스코프가 아래로 확장되기 때문에 각 익명함수가 받는 인자는 이 식의 끝까지 유지됩니다. 모나드를 사용할 때 부가 효과가 연쇄의 끝까지 유지되는 것은 이런식으로 동작한다는 의미입니다. 그리고 또 한가지, 이렇게 item 이라는 모나드와 모나드를 생성하는 함수를 연결하여 새로운 모나드를 만들었다는 것입니다.

이번에는 좀 더 다른 모양의 파서를 만들어보겠습니다. ignore2는 주어진 문자열에서 첫번째 글자와 세번째 글자를 튜플로 묶습니다. 두 번째 글자는 무시해버립니다.

ignore2 = item >>= \a -> item >>= \_ -> item >>= \c -> return (a, c)

item을 계속 결합하여 문자를 떼어내는 파서를 만들고 있다는 점을 잊지 않았겠죠? 결합이 많아지면 식이 길어집니다. 이걸 좀 보기 좋게 여러 줄로 나눠보겠습니다.

ignore2 =
  item >>= \a ->
  item >>= \_ ->
  item >>= \c ->
  return (a, c)

이제 어디 선가 본 것 같은 모양입니다. >>= 로 연결되는 바인드식을 좌/우변을 바꾸어 <- 로 연결하면, do 블럭의 문법이 됩니다. 다시 써보면 이렇게 되겠죠.

ignore2' = do
  a <- item
  _ <- item
  c <- item
  return (a, c)

이렇게 정리가 되는군요! 그럼 첫 세글자를 떼어서 (Char, Char, Char)를 만드는 파서도 쉽게 만들 수 있겠죠? 원하는 만큼 글자를 떼어 사용하거나 버리거나 할 수 있습니다.

이제 Parser 모나드를 사용하는 방법에 대해 정리해보겠습니다.

  1. runParser 파서 문자열“의 형태로 호출하면 실제로 파서가 실행된 결과를 얻을 수 있습니다. 그 결과는 모나드가 아니며 실제 값입니다.
  2. 파서를 통해서 다른 파서를 만들려면 값 -> 파서를 내놓는 함수를 이용하여 바인드합니다. 이 때 익명함수를 이용하는 방식으로 쓴다면 do 문법으로 치환할 수 있습니다. 이 때 파서 생성 함수는 바인드 왼쪽의 파서의 결과를 받아서 새로운 파서를 만드는 함수의 형태가 됩니다. 그리고 많은 경우에 익명함수로 작성하게 됩니다.

조건부 파서

이번에는 쪼금 더 실용적인? 파서를 만드는 새로운 방법을 보겠습니다. 조건식을 받아서 조건식에 맞을 때에만 새 파서를 만드는 모나딕 함수를 작성해보겠습니다. 이름은 sat(istfying)으로 하겠습니다.

  1. Char 타입을 Bool로 판단하는 조건식을 인자로 받습니다.
  2. Parser Char 타입을 리턴합니다.

모나딕 연산을 사용하면 되기 때문에 다음과 같이 쓸 수 있겠습니다.

sat = item >>= \x -> if p x then return x else failure

do 블럭을 사용해서 조금 더 읽기 쉽게 정리하면 아래와 같습니다.

sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else failure

첫글자를 떼어서 조건에 판별, 조건이 맞다면 첫 글자를 포함한 결과를 리턴할 것이고 그렇지 않다면 무조건 실패하는 파서를 만드는 함수입니다. 이 함수를 여러 조건과 잘 조합하면 제법 쓸모있는 물건을 만들 수 있겠습니다. 예를 들자면, Data.Char에는 isDigit이라는 함수가 있으니, 이를 사용해서 숫자 하나를 파싱해내는 파서를 만들 수 있습니다. (숫자 한 글자를 파싱한 것이지, 아직 정수로 변환하는 건 아닙니다.)

digit :: Parser Char
digit = sat isDigit

그 외에 Char -> Bool 타입인 isLower, isUpper, isAlpha, isAlphanum 등의 함수를 사용하면 얼마든지 다른 형식의 문자만 떼어내는 파서를 만들 수 있습니다. (이들 함수는 모두 Data.Char 모듈에 있습니다.)

비슷한 예로 떼어낸 글자가 미리 정한 어떤 글자와 같은 경우를 원할 수도 있습니다. 이건 간단하게 작성할 수 있겠네요.

char :: Char -> Parser Char
char x = sat (== x)

char 함수처럼 쓰되 한 개의 문자가 아니라, 여러 문자에 대해서 재귀형태로 써서 원하는 문자열을 뽑아내는 파서를 만들 수 있습니다. 아래 코드는 어떤 문자열을 주고 그 문자열과 일치하는 앞부분을 뽑아냅니다.

string :: String -> Parser String
string [] = return []
string (x:xs) = do
  x <- char x
  string xs
  return (x: xs)

쉽죠? 여기서 흥미로운 점은 중간에 글자가 틀렸을 경우에 대한 처리가 따로 필요없어 보인다는 것입니다. 왜냐? 재귀적으로 호출되는 과정에 failure가 발생한다면, 더 이상 반복을 진행하지 않고 do 블럭 전체가 failure로 평가되기 때문이죠. 게다가 failure는 빈 리스트를 반환하기 때문에, 만약 처리 중간에 failure로 귀결된다면 남아있는 문자열 뒷부분에 대한 파싱도 그자리에서 중단됩니다.

마찬가지로 ys <- string xs 라고 바인딩을 쓸 필요도 없습니다. 중간의 어디선가 x <- char x가 실패한다면 failure로 끝나기 때문이죠.

숫자값을 파싱하는 경우를 생각해보겠습니다. 2자리 이상의 숫자는 앞서 만든 digit파서를 이용해서 string 파서를 만든 것과 같이 재귀적으로 돌아가도록 작성하여 파서를 만들 수 있을 것입니다. 그런데 문자열, 부호, 공백, 숫자, 알파벳… 이런 식으로 원하는 데이터 종류마다 단일 문자 파서를 만들고 이를 통해 다시 재귀호출하는 파서를 만드는 것은 여간 귀찮은 일이 아닐 수 없습니다.

이 케이스들을 일반화하여 아예 같은 타입의 값 여러 개를 파싱해내는 many 함수를 만들어 버립시다. 이는 many' 라는 보조 함수를 사용해서 상호 재귀 형태로 파서 p를 반복해서 적용하고, 매 결과들을 리스트로 묶어 냅니다.

many :: Parser a -> Parser [a]
many p = many' p +++ return []
many' :: Parser a -> Parser [a]
many' p = do
  x <- p
  xs <- many p
  return (x:xs)

do 블럭의 특성상 잔여 문자열을 다음 라인으로 넘기는 코드가 생략되기 때문에 표현이 엄청나게 간단해졌습니다. many는 처음에 many’를 호출하고, many’는 첫 글자를 파싱하고 다시 many를 통해 나머지 부분을 파싱한 결과를 얻습니다. 최정적으로는 (x: xs)로 얻어진 값들을 하나의 리스트로 만들어버립니다. 이제 너무 간단하게 정리돼서 살짝 무서운 기분이듭니다.

many를 사용하면 자연수를 파싱해서 정수로 바꾸는 파서를 다음과 같이 간단히 만들 수 있습니다. many digit 으로 숫자의 리스트를 얻은 다음, read 함수를 적용해서 정수로 변환하면 됩니다. 이 일을 하는 자연수 파서 nat은 다음과 같습니다. 이 외에도 many 파서는 이후 여러 곳에서 상당히 유용하게 쓰이게 됩니다.

nat :: Parser Int
nat = do
  ds <- (many digit)
  return (read ds)

이번에는 공백을 처리하는 방법을 생각해봅시다. 보통 파서에서 공백은 토큰을 구분할 때 쓰며, 공백 자체가 트리로서 의미를 갖고 쓰일 일이 없으니 그냥 빈값 ()을 리턴해버리면 됩니다. many를 사용해 하나 혹은 그 이상의 연속된 공백을 이런식으로 무시해나갈 수 있습니다.

spc :: Parser ()
spc = do
  many (sat isSpace)
  return ()

이번에는 이 spc 파서를 사용해서 공백으로 구분되는 단어 하나를 읽어내는 token 함수를 작성해보겠습니다. 이 함수는 파서를 하나 받아서 앞의 공백을 버리고, 공백이 아닌 영역을 파서를 통해 읽고, 다시 공백을 버립니다. 즉 공백을 기준으로 잘라낸 가운데 토큰 값만을 얻는 파서로 변환해주는 함수입니다.

token :: Parser a -> Parser a
token p = do
  spc
  x <- p
  spc
  return x

이번에는 특정한 문자열에 해당하는 토큰을 파싱하는 함수를 만들어봅니다. string xs로 특정한 문자열을 앞에서부터 자를 수 있는데, 이 앞뒤의 공백을 무시하면 되니, token에 연결하기만 하면 됩니다. (참 쉽죠?)

symbol :: String -> Parser String
symbol xs = token (string xs)

지금까지 만들어진 모나드와 모나딕 함수/연산을 정리해보겠습니다.

  1. item – 무조건 한 글자를 파싱합니다.
  2. digit – 숫자 한개를 파싱합니다.
  3. sat – 함수 f를 만족하는 파서를 생성합니다.
  4. char – 주어진 글자와 같은 경우에 그 글자를 파싱합니다.
  5. string – char를 반복적용하여 주어진 문자열과 같은 문자열을 파싱합니다.
  6. many – 파서를 반복해서 적용하고, 그 결과를 리스트로 만드는 모나딕함수입니다
  7. nat – 숫자인 글자를 반복적으로 파싱하여 정수값을 파싱합니다.
  8. spc – 공백을 반복적으로 파싱합니다.
  9. token – 공백으로 나눠진 단어를 파싱합니다.
  10. symbol – 문자열로된 토큰을 파싱합니다.

기본적인 간단한 파서들을 준비했으니, 이를 조합하여 정수의 리스트를 표현하는 리터럴 문자열을 읽어서 정수 리스트로 파싱하는 파서를 만들어봅시다. 의외로 어렵지 않습니다. 일단 코드는 이렇게 됩니다.

natList :: Parser [Int]
natList = do
  symbol "["
  n <- token nat
  ns <- many (do symbol ","
                 token nat)
  symbol "]"
  return (n:ns)

동작 과정을 보겠습니다.

  1. “[” 문자를 파싱합니다. 대괄호 주변의 공백은 무시되겠죠?
  2. token nat을 사용하여 처음에 나오는 정수값 하나를 파싱합니다.
  3. 다음은 컴마 정수… 가 순서대로 0 개 이상 나올 수 있습니다. 이를 위해 many에 (do symbol ","; token nat)을 적용해줍니다. 바깥의 do 블럭이 Parser 모나드이기 때문에 내부의 do 블럭 역시 동일하게 Parser 입니다. 즉 콤마 다시 정수 이 패턴을 반복합니다. 물론 do의 마지막 액션의 결과인 숫자값만 리턴되면서 ns는 정수의 리스트가 됩니다.
  4. 마지막으로 “]”로 닫습니다. 이렇게 닫히지 않는다면 올바른 정수 리스트가 아니겠죠.
  5. 이제 모든 정수들을 리스트로 연결하여 리턴합니다.

만약 이 파서가 파싱을 실패했을 때, 빈 리스트를 내놓는 파서를 어떻게 구현하면 좋을까요? 네, natList +++ return [] 입니다.

이제 이 파서가 올바르게 동작하는지 보겠습니다. main 함수를 다음과 같이 작성합니다.

main :: IO ()
main = do
    str <- getLine
    let [(ds, _)] = runParser natList str
    print ds
    print $ foldl1 (+) ds

프로그램을 실행하고 “[1,2,3,4]” 따위의 정수 리스트 표현식을 입력하면 파싱된 결과와 정수 리스트의 합을 출력합니다.

정리

지금까지 보였던 예시는 item 이라는 단순히 문자열의 첫 글자를 떼어내는 간단한 파서를 만든 후, 이를 모나드로 정의하고 모나드의 성질로부터 모나드를 변환/조합하는 과정을 통해서 정수 리스트를 파싱해내도록 확장하는 과정을 보인 것입니다.

모나드의 성질이나 개념 자체를 모두 이해할 필요는 없지만, 단순히 기성 모나드를 사용하는 것만으로는 모나드를 활용하는 것에 부족함이 느껴지는 것이 사실입니다. 함수와 함수를 합성하여 새로운 함수를 만드는 것처럼, 모나드 역시 모나드를 만드는 함수와 바인드 연산을 통해 연산을 조합하고 보다 복잡한 동작을 수행하는 연산으로 확장해 나갈 수 있다는 점을 이해하는 것이 중요하며, 거기에 이 글이 조금이나마 도움이 되었으면 합니다.