How do I generate memoized recursive functions in Clojure?

Question

I'm trying to write a function that returns a memoized recursive function in Clojure, but I'm having trouble making the recursive function see its own memoized bindings. Is this because there is no var created? Also, why can't I use memoize on the local binding created with let?

This slightly unusual Fibonacci sequence maker that starts at a particular number is an example of what I wish I could do:

(defn make-fibo [y]   (memoize (fn fib [x] (if (< x 2)              y              (+ (fib (- x 1))                 (fib (- x 2)))))))  (let [f (make-fibo 1)]   (f 35)) ;; SLOW, not actually memoized 

Using with-local-vars seems like the right approach, but it doesn't work for me either. I guess I can't close over vars?

(defn make-fibo [y]   (with-local-vars [fib (fn [x] (if (< x 2)                                   y                                   (+ (@fib (- x 1))                                      (@fib (- x 2)))))]     (memoize fib)))  (let [f (make-fibo 1)]   (f 35)) ;; Var null/null is unbound!?!  

I could of course manually write a macro that creates a closed-over atom and manage the memoization myself, but I was hoping to do this without such hackery.

Answer 1

There is an interesting way to do it that does rely neither on rebinding nor the behavior of def. The main trick is to go around the limitations of recursion by passing a function as an argument to itself:

(defn make-fibo [y]   (let     [fib       (fn [mem-fib x]          (let [fib (fn [a] (mem-fib mem-fib a))]            (if (<= x 2)              y              (+ (fib (- x 1)) (fib (- x 2))))))      mem-fib (memoize fib)]       (partial mem-fib mem-fib))) 

Then:

> ((make-fibo 1) 50) 12586269025 

What happens here:

• The fib recursive function got a new argument mem-fib. This will be the memoized version of fib itself, once it gets defined.
• The fib body is wrapped in a let form that redefines calls to fib so that they pass the mem-fib down to next levels of recursion.
• mem-fib is defined as memoized fib
• ... and will be passed by partial as the first argument to itself to start the above mechanism.

This trick is similar to the one used by the Y combinator to calculate function's fix point in absence of a built-in recursion mechanism.

Given that def "sees" the symbol being defined, there is little practical reason to go this way, except maybe for creating anonymous in-place recursive memoized functions.

Answer 2

This seems to work:

(defn make-fibo [y]   (with-local-vars       [fib (memoize             (fn [x]               (if (< x 2)                 y                 (+ (fib (- x 2)) (fib (dec x))))))]     (.bindRoot fib @fib)     @fib)) 

with-local-vars only provides thread-local bindings for the newly created Vars, which are popped once execution leaves the with-local-vars form; hence the need for .bindRoot.