functional-programming - 功能上的“同时性”？

Question

在此link中，谈到了函数编程。具体来说，作者这样说：

同时性意味着我们假设一次对lambda微积分中的一条语句进行了一次评估。琐碎的功能：

λf(x) ::= x f(x)

定义了x插入的无限序列。逐步扩展如下所示：

0   - f(x)
1   - x f(x)
2   - x x f(x)
3   - x x x f(x)

关键是我们必须假设步骤三百万中的“ f（）”和“ x”具有与步骤一相同的含义。

在这一点上，那些对FP有所了解的人正在集体呼吸下喃喃地说“参照透明性”。我知道。一分钟后，我会击败它。现在，只需暂停您的怀疑，以承认约束确实存在，并且土豚也不会受到伤害。

现实世界中计算机无限扩展的问题在于，它们是无限的。如在“无限循环”中无限。除非打算在等待答案的同时准备好长时间的咖啡休息时间，否则无法在继续进行下一个评估之前评估无限序列的每个术语。

幸运的是，理论逻辑得以解救，并告诉我们预购评估将始终为我们提供与后购评估相同的结果。

更多的词汇表..为此需要另一个功能..幸运的是，这是一个简单的功能：

λg(x) ::= x x

现在..当我们发表声明时：

g(f(x))

预评估要求说，在将f（x）插入g（）之前，我们必须完全扩展它。但这需要永远，这很不方便。后期评估表明我们可以做到这一点：

0   - g(f(x))
1   - f(x) f(x)
2   - x f(x) x f(x)
3   - x x f(x) x x f(x)

。 。 。有人可以给我解释一下这是什么意思吗？我不知道在说什么。也许给我指出了一个非常好的FP入门，它将帮助我入门。

Answer 1

（警告，这个答案非常冗长。我认为最好包括lambda演算的一般知识，因为几乎找不到很好的解释）

作者似乎在使用语法λg(x)来表示命名函数，而不是lambda演算中的传统函数。作者似乎还在详细讨论lambda演算如何不是函数式编程，就像Turing机器不是命令式编程一样。那些通常用于表示它们的编程语言所没有的抽象存在一些实用性和理想。但是，在此之前，对lambda演算进行入门可能会有所帮助。在lambda演算中，所有函数如下所示：

λarg.body

而已。有一个 λ符号（称为“ lambda”，因此称为名称），后跟一个命名参数，只有一个命名参数，然后是句点，然后是表示函数主体的表达式。例如， identity函数可以接受任何内容并仅将其返回就可以像这样：

λx.x

计算表达式只是将函数和参数与其主体表达式交换出来的一系列简单规则。表达式的形式为：

function-or-expression arg-or-expression

减少它通常具有以下规则：“如果左物是一个表达式，则将其减少。否则，它必须是一个函数，因此请使用 arg-or-expression作为函数的参数，并将该表达式替换为函数的 body 。非常重要的一点是要注意，在将 arg-or-expression用作参数之前，不要求将其还原。也就是说，以下两项都是对 λx.x (λy.y 0)的等价且在数学上相同的化简（假设您有一些定义为0，因为lambda演算需要您将数字定义为函数）：

λx.x (λy.y 0)
=> λx.x 0
=> 0

λx.x (λy.y 0)
=> λy.y 0
=> 0

在第一个归约中，自变量在 λx.x函数中使用之前已被还原。在第二个中，该参数仅被替换为 λx.x函数体-在使用之前未进行任何还原。在编程中使用此概念时，它称为“惰性求值”-直到需要时才真正求值（化简）表达式。需要注意的重要一点是，在lambda演算中，在替换之前是否减少参数并不重要。 lambda演算的数学证明，只要两者都终止，您将以两种方式获得相同的结果。在编程语言中，绝对不是这种情况，因为各种各样的事情（通常与程序状态的变化有关）可以使惰性评估与常规评估有所不同。

Lambda演算需要一些扩展才能有用。没有办法命名。假设我们允许了。特别地，让我们为lambda演算中的函数创建自己的定义：

λname(arg).body

我们将说这意味着函数 λarg.body绑定到 name，并且在任何附带的lambda表达式中的其他任何地方，我们都可以将 name替换为 λarg.body。因此，我们可以这样做：

λidentity(x).x

现在，当我们编写 identity时，我们将其替换为 λx.x。但是，这带来了一个问题。如果命名函数引用自身，会发生什么？

λevil(x).(evil x)

现在我们遇到了问题。根据我们的规则，我们应该能够用名称绑定的内容替换 evil中的 body。但是由于名称绑定到 λx.(evil x)，因此我们尝试一下：

λevil(x).(evil x)
=> λevil(x).(λx.(evil x) x)
=> λevil(x).(λx.(λx.(evil x) x) x)
=> ...

我们得到一个无限循环。我们永远无法评估该表达式，因为我们无法将其从特殊的lambda形式转换为正则lambda形式。我们不能从具有特殊扩展名的语言扩展到常规的lambda演算，因为我们不能满足“用函数表达式 evil绑定到 evil绑定到”的规则。有一些技巧可以解决这个问题，但我们将在一分钟内解决。

这里的重要一点是，这与常规的lambda演算程序完全不同，后者可以无限求值并且永远不会结束。例如，考虑一下自我应用程序函数，该函数接受某些内容并将其应用于自身：

λx.(x x)

如果使用 identity函数对此进行评估，则会得到：

λx.(x x) λx.x
=> λx.x λx.x
=> λx.x

使用命名函数并命名该函数 self：

self identity
=> identity identity
=> identity

但是，如果我们将 self传递给自身，会发生什么？

λx.(x x) λx.(x x)
=> λx.(x x) λx.(x x)
=> λx.(x x) λx.(x x)
=> ...

我们得到一个表达式，该表达式循环反复地将 self self一次又一次地减少到 self self中。在任何（图灵完备）编程语言中，这都是一个普通的旧无限循环。

这与我们的递归定义问题之间的区别在于，我们的名称和定义不是lambda演算。它们是简写，我们可以通过遵循一些规则来扩展为lambda演算。但是在 λevil(x).(evil x)的情况下，我们无法将其扩展为lambda演算，因此我们甚至无法运行lambda演算表达式。从某种意义上说，我们的命名函数“无法编译”，类似于将编程语言编译器发送到无限循环中，并且与实际运行时循环相比，代码甚至从不启动。 （是的，使编译器陷入无限循环是 entirely possible。）

有一些非常巧妙的方法可以解决此问题，其中之一就是臭名昭著的 Y-combinator。基本思想是，您将有问题的 evil函数更改为，而不是接受参数并尝试递归，然后接受参数并返回另一个接受参数的函数，因此您的 body表达式具有两个参数与：

λevil(f).λy.(f y)

如果我们评估 evil identity，我们将获得一个新函数，该函数接受一个参数，并仅使用它调用 identity。以下评估首先显示使用->的名称替换，然后显示使用=>的名称替换：

(evil identity) 0
-> (λf.λy.(f y) identity) 0
-> (λf.λy.(f y) λx.x) 0
=> λy.(λx.x y) 0
=> λx.x 0
=> 0

有趣的是，如果我们将 evil传递给自身而不是 identity：

(evil evil) 0
-> (λf.λy.(f y) λf.λy.(f y)) 0
=> λy.(λf.λy.(f y) y) 0
=> λf.λy.(f y) 0
=> λy.(0 y)

我们最终得到了一个完全废话的功能，但是我们取得了重要的成就-我们创建了一个递归级别。如果我们评估 (evil (evil evil))，我们将获得两个等级。用 (evil (evil (evil evil)))，三个。因此，我们需要做的是代替传递 evil本身，而需要传递一个以某种方式为我们完成此递归的函数。特别地，它应该是具有某种自我应用程序的功能。我们想要的是Y组合器：

λf.(λx.(f (x x)) λx.(f (x x)))

该函数很难定义，因此最好将其称为 Y并查看当我们尝试对其进行评估时会发生什么：

Y evil
-> λf.(λx.(f (x x)) λx.(f (x x))) evil
=> λx.(evil (x x)) λx.(evil (x x))
=> evil (λx.(evil (x x))
         λx.(evil (x x)))
=> evil (evil (λx.(evil (x x))
               λx.(evil (x x))))
=> evil (evil (evil (λx.(evil (x x))
                     λx.(evil (x x)))))

正如我们所看到的，这是无限进行的。我们所做的是 evil，它首先接受一个函数，然后接受一个参数，并使用该函数评估该参数，然后将 evil函数的特殊修改版本传递给它，以扩展以提供递归。因此，我们可以通过减少 evil在 evil (Y evil)函数中创建“递归点”。所以现在，只要我们看到使用递归的命名函数，如下所示：

λname(x).(.... some body containing (name arg) in it somewhere)

我们可以将其转换为：

λname-rec(f).λx.(...... body with (name arg) replaced with (f arg))
λname(x).((name-rec (Y name-rec)) x)

我们将函数转换为一个版本，该版本首先接受用作递归点的函数，然后提供功能 Y name-rec作为用作递归点的函数。

之所以起作用，是让作者回到原来的观点，是因为表达式 name-rec (Y name-rec)在开始其自身的归约之前不必完全归因于 Y name-rec。我不能太强调这一点。我们已经看到，减小 Y name-rec会导致无限循环，因此，如果 name-rec函数中存在某种条件，则递归有效，这意味着可能无需减少 Y name-rec的下一步。

这在许多编程语言（包括功能性语言）中都有所细分，因为它们不支持这种惰性评估。另外，几乎所有的编程语言都支持变异。也就是说，如果定义变量 x = 3，稍后可以在同一代码中创建 x = 5，并且所有引用 x时为3的旧代码现在都将 x视为5。这意味着如果旧代码经过延迟评估而“延迟”并仅在以后计算，则您的程序可能会产生完全不同的结果，因为那时 x可能是5。在一种语言中，可以在任何时间以任意顺序任意执行代码，您必须完全消除程序对语句顺序和时变值之类的依赖。如果您不这样做，则程序可以根据您的代码以什么顺序运行来计算任意不同的结果。

但是，编写没有顺序感的代码非常困难。我们看到了如何使lambda演算变得多么复杂，以至于使我们无法进行简单的递归。因此，大多数函数式编程语言都选择一个模型，该模型系统地定义事物评估的顺序，并且从不偏离该模型。

Racket是Scheme的一种方言，它指定在普通的Racket语言中，所有表达式都“急切地”求值（没有延迟），并且所有函数参数都从左到右急切地求值，但是Racket程序包含一些特殊形式，可以让您有选择地进行某些表达式是惰性的，例如 (promise ...)。 Haskell的做法与此相反，默认情况下表达式使用惰性求值，并使编译器运行“严格性分析器”来确定专门声明需要急切求参数的函数所需要的表达式。

提出的主要观点似乎是，设计一种完全允许所有表达式单独变得懒惰或渴望的语言是太不切实际的，因为这对您可以在该语言中使用哪些工具构成了限制。因此，重要的是要记住功能语言为您提供了哪些工具来处理惰性表达式和热切表达式，因为它们肯定在所有实用的函数编程语言中都不等效。