如何編譯函數閉包

閉包（英語：Closure），又稱詞法閉包（Lexical Closure）或函數閉包（function closures），是引用了自由變數的函數。這個被引用的自由變數將和這個函數一同存在，即使已經離開了創造它的環境也不例外。所以，有另一種說法認為閉包是由函數和與其相關的引用環境組合而成的實體。閉包在運行時可以有多個實例，不同的引用環境和相同的函數組合可以產生不同的實例。

想要實現一個同時支持詞法作用域與 first-class function 的編程語言，一個重要的轉換就是所謂的 lambda-lifting：把嵌套函數定義（包括匿名函數）轉換為獨立的全局函數定義；把自由變數的引用轉換為參數傳遞。

P.S.

• 代碼有省略
• 出於簡化的目的，這裡只考慮了最簡單的情況，並且沒有做任何有效性的檢查，假設了表達式中出現的變數全都是定義過的。
• 同樣是為了簡化，這裡不考慮類型。涉及到類型的情況下，需要在函數定義處保存自由變數的類型信息；這樣視需求可能又要在轉換過程中維護一個變數環境表來查找變數的類型。這裡不累述，具體可以參考後附的一個簡單的 OCaml 子集實現的源碼。

函數定義

這裡首先定義一個簡單的語言表示

這個語言類似於 untyped lambda calculus，有 lambda、apply 語句，只是多了一個 let 語句用於綁定一個變數。一般語言中的一些表達式形式（如 binary operator）一般則可以看作是 apply 的特殊形式。

用 Rust 代碼寫出來大概是這樣

enum Exp {n /// Lambda 抽象，參數名 -> 函數體n Abs(Id, Box<Exp>),n /// Let 定義，let 變數名 = 變數值 in 表達式n Let(Id, Box<Exp>, Box<Exp>),n /// 函數應用，變數名(參數)n App(Box<Exp>, Box<Exp>),n Var(Id),n}n

我們要做的事情是提取出一個匿名函數定義（lambda）中的自由變數，把匿名函數定義轉換為全局函數定義，並將函數定義入口和自由變數列表打包成一個實體（即所謂閉包），替換原來的 lambda 節點。

這樣，轉換之後的 AST 中沒有了 lambda 節點，取而代之的是類似 let 節點的閉包 closure 定義節點。

enum Term {n Cls(Id, Box<Cls>, Box<Term>),n App(Box<Term>, Box<Term>),n Let(Id, Box<Term>, Box<Term>),n Var(Id),n}n

閉包實體 Cls 中需要保存全局函數定義的入口和當前環境中自由變數的列表。

struct Cls {n label: Id,n fvs: Vec<Id>,n}n

由於需要保持自由變數的信息，全局函數定義需要保存一個自由變數的列表。

這樣我們有了全局函數定義的表示——入口 label，參數名，函數體，自由變數列表

struct Fundef {n pub label: Id,n pub param: Id,n pub body: Term,n pub fvs: Vec<Id>,n}n

自由變數的提取

自由變數的提取規則其實就是把變數加入符號表（環境）的逆過程。

• 變數表達式（Var）的自由變數就是變數自己；
• 函數應用（Apply）的自由變數是 callee 的自由變數和參數的自由變數取並集；
• Let 節點和 Cls 節點定義的變數，從其後繼表達式的自由變數中剔除，然後與初始化值表達式的自由變數合併。

即

最後，作為一個整體的函數定義，其參數要從自由變數中剔除。這個可以留到之後的轉換過程中實現。

在 rust 中同樣可以直截了當的實現。

fn fv(&mut self, source: &Term) -> HashSet<Id> {n use self::Term::*;n match source {n &App(box ref callee, box ref body) => {n let mut ret = fv(body);n ret.extend(fv(callee));n retn }n &Let(ref var, box ref val, box ref body) => {n let mut ret = fv(body);n ret.remove(var);n ret.extend(fv(val));n retn }n &Cls(ref var, box ref cls, box ref body) => {n let mut ret = cls.fv();n ret.extend(fv(body));n ret.remove(var);n }n &Var(v) => HashSet::new(v)n }n}nimpl Cls {n pub fn fv(&self) -> HashSet<Id> {n self.fvs.clone()n }n}n

函數閉包轉化

顯然，為了實現 lambda 到全局定義的轉換，我們需要保持一個全局定義表。為了之後方便的生成函數名和臨時變數名之類可能還需要一個生成器，這裡省略。

struct Conversion {n global: HashMap<Id, Fundef>,n}n

綜上所述，很容易寫出轉換過程。我們定義的 cls 節點有著類似與 let 的語義；當 lambda 單獨出現時，這裡直接將其轉換成一個單獨的定義了一個臨時變數的 cls 子表達式（類似於嵌套 let）。

impl Conversion {n fn define(&mut self, fun: Fundef) {n self.global.insert(fun.label.clone(), fun);n }n fn cvrt_cls(&mut self, param: Id, body: Exp) -> (Id, Vec<Id>) {n let cls_name = self.gen_cls_name();n let body = self.go(_body);n let fvs = {n let _fvs = self.fv(&body);n _fvs.remove(param);n _fvs.into_iter().collect()n };n self.define(Fundef {n label: cls_name.clone(),n param,n body,n fvs.clone()n });n (cls_name, fvs)n }n pub fn go(&mut self, exp: Exp) -> Term {n use self::Exp::*;n match exp {n Abs(param, box _body) => {n let (cls_name, fvs) = self.cvrt_cls(param, _body);n let tmp_var = self.gen_tmp_name();n Term::Cls(tmp_var, Cls {n label: cls_name,n fvsn }, Term::Var(tmp_var))n }n Let(var, box _val, box _body) => {n let body = self.go(_body);n if let Abs(param, box _body) = _val {n let (cls_name, fvs) = self.cvrt_cls(param, _body);n Term::Cls(var, Cls {n label: cls_name,n fvsn }, body)n } else {n let val = self.go(_val);n Term::Let(var, box val, box body)n }n }n App(box _callee, box _arg) => {n let callee = self.go(_callee);n let arg = self.go(_arg);n Term::App(callee, arg)n }n Var(v) => Term::Var(v)n }n }n}n

這裡對於 let 綁定 lambda 的處理是不把綁定的變數名剔除出自由變數。由於這裡的 let 語義默認是不允許遞歸綁定的，而 lambda 很多時候有遞歸的需求，所以這裡使用了靈活的辦法：把lambda 自己的名稱作為自由變數傳進去。這樣便可以通過後續代碼生成的順序控制能否遞歸：如果在完成函數名的綁定前先完成自由變數的綁定，便不允許遞歸，否則允許遞歸。

這樣便完成了閉包轉換的過程。後續便可以使用常規的編譯技術生成所有的全局函數定義。

參考

min-caml

Essentials of Compilation

Closure conversion: How to compile lambda