請問大家了解函數式語言編譯器的實現技術嘛?

01-06

鄙人已經試過實現一個簡單的C語言的子集，但是對函數式語言編譯器的實現很感興趣。請問大家知道有比較系統的關於函數式語言的編譯器實現的資料嘛？好像市面上的書，龍書，Engineering A Compiler都是傳統的對C類型的語言的編譯器實現。例如聽說
好像SML這個強靜態類型的語言，有closure conversion, CPS conversion, phase splitting, 垃圾回收之類的編譯過程，跟傳統的不太一樣。請問大家了解相關的技術資料嘛，對這方面很感興趣，但是對類型理論什麼的都不是很了解。麻煩大家了！

嘛碰巧這學期我在上SML Compilation(15-417)的課，很可惜教科書/課件是沒有的，教授太懶了還沒寫出來233，我也剛開始上課所以還不是特別了解整個過程。不過我可以大致先貼一個SML編譯的流程，過一個學期再回來填坑。

上課上了一半了終於可以來填坑了。CPS-conversion的目的在於抓取程序的control flow。這麼做主要是因為函數式編程的control flow一般都不是explicit的，所以導致很難生成對應的機器碼。通過CPS變換，我們可以準確分辨程序中的「值」和「操作」，使得代碼更像普通的命令式的代碼。之後對的closure conversion和hoisting是為了把程序中的variable和type variable抓取到top level，再通過allocation去把tuples and sums給變換成內存里的tag和地址，最後得到一個只依賴heap的C的代碼。

個人覺得如果真的想搞一個functional compiler的話大可不必從SML起步，因為SML的module system相對而言比單純的函數式語言來的複雜得多，這個module system也使得SML的type inference變得極其複雜（事實上，SML的type equivalence algorithm都是最近20年才提出的）。題主提到的phase spliting就是為了區分module中靜態和動態的內容而產生的。如果真的想了解這塊內容的話，我覺得還是先從PFPL裡面的existential type開始看起來。我的小夥伴們整理的notes在這裡，如果想圍觀的話可以戳這裡zachhalle/hotc

如果您需要相關課程的話，IU 有一門 Compiler 課程講如何把 Scheme/Racket 編譯到 x86-64 彙編。之前用 Scheme 來教學，去年這門課被重新設計為使用 Racket 了。

內容包括：

Instruction Selection
Register Allocation
Static type checking
Conditional control flow
Mutable data
Garbage collection
Procedures and calling conventions
First-class functions and closure conversion
Dynamic typing
Generics
High-level optimization (inlining, constant folding, copy propagation, etc.)

教材：https://www.sharelatex.com/project/5637a774990f556d48bab667

代碼：https://github.com/IUCompilerCourse/support-code-for-students

課程主頁：https://iu.instructure.com/courses/1517577

題主提到的書：

好像市面上的書，龍書，Engineering A Compiler都是傳統的對C類型的語言的編譯器實現

正好完美避開了講FP語言的編譯器的…

作為入門，題主可以從Andrew Appel大神的書開始：

Modern Compiler Implementation in ML，ISBN 0-521-60764-7，又名「虎書」ML版
Compiling with Continuations，ISBN 9780521033114

先把虎書ML版里的Tiger語言給實現出來了再說別的 ^_^

跟上面的後者差不多時期的還有另外一個答案提到的 The Implementation of Functional Programming Languages。

說到函數式語言的編譯器肯定得提GHC啊。這個博主（Stephen Diehl）寫了個 Dive into GHC series。（裡面附帶了很多GHC internals的相關資料和references）

之前他還寫了一個 Write You a Haskell ( Stephen Diehl ) 其實更加approachable, 不過這個在github上有半年多沒更新了，希望作者還是能抽空把書寫完了，不過目前的前10章內容也是非常好的。

嚴格求值的函數式語言前端和後端和命令式語言是一樣的，不一樣的是ast到線性ir這塊。看compiling with comtinuation 就可以了，這本是此領域的巔峰之作

可以看下CMU的HOT (High Order, Typed) compilation這門課

15-501/15-819 HOT Compilation, Fall 2006

評論區提到編譯器後端，我想題主的問題函數式語言編譯器，是很明顯對偏前端的問題感興趣，後端的那些技術估計題主興趣不大。

單趟走完不分前後端不做優化的編譯器多得是。把解釋執行部分替換成目標代碼生成，很複雜嗎。

我理解提起編譯器第一想法就是一大堆優化，生成彙編。可解釋器也可以對輸入做優化，執行部分用彙編。

// 原答案

SICP頭幾章不就是教你寫Scheme解釋器么。