Reputation: 13747
Could you kindly explain in more breadth and clarity, how does lazy-seq
make tail recursion "safe" as per this docs page?
https://clojuredocs.org/clojure.core/lazy-seq
;; The following defines a lazy-seq of all positive numbers. Note that
;; the lazy-seq allows us to make a recursive call in a safe way because
;; the call does not happen immediately but instead creates a closure.
user=> (defn positive-numbers
([] (positive-numbers 1))
([n] (lazy-seq (cons n (positive-numbers (inc n))))))
#'user/positive-numbers
user=> (take 5 (positive-numbers))
(1 2 3 4 5)
Upvotes: 3
Views: 310
Reputation: 91
If you look at the source of lazy-seq
you'll notice that it's a macro that packages its argument in a function body:
user=> (source lazy-seq)
(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)))
Which produces something like this:
user=> (macroexpand '(lazy-seq (cons 1 (lazy-seq [2 3 4]))))
(new clojure.lang.LazySeq (fn* [] (cons 1 (lazy-seq [2 3 4]))))
This gives you a hint what is happening: execution of the tail position is deferred until it's' required. How is this achieved? Look at clojure/lang/LazySeq.java (Copyright (c) Rich Hickey. All rights reserved):
final synchronized Object sval(){
if(fn != null)
{
sv = fn.invoke();
fn = null;
}
if(sv != null)
return sv;
return s;
}
final synchronized public ISeq seq(){
sval();
if(sv != null)
{
Object ls = sv;
sv = null;
while(ls instanceof LazySeq)
{
ls = ((LazySeq)ls).sval();
}
s = RT.seq(ls);
}
return s;
}
These two methods execute the callable to get the tail values out -- they also unwind contained LazySeq if they see one. Then cache the result.
Upvotes: 1
Reputation: 34870
If you look at the implementation of lazy-seq
you will see it indeed returns a closure (a function which holds on to a piece of context):
(list 'new 'clojure.lang.LazySeq (list* '^{:once true} fn* [] body))
So the call to positive-numbers
in (cons n (positive-numbers (inc n))
is not evaluated immediately, but delayed until the closure gets called.
Upvotes: 1