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?

Solomon

The (Common) lisp version does not memoize. No lisps I know of are purely functional, but you can easily make a function that wraps your implementation in a memoization process, but it's not part of CL standard, but easy to implement and use. I think Clojure has memoize as a part of the lamguage, but not automatically. – Nitrometer

cs.princeton.edu/courses/archive/spr05/cos423/lectures/… – Intangible

The author is simply wrong. If that Lisp example is supposed to be ANSI Common Lisp, it does not memoize; it is functionally equivalent to the Java code. The author is also wrong by referring to Lisp without making it clear which Lisp and by claiming that Lisp is a functional language, which main stream dialects of Lisp are not; they are multi-paradigm languages with good support for (untyped) functional programming. – Jodoin

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.

Jainism

I don't see why not supporting tail recursion optimizations makes memoization useless. – Hooghly

It doesn't, but makes it much less useful because algorithms are written in the iterative idiom. – Jainism

@MarkoTopolnik tail recursion have little to do with memoization. In fact memoized general recursive versions does the same or better time complexity as iterative tail recursive versions. I use memoization in non tail recursive languages like JavaScript. – Nitrometer

@Nitrometer You can get away with that only as long as you carefully pick the functions where the recursion depth is small enough to fit the stack. – Jainism

@MarkoTopolnik A typical scenario where memoization is best is where you have a O(n^2) time complexity and cannot rewrite it like with the fibonacci sequence. Traversing a tree in Scheme only one of the two calls can be a tail call giving Scheme the same stack depth issue as a non tail recursive language. A perfectly balanced three would have a depth of log(n) so the tree must be huge in order to blow a stack or reasonable size. – Nitrometer

We can always find some problem which is a perfect match for memoization in any language, but that is not the point I'm going for. – Jainism

The presence of side effects or mutable objects in imperative languages like Java are obstacles for memoization, but that doesn’t preclude memoization for methods like in the question, which are side effect free and return an immutable value. But the presence of memoization would be a JVM implementation specific detail that a developer should not rely on. In Java, recursive algorithms are dangerous in general, because the number of recursions can be (and actually is) limited, but the actual maximum number of recursions is completely unspecified… – Lenity

@holger If there was any auto-memoization by the JVM, it would result in quite unpredictable resource management and would probably have some bad cases. Explicit memoization is always a choice, of course. – Jainism

@Marko Topolnik: A JVM knows the full picture regarding memory utilization and function usage. It could automatically drop the results of the least recent function evaluations when the memory is required for something else. But, of course, this aspect would emphasize that a developer must not rely on the presence of auto-memoization, as its presence depends on the available memory which is unpredictable at development time. Likewise, a JVM could be capable of transforming a particular recursive method into a non-recursive one, but a developer must not assume that it can (and will). – Lenity

@Lenity Yes, an OOME can certainly be prevented, but my point was that this would add unpredictability to the performance profile and, if it was automatic, the user would have no choice. Your second point is the long-standing feature request to add TCO to HotSpot. However, with TCO the point is even stronger that it must be first-class and not an implementation detail. Think of the stacktraces, for example. – Jainism

Unpredictability of the performance profile is the standard for managed code environments. Every added optimization may have such effect and there are already optimizations with such a dramatic effect. As shown here, the JIT compilation state can make a factor of six regarding maximum stack depth… – Lenity

@holger But with TCO, the stacktrace becomes completely different. It doesn't pass as an implementation detail. – Jainism

Well, if you collapse the stack trace of a recursive method into a counter holding the number of recursions, you are able to reconstruct a stack trace if you wish. That’s similar to what happens when inlining the recursive call, which happens, as the reduced stack space requirement proves. Besides that, JVMs are not required to maintain all stack trace entries or supporting stack traces at all. “Some virtual machines may, under some circumstances, omit one or more stack frames from the stack trace. …” – Lenity

@holger Often there is more than one tail-call site in the function. And come on, omitting stack frames? A lot of things are allowed by specification, yet are still considered bugs if they actually happen. – Jainism

Well, if you want TCO without compromises, you have to give up the idea of having complete stack traces. The fact that complete stack traces aren’t guaranteed by the specification, might help. Hey, I wished, the JVM would omit stack trace elements of recursive methods, especially on StackOverflowErrors, more than often… – Lenity

@holger My point is, that should be first class behavior and not an implementation detail that can vary between environments. It has always been treated as such in languages that have it. – Jainism

Sure. There is a significant difference between TCO being allowed by the spec or being mandated by the spec. We agree on that. – Lenity

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.

Intangible

The binding has to be used in the recursion. Often I use an internal function defined in labels to do the actual recursion and then you need to memoize that instead. – Nitrometer

@Nitrometer "The binding has to be used in the recursion": I am not sure I understand what you mean here, sorry. But w.r.t. the library, there is a memoized-labels version too. Of course, the way it is done in OCaml can be replicated in Lisp, that would work with labels. – Intangible

I meant if you don't actually do the recursion by calling F but with labels, then you cannot simply add memoization without touching the implementation in the manner you show in your answer. memoized-labels would need to be used inside the function so then the abstractions leaks a bit and you might need to modify third party code to get it memoized, but thats usually not a problem in the community. – Nitrometer

@Nitrometer Making statements about the inner labels of a function from the outside would be another form of leak, which would severely restrict the kind of optimizations that are currently possible, when all local definitions are guaranteed to be static. But I guess a language could define memoization and provide built-in support. – Intangible

Answer 3

Although I'm not sure any widely-used Lisps have supported automatic memoization, I think there are two reasons why memoization is more common in functional languages, and an additional one for Lisp-family languages.

First of all, people write functions in functional languages: computations whose result depends only on their arguments and which do not side-effect the environment. Anything which doesn't meet that requirement isn't amenable to memoization at all. And, well, imperative languages are just those languages in which those requirements are not, or may not be, met, because they would not be imperative otherwise!

Of course, even in merely functional-friendly languages like (most) Lisps you have to be careful: you probably should not memoize the following, for instance:

(defvar *p* 1)

(defun foo (n)
  (if (<= n 0)
      *p*
    (+ (foo (1- n)) (foo (- n *p*)))))

Secondly is that functional languages generally want to talk about immutable data structures. This means two things:

1. It is actually safe to memoize a function which returns a large data structure
2. Functions which build very large data structures often need to cons an enormous amount of garbage, because they can't mutate interim structures.

(2) is slightly controversial: the received wisdom is that GCs are now so good that it's not a problem, copying is very cheap, compilers can do magic and so on. Well, people who have written such functions will know that this is only partly true: GCs are good, copying is cheap (but pointer-chasing large structures to copy them is often very hostile to caches), but it's not actually enough (and compilers almost never do the magic they are claimed to do). So you either cheat by gratuitously resorting to non-functional code, or you memoize. If you memoize the function then you only build all the interim structures once, and everything becomes cheap (other than in memory, but suitable weakness in the memoization can handle that).

Thirdly: if your language does not support easy metalinguistic abstraction, it's a serious pain to implement memoization. Or to put it another way: you need Lisp-style macros.

To memoize a function you need to do at least two things:

1. You need to control which arguments are the keys for the memoization -- not all functions have just one argument, and not all functions with multiple arguments should be memoized on the first;
2. You need to intervene inside the function to disable any self-tail-call optimization, which will completely subvert memoization.

Although it's kind of cruel to do so because it's so easy, I will demonstrate this by poking fun at Python.

You might think that decorators are what you need to memoize functions in Python. And indeed, you can write memoizing tools using decorators (and I have written a bunch of them). And these even sort-of work, although they do so mostly by chance.

For a start, a decorator can't easily know anything about the function it is decorating. So you end up either trying to memoize based on a tuple of all the arguments to the function, or having to specify in the decorator which arguments to memoize on, or something equally grotty.

Secondly, the decorator gets the function it is decorating as an argument: it doesn't get to poke around inside it. That's actually OK, because Python, as part of its 'no concepts invented after 1956' policy, of course, does not assume that calls to f lexically within the definion of f (and with no intervening bindings) are in fact self-calls. But perhaps one day it will, and all your memoization will now break.

So in summary: to memoize functions robustly, you need Lisp-style macros. Probably the only imperative languages which have those are Lisps.

Parishioner

Genuine functions are referentially transparent, which makes them candidates for memoization. – Scabrous

@JoshuaTaylor Well, referential transparency is really part of what it means for a programming language to be functional. – Parishioner

indeed. The term hadn't appeared in this question or its answers yet, and I thought it might be helpful for readers and OP to have it as another term to search for. – Scabrous

@JoshuaTaylor Yes, sorry, I wasn't trying to be snarky: you're right that it's an important term! It just took me ages to realise that 'functional language' => 'referential transparency' but I think not the other way round: a language could have only pure functions but not have functions as first-class objects, and I think such a language would not really be functional in the sense it's normally meant. – Parishioner