Lazyness and stackoverflow

Question

I wrote the following:

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

to solve 4clojure.com's problem #118: http://www.4clojure.com/problem/118

which asks to reimplement map without using map etc. and that solution passes the tests (I don't know if it's correct or not: it's very close to other solutions that said).

Because the problem stated that it had to be lazy I wrote the code above by "wrapping" my solution in a lazy-seq... However I don't understand how lazy-seq works.

I don't understand what is "lazy" here nor how I could test it out.

When I ask (type ...) I get, unsurprisingly, a clojure.lang.LazySeq but I don't know what's the difference between that and what I get if I simply remove the lazy-seq "wrapping".

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

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

Otherwise (that is: if I let the lazy-seq wrapping in place), it seems to work fine.

So I decided to try to somehow "debug" / trace what is going on 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 the working version inside the dbg macro and tried to execute it again. And now kaboom: the version which worked fine now throws a stackoverflow too.

Now I'm not sure: maybe it's an unwanted effect of the macro that would somehow force the evalution of stuff that otherwise wouldn't be evaluated?

It would be great if anyone could explain, using this simple function and the simple test, how lazyness does work here, what exactly gets called when, etc.

Answer 1

The whole magic lies in clojure.lang.LazySeq java class. Which itself implement the ISeq interface and the s-expressions parameter to the lazy-seq macro are converted to a function without any parameter and is passed to the constructor of clojure.lang.LazySeq (to the constructor which take IFn object as parameter) and because in the end you have called r function again (which is returning a ISeq and not the complete list) this allows the LazySeq to evaluate items lazily.

So basically the flow goes something like this:

• LazySeq calls the Fn passed to it (i.e the rest body of the code)
• This Fn call returns a ISeq because Lists implements ISeq. This return ISeq (list) with first value as a concrete value and second is a LazySeq object due to recursive call to r. This returned ISeq is stored in a local variable in the class.
• The ISeq implementation of LazySeq on calling next item does call the next of ISeq (list) that it stored in local class variable in above step and check if it is of type LazySeq (which it will be in 2nd item due to r call), if it is LazySeq then evaluate that and return then item else return the item directly (the first concrete value that you passed to cons)

I know it is a little mind bending thing :). I also went through the Java code just now and was able to figure out after I realized that the magic is possible because the recursive call to r itself return a lazy sequence. So there you have it, kind of custom delimited continuations :)