How to: an anonymous recursive function

[Tim Robinson]

So I am reading On Lisp + some blogs while learning Clojure (I know,
scary stuff :)

Anyway, I've been playing around to see if I can get an anonymous
recursive function to work, but alas I am still a n00b and not even
sure what Clojure's approach to this would be.

How would I do this in Clojure?:

My first attempt:

((fn [x]
(if (= x 0)
1
(* 2 (recur (dec z))))) 5)

Then my second:

((fn [x]
(let [z (if (= x 0)
1
(* 2 x))]
(recur (dec z)))) 5)

Ideally one could do:

((recursive-fn #( if (= % 0) 1 (* 2 %)) (recur it)) 5)


Obviously none work, and I believe I understand why. I just don't
understand how to actually do this or if for some reason Clojure
avoids this for some reason.

I am not actually trying to accomplish a specific task, so the example
was made to be simple not meaningful. I'm just playing around to learn
recursive functions and Clojure style.

Thanks,
Tim

[Mike Meyer]

On Tue, 29 Jun 2010 22:44:58 -0700 (PDT)
Tim Robinson <tim.bl...@gmail.com> wrote:

> So I am reading On Lisp + some blogs while learning Clojure (I know,
> scary stuff :)
>
> Anyway, I've been playing around to see if I can get an anonymous
> recursive function to work, but alas I am still a n00b and not even
> sure what Clojure's approach to this would be.
> How would I do this in Clojure?:

IIUC based on examples involving label and letrec, you want a
recursive function whose name isn't visible outside of some restricted
scope. letfn is analogous to those, and that would look like:

(letfn [(anon [x]

(if (= x 0)
1

(* 2 (anon (dec x)))))]
(anon 5))

> My first attempt:
>
> ((fn [x]
> (if (= x 0)
> 1
> (* 2 (recur (dec z))))) 5)
>
> Then my second:
>
> ((fn [x]
> (let [z (if (= x 0)
> 1
> (* 2 x))]
> (recur (dec z)))) 5)
>
> Ideally one could do:
>
> ((recursive-fn #( if (= % 0) 1 (* 2 %)) (recur it)) 5)
>
>
> Obviously none work, and I believe I understand why. I just don't
> understand how to actually do this or if for some reason Clojure
> avoids this for some reason.

On the other hand, maybe I misunderstood what you're trying to do, in
which case an example of what you mean by "anonymous recursive
function" in another language (CL or Scheme by preference) would help.

<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more information.

O< ascii ribbon campaign - stop html mail - www.asciiribbon.org

[Nicolas Oury]

user=> (fn plouf [] (plouf))

#<user$eval263$plouf__264 user$eval263$plouf__264@197ebe66>

user=> ((fn plouf [] (plouf)))

java.lang.StackOverflowError (NO_SOURCE_FILE:0)

(plouf/plaf is approximate french for foo/bar)

[Shawn Hoover]

Hi Tim,

You're running into an error that you can only recur from the tail position? That's because you're trying to use the result of recur to do further computation. Clojure doesn't allow this with recur, because recur is more of a loop or goto construct behind the scenes. If you really want to run your algorithm that way you just have to give the fn a name and then call the name.

This should work:

((fn my-fn [x]

  (if (= x 0)
      1

      (* 2 (my-fn (dec x))))) 5)

That accomplishes the question as asked, but you may also want to look into calling reduce as a different approach to the problem.

[Dominic Cooney]

If you name the Y combinator, then you can write recursive anonymous functions:

<http://rosettacode.org/wiki/Y_combinator#Clojure>

You can't use Clojure's recur as written because it isn't in tail
position--the result of the function isn't just the value of the recur
expression (in the first instance it is (* 2 (recur ...)) however I
note that z is free in that expression, which looks suspicious.

If your goal is to define a function that computes 2^n with
tail-recursion, then consider threading an "accumulator" parameter
through the recursive function; something like this:

((fun [acc x]
(if (= x 0)
acc
(recur (* 2 acc) (dec x))) 1 5)

Of course, you might consider a helper wrapper function that supplies
the 1 "default" accumulator.

Many functional languages optimize tail calls to jmp instructions;
that's hard to do efficiently in general on the JVM because it doesn't
support tail calls. I expect Clojure has designed recur to work the
way it does because some algorithms depend on the tail call
optimization, but the restrictions of recur make it possible to
compile efficiently as a jmp. So it's a nice compromise.

<http://clojure.org/special_forms#Special Forms--(recur exprs*)>

HTH,

Dominic

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[Tim Robinson]

Thanks for all the replies. Sorry if my responses are delayed. I'm
still on newb moderation mode, so I find my response can take 2 - 10
hours to be published.

> note that z is free in that expression, which looks suspicious.

yup, it was supposed to be x. It was a copy paste error. I normally
would evaluate the function, but in this case I was expecting errors.

As for acc or other options, I was hoping to create a recursive fn
that could generically accept an anonymous function as an argument,
which was what I was
thinking.

Using a form like:

((recursive-fn #(do-stuff (self (dec %))) (recur self)) 5)

(obviously not the way - just the notion)

kind of thing.

When I am home tonight I can play aorund with the examples provided.

Thanks,
Tim

On Jun 30, 8:59 am, Dominic Cooney <dominic.coo...@gmail.com> wrote:
> If you name the Y combinator, then you can write recursive anonymous functions:
>
> <http://rosettacode.org/wiki/Y_combinator#Clojure>
>
> You can't use Clojure's recur as written because it isn't in tail
> position--the result of the function isn't just the value of the recur
> expression (in the first instance it is (* 2 (recur ...)) however I
> note that z is free in that expression, which looks suspicious.
>
> If your goal is to define a function that computes 2^n with
> tail-recursion, then consider threading an "accumulator" parameter
> through the recursive function; something like this:
>
> ((fun [acc x]
>     (if (= x 0)
>       acc
>       (recur (* 2 acc) (dec x))) 1 5)
>
> Of course, you might consider a helper wrapper function that supplies
> the 1 "default" accumulator.
>
> Many functional languages optimize tail calls to jmp instructions;
> that's hard to do efficiently in general on the JVM because it doesn't
> support tail calls. I expect Clojure has designed recur to work the
> way it does because some algorithms depend on the tail call
> optimization, but the restrictions of recur make it possible to
> compile efficiently as a jmp. So it's a nice compromise.
>

> <http://clojure.org/special_forms#SpecialForms--(recur exprs*)>
>
> HTH,
>
> Dominic

[Tim Robinson]

Hi folks,
I found some time this morning to look at this:

Mikes Letfn example worked out best for me:

>
(defmacro anaphoric-recur [parm-binds parms & body]
"An anaphoric recursive function that takes a vector of blind
bindable vars, parameters and a function that can handle the
bindable vars. 'self' is used to call the function recursively."
`(letfn [(~'self ~parm-binds
(do ~@body))]
(~'self ~parms)))

> (anaphoric-recur [x] 5 (if (= x 0) 1 (* 2 (self (dec x)))))
32

To answer Mike on CL or scheme?,
This is roughly equivalent to the arc 'afn' function (a scheme
variation).

Thanks everyone.
Tim

[Tim Robinson]

and now corrected!

(defmacro anaphoric-recur [parm-binds expr & parms]

"An anaphoric recursive function that takes a vector of blind

bindable vars, an expression that can handle the bindable vars.
and the parameters. 'self' is used to call the function

recursively."
`(letfn [(~'self ~parm-binds

(do ~expr))]
(~'self ~@parms)))

> (anaphoric-recur [x] (if (= x 0) 1 (* 2 (self (dec x)))) 5)
32

On Jun 30, 2:13 pm, Tim Robinson <tim.blacks...@gmail.com> wrote:

[Mike Meyer]

On Thu, 1 Jul 2010 12:50:00 -0700 (PDT)
Tim Robinson <tim.bl...@gmail.com> wrote:

> and now corrected!
>
> (defmacro anaphoric-recur [parm-binds expr & parms]
> "An anaphoric recursive function that takes a vector of blind
> bindable vars, an expression that can handle the bindable vars.
> and the parameters. 'self' is used to call the function
> recursively."
> `(letfn [(~'self ~parm-binds
> (do ~expr))]
> (~'self ~@parms)))
>
> > (anaphoric-recur [x] (if (= x 0) 1 (* 2 (self (dec x)))) 5)
> 32

Cool. I'd worry about using ~' to capture variables in a macro, except
rich hickey said that's intentional in
http://markmail.org/message/d6cubdwwxgjq4po6.