48시간 안에 나만의 스킴 만들기/파싱

프로젝트 뼈대 생성과 Parsec 설치하기

이 절에서는 Parsec 라이브러리를 사용한다. Parsec 라이브러리를 설치하려면 cabal 명령어가 필요하다.

리눅스에서는 GHCup을 이용해서 cabal을 설치할 수 있다.

다음과 같이 프로젝트를 만들자.

$ cabal update
$ mkdir myProject
$ cd myProject
$ cabal init --simple --minimal --exe

이제 myProject.cabal을 수정하자. 다음과 같이 build-depends란에 base 외에 parsec을 추가한다.

build-depends:
  base,
  parsec

cabal run을 입력해서 프로젝트를 실행하자.

Building executable 'myProject' for myProject-0.1.0.0..
[1 of 1] Compiling Main             ( app/Main.hs )
Linking myProject-0.1.0.0/x/myProject/build/myProject/myProject ...
Hello, Haskell!

마지막 줄은 프로그램이 출력한 것이다.

간단한 파서 만들기

엄청 간단한 파서를 하나 만들어 보자.

app/Main.hs 파일(cabal init이 자동으로 만든 파일이다.)에 아래와 같은 코드를 추가해보자.

import Text.ParserCombinators.Parsec hiding (spaces)
import System.Environment

위와 같이 적으면 spaces 함수만 빼고 Parsec 라이브러리를 사용할 수 있다. spaces라는 함수 이름은 나중에 따로 만들 거라 이름이 겹쳐서 뺐다.

다음과 같이 파서를 하나 정의한다. 이 파서는 스킴 식별자 중 하나인 심볼을 인식한다.

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

Parser Char도 모나드이다. 여기서 숨겨진 “추가 정보”는 입력 스트림에서 위치 정보, 백트래킹 기록 등에 관한 모든 정보이다. Parsec이 이 모든 것을 처리해준다. Parsec 라이브러리에서 함수 oneOf만 사용하면 된다. oneOf 함수는 인자로 넣은 문자열 중에 한 글자를 식별한다. Parsec에 letter와 digit 같은 내장 파서가 있다. 기본 파서를 조합해서 더 정교한 파서를 만들 수 있다.

파서를 호출하고 에러를 처리하는 함수를 정의해보자.

readExpr :: String -> String
readExpr input =
  case parse symbol "lisp" input of
    Left err  -> "No match: " ++ show err
    Right val -> "Found value"

타입 서명을 보면 readExpr은 String을 넣으면 String이 나오는 함수(->)이다. 매개변수 이름을 input으로 짓고 위에서 정의한 symbol 파서와 함께 Parsec 함수 parse에 넘긴다. parse의 두 번째 매개변수는 입력에 대한 이름인데 에러 메세지에서 쓰인다.

parse는 파싱된 값이나 에러를 리턴한다. 따라서 parse를 쓰다 에러가 나도 처리가 가능하다. 일반적인 하스켈 관례에 따라 Parsec은 Either 데이터 타입을 리턴한다. 이때 Left 생성자는 에러를 나타내고 Right 생성자는 정상 값을 나타낸다.

case...of 구문을 사용해서 parse의 여러 결과를 매칭한다. 결과가 Left일 때 에러를 변수 err에 연결하고 문자열 "No match"와 문자열로 변환한 에러를 리턴한다. 결과가 Right 값이면 결과를 변수 val에 연결하고 문자열 "Found value"를 리턴한다.

case...of 구문은 패턴 매칭의 예시이다. 패턴 매칭은 나중에 더 자세히 다룬다.

마지막으로 main 함수가 readExpr을 호출하도록 변경하고 결과를 출력하자.

main :: IO ()
main = do
  (expr:_) <- getArgs
  putStrLn (readExpr expr)

위 코드를 컴파일하고 실행하려면 다음과 같이 명령줄에서 프로젝트 이름을 적고 매개변수를 넣어야 한다.

$ cabal run myProject $
Found value
$ cabal run myProject a
No match: "lisp" (line 1, column 1):
unexpected "a"

공백

이제 점차 더 복잡한 표현식을 인식할 수 있도록 파서를 단계적으로 개선해보자. 현재 파서는 심볼 앞에 공백이 있으면 에러가 난다.

$ cabal run myProject "   %"
No match: "lisp" (line 1, column 1):
unexpected " "

코드를 고쳐서 공백을 무시해보자.

여러 공백 문자를 인식하는 파서를 정의하자. Parsec 라이브러리에 이미 spaces 함수가 있기 때문에 Parsec을 임포트할 때 hiding (spaces) 구문을 썼다. 별로 여기서 필요한 함수는 아니다.(여기서는 lexeme이라는 파서를 써도 되지만 교육 목적을 위해 직접 구현한다.)

spaces :: Parser ()
spaces = skipMany1 space

함수를 함수에 넣을 수 있듯이 액션도 액션에 넣을 수 있다. 여기서는 Parser 액션 space를 Parser 액션 skipMany1에 넣었다. 이렇게 만든 파서는 하나 이상의 공백을 인식할 수 있다.

parse 함수를 고쳐서 새로 만든 파서 spaces를 써보자.

readExpr input =
  case parse (spaces >> symbol) "lisp" input of
    Left err  -> "No match: " ++ show err
    Right val -> "Found value"

2장에서 >>(“바인드”) 연산자를 잠깐 언급했다. do블록 안에서 여러 행을 합칠 때(눈에 보이진 않지만) 바인드 연산자가 쓰인다. 여기서는 spaces 파서와 symbol 파서를 합치려고 명시적으로 바인드 연산자를 사용했다. 그런데 바인드는 Parser와 IO 모나드에서 완전히 다르게 동작한다. Parser 모나드에서 바인드는 다음과 같이 동작한다. “첫 번째 파서로 매칭을 시도하고 나머지 입력은 두 번째 파서로 매칭을 시도한다. 둘 다 실패하면 결과는 실패이다”. 일반적으로 바인드는 서로 다른 모나드에서 완전히 다른 영향을 미친다. 모나드는 계산을 구조화하는 일반적인 방법으로써 설계되었다. 모나드는 다양한 계산을 수용할 수 있을만큼 일반적이어야 한다. 모나드가 정확히 무엇을 하는지 알고 싶다면 모나드 관련 문서를 읽어보자.

코드를 컴파일하고 실행하자. spaces를 skipMany1으로 정의했기 때문에 이제 더 이상 프로그램이 한 글자는 인식을 못한다. 대신 심볼 앞에 먼저 공백 문자를 넣어야 한다. 다음과 같이 이 파서가 어떻게 유용한지 확인해보자.

$ cabal run myProject "   %"
Found value
$ cabal run myProject %
No match: "lisp" (line 1, column 1):
unexpected "%"
expecting space
$ cabal run myProject "   abc"
No match: "lisp" (line 1, column 4):
unexpected "a"
expecting space

리턴 값

아직 파서가 많은 일을 하지는 못한다. 현재 버전의 파서는 문자열을 입력하면 인식할 수 있는지, 없는지 알려줄 뿐이다. 파서는 더 많은 일을 할 수 있어야 한다. 파서가 입력 받은 문자열을 쉽게 탐색할 수 있는 자료 구조로 변환할 수 있으면 좋겠다. 이 절에서는 데이터 타입을 정의하고 파서가 데이터 타입을 리턴하는 방법을 배운다.

리스프 값을 담을 수 있는 데이터 타입을 정의하자.

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

위 코드는 대수적 데이터 타입의 예시이다. 이 타입은 LispVal 타입의 변수가 담을 수 있는 여러 값의 집합을 정의한다. |로 구분된 여러 값은 생성자 태그와 데이터를 담고 있다. 위 코드에서 LispVal은 다음과 같은 값 중 하나가 될 수 있다.

Atom: 아톰이라고 불리는 문자열을 저장한다.
List: 다른 여러 LispVal 타입의 값을 저장하는 리스트이다.(하스켈 리스트는 대괄호로 표기한다.) 올바른 리스트라고 하기도 한다.
DottedList: (a b . c)와 같은 스킴 폼을 나타낸다. 올바르지 않은 리스트라고 하기도 한다.
Number: 하스켈 정수 타입을 담는다.
String: 하스켈 문자열 타입을 담는다.
Bool: 하스켈 불린(boolean) 타입 값을 담는다.

생성자와 타입은 서로 다른 이름공간에 존재한다. 따라서 String이라는 이름을 생성자에도, 타입 이름에도 같이 쓸 수 있다. 타입과 생성자 이름은 항상 대문자로 시작해야 한다.

위에서 만든 타입을 만드는 파싱 함수를 추가해보자. 문자열은 큰따옴표로 시작하고 큰따옴표가 아닌 글자가 몇 글자 나오고 큰따옴표로 끝나는 것이다.

parseString :: Parser LispVal
parseString = do
  char '"'
  x <- many (noneOf "\"")
  char '"'
  return $ String x

>> 연산자를 쓰는 대신 다시 do표기법을 썼다. 왜냐하면 중간에 다른 파싱 동작을 하고 many (noneOf "\"")가 리턴한 값을 받아두었다가 나중에 써야 하기 때문이다. 액션이 값을 리턴하지 않으면 >>를 쓰자. 액션이 값을 리턴하고 그 값을 다음 액션으로 넘겨야 할 때는 >>=를 쓰자. 나머지 경우에는 do표기법을 쓰면 된다.

파싱이 끝나면 many가 리턴한 하스켈 문자열에 String 생성자를 적용해서 하스켈 문자열을 LispVal로 만든다. 대수적 데이터 타입의 모든 생성자는 함수처럼 동작한다. 생성자도 함수처럼 인자로 받은 것을 값으로 바꾼다. 생성자는 패턴 매칭 표현식의 왼쪽에서 패턴으로 쓸 수도 있다. Either 데이터 타입의 두 생성자를 패턴 매칭하는 예제를 #간단한 파서 만들기에서 소개했다.

LispVal 타입의 값을 Parser 모나드로 바꾸려면 내장 함수 return을 쓴다. do블록의 각 행은 모두 타입이 Parser LispVal로 같아야 한다. 그런데 String 생성자의 결과는 그냥 LispVal이다. return은 LispVal을 감싸서 아무 일도 안 하고 값만 돌려주는 Parser 액션에 넣어준다. 전체 parseString 액션의 타입은 결국 Parser LispVal이 된다.

$ 연산자는 중위 함수이다. 아래 두 코드는 같다.

return $ String x
return (String x)

$는 결합 방향이 오른쪽이고 우선순위가 낮아서 괄호를 적지 않을 수 있게 해준다. $는 연산자라서 함수에 할 수 있는 건 똑같이 다 할 수 있다.(연산자를 인자로 넘기거나 부분만 적용할 수 있다.) $는 리스프 함수 apply와 비슷하다.

이제 스킴 변수를 다뤄보자. 아톰은 글자나 심볼로 시작하고 글자, 숫자, 심볼 등을 여러 개 쓸 수 있다.

parseAtom :: Parser LispVal
parseAtom = do 
  first <- letter <|> symbol
  rest <- many (letter <|> digit <|> symbol)
  let atom = first:rest
  return $ case atom of 
    "#t" -> Bool True
    "#f" -> Bool False
    _    -> Atom atom

<|>는 선택 연산자이다. <|>는 첫 번째 파서를 시도해보고 실패하면 두 번째 파서를 시도한다. 둘 중 하나가 성공하면 성공한 파서가 리턴한 값을 리턴한다. 첫 번째 파서가 실패할 때는 파싱할 글자를 소모하지 않는다. 백트래킹 구현하는 방법은 나중에 소개한다.

아톰의 첫 번째 글자와 나머지를 읽고나서 첫 번째 글자와 나머지를 합쳐야 한다. let 구문은 새 변수 atom을 정의한다. 첫 번째 글자와 나머지를 합칠 때 리스트 생성 연산자 :를 사용한다. : 대신 리스트 연결 연산자 ++를 써도 된다.([first] ++ rest) first는 리스트가 아니라 그냥 문자라서 대괄호로 감싸 리스트로 만들어야 ++로 rest와 합칠 수 있다.

case 표현식으로 LispVal 타입 중 어떤 값을 만들고 리턴할지 정한다. 매칭 결과가 리스프 참, 거짓 리터럴인 경우 하스켈 참, 거짓을 리턴한다. 밑줄 _은 가독성을 위해 사용한다. case 블록은 위에서부터 참이 없는 경우 _를 만날 때까지 계속 내려간다.(_가 없고 모든 케이스가 실패할 경우 전체 case 표현식 자체가 실패한다.) _는 와일드카드이다. 모든 케이스가 실패하고 _까지 오면 매칭이 되고 atom을 리턴한다.

마지막으로 숫자 파서만 하나 더 만들자. 모나딕 값을 어떻게 다루는지 보자.

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

위 코드는 오른쪽부터 거꾸로 읽는 게 편하다. 왜냐하면 함수 적용($)과 함수 합성(.) 모두 결합 방향이 오른쪽이기 때문이다. 파섹 콤비네이터 many1은 인자로 넣은 파서가 파싱 할 수 있는 글자를 한 개 이상 파싱한다. 문자열을 파싱해서 LispVal 타입의 숫자 값을 리턴하고 싶은데 타입이 맞질 않는다. 먼저 내장 함수 read를 써서 문자열을 숫자로 바꾸고 Number 생성자에 넣어서 LispVal 타입으로 만든다. 표준 함수 liftM으로도 같은 일을 할 수 있다. liftM을 Number . read에 적용하고 파싱한 문자열에 적용하면 된다.

liftM을 쓰려면 다음과 같이 프로그램 제일 위에 Monad 모듈을 임포트해야 한다.

import Control.Monad

함수 합성, 함수 적용, 함수에 함수를 인자로 넣는 프로그래밍 방식은 하스켈 코드에서 흔하다. 이런 프로그래밍 방식은 복잡한 알고리즘을 한 줄로 표현할 수 있게 해주고 중간 과정을 여러 함수로 나눠서 조합하기 좋게 만든다. 하스켈 코드를 오른쪽부터 왼쪽으로 읽어야 한다거나 타입을 잘 기억해야 한다는 점은 불편할 수 있다. 이 책에서 많은 예제를 접하면서 익숙해지길 바란다.

문자열, 숫자, 아톰을 파싱하는 파서를 만들어 보자.

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseString
        <|> parseNumber

readExpr가 parseExpr을 쓰도록 수정하자.

readExpr :: String -> String
readExpr input =
  case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right _  -> "Found value"

위 코드를 컴파일하고 실행하면 다음과 같이 프로그램이 숫자, 문자열, 심볼은 파싱하지만 다른 것은 파싱하지 못하는 것을 볼 수 있다.

$ cabal run myProject "\"this is a string\""
Found value
$ cabal run myProject 25
Found value
$ cabal run myProject symbol
Found value
$ cabal run myProject (symbol)
bash: syntax error near unexpected token `symbol'
$ cabal run myProject "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\"" or digit

연습 문제

다음 항목을 써서 parseNumber를 다시 써보자. 이때 liftM은 쓰면 안 된다.
1. do표기법
2. 일련의 명시적인 >>= 연산자
R⁵RS는 문자열 안에서 인용 부호를 이스케이프 처리하는 기능이 있다. parseString을 고쳐서 \"를 만나도 문자열이 끝나지 않게 해보자. noneOf "\"" 대신 새로운 파서 액션을 만들어 보자. 이 액션은 인용 부호가 아닌 글자를 파싱하거나 백슬래시 다음에 인용 부호가 오는 문자열을 파싱할 수 있다.
\n, \r, \t, \\ 등 이스케이프 문자를 지원하도록 앞 연습 문제를 수정해보자.
다른 진법을 지원하는 스킴 표준을 따라서 parseNumber를 바꿔보자. readOct와 readHex 함수를 써보자.
LispVal 타입에 Character 생성자를 추가하자. R⁵RS에 나온 문자 리터럴을 파싱하는 파서를 만들자.
LispVal 타입에 Float 생성자를 추가하자. R⁵RS 소수점 문법을 지원하자. 하스켈 함수 readFloat을 써보자.
다양한 스킴 숫자 유형을 모두 지원하기 위해 데이터 타입과 파서를 추가하자. 하스켈에 숫자를 표현하는 다양한 내장 타입이 있다. 하스켈 표준 라이브러리 Prelude를 참고하자. Rational 타입은 분모와 분자료 표현할 수 있고 Complex 타입은 실수부와 허수부로 표현할 수 있다.(실수부와 허수부 각각을 Real 타입으로 표현할 수 있다.)

재귀 파서

인터프리터에 파서 액션 몇 개를 더해보자. 그 유명한 리스프의 괄호 파싱부터 해보자.

parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces

parseList는 parseNumber와 비슷하게 동작한다. 먼저 sepBy parseExpr spaces는 공백으로 나뉜 표현식을 파싱하고 Parser 모나드 안에서 List 생성자에 적용한다. 직접 만든 parseExpr 액션도 sepBy에 넣을 수 있다는 점을 잘 보자.

dotted 리스트 파서는 복잡해보이지만 개념 자체는 복잡하지 않다.

parseDottedList :: Parser LispVal
parseDottedList = do
  head <- endBy parseExpr spaces
  tail <- char '.' >> spaces >> parseExpr
  return $ DottedList head tail

일련의 Parser 액션을 >>로 어떻게 연결하고, 어떻게 <- 오른쪽에 적었는지 잘 보자. 표현식 char '.' >> spaces는 Parser ()을 리턴하고 parseExpr와 연결하면 Parser LispVal이 된다. do블록의 모든 줄은 각각 타입이 Parser LispVal이어야 한다.

스킴 문법 설탕인 작은따옴표 파싱 기능을 추가하자.

parseQuoted :: Parser LispVal
parseQuoted = do
  char '\''
  x <- parseExpr
  return $ List [Atom "quote", x]

위 코드는 작은따옴표 하나를 읽은 다음 표현식을 읽어서 변수 x에 연결하고 스킴 문법으로 표현하면 (quote x)를 리턴한다. Atom 생성자는 함수처럼 동작한다. Atom은 문자열을 감싸서 타입이 LispVal인 값을 준다. LispVal 타입의 값을 리스트에 넣는 것도 가능하다.

새로 만든 파서 parseQuoted를 parseExpr에서 사용할 수 있게 수정하자.

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseString
        <|> parseNumber
        <|> parseQuoted
        <|> do char '('
              x <- try parseList <|> parseDottedList
              char ')'
              return x

위 코드는 Parsec의 마지막 기능인 백트래킹을 사용한 것이다. parseList와 parseDottedList는 점이 나올 때까지 같은 문자열을 파싱해야 한다. 이때 parseList가 파싱을 실패하면 parseDottedList도 같은 문자열을 처음부터 다시 읽어야 한다. try 콤비네이터는 먼저 특정 파서를 실행하고 만약 파싱이 실패하면 이전 상태로 돌아간다. try 콤비네이터는 다른 파서를 방해하지 않고 <|>와 같이 선택하는 파서를 쓸 수 있게 해준다.

코드를 컴파일하고 실행하면 다음과 같이 나온다.

$ cabal run myProject "(a test)"
Found value
$ cabal run myProject "(a (nested) test)"
Found value
$ cabal run myProject "(a (dotted . list) test)"
Found value
$ cabal run myProject "(a '(quoted (dotted . list)) test)"
Found value
$ cabal run myProject "(a '(imbalanced parens)"
No match: "lisp" (line 1, column 24):
unexpected end of input
expecting space or ")"

파서 안에서 parseExpr를 참조함으로써 파서를 임의로 깊게 중첩할 수 있다. 이로 인해 몇 가지 정의만으로 완전한 리스프 파서를 구축할 수 있다. 이것이 바로 재귀의 힘이다.

연습 문제

억음 부호(`) 문법 설탕 기능을 추가하자. 스킴 표준에 따라 억음 부호를 쓰면 쿼시쿼트와 언쿼트를 할 수 있어야 한다.
벡터 기능을 추가하자. 하스켈 표현 방식은 자유롭게 하면 된다. GHC에 Array 데이터 타입이 있는데 쓰기 쉽진 않다. 벡터는 상수 시간 색인과 수정이 되어야 한다. 그런데 순수 함수형 언어에서 파괴적 수정은 어렵다. 이 튜토리얼 뒤에서 set!을 다루는데 set!에서 힌트를 얻을 수 있다.
try 콤비네이터를 쓰지 말고 공통된 부분을 뽑아서 먼저 파싱하도록 바꿔 보자. 일련의 표현식을 파싱하는 파서와 아무 것도 없거나 점 하나와 표현식 하나를 파싱하는 파서를 만들어야 한다. 리턴 값을 모아서 List나 DottedList로 만드는 것은 독자 여러분에게 맡긴다. 기능을 분리해서 헬퍼 함수 같은 걸 만들면 편할 수 있다.