Your posts match “ BYOHC ” tag:

Re: Build Your Own Haskell Compiler #0.0

2016-04-29 的 Workshop 重新開始,使用 stack 管理開發環境,寫自己的 transpiler 。

stack

「lts 是比較穩定的版本,什麼 nightly build 是他們還在 try 的版本。心臟比較大顆的可以試試看。」

行前先預習一下 stack 基本操作:

stack new my-project
cd my-project
stack setup
stack build
stack exec my-project-exe

stack new my-project 時, stack 會幫忙生出整個專案目錄,包含:

app/
  Main.hs
src/
  Lib.hs
test/
  Spec.hs
LICENSE
Setup.hs
stack.yaml
my-project.cabal

除了 stack.yaml 外,今天要關心的只有 my-project.cabalMain.hs

記得 Workshop 剛開始時, CindyLinz 用的是 cabal 配上秘藏的工具,好在不同的 GHC 版本間切換。後來 AlexLu 推薦了 stack ,就轉換到 stack 上了。我一開始並不熟練,花了一段時間才搞清楚,原來有兩個檔案要注意,一個是 stack 的 stack.yaml ,裡面指定了 GHC 的版本、套件、架構等。我還不清楚那裡面指定的 extra-deps: 與 cabal 檔中的有何不同?只記得用 cabal 時手動裝本地套件很麻煩。今天 silverneko 注意到, stack.yaml 裡的 packages: 應該是用來處理本地套件的。

stack.yaml 中有個重要的設定是 resolver: ,可以手動改,也能在跑 stack new my-project 時,加上參數 --resolver 。例如:

stack new my-project --resolver lts-5.14

lts-5.14 的 lts 表示 long term support ,是穩定的版本。另外還有 nightly-2016-04-28 ,其中的 nightly 表示是 nightly bulid ,每天晚上自動編譯出來的最新版。


接著下 stack setup , stack 會把這個專案用的 GHC 準備好:

stack will use a locally installed GHC
For more information on paths, see 'stack path' and 'stack exec env'
To use this GHC and packages outside of a project, consider using:
stack ghc, stack ghci, stack runghc, or stack exec

訊息中也提到要使用 ghc, ghcirunghc 時,前面得加上 stack

再來使用 stack bulid 編譯,最後下 stack exec my-project-exe ,就能看到輸出:

someFunc

如果打開 app/Main.hs ,可以看到:

module Main where

import Lib

main :: IO ()
main = someFunc

其中 someFunc 來自 src/Lib.hs ,只做一件事:輸出 "someFunc"

module Lib
    ( someFunc
    ) where

someFunc :: IO ()
someFunc = putStrLn "someFunc"

Re: Build Your Own Haskell Compiler #0.1

預習

按 CindyLinz 的計畫,這天要利用 Language.Haskell.Exts 這套件讀出原始碼本身屬於哪個套件、 import 了哪些套件,再把它們通通讀出來,然後印出來。建議先讀過的套件有:

haskell-src-exts 在做那個愚蠢的、不 pretty 的 print 看過好幾次了。那時看的是 Language.Haskell.Exts.Syntax ,後來大家用的是 Language.Haskell.Exts.Annotated.Syntax 。要注意的是,後者的結構跟前者完全不同。 petercommand 一下子就發現了這件事。

Language.Haskell.Exts.Annotated.Syntax 下的 annamap 是操作 annotations 的工具,以前 Alex 有提過。前者把 annotation 拔出來,後者只對 annotation 作用。註解中還提到: if all nodes in the AST tree are to be affected, use fmap. ,這次可以用得上。

Language.Haskell.Exts.Pretty 比較妙的是, pretty 完就變回 Haskell 了,跟有縮排的 AST 不同。但對我們來說,更需要後者。那時曾試著看 TH 的,發現 Text.PrettyPrint ,但沒看懂。現在不知道看不看得懂 XDXD

另外 Hackage 多用 Haddock 註解。但是 Base 的 lhs 多用 \begin{code}\end{code} 把 code 包起來(LaTex suggestions)。這樣還有什麼意思呢? github 上只有到 2001 年的 commit ,不知道最早是不是就這樣?

Control.Exception 的作者是嘴吐 category theory 的 ekmett !

準備

一開始要以 haskell-src-exts 讀檔案,於是先在 app/Main.hs 中加上 import Language.Haskell.Exts.Annotated

module Main where

import Language.Haskell.Exts.Annotated

import Lib

main :: IO ()
main = someFunc

並修改 my-project.cabal ,在 executable my-project-exe 那段的 build-depends: 加上 haskell-src-exts

executable my-project-exe
  hs-source-dirs:      app
  main-is:             Main.hs
  ghc-options:         -threaded -rtsopts -with-rtsopts=-N
  build-depends:       base
                     , my-project
                     , haskell-src-exts
  default-language:    Haskell2010

接著執行 stack build ,會看到它開始下載並編譯套件,需要花一點時間。

Re: Build Your Own Haskell Compiler #0.2

parseModule

其實他很邪惡,要用到時才開始讀,雖然他叫 lazy ,但是跟 lazy evaluation 沒有關係。 m*******m 很不喜歡。

先開個新檔案 sample/A.hs

module Main where

import Prelude ()

main = putStrLn "hello, world"

讀檔可以用 Prelude 中的 getContents ,它會還給你一個 IO String ,可以用在 main 的 do notation 裡面:

main = do
  inputStr <- getContents
  putStrLn inputStr

這樣子輸入一行就能看到程式輸出一行。

inputStr 餵給來自 Language.Haskell.Exts.Annotated 的 parseModule ,可以得到 ParseResult ,再以 case ... of 看看結果是 ParseOk 還是 ParseFailed ,從裡面拆出 AST :

main = do
  inputStr <- getContents
  let res = parseModule inputStr
  putStrLn $ case res of
    ParseOk mod -> show mod
    ParseFailed _ msg -> msg

Language.Haskell.Exts.Annotated 吐出來的 AST 包含了描述程式碼位置的 SrcSpanInfo ,直接印出來大概像:

Module (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 1 1 6 1, srcInfoPoints = [SrcSpan "<unknown>.hs" 1 1 1 1,SrcSpan "<unknown>.hs" 1 1 1 1,SrcSpan "<unknown>.hs" 3 1 3 1,SrcSpan "<unknown>.hs" 5 1 5 1,SrcSpan "<unknown>.hs" 6 1 6 1,SrcSpan "<unknown>.hs" 6 1 6 1]}) (Just (ModuleHead (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 1 1 1 18, srcInfoPoints = [SrcSpan "<unknown>.hs" 1 1 1 7,SrcSpan "<unknown>.hs" 1 13 1 18]}) (ModuleName (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 1 8 1 12, srcInfoPoints = []}) "Main") Nothing Nothing)) [] [ImportDecl {importAnn = SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 3 1 3 18, srcInfoPoints = [SrcSpan "<unknown>.hs" 3 1 3 7]}, importModule = ModuleName (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 3 8 3 15, srcInfoPoints = []}) "Prelude", importQualified = False, importSrc = False, importSafe = False, importPkg = Nothing, importAs = Nothing, importSpecs = Just (ImportSpecList (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 3 16 3 18, srcInfoPoints = [SrcSpan "<unknown>.hs" 3 16 3 17,SrcSpan "<unknown>.hs" 3 17 3 18]}) False [])}] [PatBind (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 1 5 31, srcInfoPoints = []}) (PVar (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 1 5 5, srcInfoPoints = []}) (Ident (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 1 5 5, srcInfoPoints = []}) "main")) (UnGuardedRhs (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 6 5 31, srcInfoPoints = [SrcSpan "<unknown>.hs" 5 6 5 7]}) (App (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 8 5 31, srcInfoPoints = []}) (Var (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 8 5 16, srcInfoPoints = []}) (UnQual (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 8 5 16, srcInfoPoints = []}) (Ident (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 8 5 16, srcInfoPoints = []}) "putStrLn"))) (Lit (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 17 5 31, srcInfoPoints = []}) (String (SrcSpanInfo {srcInfoSpan = SrcSpan "<unknown>.hs" 5 17 5 31, srcInfoPoints = []}) "hello, world" "hello, world")))) Nothing]

如果覺得自己在操作 AST 時,會被 SrcSpanInfo 干擾,可以加上 fmap (const ())

main = do
  inputStr <- getContents
  let res = parseModule inputStr
  putStrLn $ case res of
    ParseOk mod -> show (fmap (const ()) mod)
    ParseFailed _ msg -> msg

fmapconst () 作用在整個 AST 上(前面提到的 annamap 則作用在單一個 node 上),把全部的 SrcSpanInfo 清光光,變成:

Module () (Just (ModuleHead () (ModuleName () "Main") Nothing Nothing)) [] [ImportDecl {importAnn = (), importModule = ModuleName () "Prelude", importQualified = False, importSrc = False, importSafe = False, importPkg = Nothing, importAs = Nothing, importSpecs = Just (ImportSpecList () False [])}] [PatBind () (PVar () (Ident () "main")) (UnGuardedRhs () (App () (Var () (UnQual () (Ident () "putStrLn"))) (Lit () (String () "hello, world" "hello, world")))) Nothing]

在還沒有真正的 pretty print 前,手動排版後,看起來是:

Module
  ()
  (Just (ModuleHead () (ModuleName () "Main") Nothing Nothing))
  []
  [ ImportDecl
      { importAnn = ()
      , importModule = ModuleName () "Prelude"
      , importQualified = False
      , importSrc = False
      , importSafe = False
      , importPkg = Nothing
      , importAs = Nothing
      , importSpecs = Just (ImportSpecList () False [])
      }
  ]
  [ PatBind
      ()
      (PVar () (Ident () "main"))
      (UnGuardedRhs
        ()
        (App
          ()
          (Var () (UnQual () (Ident () "putStrLn")))
          (Lit () (String () "hello, world" "hello, world"))))
      Nothing
  ]

對我來說,在習慣查文件前,可以對整個 AST 長什麼樣子,有個概念。

Re: Build Your Own Haskell Compiler #0.3

讀檔與蒐集

用了 readFile ,就脫離不了 IO 。於是只好把希望得到的,放在 IO 裡面:

readModule :: String -> IO (Maybe (Module SrcSpanInfo))

一開始先來個 do ,躲到 IO 裡面去:

readModule mod = do
  content <- readFile $ modName ++ ".hs"
  let res = parseModule content
  return $ case res of
    ParseOk mod -> Just mod
    ParseFailed _ msg -> Nothing

蒐集 AST 中 import 的 Module 時,要用到 readModule 的結果, IO 也跟著出現了:

collectModule :: Module SrcSpanInfo -> IO (M.Map String Bool)

這件事一直讓我想起 What Color is Your Function 。對了,別忘記 import Map

import Language.Haskell.Exts.Annotated
import qualified Data.Map.Strict as M

並在 my-project.cabal 中補上 containers

executable my-project-exe
  hs-source-dirs:      app
  main-is:             Main.hs
  ghc-options:         -threaded -rtsopts -with-rtsopts=-N
  build-depends:       base
                     , my-project
                     , containers
                     , haskell-src-exts
  default-language:    Haskell2010

先試著蒐集不重複的 Module 就好,不遞迴讀檔:

collectModule mod = do
  retrun $ case mod of
    Module _ mModuleHead _ imports _ -> go M.empty imports where
      modName = case mModuleHead of
        Just (ModuleHead _ (ModuleName _ name) _ _) -> name
        Nothing -> "Main"
      go acc [] = acc
      go acc (m : ms) =
        let
          (Module _ name) = importModule m
        in
          case M.member name acc of
            False -> go (M.insert name True acc) ms
            True -> go acc ms
    _ -> M.empty

回到 main ,可以這樣印出單一個檔案中 import 的東西:

main = do
  mMod <- readModule "A"
  res <- case mMod of
    Just mod -> collectModule mod
    Nothing -> return M.empty
  putStrLn $ show res

Re: Build Your Own Haskell Compiler #0.4

遞迴讀檔

想要知道自己這個 Module 叫什麼名字的話,看 ModuleHead ,想要看 import 出些什麼的話,看 [ImportDecl]

在上面還推薦大家要看的一個 library 叫做 Data.Map.Strict 。這個是我用來記錄 Module 到底讀過了沒有。你也可以用 List ,但這個效率會比較好一點。只是用起來比較複雜一點。

在遞迴讀檔前,花了不少時間整理思路,最後的想法是:

  1. 我需要一個 Map 來蒐集 module name 與 module AST 的對應關係。
  2. 我希望得到的結果在 IO 裡面,因為 readFile 會給我 IO ,我也需要 IO 才能 pretty print 。
  3. 我希望可以遞迴地處理所有 import 進來的檔案。

於是 type 長這樣:

collectModule :: IO (M.Map String (Module SrcSpanInfo)) -> Module SrcSpanInfo -> IO (M.Map String (Module SrcSpanInfo))

程式一開始先處理 Module

collectModule ioMap mod =
  case mod of
    Module _ mModuleHead _ imports _ -> -- 略
    _ -> ioMap

然後問問 Map 裡面是不是已經有現在要加入的 Module 了:

collectModule ioMap mod =
  case mod of
    Module _ mModuleHead _ imports _ -> do
      let
        modName = case mModuleHead of
          Just (ModuleHead _ (ModuleName _ name)) -> name
          Nothing -> "Main"
      map' <- ioMap
      let
        map'' = case M.member modName map' of
          False -> M.insert modName mod map'
          True -> map'
        -- 略
    _ -> ioMap

在那個 do 之後就是 IO 的領域了,於是 let 後面不用 inmap' 則是把 type 是 IO (M.Map String (Module SrcSpanInfo))ioMap 裡的 (M.Map String (Module SrcSpanInfo)) 拿出來。

奇怪的是那兩個 letcase ... of 的組合,如果寫:

let modName = case mModuleHead of
  Just (ModuleHead _ (ModuleName _ name)) -> name
  Nothing -> "Main"

是會得到 parsing error 的,但是寫:

let modName = case mModuleHead of Just (ModuleHead _ (ModuleName _ name)) -> name
                                  Nothing -> "Main"

會過,像前文那樣寫也會過。覺得前文那種寫法比較美觀,故沒有把 letcase ... of 寫在一起。


最後則是讀檔,再遞迴地呼叫自己:

collectModule ioMap mod =
  case mod of
    Module _ mModuleHead _ imports _ -> do
      let
        modName = case mModuleHead of
          Just (ModuleHead _ (ModuleName _ name)) -> name
          Nothing -> "Main"
      map' <- ioMap
      let
        map'' = case M.member modName map' of
          False -> M.insert modName mod map'
          True -> map'
        go acc [] = acc
        go acc (m : ms) = go modMap ms where
          modMap = do
            let (ModuleName _ name) = importModule m
            case name of
              "Prelude" -> acc
              _ -> do
                mMod <- readModule name
                case mMod of
                  Just mm -> collectModule acc mm
                  Nothing -> acc
        go (return map'') imports
    _ -> ioMap

go 的 type 其實是:

go :: IO (M.Map String (Module SrcSpanInfo)) -> [ImportDecl] -> IO (M.Map String (Module SrcSpanInfo))

go 吃到的 [ImportDecl] 空了([])時,就把 acc 原封不動地還回去。

[ImportDecl] 中還有東西時,就先把裡面第一個東西處理完,放到 modMap 中,再把剩下的交給 go 繼續處理。而 modMap 是什麼呢?是先看看這第一個叫 mImportModule 的名字,如果不是預設會自動 import 的 Prelude 的話,才交給 readModule 把 module 讀進來,看看有沒有讀成功(是 Just mm 還是 Nothing),成功就交給 collectModule acc mm 遞迴處理,失敗就傳回本來的 acc 。不用先把 acc 這個 IO (M.Map ...) 裡的 Map 拆出來,那在下一次遞迴時會被 collectModule 處理好。

最後 go (return map'') imports 之所以要加上 return ,是為了把沒被放在 IO 裡的 map'' 放進去,這樣才能交給 go 處理。


然後 main 只要這樣寫:

main :: IO ()
main = do
  inputStr <- getContents
  let res = parseModule inputStr
  allMods <- case res of
    ParseOk mod -> collectModule (return M.empty) mod
    ParseFailed _ msg -> return M.empty
  mapM_ putStrLn $ fmap prettyPrint allMods

最後那行 mapM_ putStrLn $ fmap prettyPrint allMods 可以讀作:把 prettyPrint 套到所有 modules 上面,然後一個一個印(putStrLn)出來, mapM_ 最後會還給我們 IO () ,功德圓滿。

只剩處理檔案路徑,就完成這次的進度了。

Re: Build Your Own Haskell Compiler #0.5

檔名、路徑

sample/ 下的檔案做了些調整:

-- A.hs
module Main where

import Prelude ()
import B

main = putStrLn $ hello ++ ", " ++ world
-- B.hs
module B where

import Prelude ()
import Chat.C

hello = "hello"
-- Chat/C.hs
module Chat.C where

world = "world"

現在要把 "Chat.C" 變成 "Chat/C.hs"

System.FilePath 的協助下,很簡單就能做到。

先在 my-project.cabal 加上

build-depends:       base
                   , my-project
                   , filepath
                   , -- 略

然後:

toModPath :: String -> String
toModPath str = map go str where
  go '.' = pathSeparator
  go c = c

處理 module 名時則:

import System.FilePath
-- 略
content <- readFile $ toMdoPath modName ++ (extSeparator : "hs")
-- 後略

pathSeparatorextSeparator 都是 System.FilePath 提供的函數,會按使用的平台(POSIX 或 Windows),給出正確的 Char

然後

第一次 BYOHC 重開機(?)的進度就到此。

當初許下的願望,像是 lambda calculus interpreter ,已經做出來了。也學到很多沒想過會去學的事,像英文閱讀速度就比之前快。可是這其實只是入門,離能把 Haskell 當成自己的工具、在日常與工作上使用,還有很長一段距離。也許接下來還是回到初衷,看看一個 functional language compiler 是怎麼建立的、看看前人踩了多少雷,補足匱乏的知識,才有往前走的動力。

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

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.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.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 ,也許是個起點。