loop/recur being functional
I'm trying to “internalize” loop/recur as being a functional construct. I'm sure I'm not alone in this: I initially struggled with it, with my view unduely influenced by its implementation, especially when multiple loop heads are present. (It could be viewed as vulgar but necessary imperative optimization, playing tricks with the instruction pointer). Here is a line of reasoning that I'm interested in comments on: Take this example: (defn vrange [n] (loop [i 0 v []] (if ( i n) (recur (inc i) (conj v i)) v))) This can be rewritten applying a named inline function that closes over n: (defn vrange2 [n] ((fn loop-recur [i v] (if ( i n) (loop-recur (inc i) (conj v i)) v)) 0 [])) Then, this could be further transformed: (defn loop-recur [i v n] (if ( i n) (loop-recur (inc i) (conj v i)) v)) (defn vrange3 [n] loop-recur 0 [] n) which is clearly functional. I'm cool with this view. It with it, you see recur not so much as as not “jumping” to the nearest loop head, but instead as returning a value that results from ”calling” a function, where that function is kind-of defined by the loop head. I was wondering? Is the above transformation always possible, even given multiple loop heads? Is it always this simple, or are there corner cases that this naïve view misses? -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: loop/recur being functional
loop/recur is explicit tail recursion, and therefore will only work if the recur is in the tail position, i.e. the last form evaluated. For example, this function is tail recursive: (defn sum [coll result] (if (seq coll) (sum (rest coll) (+ result (first coll))) 0)) While this function is not: (defn sum [coll] (if (seq coll) (+ (first coll) (sum (rest coll))) 0)) In the latter case, the last function called is +, not sum. The reason this is important is that tail-recursive functions can be optimised. Normally recursive functions build up stack frames for each iteration. That's why recursive functions are vulnerable to stack overflow errors. But if the recursion is the last form in the function, there's no need to retain the stack frame, because the function is going to end immediately afterward. Most functional languages have this tail-call-optimisation, or TCO, that allows them to use recursion without blowing the stack. Clojure doesn't have automatic TCO, because it's limited by the JVM, so instead it has explicit TCO in the form of recur. You can actually use recur without the outer loop: (defn sum [coll result] (if (seq coll) (recur (rest coll) (+ result (first coll))) 0)) This will work the same as the first example, but has the advantage of not using up the stack. As you correctly assert, loop/recur is equivalent to a function: (defn sum [coll] (fn [acc] (if (seq coll) (sum (rest coll) (+ result (first coll))) 0)) 0)) Which is equivalent to: (defn sum [coll] (fn [acc] (if (seq coll) (recur (rest coll) (+ result (first coll))) 0)) 0)) Which is equivalent to: (defn sum [coll] (loop [acc 0] (if (seq coll) (recur (rest coll) (+ result (first coll))) 0 - James On 3 June 2014 22:00, Mike Fikes mikefi...@me.com wrote: I'm trying to “internalize” loop/recur as being a functional construct. I'm sure I'm not alone in this: I initially struggled with it, with my view unduely influenced by its implementation, especially when multiple loop heads are present. (It could be viewed as vulgar but necessary imperative optimization, playing tricks with the instruction pointer). Here is a line of reasoning that I'm interested in comments on: Take this example: (defn vrange [n] (loop [i 0 v []] (if ( i n) (recur (inc i) (conj v i)) v))) This can be rewritten applying a named inline function that closes over n: (defn vrange2 [n] ((fn loop-recur [i v] (if ( i n) (loop-recur (inc i) (conj v i)) v)) 0 [])) Then, this could be further transformed: (defn loop-recur [i v n] (if ( i n) (loop-recur (inc i) (conj v i)) v)) (defn vrange3 [n] loop-recur 0 [] n) which is clearly functional. I'm cool with this view. It with it, you see recur not so much as as not “jumping” to the nearest loop head, but instead as returning a value that results from ”calling” a function, where that function is kind-of defined by the loop head. I was wondering? Is the above transformation always possible, even given multiple loop heads? Is it always this simple, or are there corner cases that this naïve view misses? -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: loop/recur being functional
Have you considered the similarity between loop-recur and sequence operations? IE, tail-recursion turns the call stack into a sequence of states. The nice trick you can play in clojure is to reify this sequence as a lazy sequence. (take 5 ((fn this-fn [last] (cons (inc last) (lazy-seq (this-fn (inc last) 0)) It still looks recursive, but the values of the stack are spread across some java objects instead of disappearing (due to TCO if we had it or the explicit tail-recur that we do have). On Tue, Jun 3, 2014 at 5:00 PM, Mike Fikes mikefi...@me.com wrote: I'm trying to “internalize” loop/recur as being a functional construct. I'm sure I'm not alone in this: I initially struggled with it, with my view unduely influenced by its implementation, especially when multiple loop heads are present. (It could be viewed as vulgar but necessary imperative optimization, playing tricks with the instruction pointer). Here is a line of reasoning that I'm interested in comments on: Take this example: (defn vrange [n] (loop [i 0 v []] (if ( i n) (recur (inc i) (conj v i)) v))) This can be rewritten applying a named inline function that closes over n: (defn vrange2 [n] ((fn loop-recur [i v] (if ( i n) (loop-recur (inc i) (conj v i)) v)) 0 [])) Then, this could be further transformed: (defn loop-recur [i v n] (if ( i n) (loop-recur (inc i) (conj v i)) v)) (defn vrange3 [n] loop-recur 0 [] n) which is clearly functional. I'm cool with this view. It with it, you see recur not so much as as not “jumping” to the nearest loop head, but instead as returning a value that results from ”calling” a function, where that function is kind-of defined by the loop head. I was wondering? Is the above transformation always possible, even given multiple loop heads? Is it always this simple, or are there corner cases that this naïve view misses? -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: loop/recur being functional
Recommended: Programming Clojure, in which Stuart Halloway Aaron Bedra discuss these forms of recursion. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
