c# - 编译嵌套的相互递归函数

Question

我正在创建一种玩具动态语言（偏向于 javascript），虽然我的实现是在 DLR 之上，但我认为这个问题的解决方案与语言/平台无关。

我对编译递归函数或彼此相邻的相互递归函数没有问题。但是编译嵌套的相互递归函数要困难得多。

我用来测试的示例函数如下

void f(int x) {
 void g(int y) {
  if((x + y) < 100) {
   f(x + y);
  } else {
   print(x + y);
  }
 }
 g(x);
}

我认为解决这个问题的解决方案必须非常通用（也许我错了）而不是特定于 DLR，我假设我必须以某种方式解除g的内部定义并在f之前定义它并仍然保持关闭语境。

score 3 · Accepted Answer

闭包通常表示为组合函数指针和参数列表。第一步实际上是将所有嵌套函数提升到全局范围，并将其环境中的任何绑定变量作为参数。这相当于：

void _f(int x) 
{ 
  closure g = closure(_g,x);       
  call(g,x);  
}

void _g(int x, int y) 
{
  ...;
}

一旦你有了“闭包”和“调用”原语，它就可以工作了。在静态语言中，closure()只会保留相关变量。在动态语言中，closure()必须保持整个上下文堆栈可用，以防函数需要它。

score 1 · Accepted Answer

我知道你正在创建一种动态语言，但我认为同样的原则也适用于非动态语言——你仍然有一个符号表，你仍然必须通过多次处理来处理源代码。

如果您在代码生成阶段之前创建语义树，这很容易。对函数的调用指向将包含函数语义定义的对象（节点）。或者它只是一个说（语义上）调用这个函数的节点。由于对函数的调用不需要知道函数包含什么，只需一个指向符号表条目的指针就可以了。

如果您正在进行优化（尾端递归？），那么您需要执行两遍，然后才能对其进行分析以进行此类优化。这对于我见过的所有编译器来说都是正常的，因为这个阶段发生在语义/词法分析之后。

我想本文中的图表可以很好地显示我在说什么（但是它有两种不同的输入语言的额外位。）

score 0 · Accepted Answer

你想要完成的是一个 y-combinator

3 回答 3