来自 lambda 演算的示例汇编/机器指令

Question

我正在学习一些 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 演算的指令中实现以评估这一点？我想到的一件事是“取消 lambda 化”它，所以它只是出现如下：

// 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 $5, %edi
    mov $2, %esi
    call TRUE
    mov %eax, %edi
    mov $SYS_EXIT, %eax
    syscall

这是如何完成的，或者对函数式/类似 lambda 的语言如何编译成指令的更深入的解释是什么？

Answer 1

有许多基于 lambda 演算的函数式语言的评估和编译策略。为简单起见，我假设您在谈论如何将您的示例视为真正严格的函数式语言（我们有应用顺序调用按值应用程序和整数文字的合适编码）。

如果我们考虑您提供的程序：

(?x.?y.x) 5 2

第一步通常是执行某种独特的重命名，我们确保词法范围是明显的（如您所知，?x.?x.x是 alpha 等效的?y.?x.x- 尽管后者更清晰）并且潜在的代码运动优化不会意外导致范围冲突。上面的程序已经有唯一的名称，所以我将在此处避免使用它。

第二步是执行某种转换为正常形式的表示（其中计算产生的中间值绑定到给定唯一名称的变量）。对于严格的函数式语言，通常需要在 ANF（一种范式）和 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 抽象）现在由命名函数表示，两个应用程序的中间结果现在绑定到变量。在这种形式中可以进行很多转换，但这个答案更侧重于引入这种表示以实现结构清晰，而不是我们可以应用的任何优化。

下一步是执行闭包转换。此步骤解决了使用高阶函数编译代码时出现的问题，这些函数的主体在其自身的词法范围之外捕获值。由于我们还没有执行非柯里化转换，因此我们的代码 ( f 5) 中存在部分应用程序。这必须返回一个函数，该函数在应用时返回x我们提供的f（无论范围如何）。为了在不生成运行时代码的情况下解决这个问题，编译器开发人员选择使用“闭包”数据结构来表示这些高阶函数（之所以这么称呼，是因为它通过向自由变量提供值来关闭函数）。

转换本身使函数接受一个补充参数（到它们的环境）和高阶函数的返回来返回一个闭包数据结构（在我们的例子中，我们将使用一个“平面”闭包：由一个代码指针组成的对以及指向将在内存中由记录表示的环境的指针）。最重要的是，所有调用站点都必须适应解构返回的闭包以应用它。

这听起来很多，但这里有一些伪代码来演示这种天真地执行的转换：

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）。pair 语法(g, {x})heap-allocates a pair（作为结构），其中第一个组件是 的代码指针，g第二个组件是指向 的堆分配记录的指针{x}。的.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 个参数，因此我们不需要保留任何类型信息来生成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 $24, %rsp
    mov %rdi, (%rsp)  # preserve x
    mov $8, %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 $16, %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 $24, %rsp
    ret
main:
    push %rbx
    mov $5, %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 $2, %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）以及指向堆分配事物的指针（例如，闭包环境本身存储整数文字和指向闭包对的指针）。OCaml 之类的语言选择这样做的方式是执行最低有效位标记（通过利用指针的对齐方式，我们可以通过检查最低位来区分未装箱的 63 位整数和 64 位指针 - 然而，这确实如此，意味着所有算术都必须适用于左移 1 位并递增 1 的值；所以34看起来像69在编译的 OCaml 程序中）。除了这种区别之外，垃圾收集器必须遍历数据结构以找到指针，因此我们需要一个相当同类的结构来有效地做到这一点，而无需编译布局信息（因此记录具有严格的对齐要求并存储 64 位值 - 您可以看到OCaml 使用的同构“块”布局图在这里）。

我希望这个答案能够让人们了解在 lambda 演算中找到根源的严格的函数式语言通常是如何处理的。

总结一下，步骤基本上是：

• 唯一重命名（可以同时进行范围检查）
• 选择性或整个程序转换为 ANF 或 CPS（涉及创建新名称）
• ANF 或 CPS 特定的优化
• 闭包转换
• 吊装
• 进一步降低为更像机器的三（或两个）地址代码 IR，它为处理由转换引入的辅助结构提供了更明确的细节
• 将该 IR 降低为特定于目标的汇编语言

在编译严格的函数式语言时，这绝对不是全部。例如，如果我们将我们的语言扩展为具有命名的、相互递归的函数，那么将闭包共享工作到我们的闭包转换转换中是可取的（并且还消除了不需要闭包的情况）。