程式語言學習心得 4

接著書上教大家做 parser ，把 parser 分成兩個部分： lexical analysis clex :: String -> [Token]和 syntax analysis syntax :: [Token] -> CoreProgram 。

clex 那部分就是切 token ，保留行號並移除註解（ Core 的註解竟然是 || 開頭，是要跟 Haskell 的 -- 正交嗎？）。

因為沒受過教育（沒念到大三，活該），本來很怕 parser 超難，沒想到竟然是從 parser combinator 講起，而且沒有 monoid 也沒有 monad （但是還是可以看到他們的影子）！查了一下， Haskell 到了 1996 年才把 monad 用在 I/O 上，而這個問題 Who invented Haskell's type classes? 中提到 type classes 出自 How to make ad-hoc polymorphism less ad-hoc ，是 1988 年的事。

至於 Haskell 是不是從設計之初就有 type classes ，也許讀完 Being Lazy with Class 後才會知道 XD

按之前的習題，現在 token 長這樣：

type LineNum = Int
type Token = (LineNum, String)

而 parser 要做的事情有：

把一串 token 轉成某種結構
結果可能不只一種，也有可能沒結果（失敗）
得留下剩下的 token ，好交給下一棒
小 parser 的結果可以組合成大的

於是 parser 長這樣：

type Parser a = [Token] -> [(a, [Token])]

想起 Learn you a Haskell 把 list 稱為 non-deterministic values ，就是這樣用吧。

最基本的 parser 是 pLit 和 pVar ：

pLit :: String -> Parser String
pVar :: Parser String

pLit 讀到跟它的 String 相同的 token 時，會成功，否則得到 [] 。 pVar 現在則是看到 token 就成功。

為了把不同可能性串在一起，有了 pAlt ：

pAlt :: Parser a -> Parser a -> Parser a
pAlt p1 p2 toks = (p1 toks) ++ (p2 toks)

那個 (++) 看起來很眼熟，如果換成 (<>) 就聞到了 monoid 的味道...。

這邊還有一個陷阱，是由 type 關鍵字造成的。明明 pAlt 只有兩個 Parser a 參數，實作時卻吃 p1, p2, toks 三個東西...。原來是因為 Parser a 實際上是 [Token] -> [(a, [Token])] ，所以 pAlt p1 p2 toks 其實可以看成 (pAlt p1 p2) toks 。

記得她在「實例介紹 Monad 應用設計與實作」演講中也抱怨過初學時踩過這個雷。

另外這次讀 IFL 才知道 Haskell 可以有很多怪寫法，想是把 pattern matching 跟 guard 混著用：

clex _ [] = []
clex lineNum (c:cs)
  | c == '\n' = clex (lineNum + 1) cs

還有在 Miranda 裡，

clex (c:cs) = c == '\n' | clex cs

guard 看起來像 JS 的 || XD

為了把小 parser 組合在一起，有了 pThen ：

pThen :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
pThen combine p1 p2 toks
  = [ (combine v1 v2, toks2) | (v1, toks1) <- p1 toks
                             , (v2, toks2) <- p2 toks
    ]

要是 p1 toks 或是 p2 toks 沒結果，那整個就都沒結果，這點讓我想到 (>>=) 。而且 Miranda 沒有 monad 但是卻出現上述這種 list comprehension ，可見它還不是 do notation 的 syntactic sugar 。

還可以組合出找 0~n 個東西的 parser ：

pEmpty :: a -> Parser a
pEmpty a toks = [(a, toks)]

pZeroOrMore :: Parser a -> Parser [a]
pZeroOrMore p = (pOneOrMore p) `pAlt` (pEmpty [])

pOneOrMore :: Parser a -> Parser [a]
pOneOrMore p = pThen (:) (pZeroOrMore p)

pEmpty 看起來就一副 mempty 或 pure 的樣子， pOneOrMore 中用到的 (:) 則讓我想起 mappend ... = =|||

有趣的是，第一次寫，誤把 pOneOrMore 寫成：

pOneOrMore p = pThen (:) (pOneOrMore p)

成了 pInfinite ，對上有限長度的 [Token] ，自然失敗，得到 [] 。

還有長得像 fmap, <*> ，根本就是 <**> 的 mApply :: Parser a -> (a -> b) -> Parser b ，等這些工具都準備好，才真的開始 parse Core language 。

今天先這樣。

caasih.net