为什么函数式编程语言支持自动记忆化而命令式语言不支持？

Question

这是我在网上偶然发现的一些关于动态规划的讲座中读到的问题。（我已经毕业并且已经了解了动态规划的基础知识）

在解释为什么需要记忆化的部分，也就是说：

// psuedo code 
int F[100000] = {0};
int fibonacci(int x){
    if(x <= 1) return x;
    if(F[x]>0) return F[x];
    return F[x] = fibonacci(x-1) + fibonacci(x-2);
}

如果不使用记忆化，那么许多子问题将被重复计算多次，这使得复杂度非常高。

---

然后在一页上，笔记中有一个没有答案的问题，这正是我想问的。这里我使用确切的措辞和它所展示的例子：

自动记忆化：许多函数式编程语言（例如 Lisp）具有内置的记忆化支持。

为什么命令式语言（例如 Java）没有？

LISP示例说明它是有效的：

(defun F (n)
    (if
        (<= n 1)
        n
        (+ (F (- n 1)) (F (- n 2)))))

Java示例提供了指数级的解决方案

static int F(int n) {
  if (n <= 1) return n;
  else return F(n-1) + F(n-2);
}

在阅读本文之前，我甚至不知道有些编程语言内置了备忘录支持。笔记中的说法是否正确？如果是，那么为什么命令式语言不支持它呢？

- shole

---

（通用）Lisp版本不支持记忆化。我所知道的Lisp都不是纯函数式的，但你可以很容易地编写一个函数，将你的实现包装在一个记忆化过程中，虽然这不是CL标准的一部分，但很容易实现和使用。我认为Clojure作为语言的一部分有“memoize”，但不是自动的。 - Sylwester

https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/06dynamic-programming.pdf - coredump

作者的观点是错误的。如果那个Lisp示例应该是ANSI Common Lisp，它就不会进行记忆化；它在功能上等同于Java代码。作者还犯了一个错误，即在没有明确指出是哪种Lisp的情况下提到Lisp，并声称Lisp是一种函数式语言，而主流的Lisp方言并不是这样；它们是支持（无类型）函数式编程的多范式语言。 - Kaz

Answer 1

关于“LISP”的声明非常模糊，它们甚至没有提到指的是哪个LISP方言或实现。我熟悉的LISP方言中没有一个会自动进行记忆化，但是LISP很容易编写一个包装器函数将任何现有函数转换为已记忆化的函数。

完全自动、无条件的记忆化将是一种非常危险的做法，并且会导致内存不足错误。在命令式语言中，情况会更糟，因为返回值通常是可变的，因此不能重复使用。命令式语言通常不支持尾递归优化，进一步降低了记忆化的适用性。

- Marko Topolnik

---

@MarkoTopolnik 尾递归与记忆化几乎没有关系。事实上，记忆化的一般递归版本在时间复杂度上与迭代的尾递归版本相同或更好。我在非尾递归语言（如JavaScript）中使用记忆化。 - Sylwester

@Sylwester 只有在仔细选择递归深度足够小以适合堆栈的函数时，您才能做到这一点。 - Marko Topolnik

@MarkoTopolnik 典型的记忆化最佳应用场景是当您具有O(n^2)时间复杂度且无法像斐波那契数列一样重写它时。在Scheme中遍历树时，只有两个调用中的一个可以是尾调用，这会给Scheme带来与非尾递归语言相同的堆栈深度问题。完全平衡的树将具有log(n)的深度，因此树必须非常大才能使堆栈溢出或达到合理大小。 - Sylwester

@Holger 是的，OOM异常肯定可以被预防，但我的观点是这会给性能特性增加不可预测性，如果是自动的，用户将没有选择权。您的第二个观点是长期存在的功能请求，即在HotSpot中添加TCO。然而，对于TCO来说，更加强调它必须是一流的，而不是实现细节。例如，请考虑堆栈跟踪。 - Marko Topolnik

如果你想要没有妥协的TCO，就必须放弃完整堆栈跟踪的想法。完整堆栈跟踪不被规范保证的事实可能会有所帮助。嘿，我希望JVM会省略递归方法的堆栈跟踪元素，特别是在StackOverflowError上，这种情况更加常见... - Holger

Answer 2

支持记忆化的功能不过是拥有一流函数而已。

如果您想为Java版本的某个特定情况进行记忆化，可以明确编写：创建哈希表、检查现有值等。不幸的是，您不能轻易地将其概括以便对任何函数进行记忆化。具有一流函数的语言使编写函数和进行记忆化成为几乎正交的问题。

基本情况很容易处理，但您必须考虑递归调用。在 OCaml 等静态类型的函数式语言中，记忆化的函数不能仅仅递归调用自身，因为这会调用非记忆化版本。然而，对您现有函数的唯一更改是接受一个名为 self 的函数作为参数，每当您的函数想要递归时就应该调用它。通用的记忆化功能会提供适当的函数。关于这点的完整示例可参见此答案。

Lisp 版本有两个特性使得记忆化现有函数变得更加简单。

1. 您可以像处理其他值一样处理函数
2. 您可以在运行时重新定义函数

例如，在 Common Lisp 中，您可以定义 F：

(defun F (n)
  (if (<= n 1)
      n
      (+ (F (- n 1))
         (F (- n 2)))))

然后，你发现需要使用记忆化函数，于是载入了一个库：

(ql:quickload :memoize) 

...然后你对F进行备忘录优化：

(org.tfeb.hax.memoize:memoize-function 'F)

该工具可接受参数来指定哪个输入应该被缓存以及使用哪个测试函数。然后，函数F将被替换为一个新的函数，该函数引入了必要的代码来使用内部哈希表。在F内递归调用F现在会调用包装函数，而不是原始函数（您甚至不需要重新编译F）。唯一可能存在的问题是原始函数F是否经过尾调用优化。您可能应该声明它为notinline或使用DEF-MEMOIZED-FUNCTION。

- coredump

---

绑定必须在递归中使用。通常我会使用在“标签”中定义的内部函数来执行实际的递归，然后需要对其进行记忆化处理。 - Sylwester

@Sylwester "绑定必须在递归中使用"：抱歉，我不确定我理解你的意思。但就库而言，也有memoized-labels版本。当然，在Lisp中可以复制OCaml的方式，这将与labels一起使用。 - coredump

我的意思是，如果你不是通过调用F来实际执行递归，而是使用labels，那么你不能简单地添加记忆化而不触及你在答案中展示的实现方式。memoized-labels需要在函数内部使用，因此抽象会有点泄漏，你可能需要修改第三方代码才能使其记忆化，但这通常不是社区中的问题。 - Sylwester

@Sylwester 从外部对函数的内部标签进行声明将是另一种泄漏形式，这将严重限制当前可能的优化类型，当所有本地定义都保证是静态时。但我猜测一种语言可以定义记忆化并提供内置支持。 - coredump

Answer 3

虽然我不确定任何广泛使用的Lisp是否支持自动记忆化，但我认为函数式语言中存在两个更常见的记忆化原因，并且Lisp系语言还有一个附加原因。

首先，在函数式语言中，人们编写函数：计算仅取决于它们的参数并且不会对环境产生副作用的函数。任何不符合此要求的内容都无法进行记忆化。而命令式语言就是那些不满足这些要求的语言，否则它们就不会是命令式语言！

当然，即使在像（大多数）Lisp这样的仅仅友好的函数式语言中，您也必须小心：例如，您可能不应该记忆以下内容：

(defvar *p* 1)

(defun foo (n)
  (if (<= n 0)
      *p*
    (+ (foo (1- n)) (foo (- n *p*)))))

其次，函数式编程通常希望讨论不可变数据结构。这意味着两件事：

1. 实际上，可以安全地记忆返回大型数据结构的函数。 2. 构建非常大的数据结构的函数通常需要连接大量垃圾，因为它们无法改变中间结构。

第二点有些争议：普遍认为GC已经很好了，复制很便宜，编译器可以做到神奇等等。但是，编写此类函数的人会知道，这只是部分正确的：GC确实很好，复制确实很便宜（但追踪指针以复制大型结构对缓存来说通常非常不友好），但这还不够（编译器几乎从不做它们声称要做的魔术）。所以你要么通过任意地使用非函数式代码来欺骗，要么记忆。如果你记忆该函数，那么你只需要一次构建所有中间结构，一切都变得便宜（除了内存之外，但是适当的记忆弱点可以处理它）。

第三：如果您的语言不支持易于元语言抽象，则实现记忆化将非常麻烦。或者换句话说：你需要Lisp风格的宏。

为了将函数记忆化，您至少需要做两件事:

1. 您需要控制哪些参数是记忆化的键 - 并非所有函数都只有一个参数，并且不应该在第一个参数上记忆化具有多个参数的所有函数;
2. 您需要在函数内部进行干预，以禁用任何自我尾调用优化，这将完全颠覆记忆化。

虽然这样做有点残酷，因为它很容易，但我会拿Python开玩笑来演示。

您可能认为装饰器是Python中记忆化函数所需的工具。实际上，您可以使用装饰器编写记忆化工具（我已经写了一堆）。这些工具甚至有点工作，尽管它们主要是偶然的。

首先，装饰器无法轻松地了解其正在装饰的函数。因此，您最终要么尝试根据函数的所有参数元组进行记忆化，要么在装饰器中指定要记忆化的参数，或者其他一些令人讨厌的事情。

其次，装饰器会将其装饰的函数作为参数传入：它无法在函数内部进行任何操作。这实际上是可以接受的，因为 Python 的“1956年后不发明新概念”政策并不假定在定义中对 f 的调用（且没有插入绑定）实际上是自己的调用。但也许有一天会改变，那么你所有的记忆化都将失效。

所以总之：要使函数记忆化稳健，你需要 Lisp 风格的宏。可能唯一具备这种功能的命令式语言就是 Lisp。

- user5920214

---

真正的函数是引用透明的，这使它们成为记忆化的候选对象。 - Joshua Taylor

@JoshuaTaylor 嗯，引用透明度确实是编程语言函数化的一部分。 - user5920214

确实。这个术语在这个问题或其答案中还没有出现过，我认为将其作为另一个可搜索的术语对于读者和OP可能会有帮助。 - Joshua Taylor

@JoshuaTaylor 是的，抱歉，我并不是在挖苦你：你说得对，这是一个重要的术语！只是我花了很长时间才意识到“函数式语言”=>“引用透明”，但我认为反过来不成立：一种语言可能只有纯函数，但没有将函数作为一等对象，我认为这样的语言实际上不符合通常所说的函数式。 - user5920214