In to the Core

整場演講配上 SPJ 的語調與活力,超歡樂!可惜投影片看不太清楚 XD

本來以為只是介紹 Core 有多精巧,沒想到後面在講 Core optimisations :

  • Inlining
  • Rewrite rules
  • Beta reduction
  • Case of case
  • Case of known constructor
  • ...

But once you done this. Very good things happen!

目前我聽得懂的部分中,最讓我驚訝的是把 beta reduction 到 let 的那段。我才剛剛在心中建立起 let x = expr2 in expr1(\x . expr1) expr2 的關係,沒想到 GHC 反過來做,看到後者就轉成本來就存在 Core 中的前者。也許我在 Implementing functional languages: a tutorial 中也會讀到這樣的應用?

... the transformations cascade! meaning you do one thing and that exposes the opportunity for another thing and that exposes the opportunity for another thing ...

另外讓我驚訝的是,這些最佳化彼此相輔相成地。於是會發生先把 beta reduction 變成 let ,再 inline ,或是 case of case 後,再 inline ... 一直做下去。

雖然最後指出和這主題相關的論文還有二三十篇(這輩子看得完嗎?),像是 Secrets of the GHC inliner ,但這充滿感染力的演講一掃週一夜晚的煩悶。我錯了,如果可以的話,真想成為這樣帶來知識和歡笑的人 XD

演講尾聲時還提到:

... compile strict language and lazy language into the same thing.

猜就算幾年後再重聽,一定還會從中學到東西。

Being Lazy with Class

沒想到 SPJ 同樣以 Being Lazy with Class 為名講過 Haskell 的歷史,非常歡樂 XD

目前好奇的部分有:

  • type classes 一開始就存在了,是為了 (==) ,還用一張投影片展示其實作背後的概念
  • 介紹 QuickCheck 如何善用 type classes (一半聽不懂),並建議大家讀論文 XD
  • 介紹了 GHC 中的 SystemFC ,和 IFL 中的 Core 差距滿大的,但小到一張投影片就塞得下!
data Expr
  = Var    Var
  | Lit    Literal
  | App    Expr Expr
  | Lam    Var Expr
  | Let    Bind Expr
  | Case   Expr Var Type [(AltCon, [Var], Expr)]
  | Cast   Expr Coercion
  | Note   Note Expr
  | Type   Type
type Coercion = Type
data Bind   = NonRec Var Expr | Rec [(Var, Expr)]
data AltCon = DEFAULT | LitAlt Lit | DataAlt DataCon

不知道哪天可以搞懂? XD


最後一個問問題的人是 Guy Steele !?

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