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

Question

This is a question I read on some lectures about dynamic programming I randomly found on the internet. (I am graduated and I know the basic of dynamic programming already)

In the section of explaining why memoization is needed, i.e.

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

If memoization is not used, then many subproblems will be re-calculated many time that makes the complexity very high.

---

Then on one page, the notes have a question without answer, which is exactly what I want to ask. Here I am using exact wordings and the examples it show:

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

Why not in imperative languages (e.g. Java)?

LISP example the note provides (which it claims it is efficient):

(defun F (n)
    (if
        (<= n 1)
        n
        (+ (F (- n 1)) (F (- n 2)))))

Java example it provides (which it claims it is exponential)

static int F(int n) {
  if (n <= 1) return n;
  else return F(n-1) + F(n-2);
}

---

Before reading this, I do not even know there is built-in support of memoization in some programming languages.

Is the claim in the notes true? If yes, then why imperative languages not supporting it?

Answer 1

The claims about "LISP" are very vague, they don't even mention which LISP dialect or implementation they mean. None of LISP dialects I'm familiar with do automatic memoization, but LISP makes it easy to write a wrapper function which transforms any existing function into a memoized one.

Fully automatic, unconditional memoization would be a very dangerous practice and would lead to out-of-memory errors. In imperative languages it would be even worse because return values are often mutable, therefore not reusable. Imperative languages don't usually support tail-recursion optimization, further reducing the applicability of memoization.

Answer 2

The support for memoization is nothing more than having first-class functions.

If you want to memoize the Java version for one specific case, you can write it explicitly: create a hashtable, check for existing values, etc. Unfortunately, you cannot easily generalize this in order to memoize any function. Languages with first-class functions make writing functions and memoizing them almost orthogonal problems.

The basic case is easy, but you have to take into account recursive calls. In statically typed functional languages like OCaml, a function that is memoized cannot just call itself recursively, because it would call the non-memoized version. However the only change to your existing function is to accept a function as an argument, named for example self, which should be called whenever you function wants to recurse. The generic memoization facility then provides the appropriate function. A full example of this is available in this answer.

The Lisp version has two features that makes memoizing an existing function even more straightforward.

1. You can manipulate functions like any other value
2. You can redefine functions at runtime

So for example, in Common Lisp, you define F:

(defun F (n)
  (if (<= n 1)
      n
      (+ (F (- n 1))
         (F (- n 2)))))

Then, you see that you need to memoize the function, so you load a library:

(ql:quickload :memoize) 

... and you memoize F:

(org.tfeb.hax.memoize:memoize-function 'F)

The facility accepts arguments to specify which input should be cached and which test function to use. Then, the function F is replaced by a fresh one, which introduces the necessary code to use an internal hash-table. Recursive calls to F inside F are now calling the wrapping function, not the original one (you don't even recompile F). The only potential problem is if the original F was subject to tail-call optimization. You should probably declare it notinline or use DEF-MEMOIZED-FUNCTION.