Automatic memoizing in functional programming languages

Question

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)

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?

Thanks, Albert

---

Edit: 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.

---

Edit: Some own thoughts with a sample implementation (which has a limit) can be found here.

---

Edit: 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.

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.

Answer 1

I said in a comment that your requirements sounded like garbage collection. I thought this because you are interested in managing a limited pool of memory, purging it once in a while so that it doesn't go over.

Now that I think about it, it's more like a virtual memory page replacement algorithm. You can read that Wikipedia page for various approaches used to solve that kind of problem, such as "not recently used", "aging", "clock", "second chance", etc.

However, memoization isn't often done by restricting the results retained; the required mutation for the above-mentioned algorithms is generally un-haskellish. Don't let that discourage you, though. You have interesting ideas that could be valuable additions to the exploration of memoization possibilities in Haskell performed thusfar.

Sometimes a particular memoization problem lends itself well to limited memory. For example, aligning two gene sequences can be done with Dynamic Programming (see Wikipedia's Dynamic Programming # Sequence alignment) with a 2-dimensional memoization table. But since the DP solution for a given cell only depends on the results from the preceding row, you can start from the bottom and discard rows that are more than 1 away from the current row. Fibonacci numbers are the same: you only need the previous two numbers in the sequence in order to compute the next. You can discard anything earlier if all you are interested in is the n^th number.

Most memoizations are for the sake of speeding up recursive algorithms where there are shared subproblems. Many such problems do not have an easy way of sequencing the evaluations in order to throw away the results you no longer need. At that point, you're just guessing, using heuristics (like frequency of use) to determine who gets how much access to the limited resource.

Answer 2

No, Haskell does not do automatic memoisation of functions. What it does is store values, so if you have

x = somethingVeryLong

and somewhere else in the same scope you have

y = f x
z = g x

then x will only be computed once.

This package shows how memoised values can be stored using a variety of keys and look-up tables. The memoising is typically used within a single invocation of a larger function, so that the memoised values don't hang around forever (which as you say would be a problem). If you want a memoiser that also forgets old values using LRU or something then I think you probably need to put it in a state monad or something; you can't get Haskell to behave like that using the conventional memoising approach.

Answer 3

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

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?

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?

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.

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.

Edit: 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.

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.

Answer 4

For example of implementing automatic memoization, you may look at the Factor programming language and its Memoization vocabulary. For example, simple Fibonacci number generator:

: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

may be memoized by replacing ":" word with "MEMO:"

MEMO: fib ( n -- n )
    dup 1 > [
        [ 1 - fib ]
        [ 2 - fib ]
        bi +
    ] when ;

In that case, fib inputs and corresponding outputs will be transparently stored within in-memory dictionary.

Factor language syntax may be confusing :). I recommend you to watch video presentation from Google Tech Talks about Factor to understand, how is it possible to implement memoization in that way.

Answer 5

No exactly an answer, but this page: http://www.haskell.org/haskellwiki/Memoization offers ideas about Memoization in Haskell and also shows a list-based implementation of the Fibonacci sequence that may be of interest.

Answer 6

In Maple you can use the option remember

F := proc(n) option remember;
    if n<2 then n else F(n-1)+F(n-2)
    end if
end proc;