3

I'm new on clojure and it's not clear how exactly work lazy-sequence internally or to be more specific a function that return a lazy sequence mean that the result will be computed only when is needed. For example in the following example:

(defn fc-lazy [ fn xs ]
 (lazy-seq
  (if-let [ xss (seq xs) ]
   (cons (fn (first xs)) (fc-lazy fn (rest xs)))
  ())))

when I call:

(fc-lazy #(* % 2) (range 100))

result will be a collection of 100 numbers, this mean that the fc-lazy function will be called for 100 times, what is not clear to me; in this case we have on stack all those 100 functions, if NOT, why ?

Thanks.

srncristea
  • 121
  • 1
  • 8
  • You might get something out my answer here, http://stackoverflow.com/a/22328694/1756702, where I show first how delayed realization can be implemented and then the sequence interface with caching behavior, both in Clojure. The actual implementation in Java is similar. – A. Webb Mar 26 '14 at 13:19

2 Answers2

6

I imagine it works this way.

The lazy-seq macro

  • transforms its expression-form argument into a function-form,
  • compiles it into a Clojure closure (an invoke method on a JVM class complying with the IFn interface)
  • binds this function-class to a new LazySeq object,
  • leaving a null hole in it for the realized sequence.

At this stage, instead of evaluating the expression that yields the sequence, the expression has been captured as a function-object in an object that looks like (and therefore is) a sequence.

When some function, such as first or next or seq, that requires the realized sequence, is called on the LazySeq,

  • it notes the null hole and invokes the captured closure,
  • filling the hole with the result,
  • to which the required function is applied
  • the result of which is returned.

Subsequent calls find the hole filled, and return its required aspect at once.

So, as you run through the sequence, you do get your hundred calls, but one at a time, not all at once.

I'd be grateful for any corrections required.

Thumbnail
  • 13,293
  • 2
  • 29
  • 37
  • 1
    This is exactly what happens, and well described. You might go into more detail about why this consumes only one stack frame instead of a hundred, though. – amalloy Mar 26 '14 at 06:12
2

If you typed this in your REPL:

(source lazy-seq)

You will get:

(defmacro lazy-seq
"Takes a body of expressions that returns an ISeq or nil, and yields a Seqable object that will invoke the body only the first time seq is called, and will cache the result and return it on all subsequent seq calls. See also - realized?"
{:added "1.0"}
[& body]
(list 'new 'clojure.lang.LazySeq (list* '^{:once true} fn* [] body)))

Then have a look at: LazySeq class.

Keep in mind that a lazy sequence will be realized when you test them in the REPL.

Chiron
  • 20,081
  • 17
  • 81
  • 133