如何编译函数闭包

// 知乎不仅不给我开专栏还说我这篇文章zz敏感，破网站吃枣药丸

闭包（英语：Closure），又称词法闭包（Lexical Closure）或函数闭包（function closures），是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在，即使已经离开了创造它的环境也不例外。所以，有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。闭包在运行时可以有多个实例，不同的引用环境和相同的函数组合可以产生不同的实例。

想要实现一个同时支持词法作用域与 first-class function 的编程语言，一个重要的转换就是所谓的 lambda-lifting：把嵌套函数定义（包括匿名函数）转换为独立的全局函数定义；把自由变量的引用转换为参数传递。

函数定义的转化

简便起见，这里定义一个简单的语言表示

\begin{aligned} exp\ ::=\ &Lam(id,exp)\\\\ &App(exp,exp)\\\\ &Let(id,exp,exp)\\\\ &Var(id) \end{aligned}

这个语言类似于 untyped lambda calculus，有 lambda、apply 语句，只是多了一个 let 语句用于绑定一个变量。一般语言中的一些表达式形式（如 binary operator）一般则可以看作是 apply 的特殊形式。

用 Rust 代码写出来大概是这样

enum Exp {
    /// Lambda 抽象，参数名 -> 函数体
    Abs(Id, Box<Exp>),
    /// Let 定义，let 变量名 = 变量值 in 表达式
    Let(Id, Box<Exp>, Box<Exp>),
    /// 函数应用，变量名(参数)
    App(Box<Exp>, Box<Exp>)，
    Var(Id),
}

我们要做的事情是提取出一个匿名函数定义（lambda）中的自由变量，把匿名函数定义转换为全局函数定义，并将函数定义入口和自由变量列表打包成一个实体（即所谓闭包），替换原来的 lambda 节点。

这样，转换之后的 AST 中没有了 lambda 节点，取而代之的是类似 let 节点的闭包 closure 定义节点。

\begin{aligned} term\ ::= \ &Cls(id,cls,term)\\\\ &App(term,term)\\\\ &Let(id,term,term)\\\\ &Var(id) \end{aligned}

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

闭包实体 Cls 中需要保存全局函数定义的入口和当前环境中自由变量的列表。

\begin{aligned} cls\ ::=\ &(label,(fv_1,fv_2,...,fv_n)) \end{aligned}

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

由于需要保持自由变量的信息，全局函数定义需要保存一个自由变量的列表。

这样我们有了全局函数定义的表示——入口 label，参数名，函数体，自由变量列表

\begin{aligned} fundef\ ::=\ &fun(label,id,exp,(fv_1,fv_2,...,fv_n)) \end{aligned}

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

自由变量的提取

自由变量的提取规则其实就是变量加入环境的逆过程。

变量表达式（Var）的自由变量就是变量自己
函数应用（Apply）的自由变量是 callee 的自由变量和参数的自由变量取并集
Let 节点和 Cls 节点定义的变量，从其后继表达式的自由变量中剔除，然后与初始化值表达式的自由变量合并。

即

\begin{aligned} fv(Var(v))&=\{v\}\\\\ fv(App(callee,arg))&=fv(callee) \ \cup \ fv(arg)\\\\ fv(Let(v,val,exp))&=fv(val) \ \cup\ fv(exp)\ -\ \{v\} \end{aligned}

最后，作为一个整体的函数定义，其参数要从自由变量中剔除。这个可以留到之后的转换过程中实现。

在 rust 中同样可以直截了当的实现

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

函数闭包转化

显然，为了实现 lambda 到全局定义的转换，我们需要保持一个全局定义表。为了之后方便的生成函数名和临时变量名之类可能还需要一个生成器，这里省略。

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

综上所述，很容易写出转换过程。我们定义的 cls 节点有着类似与 let 的语义；当 lambda 单独出现时，这里直接将其转换成一个单独的定义了一个临时变量的 cls 子表达式（类似于嵌套 let）。

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

这里对于 let 绑定 lambda 的处理是不把绑定的变量名剔除出自由变量。由于这里的 let 语义默认是不允许递归绑定的，而 lambda 很多时候有递归的需求，所以这里使用了灵活的办法：把lambda 自己的名称作为自由变量传进去。这样便可以通过后续代码生成的顺序控制能否递归：如果在完成函数名的绑定前先完成自由变量的绑定，便不允许递归，否则允许递归。

这样便完成了闭包转换的过程。后续便可以使用常规的编译技术生成所有的全局函数定义。