lambda演算表达

Question

对于lambda表达 (x (λx y. x y) z h), ，我不明白变量如何 x (outer x), z 和 h 可以用C代码转换吗？

问候，Darkie

Answer 1

自由变量是lambda微积分中的一种特殊情况 - 它们不能“转换为”任何东西，因此通常将它们视为符号。在您的示例中，并给出了一些用于lambda表达式的虚拟构造函数，您将其转换为以下（包括处理隐式咖喱）c like表达：

mk_app(mk_app(mk_app(mk_sym("x"),
                     mk_lam("x",
                            mk_lam("y",
                                   mk_app(mk_var("x"),
                                          mk_var("y"))))),
              mk_sym("z")),
       mk_sym("h"));

显然，您可以使用 mk_var() 对于这些符号也是如此，但这会产生误导，因为它们不是真正的变量，因为它们没有绑定。换句话说，如果您对表达式进行任何alpha转换，则必须保持不变。

（顺便说一句，这里的相关部分是Barendregt的免费变量假设。）

Answer 2

将lambda演算转换为C代码是不平凡的。通常，您会写一个解释器，该解释器评估逐步。也就是说，将表达式变成树，并找到最接近根部的节点，该节点是一个应用程序，左侧是lambda。现在在右侧替换。重复，直到您再也无法应用，并有结果。

请注意，这里没有直接等效的。我们只是用他们来知道在哪里替代事物。

请记住，图灵对等不需要 精确的 两种图灵完整语言中的任何概念之间的等效性。它只是要求您能够与另一个效仿，反之亦然。