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
은 쓰면 안 된다.- do표기법
- 일련의 명시적인
>>=
연산자
- R5RS는 문자열 안에서 인용 부호를 이스케이프 처리하는 기능이 있다.
parseString
을 고쳐서\"
를 만나도 문자열이 끝나지 않게 해보자.noneOf "\""
대신 새로운 파서 액션을 만들어 보자. 이 액션은 인용 부호가 아닌 글자를 파싱하거나 백슬래시 다음에 인용 부호가 오는 문자열을 파싱할 수 있다. \n
,\r
,\t
,\\
등 이스케이프 문자를 지원하도록 앞 연습 문제를 수정해보자.- 다른 진법을 지원하는 스킴 표준을 따라서
parseNumber
를 바꿔보자.readOct
와readHex
함수를 써보자. LispVal
타입에Character
생성자를 추가하자. R5RS에 나온 문자 리터럴을 파싱하는 파서를 만들자.LispVal
타입에Float
생성자를 추가하자. R5RS 소수점 문법을 지원하자. 하스켈 함수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
로 만드는 것은 독자 여러분에게 맡긴다. 기능을 분리해서 헬퍼 함수 같은 걸 만들면 편할 수 있다.