recursion - Si la única construcción de bucle que no consume pila en Clojure es "recurrente", ¿cómo funciona este lazy-seq?

tail-recursion

Question

La página ClojureDocs para lazy-seq da un ejemplo de generación de un lazy-seq de todos los números positivos:

(defn positive-numbers
  ([] (positive-numbers 1))
  ([n] (cons n (lazy-seq (positive-numbers (inc n))))))

Este lazy-seq puede evaluarse para índices bastante grandes sin lanzar un StackOverflowError (a diferencia del ejemplo del tamiz en la misma página):

user=> (nth (positive-numbers) 99999999)
100000000

Si solo se puede recurrir para evitar consumir fotogramas de pila en una función recursiva, ¿cómo es posible que este ejemplo de lazy-seq pueda llamarse a sí mismo sin desbordar la pila?

Answer 1

Creo que el truco es que la función de productor (números positivos) no recibe un llamado recursivo, no acumula marcos de pila como si se llamara con el estilo de recursividad básica de Little-Schemer, porque LazySeq lo invoca según sea necesario para el entradas individuales en la secuencia. Una vez que un cierre se evalúa para una entrada, se puede descartar. Por lo tanto, los cuadros de pila de las invocaciones previas de la función pueden recogerse como basura a medida que el código avanza por la secuencia.

Answer 2

Tenga en cuenta que lazy-seq es una macro y, por lo tanto, no evalúa su cuerpo cuando se llama a su función de positive-numbers . En ese sentido, positive-numbers no son verdaderamente recursivos. Vuelve inmediatamente, y la llamada "recursiva" interna a positive-numbers no ocurre hasta que se consume el seq.

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)))

Answer 3

Una secuencia perezosa tiene el resto de la secuencia que genera el cálculo en un procesador. No se llama inmediatamente. Como se solicita cada elemento (o fragmento de elementos según sea el caso), se realiza una llamada al siguiente procesador para recuperar los valores. Ese procesador puede crear otro procesador para representar la cola de la secuencia si continúa. La magia es que (1) estos thunks especiales implementan la interfaz de secuencia y se pueden usar transparentemente como tales y (2) cada thunk solo se llama una vez, su valor se almacena en caché, por lo que la parte realizada es una secuencia de valores.

Aquí está la idea general sin la magia, solo buenas funciones antiguas:

(defn my-thunk-seq 
  ([] (my-thunk-seq 1)) 
  ([n] (list n #(my-thunk-seq (inc n)))))

(defn my-next [s] ((second s)))

(defn my-realize [s n] 
  (loop [a [], s s, n n] 
    (if (pos? n) 
      (recur (conj a (first s)) (my-next s) (dec n)) 
      a)))

user=> (-> (my-thunk-seq) first)
1
user=> (-> (my-thunk-seq) my-next first)
2
user=> (my-realize (my-thunk-seq) 10)
[1 2 3 4 5 6 7 8 9 10]
user=> (count (my-realize (my-thunk-seq) 100000))
100000 ; Level stack consumption

Los bits mágicos suceden dentro de clojure.lang.LazySeq definido en Java, pero en realidad podemos hacer la magia directamente en Clojure (implementación que sigue, por ejemplo, con fines), implementando las interfaces en un tipo y usando un átomo para almacenar en caché.

(deftype MyLazySeq [thunk-mem]
  clojure.lang.Seqable 
  (seq [_] 
    (if (fn? @thunk-mem) 
      (swap! thunk-mem (fn [f] (seq (f)))))
      @thunk-mem)
  ;Implementing ISeq is necessary because cons calls seq
  ;on anyone who does not, which would force realization.
  clojure.lang.ISeq
  (first [this] (first (seq this)))
  (next [this] (next (seq this)))
  (more [this] (rest (seq this)))
  (cons [this x] (cons x (seq this))))

(defmacro my-lazy-seq [& body] 
  `(MyLazySeq. (atom (fn [] ~@body))))

Ahora esto ya funciona con take , etc., pero a medida que take llamadas lazy-seq haremos un my-take que usa my-lazy-seq para eliminar cualquier confusión.

(defn my-take
  [n coll]
  (my-lazy-seq
   (when (pos? n)
     (when-let [s (seq coll)]
      (cons (first s) (my-take (dec n) (rest s)))))))

Ahora hagamos una secuencia infinita lenta para probar el comportamiento de almacenamiento en caché.

(defn slow-inc [n] (Thread/sleep 1000) (inc n))

(defn slow-pos-nums 
  ([] (slow-pos-nums 1)) 
  ([n] (cons n (my-lazy-seq (slow-pos-nums (slow-inc n))))))

Y la prueba REPL

user=> (def nums (slow-pos-nums))
#''user/nums
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 9000.384616 msecs"
(1 2 3 4 5 6 7 8 9 10)
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 0.043146 msecs"
 (1 2 3 4 5 6 7 8 9 10)