Mutual Recursion

Discussion on implementing mutual recursion

Note: Potentially deprecated, see implementation of ->recursive-simple-multi-fn

Points to cover

• calling the plural-fn from the implementations
• want to retain extensibility

Why is this an issue?

A common use case of plural-fns is to walk a nested data structure. One implementation is to have the plural-fn dispatch on the type and on collection types, the method will iterate through the values, and call out to the plural-fn each time. This is one of the forms of mutual recursion. Since dj.plurality does not use vars, it does not on its own provide a way to call the plural-fn.

In detail, let's look at the following code:

(defn ->plural-fn [implementations]
 (fn inaccessible [x]
   (pick-imp implementations x)))

(->plural-fn {:a (fn ...) :b (fn ...)})

Note that the fns in the map cannot access the plural-fn. Normally, defmulti acts as a forward declaration. So we could imitate this in a local way using local vars.

(let [pfn (clojure.lang.Var/create)]
 (.bindRoot pfn (->plural-fn {:a (fn ... (pfn ...)) :b (fn ... (pfn ...))}))
 @pfn)

Note: I've written a macro that acts like let but does the above pattern. It's useful for any mutual recursion situations and is still as immutable as possible.

Other possibilities

• Create your own plural-fn generator which accepts a method generator instead of the methods directly.

(defn ->plural-fn [implementation-fn]
 (fn plural-fn [x]
   (let [implementations (implementation-fn plural-fn)]
     ...)

(->plural-fn (fn [pfn] {:a (fn ... (pfn ...)) :b (fn ... (pfn ...))}))

This requires generating a closure at each plural-fn invocation though... but we do eliminate the usage of vars.

Dynamic extensibility

Sometimes we want to modify the plural-fn as we walk through the data structure.

We can use fn-generators and call them.

(defn walker [option]
 (->plural-fn {:a (fn [...] ... ((walker new-option) ...))}))

Downside is we need to create a closure on the extension points.

The most flexible method is to use continuations where you explicitly pass the fn to call. The downside to this is we add another argument to pass and the dynamic behavior might affect JIT optimizations.

(let [pfn (->plural-fn {:a (fn [args pfn'] ... (if ... (pfn' ...) (new-pfn ...))})]
 (pfn ... pfn))