caasih.net

Re: Build Your Own Haskell Compiler #1.1

坑主在五月底時曾建議可以從最簡單的 context 開始 -- 記錄現在 AST 中含的 expression 數量就好:

type Info = Int

然後會有一個叫做 Desugar 的 data :

data Desugar a = D (Info, a)
  deriving (Show)

根據她的建議:

定義自己的 monad 來攜帶未來要加的資料結構, 讓這個骨幹的運行是在這個 monad 裡

我們必須要實作:

instance Monad Desugar where
  return = pure
  D (info, module) >>= f = ...

但是, return 所代表的 minimum context 是什麼?我該在何時改變 info 來反應 expression 數量更新了呢?光看 return(>>=) 一點頭緒也沒有。事後我才知道, desugar 這件事可以分成兩個問題來看。

其一是如何從 AST 中把我們要的資訊找出來,如果不對 AST 做任何改變,那就是單純把 AST 拆開,經過一些計算再組合回去。這件事可以靠 Applicative 的 (<$>)(<*>) 幫我們做到。

其二是當遇上放在其他 context (例如 MaybeList )中的 Desugar 時,要怎麼把已經找出來的資訊組合起來?這件事情靠 Monad 的 (>>=) 做到。


整個 Haskell.Src.Exts 的 AST 太複雜了,不如先從簡單的 AST 開始。哪裡有簡單的 AST 呢?剛好 BYOHC 前面做過 lambda calculus XD

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

現在準備我們的 Desugar

type Info = Int

data Desugar a = D { runDesugar :: (Info, a) }
  deriving (Show)

Term 裡面沒有 MaybeList ,於是做到 Applicative 就可以了:

instance Functor Desugar where
  fmap f (D (info, term)) = D (info, f term)

instance Applicative Desugar where
  pure term = D (0, term)
  D (info, f) <*> D (info', t) = D (info + info', f t)

為了方便直接寫 desugar 而不是 desugarVar, desugarLam, desugarApp ,來做一個自己的 type class :

-- 需要用到 MultiParamTypeClasses 這個 language extension ,我還不是很明白它的意義與重要性
class (Applicative m) => Desugarable m t where
  desugar :: t -> m t

然後就可以實作給各種 Term 用的 desugar

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

看看 Lam a termLam <$> pure a <*> desugar term ,是不是就像拆開來做些什麼,再組合起來? XD

現在算算有幾個 Lam 。加上陽春的 count function :

increase :: Desugar a -> Desugar a
increase (D (info, term)) = D (info + 1, term)

並把 desugar 改成:

instance Desugarable Desugar (Term a) where
  desugar (Var a) = Var <$> pure a
  desugar (Lam a term) = increase (Lam <$> pure a <*> desugar term)
  desugar (App term term') = App <$> desugar term <*> desugar term'

之後會再改進這個 increase ,讓它跟 (>>=) 合作,現在先:

main :: IO ()
main =
  putStrLn . show . runDesugar . desugar $
    App (Lam "x" (Lam "y" (Var "x"))) (Var "z")

就能看到它輸出:

(2,App (Lam "x" (Lam "y" (Var "x"))) (Var "z"))

的確有 2 個 Lam

Isaac Huang 發佈於