緣起

「雲泥之間」是一系列關於 Haskell 的教學/筆記文章。

最初的目的只是希望釐清幾個常見但是容易混淆的詞彙諸如 boxed 和 lifted 等等， 但是，隨著深入這些詞彙背後的情境，問題漸漸的形成了一個共同的問題： 「我們怎麼(在 Haskell 中)描述資訊(information¹)？」。 為了進一步地理解這個問題，便產生了這個系列文章。 也許最終沒有辦法有個結論或是答案，但是至少這系列的文章可以留下一些線索， 讓我們可以朝著答案前進。

系列結構與列表

我們更進一步地把問題粗略地分成三個不同的層次：

1. 要怎麼在計算世界裡面表示資訊？
2. 在 Haskell 的世界中資訊被怎麼表示？
3. Haskell 怎麼表示資訊？

而這三個不同的問題有著各自專屬的理論領域以及著重的重點。 接著，我們根據這三個層次來將此系列文章分成三個子系列： 因為我們探討的是如何在程式(或計算)中表示資訊， 所以第一個子系列，「Denotational Semantics and Domain」， 將試著整理程式語意以及相關的數學背景。 一旦對於抽象資料建構有一定程度的理解了， 我們接著會在第二個子系列「Constructions on Datatype in Haskell」 試著歸納出 Haskell 中怎麼建構或是表示資訊的方法。 以及這些方法是怎麼對應到數學理論上面的。 最後，最終的子系列「Haskell, GHC and STG Machine」 則是嘗試理解 Haskell 底層怎麼提供 Haskell 能力去讓他可以如是表示資訊。 或者說，試圖去理解 Haskell 底層是怎麼實踐那些抽象的資訊表示方法的。

Denotational Semantics and Domain

• Pointed? Lifted!
• (尚未完成) Constructions on Datatype
• (尚未完成) Eval Strategy and Bottom
• (尚未完成) Algebraic Datatype

Constructions on Datatype in Haskell

• (尚未完成) Kinds, # and *
• (尚未完成) Lazeness

Haskell, GHC and STG Machine

• (尚未完成) something you must know about STG Machine
• (尚未完成) Heap objects in STG Machine
• (尚未完成) Boxed/unboxed
• (尚未完成) Pack/unpack
• (尚未完成) Closure/thunk

參考資料

Stage I

• Denotational Semantics
  • Hutton’s Introduction to Domain Theory
  • Horwitz’s Domain Theory
  • Haskell Wikibook [Denotational semantics]https://en.wikibooks.org/wiki/Haskell/Denotational_semantics#Algebraic_Data_Types
• Layzeness
  • Yang’s How I Learned to Stop Worrying and Love the ⊥
  • Yang’sHussling Haskell types into Hasse diagrams
  • Yang’s Gin and monotonic (Errata)
  • Yang’s ω: I’m lubbin’ it – a great way to modularize laziness
  • Harper’s The Point of Laziness
• ADT
  • Wikipedia Algebraic data type
  • Wikipedia Generalized algebraic data type
  • Haskell wiki Algebraic data type
  • Haskell wiki GADT

Stage II

• WHNF
  • Haskell wiki weak head normal form
  • Haskell wikibook weak head normal form
• Eval and Buttom
  • Apfelmus’ Haskell’s Non-Strict Semantics
• lifting(in general)
  • haskell wiki Lifting
• kinds and datatype
  • GHC wiki Kinds
  • GHC wiki Unlifted data types
  • GHC wiki The data type Type and its friends

Stage III

• unpack
  • GHC user’s guide 7.22.11. UNPACK pragma
  • Haskell wiki Performance/Data types
  • GHC wiki Unpacked sum types
• unboxed
  • GHC user’s guide 7.2. Unboxed types and primitive operations
  • Hashell wiki Unboxed type
  • Haskell-Cafe Boxed versus Unboxed
• Thunk
  • stack overflow How much memory does a thunk use?
• STG
  • GHC wiki I know kung fu: learning STG by example
  • GHC wiki GHC Commentary: The Layout of Heap Objects

其他或是無關的參考資料與註記

Text and how to pick a text library

• Yang’s How to pick your string library in Haskell
• Shmalko’s Haskell String Types
• Haskell wiki Dealing with binary data

---

1. 這裡所謂的資訊 (information) 是泛指包含廣泛的資料 (data) 或是資料結構 (data structure) 等等。↩