lambda - Lambda演算表达式实现函数应用

Question

我刚刚找到了以下 lambda 演算表达式：

(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))

所以这是一个函数，它接受一个参数 f 并返回另一个函数，该函数接受一个参数 x 并产生 x 应用于 f 的结果。上述表达式的结果将是 (λ b . b)。

这让我想起了部分应用程序和柯里化，但是“由内而外”的函数应用程序 (fx) 引起了我的兴趣。

这个表达有更深层次的理论意义吗？

Answer 1

这个表达式实际上很酷，尽管它是一个非常简单的操作。毕竟函数只是函数应用，对吧？

这就是事情变得有趣的地方。在 lambda 演算中，应用程序是一个句法规则，它简单地说“如果f是一个表达式并且x是一个表达式，那么f x就是一个表达式”。应用程序不是任何类型的功能。这是不幸的：因为 lambda 演算完全是关于函数的，所以不得不严重依赖不是函数的东西会很糟糕！

您的示例是对此的一种补救措施。虽然我们无法摆脱应用程序，但我们至少可以定义一个应用程序的对应物。该对应物是 lambda 函数(λ f . (λ x . (f x)))（或更惯用的说法是λfx.f x）。这是一个函数，因此我们可以对其进行推理并像使用任何其他函数一样使用它。我们可以将它作为参数传递给其他函数，也可以将其用作函数的结果。突然之间，函数应用变得更加可用。

就 lambda 演算而言，这就是我所掌握的全部内容，但是这个函数以及其他类似函数在现实生活中也很有帮助。在函数式编程语言 F# 中，这个函数甚至有一个名字，“向后管道运算符”，我们写它有中缀运算符<|。f (x)因此，作为写where xis some expression的替代方法，我们可以写f <| x. 这很好，因为它通常可以让我们免于编写很多烦人的括号。我在这里要说明的关键点是，尽管您的示例乍一看似乎很学术，或者可能只是没有多大帮助，但它实际上已经进入了几种主流编程语言。