여기 글들은 일종의 질문입니다. 용어 선택도 학계, 업계에서 쓰는 걸로 되어 있지 않고, 틀린 내용이 있을 수도 있습니다.
참고 문서1들을 보고 의문이 생기는 부분들을 정리한 포스트이니, 참고 문서들을 먼저 보세요.
여기 쓰인 코드는 parsec의 기본 아이디어를 볼 수 있도록 간단하게 만든 nanoparsec의 코드로 아래 사이트에서 발췌했습니다. Stephen Diehl-Parser(2023-11-30 사이트는 열리는데, 해당 주소는 열리지 않습니다.)
※ 위 사이트 코드는 그래함 허튼, 에릭 마이어의 Monadic parsing in haskell 문서의 Gofer코드를 하스켈로 수정한 코드입니다.
왜 모나드 구조가 어울리는지부터 고민해보고 가겠습니다. 문자열stream을 받아서, 파서가 지정한 단어가 있으면, 문자열을 단어 길이만큼 consume하고 찾은 단어를 기억하고, 아니면 하나도 consume하지 않고 에러를 리턴합니다. 그 다음 이어지는 파서가 또 다시 원하는 단어가 있는지 봐서, 있으면 consume하고, 찾은 단어들을 누적하고 없으면 에러를 리턴할 겁니다.
-- 2021/05/19 이렇게 생긴 날짜를 파싱한다면 이런 모양을 예상할 수 있습니다.
parser 숫자4개 >>= parser '/' 또는 '-' >>= parser 숫자2개 >>= parser '/' 또는 '-' >>= parser 숫자2개
do
parser 숫자4개
parser '/' 또는 '-'
parser 숫자2개
parser '/' 또는 '-'
parser 숫자2개결과 누적에 특화된 모나드가 state 모나드가 있고, 분기하는 모나드로 가장 유명한게 Maybe 모나드입니다. 둘과 비슷한 모양의 바인드가 나오지 않을까 예상하며 다음으로 넘어가겠습니다.
newtype Parser a = Parser { parse :: String -> [(a,String)] }유지하고 있어야 할 정보가 두 가지입니다. 리스트로 가지고 있든, 특별히 만든 타입으로 가지고 있든, 두 가지 정보만 가지고 있으면 됩니다. 두가지 정보를 효율적으로 묶어 놓기 좋은 방법이 바로 튜플입니다. 파싱된 결과가 하나가 아닐 경우를 위해 리스트로 만들었습니다.
Parser는 문자열을 받아서 어떤 작업을 한 후 튜플 리스트를 돌려주는 함수 타입을 말합니다.
파서를 “스트림을 받아서 튜플 리스트를 주는 함수” 타입이라 읽겠습니다. 아마도 파서를 연결 연결한 모양으로 스트림을 파싱하게 될 겁니다. Parser는 입력은 문자열인데, 출력이 튜플이라 컴포지션이 안됩니다. 나중에 들어올 값이 첫 번째 Parser를 통과하고, ‘남은 스트림’과 ’파싱된 결과’ 이 두 개의 정보를 가지고, 두 번째 Parser도 통과할 준비를 해놔야 합니다. 이게 바로 바로 값을 통과시키며 따라가는게 아니라, 값은 언젠가 들어 오겠거니 하고 함수를 미리 조립해 놓는 것입니다.
String -> (a, String)쯤이면 될 것 같은데, 결과값이 왜 튜플 리스트일까요? 파서가 실패하게 되면 Maybe 타입을 써서 Nothing을 리턴하고, 성공하면 Just (a, String)을 리턴하게 할 수도 있을텐데, 그러지 않고 리스트를 이용했습니다. 성공하면 싱글턴 리스트 [(a, String)], 실패하면 빈 리스트 []를 리턴하도록 만들었습니다. 이렇게 리스트로 만들면, 딱 하나의 결과만 나오는 파서가 아닌 여러 갈래의 길로 나갈 수도 있는 파서를 만들 수 있습니다. (@todo:여러 갈래길이 나오는 예시 추가)
bind :: Parser a -> (a -> Parser b) -> Parser bParser a와 a -> Parser b를 연결하는 bind입니다. 왜 Parser a -> Parser b가 아닐까요?
보통 모나드에서 bind를 정의할 때는 m a 자체가 함수가 아니어서, m a -> (a -> m b) -> m b 의미를 알겠는데, Parser는 Parser 자체가 함수라 Parser a와 Parser b를 연결하는 bind를 만들면 될 것 같은데, 왜 a -> Parser b 가 나왔을까요?
익숙한 Maybe부터 다시 살펴 보겠습니다.
data Maybe a = Just a | Nothing
bind :: Maybe a -> (a -> Maybe b) -> Maybe bMaybe 바인드는 첫 번째 Maybe와 두 번째 Maybe를 연결하는게 아닙니다. 첫 번째 Maybe와 Maybe를 만들어내는 함수를 연결합니다. 어떤 뜻일까요? 첫 번째 Maybe에서 Maybe를 벗겨내고 a를 꺼내면서 Maybe의 펑크터 컨텍스트가 발현됩니다. Nothing인지 보는 겁니다. Nothing이 아니라면 내부에서 어떤 작업을 한 후 다시 Maybe로 감쌉니다. 컨텍스트를 발현시키려면 반드시 벗겨 내는 절차가 나와야 합니다.
그럼 똑같이 Parser에 적용해 보겠습니다. Parser를 벗겨내고 a를 꺼내면서 Parser 컨텍스트가 발현되고 결과를 다시 Parser로 감쌉니다. 일단, 추측할 수 있는게, 파서를 돌리고, 그 다음 파서를 돌리기 전에 어떤 사전 작업을 할 거라 예측을 할 수 있습니다. 단순히 파싱 결과로 나온 정보를 다음 파서가 그대로 가져가지 않고 뭔가 상황을 보고 다음 파서로 간다는 말입니다. 이제 궁금한 대상이 조금은 더 좁혀졌습니다. Parser의 컨텍스트가 뭔지 알아야 합니다.
바인드의 정의를 살펴 보면
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s
-- 결과값을 누적시키는 바인드 참고 - state 모나드의 바인드
(State x) >>= f = State $ \s -> let (v,s') = x s in runState (f v) s'
-- state모나드 액션은 s -> (a, s)
-- 상태s를 받아 (결과, 새로운 상태) 튜플을 리턴하는 액션입니다.
-- 다음 액션을 만드는 f에 결과값 v를 넣어 액션을 만든 다음 새로운 상태 s'을 넣어줍니다.
-- 값에 따라 체인을 끊을 수 있는 바인드 - 참고 Maybe 모나드의 바인드
Nothing >>= f = Nothing -- Nothing일 경우 아예 다음 액션인 f를 실행하지 않습니다.
(Just x) >>= f = f xconcatMap은 concat과 Map을 합친 함수입니다.
> concat [[1],[2]]
[1,2]
> :t concatMap
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]bind p f 는p를 나중에 들어올(인자로 받을) 스트림에 적용해서 나온 튜플 a, s' 중a에 f함수를 적용하고 나온 파서를 s'에 적용한 후concat할 준비를 합니다.bind p f의 결과도 하나의 파서입니다. 무슨 일이 벌어지는 건지 더 자세히 읽어 보겠습니다.
f 함수는 a -> Parser b 타입의 함수로, 첫 번째 파서 p의 결과에서 튜플(a,s') 하나를 뽑아 그 중 a를 넣어주면Parser b를 결정합니다. 이 Parser b를 나머지 스트림s'에 다시 적용합니다. 결과로 튜플 리스트가 나옵니다.p의 결과에서 또 하나의 튜플을 뽑아 Parser b를 적용하고 결과로 튜플 리스트가 나옵니다.([(O,O),(O,O)...], [(O,O),(O,O)...],...) 이런 형태가 되고, concat을 먹이면[(O,O),(O,O),(O,O)...]이 됩니다.이렇게 바인딩, 바인딩되어 큰 하나의 파서가 된 걸
runParser :: Parser a -> String -> a
runParser m s =
case parse m s of
[(res, [])] -> res
[(_, rs)] -> error "Parser did not consume entire stream."
_ -> error "Parser error."runParser에 넣으면, 스트림을 모두 consume했으면 결과를 돌려주고 아니면 에러가 납니다.
2021.5.22 추가
※ 아래 코드는 그래함 허튼의 문서에서 발췌했습니다.
seq :: Parser a -> Parser b -> Parser (a,b)
p ‘seq‘ q = \inp -> [((v,w),inp’’) | (v,inp’) <- p inp, (w,inp’’) <- q inp’]고퍼 언어 코드인데, 여기선 하스켈하고 크게 다른 부분이 없습니다. 눈여겨 볼 부분이 p파서 결과와 q파서 결과를 ( (v,w), ...) 로 유지하고 있습니다. 이렇게 합쳐진 파서와 또 다른 파서를 합치면 아마도 (((v,w), x), ...) 이렇게 될 겁니다. 나중에 파싱 결과를 이용하기 위해서 어딘가에는 저장해 둬야 합니다. 리스트같은 데이터 타입을 만들어 주욱 저장해 놓고 다음 파서로 넘기게 해서 끌고 다니는 것도 한 가지 방법이 될 수 있습니다. 어떻게든 정보를 모두 저장해서 나중에 한 번에 처리하는 함수에 모두 넘겨야 합니다. 함수형은 매개 변수 이외에는 정보를 받을 수 없는, 외부 변수값에 절대 접근 할 수 없는 특징 때문에 생긴 고민입니다. 하지만 이렇게 함수들을 엮는(연결하는, 합성하는, combine하는, bind하는) 모양엔 중요한 특징이 있습니다.
바로 람다 변수에 결과를 저장할 수 있습니다. 다른 말로 클로저를 활용하는 겁니다. 참고 - 모나드 문턱에서 포스트
두 가지 경우 모두 클로저를 활용하는 방법으로 해결할 수 있습니다. 비수학적으로 모나드를 바라 볼 때, 아주 중요한 특징입니다.
파서1 >>= \r1 -> 파서2 >>= \r2 -> 파서3 >>= \r3 -> 최종 작업이 체인의 끝에 있는 최종 작업은 r1, r2, r3를 모두 사용할 수 있습니다. 액션과 액션을 바로 붙이지 않고, 접착제로 쓰이는 바인드>>=함수가 람다 변수에 결과값을 저장하도록 만드는 게, 모나드 패턴을 쓸 때 아주 유용합니다.
bind :: Parser a -> (a -> Parser b) -> Parser b
p ‘bind‘ f = \inp -> concat [f v inp’ | (v,inp’) <- p inp]두 번째 인자로 받은 f :: a -> Parser b 함수를 첫 번째 파서p의 결과값v에 적용, 결과적으로 p의 리턴값을 람다 변수에 두면서 바인딩하게 됩니다. 이렇게 람다 변수에 둔 값은 현재 액션에서 써먹을 수도 있고, 이 체인에 연결되어 있는 다른 액션(보통은 가장 마지막 액션)에서 써 먹을 수도 있습니다. 다른 함수들의 결과를 매개 변수로 명시적으로 받지 않아도 써먹을 수 있는 중요한 특징입니다.
클로저를 어떻게 보냐에 따라, “매개 변수 이외에는 절대 정보를 받을 수 없다”는 맞는 말일수도, 틀린 말일 수도 있습니다.
다음은 파서를 조립할 때 쓸 컴비네이터들입니다.
※ Combinator - 람다 대수에선 free variable이 없는 함수를 말하지만, 여기선 Parser함수와 Parser함수를 연결해서 또 다른 Parser함수를 만드는 접착제 갈은 역할을 하는 브로커 함수들을 말합니다. 모나드의 바인드같은 함수들을 컴비네이터라 부릅니다. 의미에 맞게 번역한다면 접착 함수쯤일텐데 입에 딱 감기진 않습니다. - https://wiki.haskell.org/Combinator
combine :: Parser a -> Parser a -> Parser a
combine p q = Parser (\s -> parse p s ++ parse q s)
-- 이렇게 파싱 결과를 합치려면 결과가 [(,)] 인게 말이 됩니다.
failure :: Parser a
failure = Parser (\cs -> [])
option :: Parser a -> Parser a -> Parser a
option p q = Parser $ \s ->
case parse p s of
[] -> parse q s
res -> res
instance MonadPlus Parser where
mzero = failure
mplus = combine
instance Alternative Parser where
empty = mzero
(<|>) = option상호 재귀2로 매직같은 일을 하는 Alternative 클래스의 메소드 some, many는 다른 기본 함수들을 훑어 본 후 자세히 보도록 하겠습니다.
-- 하나 이상
some :: f a -> f [a]
some v = some_v
where
many_v = some_v <|> pure []
some_v = (:) <$> v <*> many_v
-- 0 이상
many :: f a -> f [a]
many v = many_v
where
many_v = some_v <|> pure []
some_v = (:) <$> v <*> many_v이 함수들을 이용해 현재 글자가 predicate함수(ex. isDigit, isLetter,..)를 만족하는지 확인하는 함수를 만들 수 있습니다.
unit :: a -> Parser a
unit a = Parser (\s -> [(a,s)])
item :: Parser Char
item = Parser $ \s ->
case s of
[] -> []
[c:cs] -> [(c,cs)]
satisfy :: (Char -> Bool) -> Parser Char
satisfy p = item `bind` \c ->
if p c
then unit c -- Just와 닮았습니다.
else (Parser (\cs -> [])) -- Nothing과 닮았습니다.여기까지가 기본 재료들이 되는 코드입니다. 이 코드들을 재료로 고차원적인 파서들을 만들어 가게 됩니다.
char :: Char -> Parser Char
char c = satisfy (c ==)
satisfy ('A' ==)
= item `bind` \c -> if ('A' == c)
then unit c
else (Parser (\cs -> []))char 'A' >>= (\_ -> char 'A') 파서 뭉치를 "AA" 문자열에 적용하는 걸 풀어 보겠습니다. (여러 파서를 바인딩 해 놓은 걸 표현할 적당한 용어가 떠오르지 않습니다. 일단 투박하지만 뭉치라 표현하겠습니다.)
runParser :: Parser a -> String -> a
runParser m s =
case parse m s of
[(res, [])] -> res
[(_, rs)] -> error "Parser did not consume entire stream."
_ -> error "Parser error."
> runParser (char 'A') "AA"
case \s-> [('A',"A")] `bind` \c -> if ('A' == c)
then unit c
else (Parser (\cs -> []))일단 char 'A'부터 풀면,
-- item `bind` (\c ->...) 를 풀면
concatMap (\(a, s') -> (f파서 a) s') $ \s -> item파서 "AA"
concatMap (\(a, s') -> (f파서 a) s') $ [('A',"A")]
-- a는 'A', s'은 "A"
( parse ( 결과 'A'를 보고 unit 파서 선택 ) "A" )
( parse ( unit 'A' ) "A" )
(\s -> [('A',s)] ) "A"
[('A',"A")]첫 번째 파서 char 'A'가 실패하지 않았기 때문에 다음 바인딩 되어 있는 char 'A'에 "A"가 넘어갑니다.
concatMap (\(a, s') -> (f파서 a) s') $ \s -> item파서 "A"
concatMap (\(a, s') -> (f파서 a) s') $ [('A',"")]
-- a는 'A', s'은 "A"
( parse ( 결과 'A'를 보고 unit 파서 선택 ) "" )
( parse ( unit 'A' ) "" )
(\s -> [('A',s)] ) ""
[('A',"")]만일 파서 뭉치를 "BA" 문자열에 적용하면
( parse ( (\c -> ...) 'B') "A" )
( parse ( Parser (\cs -> [])) "A" )
[]위 코드를 말로 표현하면, char 'A' 파서는
한 글자를 봐서 A이면 [('A',나머지 문자열)] 아니면 [] 작업을 하는 파서입니다.
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser achainl은 LL파서에서 흔히 만나는 왼쪽 무한 재귀left-recursive grammar를 피하기 위해 쓴다고 합니다.
왜 사람들이 궁금해 하지 않을까요? 인터넷에서 꽤 많은 파서 관련 글들을 찾아 보았는데, 다들 이렇게 저렇게하면 무한 재귀가 사라진다하고 넘어갑니다. 아니면 생성 규칙 가장 왼쪽에 같은 비단말이 있어서 그렇다는 동어 반복 같은 설명만 있습니다.
드래곤책(Compilers Principles, Techniques, and Tools - Alfred V.Aho 외)에 있는 설명을 보면
A -> Aα | β이 문법이 만들어 낼 수 있는 토큰열 : βα, βαα, βααα …
이 문법은 무한 재귀가 돌고
A -> βA'
A' -> αA' | ε이 문법이 만들어 낼 수 있는 토큰열 : βα, βαα, βααα …(위와 같습니다.)
이렇게 문법을 쪼개면 무한 재귀가 사라집니다.
같은 문자열을 생성하는 규칙인데, 어째서 차이가 날까요? 두 번째 문법은
α반복과 β를 분리해서 각각의 규칙을 만들었습니다.
Aα는 α 하나를 매칭하기 전 비단말 A를 풀어야 하고, αA'는 α 하나를 매칭하고, 그 다음 비단말 A'를 풉니다.
두 단계로 규칙을 나누면 비단말 두 개를 풀기 위해 생성 규칙이 두 번 적용됩니다. 그런데 첫 번째 규칙을 적용하는 순간 매칭이 이루어지면 lookahead(입력 토큰열의 현재 토큰을 가리키는 포인터)가 다음 토큰으로 넘어갑니다. 이게 주요 아이디어 같습니다.
아이디어를 알아야, 나중에 왼쪽 재귀를 넣어야 될 상황이 오면 대처할 수 있을텐데 아이디어를 콕 집어서 설명해주는 자료를 못 찾았습니다.
제가 정리한 아이디어는 다음과 같습니다.
이 정리도 딱 마음에 드는 건 아닌데, 재귀가 가장 왼쪽에 있어서 그렇다는 설명보다는 조금 더 낫지 않을까 합니다.
그럼 이 아이디어를 기억해 두고, chainl을 풀어 보겠습니다.
왜 Parser (a -> a -> a) 타입의 파서 연산자가 왔을까요? p는 term이나 expr등이 들어옵니다. expr과 term이 그냥 붙어 있진 않습니다. + 나 * 같은 연산자를 통해 여러번 붙어 있는 걸 파싱하는게 목표입니다. 그래서 두 번째 인자는 파서 두 개를 받아 합친 파서를 만들어 주는 연산자가 들어옵니다. 다시 정확히 얘기하면
( 연산자는 여러가지가 올 수 있는데, 눈에 잘띄도록 연산자는 +로 표기 하겠습니다. )
p에 파서를 넣으면, 반복된 + p를 p뒤에 붙여야 합니다.
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) <|> return a
-- p가 한번 이상 매치되는 걸 파싱합니다.
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do r <- p -- r은 나중에 토큰열을 받으면 a 타입 값이 될 함수
rest r
where rest r1 = (do oper <- op
r2 <- p -- 파서는 같은 파서입니다.
rest (oper r1 r2)) <|> return arest 함수는 op에서 파서 연산자를 꺼내고 (ex. +)
p 에서 파서를 꺼내
처음 lookahead가 가리키는 토큰을 파싱하는 파서와
다음으로 이동한 lookahead가 가리키는 토큰을 파싱하는 파서를
연산자로 붙입니다. 그리고, 다시 자기 자신을 부릅니다.(재귀)
언제까지? 파싱이 실패해서 <|> return a가 돌 때까지 계속합니다.
정리하면, 몇 번이고 +p를 적용할 준비가 되어 있는 파서 뭉치를 만들어냅니다.
rest 함수가 하는 일은, 3번 아이디어의 lookahead를 다음으로 이동하는 역할을 합니다. r1 에서 <-가 동작해서 lookahead를 옮기고, r2 에서 <-가 동작해서 lookahead를 옮깁니다.
expr = expr + term을 파싱해 보겠습니다.
expr과 매칭할 파서는 다음 모양 중 하나일 겁니다.
expr = term 이거나,
expr = expr + term 이거나,
expr = (expr + term) + term 이거나,
expr = ((expr + term) + term) + term 이거나,
...
-- expr 비단말은 언젠가는 term 비단말로 풀릴테니
term 이거나,
term + term 이거나,
(term + term) + term 이거나,
((term + term) + term) + term 이거나,
...α가 + term, β가 term입니다. 비단말 expr은 term 하나가 아니라, term을 한 번 실행하고 + term을 반복시키는 역할을 할 뿐입니다.
expr :: Parser Expr
expr = term `chainl1` addop 표기를 간단히 하기 위해 addop를 + 하나로 생각하고, chainl이 준비하는 파서 모양을 보면
-- r1 : term
-- r2 : term
-- oper : +
-- rest 함수 재귀를 돌려보면,
...return a...
...rest (term + term)...
...rest ((term + term) + term)...
...rest (((term + term) + term) + term)...
...위의 expr 파서 모양과 동일함을 알 수 있습니다.
Q. 어차피 파싱 함수가 한 번 매칭을 하면
lookahead가 다음으로 넘어가는데, 단순히 재귀를 돌리는 것과 무슨 차이가 있을까요?
A. 매칭을 호출했다고lookahead를 다음으로 보내지 않습니다. 매칭 작업을 완료하면 넘어가지만, 매칭을 완료하기 전에 재귀 호출을 하면lookahead는 다음으로 넘어가지 않습니다.
Q.
Some term을 부르는 것과 무슨 차이일까요?
A.Some term에는 연산자가 빠져 있습니다.runParser (some expr) "123(345)"이런 경우 매칭은 되나, 중간에 연산자가 있는 토큰열은 매칭되지 않습니다.
Q. 그럼
term과many (+ term)을 붙이는 건 어떨까요?
A. 가능합니다. 이해한게 맞는지 확인하기 위해 에러에 에러, 에러산을 넘어 만들긴 했는데, 코드가 더 줄어들거나 보기 좋진 않네요.chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a chainl1 p op = do r <- p rest r where rest r1 = ( do r2 <- ( many (op >>= \f -> p >>= \b -> return $ f b) ) -- ex. Parser [ ( (+int):(+int):[] , "" ) ] return $ ( (foldl (flip ($)) r1 r2) ) -- int + int + int ) <|> return r1
※ GHC는 newtype으로 싸놓은 Parser를 필요할 때까지 뭔지 보지 않습니다. 안에 함수가 들어 있는지, 무슨 구조로 되어 있는지 관심이 없습니다. 그저 a를 래핑한 타입으로 봅니다. 패턴 매칭으로 벗겨져야만 함수가 드러납니다.
※ 설마 이런 오해를 할까 싶은 오해도 합니다.
Parser (a -> a -> a) 에서 Parser를 벗겨내면 (a -> a -> a)가 나올까요?
선언에 쓰여있는 Parser (a -> a -> a)는 값이 아니라 타입 생성자입니다. 이 타입의 값에서 값 생성자 Parser를 벗겨내면
String -> [ ( (a -> a -> a) , String) ] 타입의 값이 나옵니다. 굳이 (a -> a -> a)를 이 구조안에 우겨 넣을까요? Parser 컨텍스트를 유지하기 위해서입니다.
타입 생성자가 아닌 값 생성자 Parser로 값을 만들려면 String -> [(a, String)] 타입의 함수를 인자로 줘야 합니다.
-- char 'A', char 'b', char '=' ...
char :: Char -> Parser Char
char c = satisfy (c ==)
-- 하나 이상의 숫자를 가진 숫자열
natural :: Parser Integer
natural = read <$> some (satisfy isDigit)
-- string "hello"
string :: String -> Parser String
string [] = return []
string (c:cs) = do { char c; string cs; return (c:cs)}
-- 공백으로 분리된 낱말
-- token (string "WORD")는 "WORD "를 파싱
token :: Parser a -> Parser a
token p = do { a <- p; spaces ; return a}
-- string과 token을 합쳐 놓은 건데, 여기서 매칭된 건 파싱 결과에 포함되지 않습니다.
-- 예약어란 의미에서 reserved입니다.
-- (SOME) 을 parens SOME으로 파싱하면 결과는 ()를 뺀 SOME입니다.
reserved :: String -> Parser String
reserved s = token (string s)
-- 공백 문자
spaces :: Parser String
spaces = many $ oneOf " \n\r"
-- 숫자 하나
digit :: Parser Char
digit = satisfy isDigit
-- 부호 포함 숫자열
number :: Parser Int
number = do
s <- string "-" <|> return []
cs <- some digit
return $ read (s ++ cs)
-- parens (some digit) 하면
-- (11) ( 11) 은 인식하는데, (11 )은 못합니다.
parens :: Parser a -> Parser a
parens m = do
reserved "("
n <- m
reserved ")"
return n상호 재귀를 기차게 쓰는 예시입니다.
Applicative 클래스의 메소드 some, many를 살펴보겠습니다.
https://hackage.haskell.org/package/base-4.6.0.1/docs/src/Control-Applicative.html#%3C%2A
some :: f a -> f [a]
some v = some_v
where
many_v = some_v <|> pure []
some_v = (:) <$> v <*> many_v
many :: f a -> f [a]
many v = many_v
where
many_v = some_v <|> pure []
some_v = (:) <$> v <*> many_vsome에서 출발해 보겠습니다.
some v
= some_v
= (:) <$> v <*> many_v -- (1단계)
= (:) <$> v <*> (some_v <|> pure []) -- (2단계)
= (:) <$> v <*> (((:) <$> v <*> many_v) <|> pure []) -- (3단계)
= (:) <$> v <*> (((:) <$> v <*> (some_v <|> pure [])) <|> pure [])
= (:) <$> v <*> (((:) <$> v <*> (((:) <$> v <*> many_v) <|> pure [])) <|> pure [])
= ...reduce과정이야 무식하게 따라가면 읽을 수 있긴 한데, 이 상호 재귀의 종료 조건(엣지 조건)은 뭘까요?
v를 반복해서 붙여 놓습니다. 붙일 때마다 언제든 다음 단계로 진행하지 않을 조건 바로 <|> pure []도 계속 같이 붙여 놓습니다. 이 함수들은 꼭 파서를 위한 함수들만은 아닌데, 파서를 만들면서 같이 나온 건 아닐까 싶습니다. 파서와 정말 찰떡인 함수들입니다. 몇 번이고 반복하다가 파서가 실패하면 <|> pure [] 로 넘겨서 더 이상 진행하지 않고 결과값을 리턴합니다. many_v 는 <|> pure []를 붙이는 역할, some_v는 v를 리스트에 넣어두는 역할을 반복하고 있습니다. 하스켈을 공부하려면 충분히 Lazy해져야 합니다.
이 파서 뭉치는 상호 재귀가 끊임 없이 되어 있어 쓸 수 있는 함수는 무한대로 준비 되어 있습니다. 하지만 함수를 꺼내 쓰다 한 번이라도 fail하면 더 이상 이 뭉치에서 함수를 꺼내지 않습니다. 끊임 없이 준비를 해야 하는데, 필요하면 그 때 준비를 하지, 미리 준비해 놓지 않습니다. 하나를 적용한 후 fail하지 않으면, 다음 재귀를 돌려 또 함수 하나를 꺼내고, 또 꺼내고,… 그러다 fail이 나면 더 이상 진행하지 않고 결과를 리턴하는 함수 뭉치입니다.
머릿속에서 시뮬레이션할 때, 딱 필요한 시점에 재귀를 한 단계만 돌리세요.
어플리커티브<*>를 쓰는 이유는, fmap(중위 표현 <$>)을 쓰면 펑크터 안에서 커링된 상태가 되기 때문입니다. 참고 - 컨텍스트, Applicative Functor, Traversable
실제 파서와 같이 쓰이는 걸 해석해 보기 위해 some digit를 풀어 보겠습니다.
instance Functor Parser where
fmap f (Parser cs) = Parser (\s -> [(f a, b) | (a, b) <- cs s])
instance Applicative Parser where
pure = return
(Parser cs1) <*> (Parser cs2) = Parser (\s -> [(f a, s2) | (f, s1) <- cs1 s, (a, s2) <- cs2 s1])
instance Alternative Parser where
(<|>) :: Parser a -> Parser a -> Parser a
p <|> q = Parser $ \s ->
case parse p s of
[] -> parse q s
res -> res저는 위 정의를 유심히 보지 않고, Maybe의 정의와 비슷하겠거니 하고 그냥 읽다가 헤맸습니다. 위 정의를 먼저 잘 봐야합니다.
some digit
= ( (:) <$> digit <*> many_v ) "12345"
= ( (:) <$> (\s -> [(a,s)] 또는 \s -> []) <*> many_v ) "12345"
-- 일단 <*> many_v 앞에 것부터
(:) <$> Parser (\s -> 숫자파서) ---------------------------------- (1번)
= Parser (\s -> [ ( (:) a, b) | (a, b) <- 숫자파서 s])
-- <*> many_v를 붙이면
Parser (\s0 -> [ ( (:) a, b) | (a, b) <- 숫자파서 s0]) <*> many_v
= Parser (\s -> [(f a, s2) | (f, s1) <- (\s0 -> [ ( (:) a, b) | (a, b) <- 숫자파서 s0]) s
, (a, s2) <- many_v s1] )
-- s에 문자열 "12345"가 들어가면
= [(f a, s2) | (f, s1) <- (\s0 -> [ ( (:) a, b) | (a, b) <- 숫자파서 s0]) "12345"
, (a, s2) <- many_v s1] )
-- s0에 문자열 "12345"가 들어가면
= [(f a, s2) | (f, s1) <- ([ ( (:) a, b) | (a, b) <- 숫자파서 "12345"])
, (a, s2) <- many_v s1] )
= [(f a, s2) | (f, s1) <- ([ ( (:) '1', "2345") ])
, (a, s2) <- many_v s1] )
= [(f a, s2) | (f 는 (:) '1', s1은 "2345") , (a, s2) <- many_v "2345"]
-- 하스켈은 Lazy하니 여기까지 와서야 many_v를 (1번) <*> many_v 으로 reduce 합니다.
= [ (f a, s2) | (f 는 (:) '1', s1은 "2345") , (a, s2) <-
[(f a, s2) | (f 는 (:) '2', s1은 "345") , (a, s2) <- many_v "345"]
]
...
-- many_v가 실패해서 <|> pure []를 만날 때까지 계속 적용하면
= [(f a, s2) | (f 는 (:) '1', s1은 "2345") , (a, s2) <-
[(f a, s2) | (f 는 (:) '2', s1은 "345") , (a, s2) <-
[(f a, s2) | (f 는 (:) '3', s1은 "45") , (a, s2) <-
[(f a, s2) | (f 는 (:) '4', s1은 "5") , (a, s2) <-
[(f a, s2) | (f 는 (:) '5', s1은 "") , (a, s2) <- many_v ""]
]
]
]
]
-- 가장 안 쪽 many_v = some_v <|> pure [] 는 ""를 받으니, a= '', s2 = ""
-- (:) 프리픽스를 인픽스 형태로 쓰고, 안쪽부터 바깥으로 풀면서 나오면
'5' : "" , ""
'4' : '5' : "", ""
'3' : '4' : '5' : "", ""
'2' : '3' : '4' : '5' : "", ""
'1' : '2' : '3' : '4' : '5' : "", ""
-- 최종 결과는
[("12345","")]
-- runParser는 튜플의 두 번째가 []이면 "12345"를 리턴하니
"12345"늘 그렇지만 막막한 정의를 따라 가다보면 숨도 차고, 살짝 한 숨도 나옵니다. 과연 이렇게 흘러갈 걸 다 알고, <$>, <*>, <|> … 들을 정의 했을까요? 따라가기가 쉽지 않은데, 몇 가지 핵심은 다음과 같습니다.
<*> 해석을 Maybe 인스턴스처럼 단순하게 Parser 안에 걸 꺼내는 것으로 하면 안됩니다. Parser의 Applicative 인스턴스에 있는 <*>를 먼저 잘 봐 두어야 합니다.Parser [digit : digit :....] 이렇게 Parser가 숫자 파서들로 이루어진 리스트인데, 여기에 어떻게 문자열 "12345"를 넣어주지?” 였습니다. 이 질문의 답은(:) 함수 때문에 오해해서 그렇습니다. Parser를 <*>로 묶으면 결과는 Parser입니다. Parser 타입이니 문자열을 받을 수 있습니다. 그럼 (:)는 언제 작동할까요? 파서를 반복하면서 얻은 결과들을 합쳐서 하나의 결과로 만들 때 씁니다. 파서를 리스트로 묶는게 아니라, 파서의 파싱 결과를 리스트로 묶는 겁니다. Parser에서 뿐만 아니라 어디에서든 some, many가 쓰이면 무언가를 반복하기 때문에 항상 결과를 리스트로 묶어야 합니다. 위에 고퍼 코드 중 seq 정의를 보면 파싱 결과를 튜플로 묶고 있는데,p ‘seq‘ q = \inp -> [((v,w),inp’’) | (v,inp’) <- p inp, (w,inp’’) <- q inp’]
^^^^^이 것과 비슷하게 <*>는 묶을 때 쓸 함수를 Parser 타입에서 빼내와 넣을 수 있도록 f로 자리를 만들어 두었습니다. some에서 이 자리에 (:)을 넣어 결과를 묶고 있습니다.
(Parser cs1) <*> (Parser cs2) = Parser (\s -> [(f a, s2) | (f, s1) <- cs1 s, (a, s2) <- cs2 s1])한 번 더 Parser 타입의 인스턴스들을 정리하면, Parser를 묶는(접착, 연결, …) 브로커 함수들은 대부분 첫째 파서의 결과를 두 번째 파서에 넣으면서 결과값들을 어떻게 정리하는지가 조금씩 다를 뿐입니다. 파서들을 묶었으니, 뒷 파서들은 항상 앞 파서들의 결과를 받아야 합니다.
이제 some의 동작을 알았으니, 나머진 믿고 써야지요. 매 번 이렇게 함수들을 풀어서 이해하며 쓸 수는 없는 노릇입니다. 희미하게나마 함수들의 동작이 눈에 들어오면 믿고 넘어가야 합니다.
char 파서 안에서 한 글자를 떼어내는 item 파서와 unit 파서를 만들어 내는 함수와 바인드 했습니다. 파서와 파서끼리 바인딩하지 않는 이유는, 파서의 결과를 그대로 가지고 다음 파서로 가는 게 아니라서 그렇고, 파싱 결과를 람다 변수에 저장하기 위해서이기도 합니다. 참고 - 상태 개념 포스트 파서의 결과에 따라 다음 파서를 결정할 수도 있고, 아예 파싱 포기할수도 있고, 여러가지 상황에 따른 분기가 일어납니다. 그리고 또 한가지, Maybe모나드와 마찬가지로, 파서가 fail하면 더 이상 다음 함수를 아예 부르지 않고, 체인을 끝내도록 되어 있습니다.
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s파서들이 바인딩 되어 있을 때, 어느 한 파서라도 []를 리턴하면 그냥 결과는 []이 됩니다. 왜 그런지 정의에 넣어 보면, concatMap으로 함수를 []에 적용하면 더 이상 다음 파서 연결 없이 체인은 끝납니다. 정말 모나드로 구현하기 딱 좋은 문제 같은데, 처음부터 이렇게 찰떡인 걸 알고 설계하기 시작했을까요?
파서로 다른 파서를 만드는 모양인데, 이런게 대수학algebra 아닐까요? 아직 파서 대수학이라 표기한 곳은 못 보긴 했는데, 문제 풀이를 이렇게 대수학 느낌으로 가는게 함수형 스타일입니다. 파서 구현이 모나드를 이용해서 정말 깔끔하고 짧게 구현됩니다. 그래서 그런지 하스켈로 만든 애플리케이션 중 파서를 충분히 활용하는 Pandoc은 꽤 알려져 있습니다.
Happy는 c언어 파서를 뽑아내는 yacc처럼 하스켈 파서를 뽑아내는 파서 생성기입니다. 위에 봤던 콤비네이터들을 조합해서 만든 파서보다 빠르다고 합니다. Alex는 lex처럼 어휘lexeme 분석기를 뽑아내는 생성기입니다. GHC도 Happy와 Alex로 파서를 만들어서 쓸 정도로 충분히 파워풀하다고 합니다. 잊고 살았던 컴파일러 책을 다시 뒤적이다 그냥 덮었습니다. 지금은 XML, JSON, YML등의 범용 마크업 언어들이 자리잡아, 실전에서 규모 있는 파서를 만들 일이 거의 없어져서 조금 여유를 두고 보기로 했습니다.
참고
Monadic Parser Combinator - Graham Hutton, Erik Meijer
Functional Perl - Graham Hutton, Erik Meijer
한주영님의 자바스크립트로 구현한 모나드 파서↩︎
상호 재귀Mutual recursion (상호 교차 재귀라고 썼었는데, 상호 재귀란 용어로 수정합니다. 상호 재귀가 일반적인 용어라 합니다.) 아래 코드는 “Programming in Haskell - Graham Hutton”에서 발췌했습니다.
even :: Int -> Bool
even 0 = True
even n = odd (n - 1)
odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)재귀 하나만 나와도 머리가 복잡한데, 두 개가 교차로 부르고 있습니다. 어떻게 해석할까요?
하스켈은 Lazy합니다. 필요할 때 해석하고, 아직 필요하지 않을 때는 이름만 유지합니다.
even을 부르면 odd를 부를거야.
odd를 부르면 even을 부를거야.
만일 프로그램을 머릿속에서 시뮬레이션 하는데, 이렇게 서로를 불러대서 껄끄럽다면, 아칙 충분히 Lazy하지 않아서입니다.
even 100 = odd 99아직 reduce 할게 남아 있으면 또 진행하면 됩니다.
odd 99 = even 98
...어느 함수에서 0에 도달하냐에 따라 결과값은 true | false 로 달라집니다.
이게 읽는 건 충분히 Lazy하게 하다 보면 따라갈 수 있긴 있는데, 이런 구조가 떠오르긴 쉽지 않네요.
어쨌건 핵심은 Lazy입니다. 조금은 무책임하게 접근할 줄도 알아야 이런 아이디어가 떠오를 것 같습니다.↩︎