为什么回忆录不是语言特征？

Question

我在想..。为什么我所知道的任何语言都不把回忆录作为一种语言特征来提供呢？

编辑：为了澄清，我的意思是语言提供一个关键字来指定给定的函数为可回忆录，而不是每个函数都自动“默认”回传，除非另有规定。例如，fortran提供的关键字纯用于指定特定函数。我猜编译器可以利用这些信息来回忆录调用，但是如果您声明一个带有副作用的函数，我将忽略会发生什么。

Answer 1

您希望从回忆录中获得的内容可能与编译器回忆录选项所提供的不一样。

您可能知道，只对最后10个计算出来的不同值进行回忆录是有益的，因为您知道如何使用该函数。

你可能知道，只有回忆录最后的2或3个值才有意义，因为你永远不会使用比这更久的值。(斐波纳契的顺序浮现在脑海中。)

您可能在某些运行中生成了很多值，而在其他运行中只生成了一些值。

你可能想“扔掉”一些回忆录的价值观，重新开始。(我用这种方式回忆录了一个随机数发生器，这样我就可以重放构成某种结构的随机数序列，而结构的其他一些参数已经改变了。)

回忆性作为一种优化，取决于对回忆录价值的追求，它比价值的再现要便宜得多。这又取决于输入请求的顺序。这对回忆录数据库有影响:它是否使用堆栈、所有可能的输入值数组(可能非常大)、桶哈希或b树？

回忆录编译器要么提供一个“一刀切”的回忆录，要么它必须提供许多可能的替代方案，以及控制替代方案的参数。在某种程度上，每个人都更容易要求用户提供自己的回忆录。

Answer 2

因为编译器必须发出语义正确的程序。除非是参照透明，否则不能在不改变程序语义的情况下记忆函数。在大多数编程语言中，并不是所有的函数都是引用透明的(纯函数式编程语言是一个例外)，所以您不能回忆所有的东西。但是，需要一种机制来检测引用透明度，这太难了。

Answer 3

在Haskell中，您定义的不带参数的(纯)函数的回忆录是自动的。Fibonacci的例子，Wiki实际上是我能想到的最简单的，可证明的例子。

Haskell可以这样做，因为您的纯函数被定义为每次生成相同的结果；当然，依赖副作用的一元函数不会被回溯。

我不知道上限是什么--很明显，它不会比可用的记忆记忆更多。我也不确定回忆录是在编译时发生(如果值可以在编译时确定)，还是总是在函数第一次调用时发生。