elm/parser의 keep와 skip을 사용하여 Haskell에서 더 읽기 쉬운 파서 작성

Source: Dev.to

배경

EOPL3 제 6장에 나오는 CPS 변환기는 제 3장의 LETREC 언어를 재사용하면서 다중 인자 프로시저와 다중 선언 letrec 표현식을 추가합니다. 저는 연습문제 3.33을 풀면서 이미 해당 언어의 파서를 작성했기 때문에, CPS 변환기 구현을 LETREC‑3.33을 기반으로 하기로 했습니다.

본격적인 작업에 들어가기 전에 파서를 리팩터링했습니다. 렉서(Lexer.hs)를 분리해 두면서 파서가 크게 단순화되었지만, 여전히 동작은 하지만 다소 어색하게 느껴지는 표현식 파서들이 남아 있었습니다.

예를 들어:

ifExpr :: Parser Expr
ifExpr = If  (rIf *> expr)  (rThen *> expr)  (rElse *> expr)

괄호의 배치와 터미널을 오른쪽 표현식과 묶는 방식이 마음에 들지 않았습니다. 이는 제가 생각하는 왼쪽‑에서‑오른쪽 파싱 모델과 맞지 않았습니다. 그래서 elm/parser의 keep과 skip 개념을 사용하면 가독성이 향상될지 궁금해졌습니다.

elm/parser의 keep과 skip

• keep 은 연산자 (|=) 로 구현됩니다:

(|=) : Parser (a -> b) -> Parser a -> Parser b

두 번째 파서가 만든 값을 유지합니다.

• skip 은 연산자 (|.) 로 구현됩니다:

(|.) : Parser keep -> Parser ignore -> Parser keep

두 번째 파서가 만든 값을 버립니다.

전형적인 파이프라인은 succeed 와 함께 사용됩니다:

ifExpr : Parser Expr
ifExpr =
  P.succeed If
    |. rIf
    |. leftParen
    |= P.lazy (\_ -> expr)
    |. rightParen
    |= block
    |= optional
        ( P.succeed identity
            |. rElse
            |= block
        )

(예시는 Monkey/Parser.elm 에서 가져왔습니다.)

나는 이 스타일이 읽고 쓰기 더 쉽다고 생각합니다: keep 할 것과 skip 할 것을 직접 결정하고, 괄호에 신경 쓸 필요가 없습니다.

Applicative 연산자와의 매핑

Haskell에서는:

• pure :: a -> f a 가 succeed 에 해당합니다.
• (<*>) :: f (a -> b) -> f a -> f b 가 (|=) 에 해당합니다.
• (*>) :: f a -> f b -> f a 가 (|.) 에 해당합니다.

따라서 원래 파서는

If  (rIf *> expr)  (rThen *> expr)  (rElse *> expr)

를 다음과 같이 다시 쓸 수 있습니다:

pure If <*> expr <*> expr <*> expr

(<*>) 가 왼쪽 결합이며 같은 우선순위를 가지므로, 이는 다음과 같이 파싱됩니다:

((((((pure If) <*> expr) <*> expr) <*> expr)

왼쪽에서 오른쪽으로 읽으면:

1. If 를 applicative 로 올립니다.
2. "if" 를 파싱하고 그 값을 skip 합니다.
3. expr 를 파싱하고 그 값을 keep 합니다.
4. "then" 을 파싱하고 그 값을 skip 합니다.
5. expr 를 파싱하고 그 값을 keep 합니다.
6. "else" 를 파싱하고 그 값을 skip 합니다.
7. expr 를 파싱하고 그 값을 keep 합니다.

(*>) 로 간단히 표현하기

If  expr  expr  expr

keep 과 skip 을 생각하면서 파서를 작성하면 더 읽기 쉽고 작성하기 편해집니다. 이제 작업 흐름은 다음과 같습니다:

1. 파싱하려는 비단말(non‑terminal)을 식별합니다.
2. 어떤 조각을 keep 할지(의미값)와 어떤 조각을 skip 할지(구문 토큰) 결정합니다.

문법

Program ::= Expr
Expr    ::= Const | Var | Diff | Zero | If | Let | Proc | Call | Letrec
Const   ::= Number
Var     ::= Id
Diff    ::= '-' '(' Expr ',' Expr ')'
Zero    ::= 'zero?' '(' Expr ')'
If      ::= 'if' Expr 'then' Expr 'else' Expr
Let     ::= 'let' Id '=' Expr 'in' Expr
Proc    ::= 'proc' '(' Id ')' Expr
Call    ::= '(' Expr Expr* ')'
Letrec  ::= 'letrec' (Id '(' (Id (',' Id)*)? ')' '=' Expr)* 'in' Expr
Number  ::= [0-9]+
Id      ::= [a-z]+

Parser Implementation (Haskell)

program :: Parser Program
program = Program
  expr
  diffExpr
  zeroExpr
  ifExpr
  letrecExpr
  letExpr
  procExpr
  callExpr
  varExpr

constExpr :: Parser Expr
constExpr = Const number

diffExpr :: Parser Expr
diffExpr = hyphen *> parens (Diff expr expr)

zeroExpr :: Parser Expr
zeroExpr = Zero (parens expr)

ifExpr :: Parser Expr
ifExpr = If expr expr expr

letrecExpr :: Parser Expr
letrecExpr = Letrec (many recProc) expr
  where
    recProc = (,,) identifier (parens (commaSep identifier)) expr

letExpr :: Parser Expr
letExpr = Let identifier expr expr

procExpr :: Parser Expr
procExpr = Proc (parens identifier) expr

callExpr :: Parser Expr
callExpr = parens (Call expr (many expr))

varExpr :: Parser Expr
varExpr = Var identifier

전체 소스 코드는 Letrec/Parser.hs를 참고하세요.

---

나는 Haskell로 Monkey를 구현하던 중 약 4년 전 이 개선점을 발견했지만, 잊어버렸다. 이에 대해 글을 쓰면 앞으로 사용할 때 기억하는 데 도움이 될 것이다.