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

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);
}

如果不使用memoization，那么很多子问题会重新计算很多次，复杂度很高。

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

Automated memoization: Many functional programming languages (e.g. Lisp) have built-in support for memoization.

Why not in imperative languages (e.g. 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);
}

在阅读本文之前，我什至不知道某些编程语言内置了对记忆的支持。

笔记中的说法是否属实？如果是，那么为什么命令式语言不支持它？

Answer 1

关于 "LISP" 的声明非常含糊，他们甚至没有提到 是哪个 LISP 方言或实现。 None 我熟悉的 LISP 方言会自动记忆，但 LISP 可以轻松编写包装函数，将任何现有函数转换为记忆函数。

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

Answer 2

支持memoization无非是先有class个功能

如果你想记住一个特定案例的Java版本，你可以明确地写它：创建一个散列table，检查现有值等。不幸的是，你不能轻易概括这是为了记住任何功能。具有 first-class 函数的语言使得编写函数和记忆它们几乎是正交问题。

基本情况很简单，但你必须考虑递归调用。在像 OCaml 这样的静态类型函数语言中，一个被记忆化的函数不能递归地调用自己，因为它会调用非记忆化的版本。然而，对现有函数的唯一更改是接受一个函数作为参数，例如命名为 self，只要您的函数想要递归，就应该调用它。通用记忆工具然后提供适当的功能。 this answer.

中提供了完整示例

Lisp 版本有两个功能，可以更直接地记忆现有函数。

您可以像操作任何其他值一样操作函数
您可以在运行时重新定义函数

例如，在 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 被一个新的函数取代，它引入了使用内部散列的必要代码-table。 F 中对 F 的递归调用现在调用包装函数，而不是原始函数（您甚至不需要重新编译 F）。唯一的潜在问题是原始 F 是否受到尾调用优化。您可能应该声明它 notinline 或使用 DEF-MEMOIZED-FUNCTION.

Answer 3

尽管我不确定是否有任何广泛使用的 Lisp 支持自动记忆，但我认为记忆在函数式语言中更常见的原因有两个，还有一个用于 Lisp 家族语言。

首先，人们用函数式语言编写函数：计算结果仅取决于参数，不会对环境产生副作用。任何不满足该要求的东西根本不适合记忆。而且，好吧，命令式语言只是那些不满足或可能不满足这些要求的语言，因为否则它们就不是命令式的！

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

(defvar *p* 1)

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

其次，函数式语言一般都想谈不可变数据结构。这意味着两件事：

记忆一个returns大型数据结构
构建非常大的数据结构的函数通常需要处理大量垃圾，因为它们不能改变临时结构。

(2) 略有争议：公认的观点是 GC 现在非常好，这不是问题，复制非常便宜，编译器可以变魔术等等。好吧，编写过此类函数的人会知道这只是部分正确：GC 好，复制便宜（但指针追逐大复制它们的结构通常对缓存非常不利），但这实际上还不够（而且编译器几乎从不做他们声称做的魔术）。因此，您要么无缘无故地使用非功能代码来作弊，要么就记住了。如果你记忆这个函数，那么你只构建所有的临时结构一次，一切都变得便宜（内存中除外，但记忆中的适当弱点可以解决这个问题）。

第三：如果你的语言不支持简单的元语言抽象，那么实现记忆化是一件非常痛苦的事情。或者换句话说：你需要 Lisp 风格的宏。

要记住一个函数，您至少需要做两件事：

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

虽然这样做有点残忍，因为它太容易了，但我会通过取笑 Python 来证明这一点。

您可能认为装饰器是您在 Python 中记忆函数所需要的。事实上，您可以使用装饰器编写记忆工具（我已经编写了很多）。这些甚至是某种工作，尽管他们这样做大多是偶然的。

首先，装饰器不能轻易地知道它所装饰的函数的任何信息。因此，您最终要么尝试基于函数所有参数的元组进行记忆，要么必须在装饰器中指定要记忆的参数，或者同样令人讨厌的事情。

其次，装饰器将它正在装饰的函数作为参数获取：它不会在其中四处闲逛。这实际上没问题，因为 Python，作为其 'no concepts invented after 1956' 政策的一部分，当然，不假设在 f 的定义内按词法调用 f（并且没有干预绑定）实际上是自我调用。但也许有一天它会，你所有的记忆现在都会崩溃。

总而言之：要稳健地记忆函数，您需要 Lisp 风格的宏。可能唯一具有这些功能的命令式语言是 Lisps。

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

Why functional programming language support automated memoization but not imperative languages?

lisp

java

theory

functional-programming

imperative-programming