HaskellでSchemeを書く#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はいいとして、問題はそれ以外の３つだ。

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

こんな感じになる。

あとはこれらのパーサを組み合わせてひとまずは完了！！