函数式编程语言中的自动记忆 [英] Automatic memoizing in functional programming languages

问题描述

我一直认为 Haskell 会做某种自动智能记忆.例如，朴素的斐波那契实现

I always thought that Haskell would do some sort of automatic intelligent memoizing. E.g., the naive Fibonacci implementation

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

因此会很快.现在我读了 this 似乎我错了——Haskell 似乎没有自动记忆.还是我理解错了?

would be fast because of that. Now I read this and it seems I was wrong -- Haskell doesn't seem to do automatic memoization. Or do I understand something wrong?

是否有其他语言可以自动(即隐式，非显式)记忆?

Are there other languages which do automatic (i.e. implicit, not explicit) memoization?

实现记忆的常用方法有哪些?在我见过的所有示例实现中，它们都使用哈希图，但其大小没有任何限制.显然，这在实践中是行不通的，因为您需要某种限制.鉴于此，它变得更加复杂，因为当您达到极限时，您必须丢弃一些数据.这变得复杂了:限制应该是动态的吗，经常使用的函数应该比不常用的函数有更高的限制吗?当您达到极限时，您会丢弃什么条目?只是最近用过的吗?在这种情况下，您还需要另外对数据进行排序.您可以使用链接列表和哈希映射的某种组合来实现这一点.这是常见的方式吗?

What are common ways to implement memoization? In all sample implementations I have seen, they use a hashmap but there isn't any limit in its size. Obviously, this wouldn't work in practice because you need some sort of limit. And given that, it becomes more complicated because when you hit the limit, you have to throw some data away. And there it becomes complicated: Should the limit maybe be dynamically and often used functions should have a higher limit than less often used functions? And what entry do you throw away when you hit the limit? Just the latest used one? In that case, you need to have your data also sorted in addition. You could use some combination of a linked list and a hash map to achieve that. Is that the common way?

您能否链接(或参考)一些常见的现实世界实现?

Could you maybe link (or refer) to some common real-world implementations?

谢谢，阿尔伯特

我最感兴趣的是我描述的那个问题，即如何实现这样的限制.对任何解决此问题的论文的任何参考都非常好.

I am mostly interested in that problem I described, i.e. how to implement such a limit. Any references to any papers which address this would be very nice.

可以在here.

我不是要解决特定应用程序中的特定问题.我正在寻找记忆的通用解决方案，它可以全局应用于(纯功能)程序的所有功能(因此不实现内存限制的算法不是解决方案).当然，(可能)没有最佳/最佳解决方案.但这让我的问题不那么有趣.

I am not trying to solve a specific problem in a specific application. I am searching for general solutions for memoization which could be applied globally to all functions of a (pure functional) program (thus algorithms which don't implement a memory limit are not a solution). Of course there (probably) is no optimal/best solution. But this makes my question not less interesting.

为了尝试这样的解决方案，我考虑将其添加到 Haskell 中作为优化.我真的很想知道它的表现如何.

For trying out such solution, I thought about adding it to Haskell as an optimization. I really wonder how well that would perform.

我想知道是否有人已经这样做了.

And I wonder if someone has done that already.

推荐答案

Haskell 似乎没有自动记忆.还是我理解错了?

Haskell doesn't seem to do automatic memoization. Or do I understand something wrong?

不，Haskell 没有.但是，共享表达式只计算一次.在 Paul Johnson 给出的示例中，x 作为 thunk 存储在堆上.y 和 z 都可以引用 x 因为 x 在作用域内，并且它们引用相同的位置.一旦 x 必须被评估，它只会被评估一次，并且只会保留评估的结果.所以这并不是真正的记忆，而是实施的结果.

No, Haskell doesn't. However, shared expressions are calculated only once. In the example given by Paul Johnson x is stored on the heap as a thunk. Both y and z can refer to x as x is in scope, and they refer to the same location. Once x has to be evaluated it will be evaluated only once and only the result of the evaluation will be kept. So this is not really memoisation but it is a result of the implementation.

是否有其他语言可以自动(即隐式，非显式)记忆?

Are there other languages which do automatic (i.e. implicit, not explicit) memoization?

我已经看到装饰器 @memoized 出现在一些 Python 源代码中.您当然可以为它完全创建自己的装饰器/实现.完成 LRU 和您要使用的其他策略.

I've seen the decorator @memoized come along in some python source code. You could of course completely create your own decorator / implementation for it. Complete with LRU and other policies you want to use.

实现记忆的常用方法有哪些?

What are common ways to implement memoization?

没有真正的common 实现记忆的方法.对于类似 fib 的模式(只有一个参数，它是一个数字)，fib-example 中使用的记忆化可以设计一个通用的解决方案(哈希图一个)并且它会起作用，但它也可能不是您的特定问题的最佳选择.

There is no real common way to implement memoisation. For fib-like patterns (only one argument, which is a number) the memoisation as used in the fib-example One could devise a general solution (the hashmaps one) and it will work, but it might also be suboptimal for your specific problem.

使用记忆功能会产生副作用，因此您可能希望缓存位于 State monad 中.但是，一般来说，您希望算法尽可能纯净，因此如果它有递归，您就已经有点混乱了.这是因为您将递归调用该函数的记忆版本，但这需要在 State monad 中运行，所以现在您的整个函数必须在 State monad 中运行.这也会影响懒惰，但您可以尝试 懒惰状态 monad.

With memoisation you have side-effects, so you probably want the cache to live in the State monad. However, in general you want to keep your algorithms as pure as possible so if it has recursion, you are already getting in a bit of a mess. This is because you will call the memoised version of the function recursively, but that needs to run in the State monad, so now your whole function has to run in the State monad. This also effects laziness, but you could try the lazy state monad.

记住这一点:好的自动记忆是非常难以实现的.但是你可以很容易地走很长的路.自动记忆功能可能涉及程序转换，在固定点编写内容可能会有很长的路要走.

Keeping this in mind: good automatic memoisation is very difficult to achieve. But you can come a long way easily. Automatically memoising functions probably involves program transformation, where writing things in fix point could go a long way.

我最感兴趣的是我描述的那个问题，即如何实现这样的限制.对任何解决此问题的论文的任何参考都非常好.

I am mostly interested in that problem I described, i.e. how to implement such a limit. Any references to any papers which address this would be very nice.

一旦你有了记忆的基本机制，你就可以调整记忆表的查找和存储功能，以实现 LRU 或其他一些保持内存消耗小的机制.也许您可以从 这个 C++ 示例 中获得 LRU 的想法.

Once you have the basic mechanism of memoisation you could tweak the lookup and store functions for you memoising table to implement LRU or some other mechanism of keeping memory consumption small. Maybe you can get the idea for LRU from this C++ example.

这篇关于函数式编程语言中的自动记忆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！