Tuesday 27 January 2009

Clojure Forward Declarations

Whilst working on Eliza I found I had a couple of functions that were mutually recursive; this meant I couldn't compile them because one didn't have the declaration of the other.

The solution is declare e.g.

(declare my-odd? my-even?)
(defn my-even? [x]
(if (zero? x)
(my-odd? (dec x))))

(defn my-odd? [x]
(if (zero? x)
(my-even? (dec x))))

(Update after comment from Matt)

As pointed out, this doesn't actually work because the stack can blow:

user> (my-even? 1000000000) ==> stackoverflow!

Using trampoline can fix the issue if you rewrite it so that the tail calls are actually closures

(declare my-odd?)
(defn my-even? [x] (if (zero? x) true #(my-odd? (dec x))))
(defn my-odd? [x] (if (zero? x) false #(my-even? (dec x))))

user> (trampoline #(my-even? 100000000)) ==> true

The syntax #(my-even? 1000000000) creates an anonymous function of no arguments (a thunk to be evaluated later) e.g.

user> (apply #(+ 1 1) ) ==> 2


  1. I've never used mutual recursion in clojure, but Rich created the trampoline in order to support it. Read more about it here: http://groups.google.com/group/clojure/msg/3addf875319c5c10

  2. Thanks - I hadn't seen that!