Re: Build Your Own Haskell Compiler #1.2

明明只是入門,卻讓苦惱了半年,程度真差。

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 成為了 Functor 還有 Applicative ,於是可以讓一個函式作用在被 Desugar 包起來的 Term 上面(fmap :: (a -> b) -> f a -> f b)。也有了最小最小的 context (pure :: a -> f a),跟將收在 Desugar 中的函式作用在被包起來的其他東西的辦法((<*>) :: f (a -> b) -> f a -> f b)。

再來我好奇的是,他們符合各自該符合的 laws 嗎?LYaH 教我 Functor 和 Applicative 得符合某些規定,而那些規定是 compiler 沒辦法幫忙驗證的。

Functor Laws

fmap id = id
famp (p . q) = fmap p . fmap q

Functor Laws 有兩個,一是 fmap idid 作用起來是一樣的。 Desugarfmap 對裡面的 Term 和藏起來的 Info 沒有做多餘的事情,很明顯滿足這點。另外一條是 fmap (p . q)fmap p . fmap q 作用起來是一樣的,如果從「打開...做事情...關起來」的角度看,那前者是打開來做兩件事然後關起來,後者是打開做一件事,關起來,然後再打開做一件事情,再關起來。也很明顯滿足了。

注意到 fmap 的數量,在第一條 law 裡,從 1 個變成 0 個,在第二條 law 裡,從 1 個變成 2 個,我還不知道該怎麼理解這件事、或是這件事有沒有什麼意義。

Applicative Functor Laws

pure id <*> v = v
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

第一條 pure id <*> v = v 可以說是 fmap id = id 的進階版(或者寫成 fmap id a = a 比較一致?),只是前者的 id 先放在一個最小的 context 中了。

第二條 pure f <*> pure x = pure (f x) ,也算明顯。對 Desugar 來說,最小 context 裡的 Info 都是 0,相加和本來一樣沒有變化,也符合這條 law 。

第三條 u <*> pure y = pure ($ y) <*> u ,我想重點也不是在 u 裡面的函式怎麼作用在 y 上,而是在 pure 從右邊換到左邊的過程中,是不是不造成多餘的改變?在 Desugar 中, pure 在右邊會變成 info + 0 ,和 pure 在左邊的 0 + info 是一樣的。

第四條我一開始是看不明白的,現在看來,對 Desugar 來說,是表示 0 + u的info + v的info + w的infou的info + (v的info + w的info) 不該有差別。


再來想加上被 [] 包起來的 Term ,然後需要讓 Desugar 也是個 Monad ,接著配上個和 do notation 合作起來更融洽的 increase ,就可以把這一切用在 haskell-src-exts 給我們的 AST 上了。

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

Re: Build Your Own Haskell Compiler #1.0

太久沒寫,先回憶一下進度:

  • 實作 desugar 的骨幹, 走訪整個 syntax tree

    (可以定義一個 class, 然後把所有的 syntax node type 加進 instance;

    或是為每一個 syntax node type 定義一個不一樣的函數名的作法也可以;

    也可以兩種都有...)

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

    (使用 mtl 的 Control.Monad.State 也可以)

一直聽不懂 desugar 的骨幹是什麼,只記得要把資料存在 monad 的 context 中,但對於何時修改 context 中的資料,還有該 monad 的 type 該長什麼樣子,一點概念都沒有。

這次乖乖讀 LYaH ,才知道 value constructor 和 type constructor 的差別、才知道他們本來長什麼樣子。例如平常寫 data Maybe a = Nothing | Just a ,其中 Maybe 是 type constructor ,它的 type 是 * -> * ,而 NothingJust 是 value constructor ,,它們的 type 是 Maybe aa -> Maybe a

它們都是 function !它們都是 function ! 它們都是 function !

寫成 GADT 更清楚(謝謝 petercommand 介紹 KindSignatures ):

data Maybe :: * -> * where
  Nothing :: Maybe a
  Just a :: a -> Just a

了解這件事,之後才懂得靠 (<$>)(<*>) 在拜訪 AST 時,記錄下資訊。


回到坑裡,坑主所謂:

可以定義一個 class, 然後把所有的 syntax node type 加進 instance

指的是現在 DesugarClass.hs 的作法,定義了:

class Monad m => Desugarable m a where
  desugar :: a -> m a

那傳說中五百多行的 Desugar.hs 在做的事情,就是為 Annotated.Syntax 下每個 data 實作 desugar

而:

或是為每一個 syntax node type 定義一個不一樣的函數名的作法也可以

指的應該是較早的作法,也就是 transpiler 剛開始時,靠 Template Haskell 生出來的那些 deIfName :: Name -> NamedeIfOp :: Op -> Op