CODEWITHSUNDEEP
clojure
matanox
matanox

Reputation: 13747

Clojure tail recursion with lazy-seq

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

Answers (2)

Sławek Gwizdowski
Sławek Gwizdowski

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

Michiel Borkent
Michiel Borkent

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

Related Questions