Re: Build Your Own Haskell Compiler #1.3

haskell-src-exts 的 AST 複雜很多,會遇到放在 Maybe[] 裡面的 AST 。這時要是只用 famp ,就會遇上把 [Term a] 變成 [Desugar (Term a)] 這種窘境。真正想得到的是 Desugar [Term a] ,接著才可以繼續 (<*>) 下去。

先把本來的 Term 改成這樣:

data Term a = Var a
            | Lam [a] (Term a)
            | App (Term a) [Term a]
  deriving (Show)

表示現在 Lam 可以吃多個變數。(我知道這樣不對,畢竟有 currying 就好了,但為了練習就... XD)

desugar 函數就變成:

instance Desugarable Desugar (Term a) where
  desugar (Var a) = Var <$> pure a
  desugar (Lam aList term) = Lam <$> traverse pure aList <*> desugar term
  desugar (App term termList) = App <$> desugar term <*> traverse desugar termList

increase

在這個練習中,我給自己的目標是算出 term 的數量,於是得增加 Lam <$> traverse pure aList <*> desugar term 生出來的 Desugar (Term a) 中的 info

為了可以這樣寫:

desugar (Lam aList term) = do
  increase 1
  Lam <$> traverse pure aList <*> desugar termm

就得做出這樣的函數:

increase :: Int -> Desugar ()
increase i = D (i, ()) :: Desugar ()

當兩個 Desugar a(>>=) 接在一起時,得把 tuple 的後面那項送給 monad 使用者,再將得出的結果中的 info (第一項)加在一起計數,做出新的 Desugar a

instance Monad Desugar where
  return = pure
  D (info, a) >>= f =
    let
      D (info', a') = f a
    in
      D (info + info', a')

Monad Laws

最後檢查一下這個 monad 有沒有遵守 monad laws :

return a >>= f = f a -- left identity
m >>= return = m -- right identity
(m >>= f) >>= g = m >>= (\x -> f x >>= g) -- associativity

在 left identity law 中, return a 得到的 info0 ,不影響 f a 的結果。

在 right identity law 中, m 帶的 info 會和 return 帶來的 0 加在一起,一樣不影響 m

在 associativity law 中,先完成 m >>= f 會把 mf 帶來的 info 先加在一起,再加上 g 帶來的 info ;而等號右邊,會加把 fg 帶來的 info 相加,再加上 m 的, + 自己就有結合律,故此 monad 也有。


拖了三個月。這段時間斷斷續續讀著 Haskell Programming from First Principle ,大概讀了四分之一。 haskell-src-exts 在這之中升到了 0.18 版,現在只有 Annotated AST ,還補上了一些 type 。十月初試著升級看看,沒什麼困難,就是打字罷了。剛發現已經到了 0.19 版,不知道又改了些什麼?

前途茫茫,越來越在意自己沒有扎實的電腦科學基礎。之前被推薦過 coursera 上的 Programming Languages, Part A ,也許是個起點。

Comments

comments powered by Disqus