HaskellとParsecでLisp REPL その1(Atomをパースし表示するREPL)
ここ一週間ほどHaskellを試しがてら、以下のチュートリアルをいじっていた:
Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world
まずは全部通しで実装してみて、その後コードをいろいろ書き換えたり。
このチュートリアル、非常に勉強になったしHaskellやParsec習得のために大変おすすめなのだが、ひとつ気になったのはREPLができるのが第6章という遅さ。
第2章の「パーサ作成」の時点でコードを表すデータ構造を相当作り込んでいるし、第3章では例外処理なども作っている。各パートでけっこう多機能なパーサ、評価器などを作っていってからREPLに組み合わせている感がある。
個人的には超簡単なEnd-to-EndのREPLを最初に作って、そこに機能をくっつけていくほうがしっくりくる。
というわけでその方法で作り直す段階を個別に記事にしていく。
Read-Eval-Print-Loop
最低限のLisp REPLとはなんだろうか。
そもそもREPLとはRead-Eval-Print-Loopの略なので
- ユーザから文字列を受けとり、コードを表す内部データ構造に変換 (Read)
- データ構造を評価 (Eval)
- 評価結果をプリント出力 (Print)
- はじめに戻ってユーザ入力を待つ (Loop)
を兼ね備えている必要がある。
とりあえず今回は「Lispの『関数名』『変数名』などを表すAtom
を正しくパースし、そのものとして評価し、プリントし、そしてループする」というところまで実装する。
コード:
Ultra-Minimal Lisp REPL written in Haskell - Atom only · GitHub
LispVal
データ構造
Lispコードを表現するのに代数的データ型LispVal
を定義する:
data LispVal = Atom String
Atom
型は文字列を一つ保持するデータ型。
今回はLispVal
が取り得る型はAtom
のみ。今後、機能を足していくに従ってLispVal
の型が増えていく。
LispVal
を文字列として表示できるようにShow
型クラスのインスタンスとしておく:
instance Show LispVal where show = showVal showVal :: LispVal -> String showVal (Atom name) = name
Atom
型をshow
する場合、保持している文字列が返される。
「文字列→LispVal
」パーサ
まずはトップレベルの関数:
readExpr :: String -> LispVal readExpr input = case (parse parseExpr "lisp" input) of Left err -> Atom $ "No match: " ++ show err Right val -> val
型からわかる通り、文字列からLispVal
へと変換する関数。Parsecのparse
関数と後述するparseExpr
を使っている。
parse
は第三引数の文字列に対して第一引数のパーサを適用し、Either
型を返してくる。成功したらRight
、失敗したらLeft
。
パターンマッチで、失敗したらLeft
に含まれているエラーメッセージをAtom
に入れて返し、成功ケースの場合はRight
に含まれているLispVal
を直接返す。
トップレベルのパーサ:
parseExpr :: Parser LispVal parseExpr = parseAtom
今回は非常に簡単。今後他のデータ型が増えていくに従いparseExpr
も他のパーサを組み合わせる形になっていく。
ポイントとしては、Parsecの提供するParser
モナドのなかで処理が進んでいくこと。ParsecがMonadic Parserだと言われる所以である。
parseAtom
の定義:
symbol :: Parser Char symbol = oneOf "!#$%&|*+-/:<=>?@^_~" parseAtom :: Parser LispVal parseAtom = do { first <- (letter <|> symbol); rest <- many (letter <|> digit <|> symbol); return $ Atom (first:rest); }
LispのAtom
の特徴は「アルファベット文字か指定の特殊記号で始まり、それら文字か数字が0個以上続く」というもの。
それをほぼそのまま書き表している。Parser
モナドのなかで処理しているのでdo
記法。最後にParser LispVal
型のものを返している。
評価器
評価法は「LispVal -> LispVal」の変換則を再帰的に加えていくというもの。適用できる変換則がないLispVal
の値はそのLispVal
そのもの。
eval :: LispVal -> LispVal eval lispVal = lispVal
今回はLispVal
がAtom
だけで、変換則はない。非常に単純。
REPL各部分とmain関数
まずは標準入力から文字列を受けとる関数:
readPrompt :: String -> IO String readPrompt prompt = putStr prompt >> hFlush stdout >> getLine
上で定義した関数を組み合わせて文字列をLisp的に評価し結果をプリントする関数:
readEvalPrint :: String -> IO() readEvalPrint = putStrLn . show . eval . readExpr
readPrompt
とreadExpr
が分離されているのが「REPL」という名前からすると微妙・・・ そもそもパーサの部分はReadなのかEvalなのか?
特定の入力をうけとるまでループし続ける関数:
loopUntil :: (a -> Bool) -> IO a -> (a -> IO ()) -> IO () loopUntil pred prompt action = do { x <- prompt; if pred x then return () else (action x >> loopUntil pred prompt action) }
もし停止条件が入らない場合は:
loop prompt action = prompt >>= action >> loop prompt action
というような書き方になるだろうか。停止条件のための条件分岐が必要なので少し長めのコードになっている。
do {}
記法にマルチラインの式が入る場合の書き方がイマイチ自信がない・・・
これらの関数を組み合わせたmain
:
main :: IO () main = loopUntil (== "quit") (readPrompt ">> ") readEvalPrint
"quit"が入力されるまでループし続けて、入力された文字列を評価してプリントしていく。
使用例
ghc -package parsec -o lisp-v1 --make lisp-v1.hs
などでコンパイルできる。
./lisp-v1
を実行してみると:
~$ ./lisp-v1 >> a a >> a1 a1 >> +a1 +a1 >> 1 No match: "lisp" (line 1, column 1): unexpected "1" expecting letter >> (+ a b) No match: "lisp" (line 1, column 1): unexpected "(" expecting letter >> quit ~$
このようなREPLが走る。まだ数字やリストは受け入れられない。
次回はリストを受けとりパースできるようにする。