Arantium Maestum

プログラミング、囲碁、読書の話題

HaskellとParsecでLisp REPL　その１（Atomをパースし表示するREPL）

Haskell

ここ一週間ほどHaskellを試しがてら、以下のチュートリアルをいじっていた：

Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world

まずは全部通しで実装してみて、その後コードをいろいろ書き換えたり。

このチュートリアル、非常に勉強になったしHaskellやParsec習得のために大変おすすめなのだが、ひとつ気になったのはREPLができるのが第６章という遅さ。

第２章の「パーサ作成」の時点でコードを表すデータ構造を相当作り込んでいるし、第３章では例外処理なども作っている。各パートでけっこう多機能なパーサ、評価器などを作っていってからREPLに組み合わせている感がある。

個人的には超簡単なEnd-to-EndのREPLを最初に作って、そこに機能をくっつけていくほうがしっくりくる。

というわけでその方法で作り直す段階を個別に記事にしていく。

Read-Eval-Print-Loop

最低限のLisp REPLとはなんだろうか。

そもそもREPLとはRead-Eval-Print-Loopの略なので

  1. ユーザから文字列を受けとり、コードを表す内部データ構造に変換 (Read)
  2. データ構造を評価 (Eval)
  3. 評価結果をプリント出力 (Print)
  4. はじめに戻ってユーザ入力を待つ (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が走る。まだ数字やリストは受け入れられない。

次回はリストを受けとりパースできるようにする。