在类似 Scheme 的编译器中创建闭包

Question

我正在实现一个类似于 scheme 的 lisp，它会在某个时候被编译成某种形式的字节码，可以看到 here。不幸的是，我给自己设置了一个漏洞，不知道如何摆脱它。本质上，给定一个看起来像这样的 lambda（外面的 b 有意未使用）：

(lambda (a b) (lambda (c) (+ a c)))

我的代码生成了这个语法树：

[
  type: :lambda,
  args: [[type: :word, val: 'a'], [type: :word, val: 'b']],
  body: [
    [
      type: :lambda,
      args: [[type: :word, val: 'c']],
      body: [
        [
          type: :expr,
          val: [
            [type: :word, val: '+'],
            [type: :word, val: 'a'],
            [type: :word, val: 'c']
          ]
        ]
      ]
    ]
  ]
]

不幸的是，当我真正开始生成字节码时，创建这些 lambda 所必需的闭包并不容易（据我所知）。理想情况下，我想生成一棵看起来像这样的树：

[
  type: :lambda,
  args: [[type: :word, val: 'a'], [type: :word, val: 'b']],
  closure: [],
  body: [
    [
      type: :lambda,
      args: [[type: :word, val: 'c']],
      closure: [[type: :word, val: 'a']],
      body: [
        [
          type: :expr,
          val: [
            [type: :word, val: '+'],
            [type: :word, val: 'a'],
            [type: :word, val: 'c']
          ]
        ]
      ]
    ]
  ]
]

很容易判断给定参数是否应该是闭包的一部分，方法是查看它是否出现在环境中，但是，因为我只是在 body 上调用 Enum.map 我我不确定如何将该信息返回给我的 lambda 对象。我不需要特定的代码来解决这个问题，但是在正确的方向上使用一般的 guideline/hint/push 会很好（我知道这有点模糊，但我不太确定如何进行更具体的测试这种情况）。

Answer 1

您可以沿着 AST 在每个节点构建一个绑定标识符列表。

例如，lambda 节点绑定其参数（如果它们已经在您的绑定列表中，请随意重写这些名称），以及 let 和 let*。在沿着这棵树往回走的同时，您还为每个 AST 节点构建了一个引用的自由标识符列表。

lambda、let 和 let* 从这些自由变量列表中删除标识符。

剩下的很简单：在每个 lambda 节点计算引用列表和绑定列表之间的交集，结果将是此闭包必须捕获的环境。如果为空，则这是一个没有环境的简单函数。

在您的示例中，它将是：

[b:() f:()](lambda (a b) [b:(a b) f:(a)] (lambda (c) [b: (a b c) f: (a c)] (+ a c)))

如您所见，内部 lambda 在其 b: 和 f: 列表之间有共同点 a，因此您必须在此处发出闭包分配指令，构建一个环境一个元素，a.

您可以将此过程与变量重命名相结合（例如，将 lambda 参数名称转换为参数编号）。

在类似 Scheme 的编译器中创建闭包

Creating a Closure in a Scheme-like Compiler

compiler-construction

elixir