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)
true
(my-odd? (dec x))))

(defn my-odd? [x]
(if (zero? x)
false
(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

2 comments:

  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

    ReplyDelete
  2. Thanks - I hadn't seen that!

    ReplyDelete