EDSL相關雜記（1）

EDSL好處都有啥，誰說對了就給他

既然是EDSL，那麼我們一般直接用宿主語言的表達式來構成EDSL的AST了。這樣做的一些好處：

• 不用寫解析器；可以將宿主語言的函數當成宏使用；特定類型的EDSL可以借用宿主語言的一些語法糖，比如monadic EDSL可以用Haskell的do-notation寫得好看。
• 對於有簡單類型系統的EDSL，可以在宿主語言里聲明帶類型AST，然後藉助宿主語言的類型推導，省去實現類型檢查，不用額外標類型也保證類型安全。

• 實現帶綁定的EDSL（譬如函數參數等，而且需要實現靜態作用域），可以用HOAS實現AST中的綁定，將宿主語言的substitution機制偷來實現EDSL的substitution。如此可以靜態排除scope錯誤，substitution操作保證是安全（capture-free）的。

語法方面的另一個好消息是，我們可以先實現一門EDSL，然後藉助Template Haskell和QuasiQuotes擴展，為其實現一個concrete syntax及其parser——這個parser在Haskell編譯期運行，生成Haskell EDSL的AST，如果有語法錯誤是編譯期報告的。

類型方面，我們的EDSL也許是單類型/多類型的，可能是動態類型，或者帶更高級的一些類型特性（比如Session Type之類）。得益於Haskell強悍的類型系統，許多帶複雜類型的EDSL都可以編碼。類型安全性和便捷性存在一定衝突，之後會有例子講到。

Reification

前面提到，我們可以借用宿主語言的綁定機制實現EDSL的綁定，這樣可以免費獲得capture-free substitution的實現。如果EDSL除了解釋執行，還需要編譯到其他語言，那我們面臨reification的任務——在宿主語言里，將宿主語言的函數「序列化」成first-order的語法樹！這是function reification，另外還有monadic reification（可以視作前者的特殊情況），對應EDSL是用一個monad表示的情況（命令式語言常見）

別忘記我們的Haskell是一門木有運行時反射的語言，使用GHC魔法在運行期將一個函數值像剝洋蔥一樣剝開看定義然後數著參數一個個生成字元串參數名什麼的，木有這種事！那麼reification能做到什麼程度呢，HOAS真的對代碼生成不友好？默念九字真言，「類型是人類的好朋友」，具體做法將在講higher-order/monadic EDSL的章節揭曉，而且簡單到像作弊！

Expression Problem

說說所謂Expression Problem：怎樣讓EDSL可擴展（extensible）、可組合（composable）。可擴展意味著同一個EDSL可以方便地增加新的操作，或者說後端——能夠解釋執行、序列化，或者通過不同的pass進行一定優化處理後，生成某個目標平台的代碼。可組合意味著可以將EDSL拆解成一系列不同的更小語言並方便地組合操作——比如將函數抽象與調用做成一個子集，算術運算做成一個子集，I/O操作做成另一個子集，對EDSL的某個操作單獨在每個子集上實現，然後將其一組合就能實現對整個EDSL的該項操作。

舉個例子，對Scheme熟悉的同學也許聽說過Nanopass Framework的名字，這是Kent Dybvig等人提倡的實現教學/商業級編譯器的架構，將編譯過程組織為數十個pass，每個pass對一種AST略經修改變成新的AST。在Scheme這樣的動態語言里實現Nanopass尚可，而在ML家族語言里，如果每次AST形狀略有變化都要聲明新的數據類型然後寫一堆boilerplate，或者圖麻煩搞個大數據類型然後用文檔註明什麼pass下什麼形狀的AST不可能出現，那Nanopass可就沒搞頭了撒。

下一期專欄會講兩種Expression Problem的解決方法，各有好壞。在之後具體講述各類EDSL的實現方法時，我有時會忽略可組合性的要求，退回到用原始的ADT編碼EDSL，以方便我和讀者把注意力放在更適當的地方（

AST Typing Problem

可以看看Edward Yang的一篇博文。叫做AST Annotation Problem更合適，可以看作Expression Problem的延伸：怎樣為AST節點方便地標註上額外信息，不影響不使用該信息的函數？那篇博文以及LtU討論貼中總結了許多種不同的方法，其中一種（fixpoint functor）與下期專欄講的Data types à la carte相關。之後的專欄不會涉及AST Typing Problem，我們關注的對象是類型安全的EDSL，並無在AST節點上標註parsing位置或類型信息的必要。

順便說個我覺得更符合這名字的問題吧：靜態類型的EDSL，所有表達式都在Haskell中寫出的話，自然可以推導/標註（已知）類型，但如果需要運行期通過parsing等過程構建AST，如何處理未知的類型，且不傷害類型安全性？答案將在講type-level EDSL的章節揭曉。

Observable Sharing

Observable Sharing可以粗略地理解為Common Sub-expression Elimination。我們的AST常會用遞歸的數據類型表示，也就有了很多隱式地引入common sub-expression的機會，為了編譯出高效的代碼，怎樣將遞歸的AST轉換為非遞歸的頂點帶編號的圖，common sub-expression指向同一頂點？之後講first-order EDSL的例子時我會用兩類不同方式解決這個問題：hash-consing，以及指針比較。

Deep/Shallow Embedding

Deep/Shallow Embedding的概念非常淺顯，不過揭曉之前，先提另一對相關的概念吧：Syntax/Semantics。

Syntax特指Abstract Syntax，也就是EDSL「長什麼樣」，或者說怎樣構造出EDSL的程序。一般來說會有兩類構造，一類屬於primitive，是最簡單的EDSL表達式（比如常量等）；一類屬於combinator，將其他EDSL程序組合起來生成新的程序。假如EDSL有AST，用ADT建模，那麼primitive和combinator從該數據類型的構造器一看就知；但是EDSL設計者出於各種考慮常常會選擇隱藏EDSL的定義，只export一個抽象的數據類型，以及一系列「smart constructor」（類型簽名看起來像data constructor但也許不是）用於組合EDSL。

Semantics指語義，也就是EDSL「是啥意思」或者「能辦啥事」。為EDSL實現了一個eval函數的話，也就實現了這個EDSL的指稱語義（Denotational Semantics）。同一個EDSL，有可能實現不同的eval函數，從而賦予其多重語義。舉例：

-- Give me a Parser a, I give you a parsing functionnrunParser :: Parser a -> String -> Maybe (a, String)nn-- Give me a State a, I give you a state-passing functionnrunState :: State s a -> s -> (a, s)nn-- Give me an arithmetic expression, I give you the resultnevalExpr :: Expr -> Doublenn-- Give me an arithmetic expression, I show you what it isnshowExpr :: Expr -> Stringn

如果EDSL的定義方式即嵌入了其語義，比如

newtype State s a = State { runState :: s -> (a, s) }n

這樣的EDSL，採用的即是Shallow Embedding。Shallow Embedding的EDSL只允許一種解釋方式。而如果EDSL的定義方式僅停留在語法層面，不指定任何語義，則稱為Deep Embedding，比如：

data State s a wheren Get :: State s sn Put :: s -> State s ()n

（以上兩種State怎樣組合/執行暫時略去，有興趣的同學可自行探究）

Deep/Shallow Embedding各自優缺點都很明顯。Shallow Embedding只允許單一語義，不過在很多場合（例如Parsing組合子）下單一語義已經夠用，採用Shallow可以簡化實現；Deep Embedding將語法/語義分離開，使得EDSL的多種解釋方式以及優化變得可能。

兩種不同Embedding的關係並非水火不容，而是一體兩面。Folding domain-specific languages: deep and shallow embeddings指出，Shallow實際上是Deep的數據類型上的fold（catamorphism）；Combining deep and shallow embedding of domain-specific languages提出了在Deep框架里整合Shallow擴展的方法。而下一期將要介紹的兩種Expression Problem解決方式，都可以說是Shallow與Deep的某種結合。