Lazyness and stackoverflow

Question

I wrote the following:

(fn r [f xs] (lazy-seq (if (empty? xs) '() (cons (f (first xs)) (rf (rest xs)))))) 

solve the problem 4clojure.com # 118: http://www.4clojure.com/problem/118

which asks to redefine the map without using the map, etc., and this solution passes the tests (I don’t know if it is right or not: it is very close to other solutions that say).

Since the problem was that it should have been lazy, I wrote the code above, “wrapping” my solution in lazy seq ... However, I do not understand how lazy-seq works.

I don’t understand what is “lazy” here, and how I could check it.

When I ask (type ...) , I get, not surprisingly, clojure.lang.LazySeq, but I don’t know what is the difference between this and what I get if I just remove lazy-seq "wrapping".

Now, of course, if I remove lazy-seq, I get stackoverflow trying to execute this:

 (= [(int 1e6) (int (inc 1e6))] (->> (... inc (range)) (drop (dec 1e6)) (take 2))) 

Otherwise (i.e.: if I allow lazy-seq-packaging in place), it works fine.

Therefore, I decided to try to somehow "debug" / track what is happening in order to try to understand how it all works. I took the following macro (which I found on SO IIRC):

 (defmacro dbg [x] `(let [x# ~x] (println "dbg: " '~x "=" x#) x#)) 

And wrapped up the working version inside the dbg macro and tried to execute it again. And now kaboom: the version that worked fine now also calls stackoverflow.

Now I'm not sure: maybe this is an undesirable effect of a macro that somehow forces us to analyze things that would not be evaluated otherwise?

It would be great if someone could explain, using this simple function and simple test, how laziness works here, what exactly is called when, etc.

Answer 1

All magic is in clojure.lang.LazySeq java class. Which themselves implement the ISeq interface and the s-expression parameter in the lazy-seq macro are converted to a function without any parameter and passed to the clojure.lang.LazySeq constructor (the constructor that takes an IFn object as a parameter), and because in the end you are back called the r function (which returns ISeq , not a complete list), this allows LazySeq to evaluate elements lazily.

So basically the stream looks something like this:

• LazySeq calls the Fn passed to it (i.e. the rest of the code)
• This Fn call returns ISeq, since lists implement ISeq. This returns an ISeq (list) with the first value as a specific value, and the second is a LazySeq object due to the recursive call to r . This returned ISeq is stored in a local variable in the class.
• Running ISeq LazySeq when the next element is called brings up the next ISeq list (list), which it stores in the local class variable in the previous step, and check if it is of type LazySeq (which it will be in the second element due to r call) if it is LazySeq, then evaluate this and return, and then item else will return the element directly (the first concrete value you passed minus).

I know this is a small thing for the mind. :). I also went through Java code just now and was able to understand when I realized that magic is possible, because the recursive call r itself returns a lazy sequence. So you have it, sort of custom limited continuations :)