關於函數式語言的編譯優化，有沒有好的學習資料？

01-04

之前問過一個函數式語言傳值調用的優化問題，看到回答後我自己都鄙視自己，問得不專業，實在抱歉。
仔細想了一下，我其實是對函數式語言的性能很感興趣，想知道它的（硬體無關以及硬體相關的）編譯優化技術和常用的命令式語言有什麼異同，我現在還搞不清函數式語言的語義是如何建立的，希望大家能給我推薦些材料。
十分感謝！

1. 概述

經典書籍/phd論文

Implementing Functional Language

Compiling with continuations

Compiling with types

Compiling Standard ML for efficient execution on Modern Machines

IR for optimization

CPS, CPS conversion

CFG-SSA

PDG

其他

Program analysis and transformation

Uncurrying

Sinking

Inline switch continuation

Minimizing fix

...

Control-Flow Analysis of Higher-Order Languages or Taming Lambda, Olin Shivers

CFA2-Pushdown flow analysis for higher-order language, Dimitrios Vardoulakis

Environment Analysis of Higher-Order Languages, Matthew Might

Types guided compilation

Runtime for Functional Lang

Code Generation

2. FP相關的問題與優化

Sheme那樣由dynamic typing造成的問題不在討論範疇內

Higher order function

問題：大量函數調用/返回，大量中間數據；first class函數不利於分析

解決：Inline, Partial evaluation，Stream fusion，Supercompilation，Deforestation，Defunctionlization

Recursive functions

問題：遞歸的效率

解決：和Higher order function重疊的不再列出。另外有common subexpression elimination(CSE)，eliminating redundent comparisions/switches等...

Closure

問題：Space efficient，Fast access..

解決：Closure conversion

Persistent Data

問題：如果為了保證數據結構的「不可變」，每次「更新」都簡單粗暴地完全「複製」，內存會很快耗盡

解決：Share data, GC

Lazy evaluation

問題：Thunk爆炸啦。。

解決：Graph reduction，strictness analysis

Pattern Matching

問題：

解決：Compiling Pattern Matching to Good Decision Trees, Lic Maranget...

。。。

3. 常規優化

和其他語言類似。這一塊也非常重要。打個比方，FP-specific的優化是為了不輸在起跑線上，而最後誰佔優很大程度取決於常規優化。當然FP語言的一些特性（如purely xx）可能為常規優化帶來額外優勢（比如GC）

我先等 @邵成補充。。

ghc文獻列表：ReadingList

具體來說，函數式語言的編譯器怎樣實現，跟語言的設計選擇關係很大，包括並不限於以下方面：動態/靜態/混合類型？是否有運行時元編程能力（eval）？pure or impure？strict or lazy？等等。。更多的回宿舍補充。。

======

關於優化這一塊，你們就去看 @姚培森的答案吧。。那我補充點偏基礎的，因為從問題看，題主的關注點不僅是怎樣實現得更快，而且還有怎樣實現出來。

推薦一篇綜述：A systematic study of functional language implementations。INRIA的人寫的，以pure untyped lambda calculus這個最簡單的函數式語言為對象，介紹和比較了多種抽象機器。同類資料還有Abstract Computing Machines，Programming Languages and Lambda Calculi。寫編譯器的基礎是寫解釋器，寫解釋器就需要基於一個抽象機器。從這裡的介紹出發，可以去找不同抽象機器的相關文章看看，或者自己動手實現。

買回來了，發現看不懂。

函數程序設計語言--計算機模型、編譯技術、系統結構 (豆瓣)

孔網（正版）：函數程序設計語言（計算模型編譯技術系統結構）_商品搜索_網上書店_孔夫子舊書網：中國領先的古舊書交易平台

有路（盜版）：鄭緯民《函數程序設計語言--計算機模型、編譯技術、系統結構》- 買舊書上有路