HaskellでSchemeを書く#2
構文解析その2
前回は、基本的な関数の表現などをまとめた。 今回も続けて構文解析について進めていく。 既に10時間は経過している気がするけど、48時間で終わるのか!
何はともあれ、まずは以下の定義から。
data LispVal = Atom String | List [LispVal] | DottedList [LispVal] LispVal | Number Integer | String String | Bool Bool
これは代数的データ型と呼ばれるものらしく、恐らくEither型も代数的データ型なのかな?|
で接続された、例えばAtom
みたいな部分がコンストラクタのタグ名で、その後に続いているのがそのコンストラクタに格納可能であるデータ型、ということだった。
代数的データ型とはなんぞや?ということでwikiで調べてみると、以下のような素晴らしい例が出てきた。
Prelude> data Node = Leaf Integer | Branch Node Node deriving (Show) Prelude> Leaf 1 Leaf 1 Prelude> Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4)) Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4)) Prelude>
なんかBNF記法的な何かだと理解した。いろんな表現の集合。いずれかのコンストラクタで表されているもの。
問題は、それぞれが何を意味しているか。Number
やString
、Bool
はいいとして、問題はそれ以外の3つだ。
Schemeでの表現は、全てS式と呼ばれるもので、そのS式を構成しているのが、リストと、リスト以外のモノを指すアトム(参考:Schemeのお勉強 (S式と評価,式と文,リテラル))。List
は、Haskellでのデータ型表現が[LispVal]
とLispValのリストになっているので、
そういうことなんだろう。
Schemeでは、リストとはcons
(construct語源?)セルによって構成されるらしい。
(wiki:Cons)
(1 . 2)
が最小単位のコンスセルで、ドット対の S式、ということだ・・・また知らない単語が出てきてしまったので調べると、まあ単純にこの形式のデータのことをそう呼ぶらしい。コンスセルでドット対じゃあないものが存在するということか?と思ったけどそういうことでもないらしい。じゃあコンスセルでいいやん。コンスセルの表現方法としてLispではドット対という、と。まあそういうことらしい。
ふと疑問に思ったのが、このLispVal
をリストとして持つと、リストの中の型がコンストラクタによってぐちゃぐちゃになっちゃうんじゃ?と思ったんだけど、リストには'純リスト'と'純でないリスト'というのがあるらしく、純リストは、並べられたデータの型を制限しないリストのことらしい。凄い。
そんなこんなで、次がDottedList [LispVal] LispVal
なんだけども、これってDottedList List LispVal
という書き方じゃダメなんだろうか。ダメだった。type constructor でも classでもないからダメよ、というふうに見える。
Prelude> data LispVal = Atom String | List [LispVal] | DottedList List LispVal <interactive>:118:58: Not in scope: type constructor or class `List' A data constructor of that name is in scope; did you mean -XDataKinds?
この代数的データ型にはそれぞれ呼び方があるらしく、data 型コンストラクタ(type constuctor) = 値コンストラクタ(data constructor) データ型
という並びになっているらしい(参考:Haskellのコンストラクタとデータ型)。値コンストラクタはさだめられたデータ型を返す関数なんだって。
DottedList
は、ドット対で表現されたリストのことかな?だから、List
のほうは、(1 2 3 4)
みたいなやつのことか。
残るはAtom
だけども、こいつは何を指しているんだろう。式そのものを一時的に文字列で受け取るためのものだろうか。
文字列をパース
少し疑問は残ったものの次へ。次は、文字列として表現されるものをパースする。ここも難所だった・・。
parseString :: Parser LispVal parseString = do char '"' x <- many (noneOf "\"") char '"' return $ String x
2行目のdo
は各行を適切に>>
や>>=
で接続しますよーってなことらしい。そんでchar
は、
Prelude Text.ParserCombinators.Parsec> :t char char :: Text.Parsec.Prim.Stream s m Char => Char -> Text.Parsec.Prim.ParsecT s u m Char
こんな風に定義されてて、与えられたChar
型の文字とマッチしたらポインタを一個進めて文字列を次に渡す、とかなのかなぁ。この辺、関数の定義がわからない分具体的になにしてるのかわからん。many
は次のnoneOf
と併せて、"
が出てこない間の文字列にマッチさせる。最終的にreturn
するのだけれど、ここでreturn
が必要な理由は、many
が返してくるデータ型はString
なので、この関数のデータ型であるParse LispVal
としてまとめあげるためにreturn
しているらしい。まだ深淵に触れたくないのでさらっと見てみると、
class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a
あるaをモナドとして返してくれる関数?らしい。LispValはParserモナドじゃないから、全体としてParserモナドのアクションになるようにしましょうね、ということかしら。
Atomのパース
ついに出ました、謎のAtom
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
<|>
が目新しいくらい?letter
は大文字か小文字の英字をパースしてくれるやつで、これは1文字目が英字もしくはsymbol
に指定した記号始まりで、その後に続く文字列が、英字、記号、数字のいずれかであることを判定、つまりはアトムであるかを見ているわけだな?で、真偽値だったらBoolコンストラクタでTrue
or False
として格納してそれ以外はAtomとして格納すると。だいぶ読めるようになってきたぞ?
数字のパーサ
数字のパーサは見た目がとてもシンプル。ただやってることは難しい。
parseNumber :: Parser LispVal parseNumber = liftM (Number . read) $ many1 digit
これは(Number . read)
という、String -> LispVal
というふうに合成された関数を、many1 digit
関数から返される値に適用したいんだけども、many1 digit
はParse String
という、Monad String
な値を持ってしまっているので、そのままでは適用できないと。となると、String -> LispVal
の関数を、Monad String -> Monad LispVal
という関数にしたい・・・・・!ということでそれを担うのがliftM
ということですね・・。実際に、
Prelude Control.Monad> :t (Number . read) (Number . read) :: String -> LispVal Prelude Control.Monad> :t liftM (Number . read) liftM(Number . read) :: Monad m => m String -> m LispVal
こんな感じになる。
あとはこれらのパーサを組み合わせてひとまずは完了!!