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

Question

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

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

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

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

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

Answer 1

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

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

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

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