JavaScript 모나딕 파서
하스켈 책이나 교육 과정에서 모나드를 다룬 다음에 등장하는 단골 주제가 모나딕 파서다. 파서를 만든다는 것만으로도 흥미로운데, 여기에 모나드를 엮어서 설명하니 재밌을 수 밖에.
모나딕 파서를 간단히 살펴보려면 다음 문서가 좋다. 매우 간결하다.
조금 더 긴 호흡으로 A-Z를 알아보려면 다음 문서가 좋다.
뭐니뭐니해도 직접 만들어보는 것이 재밌다. 이 재미를 위해서 하스켈을 배우기 버겁다면 그냥 개념만 따다가 Java나 JavaScript로 만들어볼 수도 있다.
모나딕 파서에서 핵심이 되는 것은 바로 파서의 타입이다. string -> a 처럼 문자열을 읽어서 결과를 내놓는 것을 생각할 수 있겠지만 이렇게 해서는 복잡한 파서를 만들기 어렵다. 입력 문자열에서 일부분만 처리하고 나머지를 반환할 수 있어야 한다. string -> (a, string)으로 바꾼다면 좀 낫다. 파싱 결과뿐아니라 남은 문자열도 반환한다. 하지만 여러가지 다양한 조합이 가능한 경우를 처리하지 못한다. Non-deterministic을 처리하지 못한다는 얘기. 그래서 최종으로 얻은 파서의 타입은 string -> [(a, string)].
이제 이런 타입의 파서를 JavaScript로 구현해보려고 하는데, Non-deterministic을 위해 배열을 사용할 수도 있지만 이번에는 특이하게 제너레이터를 사용하려고 한다. 제너레이터를 지연 리스트로 볼 수 있기 때문이다. (그리고 재미있으니까)
그럼 가장 간단한 파서 하나를 만들어보자. 아래 item파서는 입력에서 문자 하나를 파싱한다.
function* item(s) {
if (s.length > 0) yield [s[0], s.slice(1)];
}여기서 파서 타입의 JavaScript 버전을 확인할 수 있다. 문자열을 입력으로 하는 제너레이터 함수이며, yield하는 값은 길이가 2인 배열에 파싱 결과와 처리 후 남은 문자열이 된다. string -> [(a, string)] 타입을 나타내기에 적당하다고 생각된다.
아무 문자나 파싱하는 건 재미없으니 우리가 원하는 문자 하나를 읽어들이는 파서를 만들어보자.
function char(c) {
return function*(s) {
for (const [a, rest] of item(s)) {
if (a === c) yield [c, rest];
}
};
}여기서는 우리가 정한 JS 버전의 파서를 어떤식으로 사용하는지를 알 수 있다. 이미 정의한 item 파서를 이용하되 그 결과가 원하는 값인 경우 다시 yield한다.
다른 파서를 사용한 다음 그 결과를 검사하는 건 일반적인 오퍼레이션이라고 볼 수 있으므로 이미 익숙한 filter 고차함수를 파서에 대해 정의할 수 있다.
function filter(pred, p) {
return function*(s) {
for (const [a, rest] of p(s)) {
if (pred(a)) yield [a, rest];
}
};
}위의 char 파서에서 item 부분과 조건 검사 부분을 인자로 추출한 리팩터링에 불과하다. 이제 char는 filter로 구현할 수 있다.
function char(c) {
return filter(a => a === c, item);
}여기서 놀라운 일이 벌어진다. char 파서가 하는 일은 똑같은데, 구현에 제너레이터도 for-of도 사라졌다. item이 배열인지 뭔지 모르겠고 우리가 알고 있는 filter처럼 사용할 뿐이다.
이제 여러 개의 파서를 합칠 수 있는 방법을 제공해보자. 합치는 방법은 순차적 합성과 병렬적 합성을 따져볼 수 있다. 말하자면 시간을 파싱하는 time 파서와 날짜를 파싱하는 date 파서가 있는데, time과 date를 순서대로 모두 매치하는지 찾는 것과, time 혹은 date가 있는지 찾는 것이다. 순차적 합성을seq, 병렬적 합성을 alt라고 이름붙여보자. 그러면 seq(time, date)와 alt(time, date)처럼 새로운 파서를 만들어낼 수 있다.
먼저 seq 연산자는 두 개의 파서를 받는데, 첫번째 파서가 성공하면 남은 부분에 대해 두번째 파서를 적용한다.
function seq(p1, p2) {
return function*(s) {
for (const [a, rest1] of p1(s)) {
for (const [b, rest2] of p2(rest)) {
yield [[a,b], rest2];
}
}
};
}for-of가 중첩되면서 p1파서가 성공하고 남은 부분인rest1이 p2로 전달되는 것을 유의해야 한다.
두번째 합성 방법인 alt는 좀더 쉽다. 각 파서들의 결과를 그대로 합치면 된다.
function alt(p1, p2) {
return function*(s) {
yield* p1(s);
yield* p2(s);
};
}이제 조금 더 어려운 파서로 넘어가본다. 정규 표현식으로 보자면 스타(*)에 해당하는 “여러 개”를 파싱하는 것이다. 예를 들어 공백 문자 하나를 읽는 space(=char(‘ ‘))라는 파서가 있다고 하자. 공백이 0개 이상 여러 개를 파싱하는 파서를 spaces = many(space)처럼 쉽게 만들 수 있으면 좋겠다. 그런데 0개 이상이라면 하나도 없을 수도 있고, 1개 이상일 수도 있다. 일단 하나도 없는 경우는 항상 성공한다. 1개 이상인 경우는… 우선 어려우니까 many1이라고 다른 파서를 만들기로 하고 many를 구현해보자.
function many(p) {
return alt(success([]), many1(p));
}이미 만들어둔 alt를 이용했다. 하나도 없거나 1개 이상이니까 의미가 잘 표현되었다. success는 간단하다. 입력을 처리할 필요없이 항상 정해진 값으로 성공한다.
function success(v) {
return function*(s) {
yield [v, s];
};
}이제 미뤄뒀던 many1을 구현해보자. many1은 1개 이상 나와야 한다. 1개 이상이란 얘기는 1개가 무조건 나오고 그 뒤에 이어서 0개 이상 나오면 된다.
function many1(p) {
return seq(p, many(p));
}오호! alt/seq와 many/many1이 절묘하게 결합되면서 의외로 간단히 해결되었다. … 것처럼 보인다. 하지만 실제로는 상호 재귀 호출 때문에 무한 루프에 빠져버린다.
many(p)
= alt(success, many1(p))
= alt(success, seq(p, many(p))
= ...사실 seq 합성 연산자는 첫 번째 파서가 성공해야 두 번째 파서를 사용한다. 따라서 두 번째 파서를 바로 만들어서 던져줄 필요가 없다. 그런데 인자로 전달하려면 파서를 만들어야 하니 상호 재귀로 인해 끝이 나지 않는 것이다. 인자 전달 부분에 지연 평가를 도입하면 문제가 해결된다. 우선 여기서는 상호 재귀를 끊기위해 many에만 지연 평가를 적용해보자.
function many(p) {
return alt(success([]), defer(() => many1(p)));
}function defer(pf) {
return function*(s) {
yield* pf()(s);
};
}
끝난 것 같은데, 아직 many1에 남은 문제가 있다. seq 연산자는 두 파서의 결과를 단순히 배열에 합쳐서 줄 뿐이다. 그런데 그러면 many1의 두번째 파서인 many의 결과가 배열이므로 many1의 결과는 배열이 중첩되는 문제가 생긴다.
이 문제를 어떻게 해결하면 좋을까? 파서의 처리 결과를 후처리하는 데는 역시나 익숙한 map이 나을 것 같다.
function map(f, p) {
return function*(s) {
for (const [a, rest] of p(s)) {
yield [f(a), rest];
}
};
}이제 many1은 다음처럼 map을 적용해서 seq의 결과를 하나의 펼쳐진 배열로 만들 수 있다.
function many1(p) {
return map(([a, as]) => [a,...as], seq(p, many(p)));
}이쯤되면 무언가 계속 반복되는 패턴이 보일 것이다. filter가 처음 등장할 때 보았던 간결함 대신 계속 파서를 직접 제너레이터로 생성하는 모습들. 이 부분을 어떻게 리팩터링 할 수 있을까? 바로 여기서 “모나딕 파서"라는 이름에 걸맞게 flatMap이 등장한다.
flatMap은 map과 비슷하지만 파서의 결과에 함수를 적용한 것이 다시 파서가 된다.
function flatMap(f, p) {
return function*(s) {
for (const [a, rest] of p(s)) {
yield* f(a)(rest);
}
};
}함수를 결과에 적용한 다음 rest를 다시 전달하는 모양을 잘 보기 바란다.
이 함수의 등장으로 인해 갑자기 이미 만든 함수들이 매우 간단해진다.
function filter(pred, p) {
return flatMap(a => pred(a) ? success(a) : failure, p);
}function map(f, p) {
return flatMap(a => success(f(a)), p);
}
게다가 두 개를 합성하는데 그쳤던 seq도 조금더 확장하여 여러개를 순차적으로 연결할 수 있다. Non-deterministic 에 나왔던 sequence 연산자를 가져오면 된다.
function sequence(ps) {
if (ps.length === 0) return success([]);
return flatMap(a => map(as => [a, ...as], sequence(ps.slice(1))), ps[0]);
}function seq(...ps) {
return sequence(ps);
}
대략 이쯤이면 모나딕 파서의 큰 뼈대가 완성된 것 같다. 여기에 필요한 몇가지 기본 파서(ex. regex, string, number 등)나 추상화 수준이 높은 파서들(sepBy/sepBy1: many/many1와 비슷하면서 구분자가 있는 파서)을 구현하면 어지간한 복잡한 파서도 만들 수 있을 것이다.
모나딕 파서의 기본 내용을 JavaScript로 따라가 보았는데, 모나드 덕분에 코드가 간결해지는 것이 잘 드러났는지 모르겠다.
업데이트
- https://eli.thegreenplace.net/2017/deciphering-haskells-applicative-and-monadic-parsers/ — “Programming in Haskell”이란 책에 나온 파서 예제를 소개한 포스트.
