来自 lambda 演算的示例 assembly/machine 指令
Example assembly/machine instruction from lambda calculus
我正在学习一些 lambda 演算，我非常好奇的一件事是如何在指令中实际应用完全抽象的函数。让我们来看下面的例子，我允许小的自然数（给定的）和 TRUE FALSE 定义。
例如，让我们使用以下代码，其计算结果应为 5:
# using python for the example but anything would suffice
TRUE = lambda x: lambda y: x # T = λab.a
FALSE = lambda x: lambda y: y # F = λab.b
TRUE(5)(2) # T('5')('2')
这可能如何在类似 lambda 演算的指令中实现以对其进行评估？我想到的一件事是“un-lambda-ify”它，所以结果就像这样：
// uncurried
int TRUE(int x, int y) {
return x;
}
int FALSE(int x, int y) {
return y;
}
TRUE(2, 5);
结果可能类似于：
SYS_EXIT = 60
.globl _start
TRUE: # faking a C calling convention
mov %edi, %eax
ret
_start:
mov , %edi
mov , %esi
call TRUE
mov %eax, %edi
mov $SYS_EXIT, %eax
syscall
这是如何完成的，或者对 functional/lambda-like 语言如何编译成指令的更详细的解释是什么？
这个问题对于 Stack Overflow 来说实在是太大了。
但回答它的一种方法是说，如果你能机械地将 λ 演算的某些变体翻译成某种其他语言，那么你就可以减少你如何可能会编译 λ 演算来询问如何将底层语言转换为某些物理机器的机器语言：换句话说，您如何编译该底层语言。这应该给出一个关于为什么这个问题太大的初步提示。
幸运的是，λ-演算非常简单，所以翻译成底层语言也很容易，特别是如果你选择一种具有 first-class 函数和宏的底层语言：你可以简单地将 λ 演算编译成该语言的一小部分。很可能底层语言会对数字、字符串和各种其他类型的事物进行操作，但您的编译器不会针对其中任何一个：它只会将 λ-演算中的函数转换为底层语言中的函数，然后依靠该语言来编译它们。如果底层语言没有 first-class 函数，你将不得不更加努力地工作，所以我会选择一个有。
所以这是一个具体的例子。我有一种叫做 'oa' 的玩具语言（或者实际上是 'oa/normal'，它是一种无类型的、正常顺序的 λ 演算。它以传统 Lisp 表示形式的轻微变体表示函数：(λ x y)是λx.y.函数应用是(x y).
oa然后get变成Scheme（其实是Racket）大致如下
首先，它使用两个操作将正常顺序语义转换为 Scheme 的应用顺序语义：
(hold x) 延迟了对 x 的评估——它只是 Scheme 的 delay 的一个版本，所以我可以用它来查找错误。与 delay 一样，hold 不是一个函数：它是一个宏。如果没有宏，翻译过程将不得不生成 hold 扩展到的表达式。(release* x) 将强制 hold 生成的持有对象，并会一直这样做，直到它获得的对象不是持有对象。 release* 等同于迭代的 force ，它会一直强制直到事情不再是承诺。与 hold 不同，release* 是一个函数，但与 hold 一样，如果您想让转换的输出更大且更难阅读，它可以简单地扩展为内联代码。
那么这就是几个 λ 演算表达式如何变成 Scheme 表达式的。在这里，我将使用 λ 表示 'this is a oa/λ-calculus-world thing'，使用 lambda 表示 'this is a Scheme world thing'。
(define true (λ x (λ y x)))
(define false (λ x (λ y y)))
变成
(define true (lambda (x) (lambda (y) x)))
(define false (lambda (x) (lambda (y) y)))
(define cond (λ p (λ a (λ b ((p a) b)))))
变成
(define cond (lambda (p)
(lambda (a)
(lambda (b)
(((release* p) a) b)))))
请注意，它会在即将调用它包装的任何内容时释放 p：因为语言中发生的唯一操作是函数调用，这是唯一需要强制承诺的地方.
现在
(((cond p) a) b)
变成
(((cond
(hold p))
(hold a))
(hold b))
所以在这里您可以看到所有参数都保存在函数调用中，这为您提供了正常顺序的语义。
实际上，将 oa 转换为 Scheme 的规则只有两条，一条用于 oa 中的每个构造。
(λ x y) -> (lambda (x) y)(x y) -> ((release* x) (hold y))
很明显，您可以机械地将 λ 演算转换为另一种语言。如果其他语言有宏和一阶函数之类的东西，它会有所帮助，但如果你愿意努力工作，你可以把它变成任何其他东西。上述将 oa 转换为 Scheme 的方法的一个好处是，oa 函数只是化装的 Scheme 函数（或者，实际上，Scheme 函数是化装的 oa 函数，或者它们可能交换了彼此的衣服或其他东西）。
那么我们将问题简化为一个更简单的问题：如何编译 Scheme？
嗯，首先要问的是一个大问题：对于 Stack Overflow 的回答来说太大了。那里有很多 Scheme 编译器，尽管它们可能具有共同的特性，但它们绝不相同。而且，因为很多都是比较毛茸茸的，实际看他们产生的代码往往信息量不大（oa中(λ x x)的反汇编好像是154行）。
但是，至少有两个关于编译 Scheme 的特别有趣的参考资料。
第一个（或几乎是第一个）Scheme 编译器称为 'Rabbit'，由 Guy Steele 编写。我不知道 Rabbit 本身是否仍然可用，但是 Steele's thesis on it is, and there's a texty version of it here 表面上看起来更具可读性但有问题。
编译的 Scheme 方言 Rabbit 是现代 Scheme 的一个相当远的祖先：我认为论文中对它的描述足以理解它是如何工作的。
Rabbit 编译为 MACLISP 而非机器语言。那么现在还有另一个问题：如何编译 MACLISP？但实际上它编译为 MACLISP 的一个极其有限的子集，我认为很容易看出它是如何转换成机器代码的。
第二个有趣的参考是向导书：Structure and Interpretation of Computer Programs. Chapter 5 of SICP is about register machines and compilation for them. It defines a simple register machine and the implementation of a compiler for Scheme (or a subset of Scheme) for it. Figure 5.17，第 597 和 597 页包含书中定义的寄存器机的明显递归 factorial 函数的编译输出。
最后：SICP 的那一章有 120 页：这就是为什么这个问题对于 Stack Overflow 来说太大了。
作为附录，我修复了 oa/normal 中我认为是愚蠢的地方，这使得编译后的输出更易于处理。使用 Racket 的 disassemble 包（使用一些胶水将其附加到 oa/normal/pure 语言，并使用 Racket/CS）：
> (disassemble (λ x x))
0: 4883fd01 (cmp rbp #x1)
4: 7507 (jnz (+ rip #x7)) ; => d
6: 4c89c5 (mov rbp r8)
9: 41ff6500 (jmp (mem64+ r13 #x0))
d: e96ecc35f8 (jmp (+ rip #x-7ca3392)) ; #<code doargerr> ; <=
12: 0f1f8000000000 (data)
我认为甚至有可能弄清楚这是在做什么：前两条指令是检查单个参数，如果没有则转到错误处理程序。第三条指令是（我推测）当函数 returns（我猜是 rbp 并且参数大概来自 r8 时，将参数移动到它需要的任何位置，并且然后它跳到下一个需要的地方。将此与
进行比较
> (disassemble (λ x 1))
0: 4883fd01 (cmp rbp #x1)
4: 750b (jnz (+ rip #xb)) ; => 11
6: 48c7c508000000 (mov rbp #x8)
d: 41ff6500 (jmp (mem64+ r13 #x0))
11: e96acc0cc7 (jmp (+ rip #x-38f33396)) ; #<code doargerr> ; <=
16: 0f1f8000000000 (data)
这是相同的，但 (mov rbp #x8) 正在将 fixnum 1 移动到 rbp 我假设，这已经以通常的方式移动，因为我猜系统使用低标签.
显然事情从那里变得更加毛茸茸。
基于lambda演算的函数式语言有很多评估和编译策略。
如果我们考虑您提供的程序：
(λx.λy.x) 5 2
第一步通常是执行某种独特的重命名，我们确保词法范围是明显的（如您所知，λx.λx.x 等同于 λy.λx.x - 尽管后者更清楚）并且潜在的代码运动优化不会意外导致范围冲突。上面的程序已经有了唯一的名称，所以我将在此处避免使用它。
第二步是执行某种转换为标准形式表示（其中计算产生的中间值绑定到给定唯一名称的变量）。对于严格的功能语言，通常在 ANF (A Normal Form) and CPS (Continuation Passing Style) 之间做出决定。为简单起见，我将使用 ANF 的变体（如果您有兴趣，可以在 Andrew Appel 的“Compiling with Continuations”中找到对 CPS 编译思想的彻底处理）。
这是这种转换的潜在结果：
let f x =
let g y = x in g
in
let x0 = f 5 in
let x1 = x0 2 in
x1
如您所见，以前的匿名函数（lambda 抽象）现在由命名函数表示，两个应用程序的中间结果现在绑定到变量。在这种形式中可以进行相当多的转换，但这个答案更侧重于引入这种结构清晰度的表示，而不是我们可以应用的任何优化。
下一步是进行闭包转换。此步骤解决了使用高阶函数编译代码时出现的问题，高阶函数的主体捕获超出其词法范围的值。由于我们没有执行 uncurrying 转换，因此我们的代码中存在部分应用程序 (f 5)。这必须 return 一个函数，在应用时，return 是我们提供给 f 的 x（无论范围如何）。为了在不生成运行时代码的情况下解决这个问题，编译器开发人员选择使用“闭包”数据结构来表示这些高阶函数
（之所以这样称呼，是因为它通过为自由变量提供值来 关闭 函数。
转换本身使函数适应接受补充参数（到它们的环境）和 returning 高阶函数到 return 闭包数据结构（在我们的例子中我们将使用“平面”闭包：一对由代码指针和指向将在内存中由记录表示的环境的指针组成的对。除此之外，所有调用站点都必须进行调整以解构 returned 闭包以便应用它。
这听起来很多，但这里有一些伪代码来演示这种天真地执行的转换：
let f(x, e) =
let g(y, e') = e'.x in (g, {x})
in
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
在这里，我使用大括号语法来表示环境的构造（所以 {} 是一个空环境——这个天真的转换遗留下来的人工制品——而 {x} 代表一个堆——分配的记录存储 x 的值）。对语法 (g, {x}) 堆分配一对（作为结构），其中第一个组件是 g 的代码指针，第二个组件是指向 [=21= 的堆分配记录的指针]. .0 和 .1 投影表示访问这些组件。您可能还注意到我采用了多参数应用程序语法 f(x,y,...) - 这不应与我用于成对的语法混淆。
闭包转换后，程序关闭，因此我们可以安全地执行所谓的“提升”转换，我们将嵌套函数提升到全局范围内（因此它们看起来更像类 C 函数，它们是编译更简单 - 很多编译过程是一种线性化）。
提升的结果可能如下所示：
let g(y, e') = e'.x
let f(x, e) = (g, {x})
let entry() =
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
从这里开始，通常编译器可能会转到某种具有聚合和指针类型概念的三地址代码 IR（以方便地处理闭包转换引入的辅助结构）。完全有可能将上述表示形式降低为 LLVM（使用一些廉价的 i64* 转换技巧 - 请注意，每个函数都是方便的 2-argument，因此我们不需要保留任何类型信息来生成 call).作为练习，您可能希望将上面的代码转换为 C 代码（这也很简单）。但是，由于您的回答需要一些汇编，所以这是一个非常幼稚（泄漏）的实现：
.data
fmt: .asciz "result = %lld\n"
.text
.globl main
g:
mov 0(%rsi), %rax # get and return x from environment
ret
f:
sub , %rsp
mov %rdi, (%rsp) # preserve x
mov , %edi # allocate space for {x}
call malloc@plt
mov (%rsp), %rcx # load and store x into environment
mov %rcx, 0(%rax)
mov %rax, 8(%rsp) # preserve environment
mov , %edi # allocate closure pair (2 pointers)
call malloc@plt
lea g(%rip), %rcx
mov %rcx, 0(%rax) # store g's code pointer as first component
mov 8(%rsp), %rcx
mov %rcx, 8(%rax) # store g's environment, {x}, as second component
add , %rsp
ret
main:
push %rbx
mov , %edi
xor %esi, %esi # {} = null, for simplicity
call f # f(5, {})
mov 0(%rax), %rbx # extract code pointer
mov 8(%rax), %rsi # extract environment
mov , %edi
call *%rbx # g(2, {x})
# print the result
mov %rax, %rsi
lea fmt(%rip), %rdi
xor %eax, %eax
call printf@plt
xor %eax, %eax
pop %rbx
ret
现在我将讨论一些重要的、实用的、我在整个回答中忽略的细节：
- 不能总是推断闭包的“范围”（或生命周期），因此默认情况下，我们选择在堆上分配它们。如果我们可以推断出闭包不会向上逃逸（使用称为“逃逸分析”的过程来发现这些情况），我们可以更经济地分配这些闭包的位置（例如在堆栈上）。我们要优化的情况是闭包仅向 向下转义 （换句话说，高阶函数仅向下传递调用堆栈但从不向上转义 - 在调用中 -链的结果 - 或者被分配到比闭包创建站点还长的其他位置）。
- 将闭包环境表示为记录非常重要，因为我们将依靠垃圾回收来收集它们。这对我们选择如何表示未装箱的文字值（例如上例中的
5 和 2）以及指向堆分配的 things[ 的指针有很大影响。 =87=]（例如闭包环境本身存储整数文字 和 指向闭包对的指针）。 OCaml 等语言选择执行此操作的方式是执行最低有效位标记（通过利用指针的对齐方式，我们可以通过检查最低位来区分未装箱的 63 位整数和 64 位指针 - 但是这样做，意味着所有算术必须适应于左移 1 位并递增 1 的值；所以 34 在编译的 OCaml 程序中看起来像 69）。除了这种区别之外，垃圾收集器必须遍历数据结构以找到指针，因此我们需要一个相当同质的结构来有效地执行此操作而无需编译布局信息（因此记录具有严格的对齐要求并存储 64 位值 - 你可以看到OCaml 使用的同质“块”布局图 here).
我希望这个答案能让人理解通常如何处理以 lambda 演算为根源的严格的函数式语言。
总结一下，步骤基本上是：
- 独特的重命名（范围检查可以同时进行）
- 选择性或整个程序转换为 ANF 或 CPS（涉及创建新名称）
- ANF 或 CPS 特定的优化（一般的事情，如 uncurrying、内联扩展、死代码删除、常量折叠、元组参数展平等）
- 闭包转换（随后可能会采用消除策略，例如已知闭包的 lambda 提升、使用 SCC 进行修复最小化等）
- 吊装
- 进一步降低到更像机器的三个（或两个）地址代码 IR，为转换引入的辅助结构的处理提供更明确的细节
- 将该 IR 降低为目标特定的汇编语言
在编译严格的函数式语言时，这绝对不是全部。例如，如果我们将我们的语言扩展为具有命名的、相互递归的函数，那么在我们的闭包转换转换中使用闭包共享将是可取的（并且还消除了不需要闭包的情况）。
我正在学习一些 lambda 演算，我非常好奇的一件事是如何在指令中实际应用完全抽象的函数。让我们来看下面的例子，我允许小的自然数（给定的）和 TRUE FALSE 定义。
例如，让我们使用以下代码，其计算结果应为 5:
# using python for the example but anything would suffice
TRUE = lambda x: lambda y: x # T = λab.a
FALSE = lambda x: lambda y: y # F = λab.b
TRUE(5)(2) # T('5')('2')
这可能如何在类似 lambda 演算的指令中实现以对其进行评估？我想到的一件事是“un-lambda-ify”它，所以结果就像这样：
// uncurried
int TRUE(int x, int y) {
return x;
}
int FALSE(int x, int y) {
return y;
}
TRUE(2, 5);
结果可能类似于：
SYS_EXIT = 60
.globl _start
TRUE: # faking a C calling convention
mov %edi, %eax
ret
_start:
mov , %edi
mov , %esi
call TRUE
mov %eax, %edi
mov $SYS_EXIT, %eax
syscall
这是如何完成的，或者对 functional/lambda-like 语言如何编译成指令的更详细的解释是什么？
这个问题对于 Stack Overflow 来说实在是太大了。
但回答它的一种方法是说，如果你能机械地将 λ 演算的某些变体翻译成某种其他语言，那么你就可以减少你如何可能会编译 λ 演算来询问如何将底层语言转换为某些物理机器的机器语言：换句话说，您如何编译该底层语言。这应该给出一个关于为什么这个问题太大的初步提示。
幸运的是，λ-演算非常简单，所以翻译成底层语言也很容易，特别是如果你选择一种具有 first-class 函数和宏的底层语言：你可以简单地将 λ 演算编译成该语言的一小部分。很可能底层语言会对数字、字符串和各种其他类型的事物进行操作，但您的编译器不会针对其中任何一个：它只会将 λ-演算中的函数转换为底层语言中的函数，然后依靠该语言来编译它们。如果底层语言没有 first-class 函数，你将不得不更加努力地工作，所以我会选择一个有。
所以这是一个具体的例子。我有一种叫做 'oa' 的玩具语言（或者实际上是 'oa/normal'，它是一种无类型的、正常顺序的 λ 演算。它以传统 Lisp 表示形式的轻微变体表示函数：(λ x y)是λx.y.函数应用是(x y).
oa然后get变成Scheme（其实是Racket）大致如下
首先，它使用两个操作将正常顺序语义转换为 Scheme 的应用顺序语义：
(hold x)延迟了对x的评估——它只是 Scheme 的delay的一个版本，所以我可以用它来查找错误。与delay一样，hold不是一个函数：它是一个宏。如果没有宏，翻译过程将不得不生成hold扩展到的表达式。(release* x)将强制hold生成的持有对象，并会一直这样做，直到它获得的对象不是持有对象。release*等同于迭代的force，它会一直强制直到事情不再是承诺。与hold不同，release*是一个函数，但与hold一样，如果您想让转换的输出更大且更难阅读，它可以简单地扩展为内联代码。
那么这就是几个 λ 演算表达式如何变成 Scheme 表达式的。在这里，我将使用 λ 表示 'this is a oa/λ-calculus-world thing'，使用 lambda 表示 'this is a Scheme world thing'。
(define true (λ x (λ y x)))
(define false (λ x (λ y y)))
变成
(define true (lambda (x) (lambda (y) x)))
(define false (lambda (x) (lambda (y) y)))
(define cond (λ p (λ a (λ b ((p a) b)))))
变成
(define cond (lambda (p)
(lambda (a)
(lambda (b)
(((release* p) a) b)))))
请注意，它会在即将调用它包装的任何内容时释放 p：因为语言中发生的唯一操作是函数调用，这是唯一需要强制承诺的地方.
现在
(((cond p) a) b)
变成
(((cond
(hold p))
(hold a))
(hold b))
所以在这里您可以看到所有参数都保存在函数调用中，这为您提供了正常顺序的语义。
实际上，将 oa 转换为 Scheme 的规则只有两条，一条用于 oa 中的每个构造。
(λ x y)->(lambda (x) y)(x y)->((release* x) (hold y))
很明显，您可以机械地将 λ 演算转换为另一种语言。如果其他语言有宏和一阶函数之类的东西，它会有所帮助，但如果你愿意努力工作，你可以把它变成任何其他东西。上述将 oa 转换为 Scheme 的方法的一个好处是，oa 函数只是化装的 Scheme 函数（或者，实际上，Scheme 函数是化装的 oa 函数，或者它们可能交换了彼此的衣服或其他东西）。
那么我们将问题简化为一个更简单的问题：如何编译 Scheme？
嗯，首先要问的是一个大问题：对于 Stack Overflow 的回答来说太大了。那里有很多 Scheme 编译器，尽管它们可能具有共同的特性，但它们绝不相同。而且，因为很多都是比较毛茸茸的，实际看他们产生的代码往往信息量不大（oa中(λ x x)的反汇编好像是154行）。
但是，至少有两个关于编译 Scheme 的特别有趣的参考资料。
第一个（或几乎是第一个）Scheme 编译器称为 'Rabbit'，由 Guy Steele 编写。我不知道 Rabbit 本身是否仍然可用，但是 Steele's thesis on it is, and there's a texty version of it here 表面上看起来更具可读性但有问题。
编译的 Scheme 方言 Rabbit 是现代 Scheme 的一个相当远的祖先：我认为论文中对它的描述足以理解它是如何工作的。
Rabbit 编译为 MACLISP 而非机器语言。那么现在还有另一个问题：如何编译 MACLISP？但实际上它编译为 MACLISP 的一个极其有限的子集，我认为很容易看出它是如何转换成机器代码的。
第二个有趣的参考是向导书：Structure and Interpretation of Computer Programs. Chapter 5 of SICP is about register machines and compilation for them. It defines a simple register machine and the implementation of a compiler for Scheme (or a subset of Scheme) for it. Figure 5.17，第 597 和 597 页包含书中定义的寄存器机的明显递归 factorial 函数的编译输出。
最后：SICP 的那一章有 120 页：这就是为什么这个问题对于 Stack Overflow 来说太大了。
作为附录，我修复了 oa/normal 中我认为是愚蠢的地方，这使得编译后的输出更易于处理。使用 Racket 的 disassemble 包（使用一些胶水将其附加到 oa/normal/pure 语言，并使用 Racket/CS）：
> (disassemble (λ x x))
0: 4883fd01 (cmp rbp #x1)
4: 7507 (jnz (+ rip #x7)) ; => d
6: 4c89c5 (mov rbp r8)
9: 41ff6500 (jmp (mem64+ r13 #x0))
d: e96ecc35f8 (jmp (+ rip #x-7ca3392)) ; #<code doargerr> ; <=
12: 0f1f8000000000 (data)
我认为甚至有可能弄清楚这是在做什么：前两条指令是检查单个参数，如果没有则转到错误处理程序。第三条指令是（我推测）当函数 returns（我猜是 rbp 并且参数大概来自 r8 时，将参数移动到它需要的任何位置，并且然后它跳到下一个需要的地方。将此与
> (disassemble (λ x 1))
0: 4883fd01 (cmp rbp #x1)
4: 750b (jnz (+ rip #xb)) ; => 11
6: 48c7c508000000 (mov rbp #x8)
d: 41ff6500 (jmp (mem64+ r13 #x0))
11: e96acc0cc7 (jmp (+ rip #x-38f33396)) ; #<code doargerr> ; <=
16: 0f1f8000000000 (data)
这是相同的，但 (mov rbp #x8) 正在将 fixnum 1 移动到 rbp 我假设，这已经以通常的方式移动，因为我猜系统使用低标签.
显然事情从那里变得更加毛茸茸。
基于lambda演算的函数式语言有很多评估和编译策略。
如果我们考虑您提供的程序：
(λx.λy.x) 5 2
第一步通常是执行某种独特的重命名，我们确保词法范围是明显的（如您所知，λx.λx.x 等同于 λy.λx.x - 尽管后者更清楚）并且潜在的代码运动优化不会意外导致范围冲突。上面的程序已经有了唯一的名称，所以我将在此处避免使用它。
第二步是执行某种转换为标准形式表示（其中计算产生的中间值绑定到给定唯一名称的变量）。对于严格的功能语言，通常在 ANF (A Normal Form) and CPS (Continuation Passing Style) 之间做出决定。为简单起见，我将使用 ANF 的变体（如果您有兴趣，可以在 Andrew Appel 的“Compiling with Continuations”中找到对 CPS 编译思想的彻底处理）。
这是这种转换的潜在结果：
let f x =
let g y = x in g
in
let x0 = f 5 in
let x1 = x0 2 in
x1
如您所见，以前的匿名函数（lambda 抽象）现在由命名函数表示，两个应用程序的中间结果现在绑定到变量。在这种形式中可以进行相当多的转换，但这个答案更侧重于引入这种结构清晰度的表示，而不是我们可以应用的任何优化。
下一步是进行闭包转换。此步骤解决了使用高阶函数编译代码时出现的问题，高阶函数的主体捕获超出其词法范围的值。由于我们没有执行 uncurrying 转换，因此我们的代码中存在部分应用程序 (f 5)。这必须 return 一个函数，在应用时，return 是我们提供给 f 的 x（无论范围如何）。为了在不生成运行时代码的情况下解决这个问题，编译器开发人员选择使用“闭包”数据结构来表示这些高阶函数
（之所以这样称呼，是因为它通过为自由变量提供值来 关闭 函数。
转换本身使函数适应接受补充参数（到它们的环境）和 returning 高阶函数到 return 闭包数据结构（在我们的例子中我们将使用“平面”闭包：一对由代码指针和指向将在内存中由记录表示的环境的指针组成的对。除此之外，所有调用站点都必须进行调整以解构 returned 闭包以便应用它。
这听起来很多，但这里有一些伪代码来演示这种天真地执行的转换：
let f(x, e) =
let g(y, e') = e'.x in (g, {x})
in
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
在这里，我使用大括号语法来表示环境的构造（所以 {} 是一个空环境——这个天真的转换遗留下来的人工制品——而 {x} 代表一个堆——分配的记录存储 x 的值）。对语法 (g, {x}) 堆分配一对（作为结构），其中第一个组件是 g 的代码指针，第二个组件是指向 [=21= 的堆分配记录的指针]. .0 和 .1 投影表示访问这些组件。您可能还注意到我采用了多参数应用程序语法 f(x,y,...) - 这不应与我用于成对的语法混淆。
闭包转换后，程序关闭，因此我们可以安全地执行所谓的“提升”转换，我们将嵌套函数提升到全局范围内（因此它们看起来更像类 C 函数，它们是编译更简单 - 很多编译过程是一种线性化）。
提升的结果可能如下所示：
let g(y, e') = e'.x
let f(x, e) = (g, {x})
let entry() =
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
从这里开始，通常编译器可能会转到某种具有聚合和指针类型概念的三地址代码 IR（以方便地处理闭包转换引入的辅助结构）。完全有可能将上述表示形式降低为 LLVM（使用一些廉价的 i64* 转换技巧 - 请注意，每个函数都是方便的 2-argument，因此我们不需要保留任何类型信息来生成 call).作为练习，您可能希望将上面的代码转换为 C 代码（这也很简单）。但是，由于您的回答需要一些汇编，所以这是一个非常幼稚（泄漏）的实现：
.data
fmt: .asciz "result = %lld\n"
.text
.globl main
g:
mov 0(%rsi), %rax # get and return x from environment
ret
f:
sub , %rsp
mov %rdi, (%rsp) # preserve x
mov , %edi # allocate space for {x}
call malloc@plt
mov (%rsp), %rcx # load and store x into environment
mov %rcx, 0(%rax)
mov %rax, 8(%rsp) # preserve environment
mov , %edi # allocate closure pair (2 pointers)
call malloc@plt
lea g(%rip), %rcx
mov %rcx, 0(%rax) # store g's code pointer as first component
mov 8(%rsp), %rcx
mov %rcx, 8(%rax) # store g's environment, {x}, as second component
add , %rsp
ret
main:
push %rbx
mov , %edi
xor %esi, %esi # {} = null, for simplicity
call f # f(5, {})
mov 0(%rax), %rbx # extract code pointer
mov 8(%rax), %rsi # extract environment
mov , %edi
call *%rbx # g(2, {x})
# print the result
mov %rax, %rsi
lea fmt(%rip), %rdi
xor %eax, %eax
call printf@plt
xor %eax, %eax
pop %rbx
ret
现在我将讨论一些重要的、实用的、我在整个回答中忽略的细节：
- 不能总是推断闭包的“范围”（或生命周期），因此默认情况下，我们选择在堆上分配它们。如果我们可以推断出闭包不会向上逃逸（使用称为“逃逸分析”的过程来发现这些情况），我们可以更经济地分配这些闭包的位置（例如在堆栈上）。我们要优化的情况是闭包仅向 向下转义 （换句话说，高阶函数仅向下传递调用堆栈但从不向上转义 - 在调用中 -链的结果 - 或者被分配到比闭包创建站点还长的其他位置）。
- 将闭包环境表示为记录非常重要，因为我们将依靠垃圾回收来收集它们。这对我们选择如何表示未装箱的文字值（例如上例中的
5和2）以及指向堆分配的 things[ 的指针有很大影响。 =87=]（例如闭包环境本身存储整数文字 和 指向闭包对的指针）。 OCaml 等语言选择执行此操作的方式是执行最低有效位标记（通过利用指针的对齐方式，我们可以通过检查最低位来区分未装箱的 63 位整数和 64 位指针 - 但是这样做，意味着所有算术必须适应于左移 1 位并递增 1 的值；所以34在编译的 OCaml 程序中看起来像69）。除了这种区别之外，垃圾收集器必须遍历数据结构以找到指针，因此我们需要一个相当同质的结构来有效地执行此操作而无需编译布局信息（因此记录具有严格的对齐要求并存储 64 位值 - 你可以看到OCaml 使用的同质“块”布局图 here).
我希望这个答案能让人理解通常如何处理以 lambda 演算为根源的严格的函数式语言。
总结一下，步骤基本上是：
- 独特的重命名（范围检查可以同时进行）
- 选择性或整个程序转换为 ANF 或 CPS（涉及创建新名称）
- ANF 或 CPS 特定的优化（一般的事情，如 uncurrying、内联扩展、死代码删除、常量折叠、元组参数展平等）
- 闭包转换（随后可能会采用消除策略，例如已知闭包的 lambda 提升、使用 SCC 进行修复最小化等）
- 吊装
- 进一步降低到更像机器的三个（或两个）地址代码 IR，为转换引入的辅助结构的处理提供更明确的细节
- 将该 IR 降低为目标特定的汇编语言
在编译严格的函数式语言时，这绝对不是全部。例如，如果我们将我们的语言扩展为具有命名的、相互递归的函数，那么在我们的闭包转换转换中使用闭包共享将是可取的（并且还消除了不需要闭包的情况）。