功能与命令的混合体

Question

纯函数式编程语言不允许可变数据，但某些计算可以更自然/直观地以命令式方式表达，或者算法的命令式版本可能更有效。我知道大多数函数式语言都不是纯粹的，并且允许您分配/重新分配变量并执行命令性的操作，但通常不鼓励这样做。

我的问题是，为什么不允许在局部变量中操作局部状态，但要求函数只能访问它们自己的局部变量和全局常量（或者只是在外部作用域中定义的常量）？这样，所有函数都保持引用透明性（给定相同的参数，它们总是给出相同的返回值），但在函数内，计算可以用命令式术语表达（例如，while 循环）。

IO 等仍然可以通过正常的功能方式完成 - 通过 monad 或传递“世界”或“宇宙”令牌。

Answer 1

我的问题是，为什么不允许在局部变量中操作局部状态，但要求函数只能访问它们自己的局部变量和全局常量（或者只是在外部作用域中定义的常量）？

好问题。我认为答案是，可变局部变量的实用价值有限，但可变堆分配的数据结构（主要是数组）非常有价值，并且构成了许多重要集合的支柱，包括高效的堆栈、队列、集合和字典。因此，仅将突变限制为局部变量不会给纯函数式语言带来突变的任何重要好处。

与此相关的是，交换纯功能数据结构的通信顺序进程提供了两个世界的许多好处，因为顺序进程可以在内部使用突变，例如可变消息队列比任何纯功能队列快约 10 倍。例如，这在 F# 中是惯用的，其中 MailboxProcessor 中的代码使用可变数据结构，但它们之间传递的消息是不可变的。

在这种情况下，排序是一个很好的案例研究。 Sedgewick 的 C 快速排序简短而简单，并且比任何语言中最快的纯函数排序快数百倍。原因是快速排序会就地改变数组。反复无常的当地人无济于事。大多数图算法都是同样的情况。

Answer 2

简短的回答是：有一些系统可以满足您的需求。例如，您可以使用 Haskell 中的 ST monad 来完成此操作（如评论中所引用）。

ST monad 方法来自 Haskell 的 Control.Monad.ST。在 ST monad 中编写的代码可以在方便的地方使用引用 (STRef)。好的部分是，您甚至可以在纯代码中使用 ST monad 的结果，因为它本质上是独立的（这基本上就是您在问题中想要的）。

这个独立属性的证明是通过类型系统完成的。 ST monad 带有一个状态线程参数，通常用类型变量 s 表示。当你进行这样的计算时，你将得到一元结果，其类型如下：

foo :: ST s Int

要实际将其转换为纯结果，你必须使用

runST :: (forall s . ST s a) -> a

你可以读取此类型，如：给我一个计算，其中 s 类型参数并不重要，我可以给你返回计算结果，没有 ST 包袱。这基本上可以防止可变 ST 变量逃逸，因为它们会携带 s ，而这些 s 会被类型系统捕获。

这可以对使用底层可变结构实现的纯结构产生良好的效果（例如 向量包）。人们可以在有限的时间内摆脱不变性，以做一些就地改变底层数组的事情。例如，可以将不可变的 Vector 与 impure 结合起来算法包以保留就地排序算法的大部分性能特征，并且仍然获得纯度。

在这种情况下，它看起来像：

pureSort :: Ord a => Vector a -> Vector a
pureSort vector = runST $ do
  mutableVector <- thaw vector
  sort mutableVector
  freeze mutableVector

thaw 和 freeze 函数是线性时间复制，但这不会破坏整体 O(n lg n) 运行时间。您甚至可以使用 unsafeFreeze 来避免再次线性遍历，因为可变向量不会再次使用。

Answer 3

“纯函数式编程语言不允许可变数据”……实际上确实如此，您只需识别出它隐藏的位置并了解它的本质即可。

可变性是指两个事物具有相同的名称和互斥的存在时间，以便它们可以被视为“不同时间的同一事物”。但正如每个禅宗哲学家都知道的那样，不存在“不同时间相同的事情”这样的事情。一切都在瞬间停止存在，并由其后继者以可能改变的形式、（可能）无数无限连续的瞬间继承。

在 lambda 演算中，可变性采用以下示例所示的形式：(λx (λx f(x)) (x+1)) (x+1)，也可以表示为“让 x = x + 1 in let x = x + 1 in f(x)”或只是“x = x + 1, x = x + 1, f(x)”，更类似于 C 的表示法。

换句话说，“lambda演算”的“名称冲突”实际上是命令式编程的变相“更新”。在禅宗（永远是对的）眼中，它们是一体的。

因此，我们将变量的每个时刻和状态称为对象的 Zen Scope。一个带有可变对象的普通作用域相当于许多带有常量、不可变对象的 Zen 作用域，如果它们是第一个，则它们要么被初始化，要么从它们的前任继承（如果它们不是）。

当人们说“可变性”时，他们是在错误地识别并混淆这个问题。可变性（正如我们刚刚在这里看到的）完全是一个转移注意力的话题。他们实际上的意思（甚至他们自己也不清楚）是无限的可变性；即出现在循环控制流结构中的类型。换句话说，他们实际上指的是——特别是“命令式”而不是“功能性”——根本不是可变性，而是循环控制流结构以及由此带来的 Zen 范围的无限嵌套。

因此，lambda 演算中缺少的关键特征不被视为可以通过包含像 monad 这样过度劳累和深思熟虑的“解决方案”来补救的东西（尽管这并不排除它完成工作的可能性） ）但作为无限项。

控制流结构是未包装（可能无限）决策树结构的包装。分支可能会重新聚合。在相应的展开结构中，它们显示为复制但独立的分支或子树。 Goto 是到子树的直接链接。向后分支到控制流结构的早期部分（循环控制流结构“循环”的起源）的 goto 或分支是到所链接的整个结构的相同形状副本的链接。每个结构对应的是其Universally Unrolled决策树。

更准确地说，我们可以将控制流结构视为位于实际表达式之前的语句，该语句限制该表达式的值。典型的例子是 Landin 的原始案例本身（在他 1960 年的论文中，他试图将命令式语言 lambda 化）：让 f(x) 中的 x = 1。 “x = 1”部分是语句，“f(x)”是该语句所条件的值。在类似 C 的形式中，我们可以将其写为 x = 1, f(x)。

更一般地，对应于每个语句S和表达式Q的是表达式S[Q]，其表示应用S之后的结果Q。因此，(x = 1)[f(x)] 就是 λx f(x) (x + 1)。 S 环绕 Q。如果 S 包含循环控制流结构，则环绕将是无限的。

当兰丁试图制定这个策略时，当他进入 while 循环时，他碰壁了，并说“哎呀。没关系。”然后又陷入了一个过度劳累和过度思考的解决方案，而这个简单的（回想起来，显而易见的）答案却没有引起他的注意。

while 循环“while (x < n) x = x + 1;” - 具有上述“无限可变性”，本身可以被视为无限包装器，“if (x < n) { x = x + 1; if (x < 1) { x = x + 1; if (x < 1) { x = x + 1 ... } } }”。因此，当它环绕表达式 Q 时，结果是（用类似 C 的表示法）“x < n? (x = x + 1, x < n? (x = x + 1, x < n? (x = x + 1, ...): Q): Q): Q"，可以直接以 lambda 形式呈现为“x < n? (λx x < n? λx x ＜ n? (λx·...) (x + 1): Q) (x + 1): Q) (x + 1): Q”。这直接表明了循环性和无限性之间的联系。

这是一个无限表达式，尽管是无限的，但只有有限数量的不同子表达式。正如我们可以认为该表达式有一个通用展开形式 - 类似于上面显示的内容（无限决策树） - 我们也可以认为存在一个最大滚动形式，它可以通过标记每个来获得相反，不同的子表达式并引用标签。关键子表达式将是：

A: x < n？ goto B: Q

B: x = x + 1, goto A

这里的子表达式标签是“A:”和“B:”，而对子表达式的引用则标记为“goto A”和“goto B”，分别。因此，神奇的是，不定性的本质直接从无穷 lambda 演算中显现出来，无需单独或重新提出。

这种查看事物的方式甚至适用于二进制文件级别。每个字节的每种解释（无论它是开始 0、1、2 或更多个字节的指令的操作码的一部分，还是作为数据结构的一部分）都可以被视为串联存在，因此二进制文件文件是一个更大的通用展开结构的卷起，其物理字节码表示与其自身广泛重叠。

因此，当微积分扩展到包含无限项时，命令式编程语言范式自动从纯 lambda 微积分本身中出现。控制流结构直接体现在无限表达式本身的结构中；因此不需要额外的 hack（如 Landin 或后来的后代，如 monad）——因为它已经存在了。

这种命令式和函数式范式的综合出现于 1980 年代末，通过 USENET，但尚未发布。其中一部分已经隐含在对像 Prolog-II 这样的语言的处理中（大约在同一时间），以及 Irene Guessarian LNCS 99“代数语义”中通过无限表达式对循环递归结构的更早的处理。

现在，我之前说过基于岩浆的公式可能会让你到达相同的地方，或者近似的地方。我相信存在某种通用表示定理，该定理断言基于无限的公式提供了纯句法表示，并且通过此从基于单子的表示因素产生的语义为“基于 monad 的语义”=“无限 lambda 演算”+“无限语言的语义”。

同样，我们可以将上面的“Q”表达式视为延续；因此，可能还存在一个连续语义的通用表示定理，它类似地将这个公式回滚到无穷 lambda 演算中。

在这一点上，我还没有提到非理性无限项（即拥有无限数量的不同子项并且没有有限最小滚动的无限项）——特别是与过程间控制流语义相关的。有理项足以解释循环和分支，从而为过程内控制流语义提供平台；但对于作为过程间控制流语义的基本核心元素的调用返回语义来说，情况就不那么重要了，如果您认为子程序直接表示为经过修饰、美化的宏。

对于无限术语语言，可能存在类似于乔姆斯基层次结构的东西；因此，类型 3 对应于有理项，类型 2 对应于“代数项”（那些可以汇总到“转到”引用和“宏”定义的有限集合中的项），类型 0 对应于“先验项”。对我来说，这也是一个未解决的悬而未决的问题。