A letrec macro for Clojure with Y*
Anton Tayanovskyy
In this post I provide an inefficient but correct letrec macro for
Clojure. It is a straightforward translation of Oleg Kiselyov's Y*
combinator.
I find it very sad that Clojure has no letrec / recursive definitions.
So I thought - how about adding it at macro level? I have been
recently pointed out that this is not possible to do efficiently today
as letrec requires language support, which is yet missing. If you do
not care about efficiency, here is a way to do it, taken almost
verbatim from the "Many faces of the fixed-point combinator" [1]
First of all, what are we trying to achieve? That locally bound
functions will be able to call each other. To take the standard
example, let us define mutually recursive odd and even, like this:
(defn evens-up-to [k]
(letrec
((even (fn [x] (if (= x 0)
true
(odd (- x 1)))))
(odd (fn [x] (if (= x 0)
false
(even (- x 1))))))
(filter even (range k))))
So, this function gets a list of even numbers:
user=> (evens-up-to 10)
(0 2 4 6 8)
Also, the core requirement is to have this:
user=> odd
java.lang.Exception: Unable to resolve symbol: odd in this context
This means the letrec implementation has NOT modified the namespace in any way.
The official way most Scheme implementations do it, is through set!,
first establishing local bindings with *undefined* state, and then
setting them up. This is efficient and practical. However, there seems
to me there be no way to do this in pure Clojure as it stands today. I
would love to be proved wrong.
The other way stems from theoretical computer science and the
existence of strict fixed-point combinators. This is never anything
like efficient, but it is correct.
To save ourselves a lot of thinking, let us just copy Oleg's solution
(Scheme). To quote:
(define (Y* . fl)
(map (lambda (f) (f))
((lambda (x) (x x))
(lambda (p)
(map
(lambda (f)
(lambda ()
(apply f
(map
(lambda (ff)
(lambda y (apply (ff) y)))
(p p) ))))
fl)))))
This is straightforward in Clojure:
(defn Y* [& fl]
(map (fn [x] (x))
((fn [x] (x x))
(fn [p]
(map
(fn [f]
(fn []
(apply f
(map
(fn [ff]
(fn [& y]
(apply (ff) y)))
(p p)))))
fl)))))
Finally, one would need to actually write the letrec macro that
transforms a letrec form into an application of Y*. This is also
straightforward. For example (and mind, I'm not too experienced in
macros):
(defmacro letrec [heads & bodies]
(let [vars (map first heads),
defs (map rest heads),
lam (fn [x] `(fn [~@vars] ~@x)),
fixp (gensym)]
`(let [~fixp (Y* ~@(map lam defs))]
(apply ~(lam bodies) ~fixp))))
With this macro, the function evens-up-to given above expands
approximately as the following (G_2832 is an autogenerated unique
identifier from gensym).
(defn evens-up-to [k]
(let [G__2832 (Y* (fn [even odd]
(fn [x]
(if (= x 0)
true
(odd (- x 1)))))
(fn [even odd]
(fn [x]
(if (= x 0)
false
(even (- x 1))))))]
(apply
(fn [even odd]
(filter even (range k)))
G__2832)))
Y* finds the least mutual fixed point of its arguments, and that is
what they receive in even and odd as arguments. The recursive scoping
problem is solved.
The code is attached. Comments are welcome. I would also like to ask
for help making this code more Clojure-like, as I am new to the
language.
--A
[1] http://okmij.org/ftp/Computation/fixed-point-combinators.html
Meikel Brandmeyer
Am 22.07.2008 um 22:13 schrieb Anton Tayanovskyy:
> The code is attached. Comments are welcome. I would also like to ask
> for help making this code more Clojure-like, as I am new to the
> language.
The main problem with recursion is the stack overflow since the JVM
does not support tail call optimisation. Clojure provides the loop/recur
pair, which is not as general as recursion, but sufficient for most use
cases. And you get the check, whether recur is really in a tail
position.
For cosmetics, I would make the macro invocation more look like the
normal let:
(letrec [even ...
odd ...]
....)
Here is a version using loop and recur. Of course this is not as
educational as your solution, but it will not blow the stack.
(defn even? [k]
(multi-loop [k k]
:even (if (= k 0) true (recur :odd (- k 1)))
:odd (if (= k 0) false (recur :even (- k 1)))))
(defn evens-up-to [k]
(filter even? (range k)))
The macro is written pretty sloppily, but nevertheless: source attached.
Note that it uses case from fcase.clj in clojure-contrib.
Sincerely
Meikel
toyvo
> 1KDownload
>
>
>
> smime.p7s
> 5KDownload