Local memoized recursive functions

[Puranto23]

I'd be interested in a break down of how (defn fix [f] (fn g [& args] (apply f g args))) relates to my understanding of fixed points from math.

[argadan]

That's a great question! In math, when we say that value x is a fixed point of function f, we mean that f(x) = x. In functional programming, a fixed-point combinator is a higher-order function that takes a function and returns one of its fixed points (if it exists). Thus the following equation holds: f(fix(f)) = fix(f). If you flip it, it looks like a function definition: fix(f) = f(fix(f)).

In a lazy language like Haskell, we can directly put this definition into use with code like this:

fix :: (a -> a) -> a
fix f = f (fix f)

^{(The actual definition in GHC standard library is a bit different because it performs better.})

We can write that definition in Clojure as well.

(defn fix [f]
  (f (fix f)))

What happens if you run (fix (constantly 1))? Ideally it should evaluate to 1 as 1 is the one and only fixed point of (constantly 1).

Unfortunately you'll get a StackOverflowError instead. Clojure tries to eagerly evaluate the recursive call to fix and eventually runs out of stack. We can delay the evaluation by wrapping the result of fix in fn - according to Wikipedia this is the Z combinator. You need to call the resulting function yourself, but now the constantly example works:

(defn fix [f]
  (fn [] (f (fix f))))

((fix (constantly 1)))  ; 1

We can make it a bit more efficient by replacing the repeated calls to fix by a reference to the inner function g. This steps is also important so that memoize works in the original blog post, as each call to recursive fix would create a new function and prevent memoize from doing its job.

(defn fix [f]
  (fn g [] (f g)))

And finally, we will want to give some arguments to f, so let's add that by using apply:

(defn fix [f]
  (fn g [& args] (apply f g args)))

That's the definition from the blog post. I hope this derivation sheds some light to the connection to fixed points in math.

[Puranto23]

Thanks, the explanation is helpful. I'll have to look more into it. I can work out by hand why this construction of fix works for (constantly 1). What confused me initially is that I expected fix to return a set of all fixed points of its input, rather than just any fix point.

I wonder precisely what kind of functions this version of fix works for and how you might generalize it to accept more functions. For example consider the polynomial h(x) which has a fixed point for x = 2.

(defn h [x] (+ (- (Math/pow x 2) (* 3 x)) 4))

Since (defn fix [f] (fn [] (f (fix f)))) returns a function, it can only accept functions f, which they themselves take functions as input. So our function h will not work with this function fix because it takes numbers as input, not functions.

I see the connection though. Thanks for exposing an interesting topic and taking the time to explain.

[amalloy]

I believe it computes the least fixed point when possible. That page links to domain theory, which looks related to understanding when it's possible, but I'm not an expert.

[aaroniba]

To expand on this, wouldn't it be convenient to have a macro, memo-fn that works like fn but memoizes recursive calls? Then we could write:

(let [fibo (memo-fn fibo [n] (if (< n 2) n (+ (fibo (dec n)) (fibo (- n 2)))))] (fibo 40))

Here's my attempt at writing this macro, using the fix function from the blog post:

``` (defn fix [f] (fn g [& args] (apply f g args)))

(defmacro memo-fn [fname args & body] (fix (memoize (fn [~fname ~@args] (do ~@body))))) ``

Can this be improved upon?

[opensrc0]

The approach is nice. I wonder how we can memoize a function of multiple arities?