Is there a simpler way to memoize a recursive let fn?

Question

Let's say you have a recursive function defined in a let block:

(let [fib (fn fib [n]
            (if (< n 2)
              n
              (+ (fib (- n 1))
                 (fib (- n 2)))))]
  (fib 42))

This can be mechanically transformed to utilize memoize:

1. Wrap the fn form in a call to memoize.
2. Move the function name in as the 1st argument.
3. Pass the function into itself wherever it is called.
4. Rebind the function symbol to do the same using partial.

Transforming the above code leads to:

(let [fib (memoize
            (fn [fib n]
              (if (< n 2)
                n
                (+ (fib fib (- n 1))
                   (fib fib (- n 2))))))
      fib (partial fib fib)]
  (fib 42))

This works, but feels overly complicated. The question is: Is there a simpler way?

Answer 1

I take risks in answering since I am not a scholar but I don't think so. You pretty much did the standard thing which in fine is a partial application of memoization through a fixed point combinator.

You could try to fiddle with macros though (for simple cases it could be easy, syntax-quote would do name resolution for you and you could operate on that). I'll try once I get home.

edit: went back home and tried out stuff, this seems to be ok-ish for simple cases

(defmacro memoize-rec [form]
  (let [[fn* fname params & body] form
        params-with-fname (vec (cons fname params))]
    `(let [f# (memoize (fn ~params-with-fname
                         (let [~fname (partial ~fname ~fname)] ~@body)))]
       (partial f# f#))))

;; (clojure.pprint/pprint (macroexpand '(memoize-rec (fn f [x] (str (f x))))))
((memoize-rec (fn fib [n]
                (if (< n 2)
                  n
                  (+ (fib (- n 1))
                     (fib (- n 2)))))) 75) ;; instant

((fn fib [n]
                (if (< n 2)
                  n
                  (+ (fib (- n 1))
                     (fib (- n 2))))) 75) ;; slooooooow

simpler than what i thought!

Answer 2

I'm not sure this is "simpler" per se, but I thought I'd share an approach I took to re-implement letfn for a CPS transformer I wrote.

The key is to introduce the variables, but delay assigning them values until they are all in scope. Basically, what you would like to write is:

(let [f nil] (set! f (memoize (fn [] <body-of-f>))) (f))

Of course this doesn't work as is, because let bindings are immutable in Clojure. We can get around that, though, by using a reference type — for example, a promise:

(let [f (promise)] (deliver! f (memoize (fn [] <body-of-f>))) (@f))

But this still falls short, because we must replace every instance of f in <body-of-f> with (deref f). But we can solve this by introducing another function that invokes the function stored in the promise. So the entire solution might look like this:

(let [f* (promise)] (letfn [(f [] (@f*))] (deliver f* (memoize (fn [] <body-of-f>))) (f)))

If you have a set of mutually-recursive functions:

(let [f* (promise) g* (promise)] (letfn [(f [] (@f*)) (g [] (@g*))] (deliver f* (memoize (fn [] (g)))) (deliver g* (memoize (fn [] (f)))) (f)))

Obviously that's a lot of boiler-plate. But it's pretty trivial to construct a macro that gives you letfn-style syntax.

Answer 3

Yes, there is a simpler way. It is not a functional transformation, but builds on the impurity allowed in clojure.

(defn fib [n]
  (if (< n 2)
    n
    (+ (#'fib (- n 1))
       (#'fib (- n 2)))))

(def fib (memoize fib))

First step defines fib in almost the normal way, but recursive calls are made using whatever the var fib contains. Then fib is redefined, becoming the memoized version of its old self.