为什么memoization不是语言功能？

Question

我想知道...为什么我所知道的任何语言本身都没有提供备忘录作为语言功能？

编辑:澄清一下,我的意思是该语言提供了一个关键字来指定一个给定的函数为memoizable,而不是每个函数都被"默认"自动记忆,除非另有说明.例如,fortran提供关键字PURE以指定特定的功能.我想编译器可以利用这些信息来记忆调用,但是如果你声明PURE是一个带副作用的函数,我会忽略会发生什么.

Answer 1

您想要的记忆可能与编译器记忆选项提供的内容不同.

您可能知道记住最后10个左右计算的不同值是有利可图的,因为您知道如何使用该函数.

您可能知道记住最后2或3个值是有意义的,因为您永远不会使用早于此值的值.(斐波纳契的序列浮现在脑海中.)

您可能会在某些运行中生成大量值,而在其他运行中只生成少量值.

你可能想要"扔掉"一些记忆值并重新开始.(我用这种方式记忆了一个随机数生成器,所以我可以重放构建某种结构的随机数序列,而结构的其他一些参数也已经改变了.)

作为优化的记忆取决于搜索记忆值比重新计算值便宜得多.这又取决于输入请求的顺序.这对memoization数据库有影响:它是使用堆栈,所有可能输入值(可能非常大)的数组,桶哈希还是b树？

memoizing编译器必须提供"一刀切"的memoization,或者它必须提供许多可能的替代方案,以及控制替代方案的参数.在某些时候,每个人都更容易要求用户提供自己的记忆.

Answer 2

因为编译器必须发出语义正确的程序.除非它是引用透明的,否则不能在不改变程序语义的情况下记忆函数.在大多数编程语言中,并非所有函数都是引用透明的(纯函数式编程语言是例外),因此您无法记住所有内容.但是,需要一种机制来检测参考透明度,这太难了.

Answer 3

Clojure有一个memoize函数(http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize):

memoize
function

Usage: (memoize f)

Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.

Answer 4

在Haskell中,对于您定义的不带参数的(纯)函数,memoization是自动的.而Wiki中的Fibonacci示例实际上是关于我能够想到的最简单的可证明示例.

Haskell可以这样做,因为你的纯函数被定义为每次产生相同的结果; 当然,依赖于副作用的monadic函数将不会被记忆.

我不确定上限是什么 - 显然,它不会记忆超过可用内存.而且我也不确定是否在编译时发生了memoization(如果值可以在编译时确定),或者它是否总是在第一次调用函数时发生.

Answer 5

因为当它可以很容易地用语言本身实现时,你不应该将某些东西作为语言特性来实现.记忆功能属于库,这正是大多数语言所使用的.

Answer 6

A)记忆化时空交易空间.我想这可能会变成一个相当不受约束的属性,从某种意义上说,数据程序或库必须存储的数量可能会非常快地消耗大部分内存.

对于几种语言,memoization易于实现,并且易于根据给定的要求进行自定义.

例如,在大型文本体上进行一些自然语言处理,您不希望一遍又一遍地计算文本的基本属性(字数,频率,共现,......).在这种情况下,与内存缓存相比,与对象序列化相结合的memoization可能很有用,因为您可以在未更改的语料库上多次运行应用程序.

B)另一个方面:并非所有函数或方法都为同一给定输入产生相同的输出.无论如何,一些关于记忆的关键字或语法都是必要的,还有配置(内存限制,失效策略......)......