跳轉到

1996：GHC 編譯器問世#

事件#

Glasgow Haskell Compiler（GHC）起源於 1989 年，由英國格拉斯哥大學的 Will Partain 等人開始開發，經過 Simon Peyton Jones 與 Simon Marlow 等人多年的重新設計，於 1996 年前後成為 Haskell 最主流的開源實作。GHC 的核心貢獻是將「惰性求值」從昂貴的學術玩具，變成可用於實務的高效編譯技術——它把 Haskell 編譯到自創的 STG 機（Spineless Tagless G-machine），再產生高效機器碼。

語法/特性加入的理論與實用原因#

1. STG 機：惰性求值的高效實作#

  • 理論原因：惰性求值在理論上保證了引用透明與非終止性處理的正確性，但每次求值都要「建立 thunk（未求值運算）」再強制（force），開銷巨大。Simon Peyton Jones 在 1992 年提出 Spineless Tagless G-machine：以「進入（enter）」指標取代標籤分派、以更新（update）機制共用已求值結果，將惰性成本壓到最低。
  • 實用原因：1996 年版 GHC 以 C 為後端（透過 -fvia-C）兼產生原生碼，配合嚴謹的嚴格性分析（strictness analysis），效能首次接近 C 語言的量級。
  • 彌補缺陷：早期 Haskell 直譯器（Hugs、GHC 1.x）與小型編譯器效能不足，無法用在實務系統。

2. 嚴格性分析與最佳化管線#

  • 理論原因：透過抽象直譯（abstract interpretation）推論哪些參數一定會被用到，將惰性求值自動轉為嚴格求值，免除 thunk 開銷而不破壞語意。
  • 實用原因：1990 年代 GHC 團隊開發 foldr/build 融合（fusion）轉換：讓串列管道（map f . filter p）的中間串列在編譯期被消除，理論基礎是代數律證明。
  • 彌補缺陷：惰性求值最大的實務罵名——處理串列時不斷產生中間結構與空間洩漏（space leak）——首次被系統性解決。
-- foldr/build fusion：下列兩者結果相同，但左式在編譯後不產生中間串列
sum (map (+1) [1..1000000])

看清楚融合到底消除了什麼——未融合版本會先在記憶體中建立一百萬個元素的中間串列，再逐一相加：

-- 未融合：產生中間串列 [2,3,4,...]，佔用大量記憶體
sum (map (+1) [1..1000000])

-- 融合後（GHC 的 foldr/build 轉換）：map 與 sum 交織成一個迴圈
-- 概念上等價於：
-- go 1 | if 1 > 1000000 then 0 else (1 + 1) + go 2
-- 中間串列完全不存在，常數空間完成運算

嚴格性問題的經典教訓：foldl 惰性累積 thunk 導致空間洩漏（甚至 stack overflow），foldl' 以 $!（或 seq）強制求值，常數空間完成：

-- 錯誤示範：foldl 不會立刻算出 acc+1，而是累積 ((0+1)+1)+1... 的 thunk
sumSlow = foldl (+) 0 [1..1000000]    -- 記憶體爆掉

-- 正確做法：foldl'（Data.List）在每步以 $! 強制求值 acc
import Data.List (foldl')
sumFast = foldl' (+) 0 [1..1000000]   -- 常數空間

-- $! 與 seq 是強制求值的基本工具：
strictAdd acc x = let s = acc + x in s `seq` s   -- 先算出 s，再回傳 s

GHC 擴展文化的代表——GADTs，讓代數資料型別攜帶型別等式，把更多不變量搬進型別層次：

{-# LANGUAGE GADTs #-}

-- 表達式語言：GADTs 保證「不能拿 Bool 加 Int」這類錯誤在編譯期被攔截
data Expr a where
  LitInt  :: Int  -> Expr Int
  LitBool :: Bool -> Expr Bool
  Add     :: Expr Int -> Expr Int -> Expr Int

eval :: Expr a -> a
eval (LitInt n)   = n
eval (LitBool b)  = b
eval (Add a b)    = eval a + eval b

-- eval (LitBool True `Add` LitInt 1)  -- 編譯錯誤：型別不符

3. 擴展文化：活的研究實驗室#

  • 理論原因：GHC 採用 -X 編譯旗標開關語言擴展，讓新理論（GADTs、type families、Template Haskell、ViewPatterns 等）能以「實驗性擴展」形式落地，經過社群驗證後再考慮納入標準。
  • 實用原因：研究人員可直接在真實編譯器上實驗，使用者可立即受益；這確立了「穩定標準 + GHC 擴展」的雙軌模式。
  • 彌補缺陷：語言標準（見 1998-Haskell-98標準化）凍結後缺乏演進管道，GHC 擴展成為事實上的語言演進機制。

STG 機下每個 Haskell 值都是 thunk 或已求值物件，編譯器產生的程式碼持續「enter → force → update」；嚴格性分析會在能證明安全時自動省略這些開銷：

-- GHC 的嚴格性分析：f 的兩個參數一定會被用到，編譯器自動轉為嚴格求值
f :: Int -> Int -> Int
f x y = x + y     -- 免除 x、y 的 thunk 建立成本，不必手寫 seq

彌補了什麼缺陷#

GHC 彌補了早期 Haskell 實作效能不足、無法實用的缺陷，讓惰性函數式語言從紙上談兵變成可用工具。此後 GHC 更成為型別系統研究的主要載體：GADTs（2006）、type families、Template Haskell、Category 與 Monad 庫生態，都使 Haskell 成為「活的研究實驗室」，許多構想（如泛型程式設計、效果系統）日後回饋到其他主流語言。

相關條目#