How do I memoize a recursive function in Lisp?

Question

I'm a Lisp beginner. I'm trying to memoize a recursive function for calculating the number of terms in a Collatz sequence (for problem 14 in Project Euler). My code as of yet is:

(defun collatz-steps (n)
  (if (= 1 n) 0
       (if (evenp n) 
           (1+ (collatz-steps (/ n 2)))
           (1+ (collatz-steps (1+ (* 3 n)))))))

(defun p14 ()
  (defvar m-collatz-steps (memoize #'collatz-steps))
  (let 
      ((maxsteps (funcall m-collatz-steps 2))
       (n 2)
       (steps))
    (loop for i from 1 to 1000000
          do 
          (setq steps (funcall m-collatz-steps i))
          (cond 
            ((> steps maxsteps) 
             (setq maxsteps steps)
             (setq n i))
            (t ())))
    n))


(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind 
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

The memoize function is the same as the one given in the On Lisp book.

This code doesn't actually give any speedup compared to the non-memoized version. I believe it's due to the recursive calls calling the non-memoized version of the function, which sort of defeats the purpose. In that case, what is the correct way to do the memoization here? Is there any way to have all calls to the original function call the memoized version itself, removing the need for the special m-collatz-steps symbol?

EDIT: Corrected the code to have

(defvar m-collatz-steps (memoize #'collatz-steps))

which is what I had in my code. Before the edit I had erroneously put:

(defvar collatz-steps (memoize #'collatz-steps))

Seeing that error gave me another idea, and I tried using this last defvar itself and changing the recursive calls to

       (1+ (funcall collatz-steps (/ n 2)))
       (1+ (funcall collatz-steps (1+ (* 3 n))))

This does seem to perform the memoization (speedup from about 60 seconds to 1.5 seconds), but requires changing the original function. Is there a cleaner solution which doesn't involve changing the original function?

Answer 1

Would something like this work?

(defun collatz-steps (n)
  (if (= 1 n) 0
       (if (evenp n) 
           (1+ (collatz-steps (/ n 2)))
           (1+ (collatz-steps (1+ (* 3 n)))))))

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind 
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

(defun collatz-steps (memoize #'collatz-steps))

(defun p14 ()
  (let 
      ((maxsteps (funcall collatz-steps 2))
       (n 2)
       (steps))
    (loop for i from 1 to 1000000
          do 
          (setq steps (funcall collatz-steps i))
          (cond 
            ((> steps maxsteps) 
             (setq maxsteps steps)
             (setq n i))
            (t ())))
    n))

I don't know the Lisp syntax, but you're redefining collatz-steps to be the memoized version of collatz-steps.

Also, do you need funcall in the body of p14?

Answer 2

something like this:

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

IOW: your original (non-memoized) function is anonymous, and you only give a name to the result of memoizing it.

Answer 3

I assume you're using Common-Lisp, which has separate namespaces for variable and function names. In order to memoize the function named by a symbol, you need to change its function binding, through the accessor `fdefinition':

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

(defun p14 ()
  (let ((mx 0) (my 0))
    (loop for x from 1 to 1000000
          for y = (collatz-steps x)
          when (< my y) do (setf my y mx x))
    mx))

Answer 4

Here is a memoize function that rebinds the symbol function:

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

You would then do something like this:

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

I'll leave it up to you to make an unmemoize-function.

Answer 5

Changing the "original" function is necessary, because, as you say, there's no other way for the recursive call(s) to be updated to call the memoized version.

Fortunately, the way lisp works is to find the function by name each time it needs to be called. This means that it is sufficient to replace the function binding with the memoized version of the function, so that recursive calls will automatically look up and reenter through the memoization.

huaiyuan's code shows the key step:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

This trick also works in Perl. In a language like C, however, a memoized version of a function must be coded separately.

Some lisp implementations provide a system called "advice", which provides a standardized structure for replacing functions with enhanced versions of themselves. In addition to functional upgrades like memoization, this can be extremely useful in debugging by inserting debug prints (or completely stopping and giving a continuable prompt) without modifying the original code.

Answer 6

A while ago I wrote a little memoization routine for Scheme that used a chain of closures to keep track of the memoized state:

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

This needs to be used like so:

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

I'm sure that this can be ported to your favorite lexically scoped Lisp flavor with ease.

Answer 7

I'd probably do something like:

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

It's not Nice and Functional, but, then, it's not much hassle and it does work. Downside is that you don't get a handy unmemoized version to test with and clearing the cache is bordering on "very difficult".

Answer 8

Note a few things:

(defun foo (bar)
   ... (foo 3) ...)

Above is a function that has a call to itself.

In Common Lisp the file compiler can assume that FOO does not change. It will NOT call an updated FOO later. If you change the function binding of FOO, then the call of the original function will still go to the old function.

So memoizing a self recursive function will NOT work in the general case. Especially not if you are using a good compiler.

You can work around it to go always through the symbol for example: (funcall 'foo 3)

(DEFVAR ...) is a top-level form. Don't use it inside functions. If you have declared a variable, set it with SETQ or SETF later.

For your problem, I'd just use a hash table to store the intermediate results.

Answer 9

This function is exactly the one Peter Norvig gives as an example of a function that seems like a good candidate for memoization, but which is not.

See figure 3 (the function 'Hailstone') of his original paper on memoization ("Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems").

So I'm guessing, even if you get the mechanics of memoization working, it won't really speed it up in this case.