¿Cómo se implementan las secuencias perezosas en Clojure?

lisp lazy-evaluation

Question

Me gusta Clojure. Una cosa que me molesta por el lenguaje es que no sé cómo se implementan las secuencias perezosas o cómo funcionan.

Sé que las secuencias perezosas solo evalúan los elementos en la secuencia que se solicitan. ¿Como hace esto?

• ¿Qué hace que las secuencias perezosas sean tan eficientes que no consuman mucha pila?
• ¿Cómo es posible que pueda ajustar las llamadas recursivas en una secuencia perezosa y que ya no obtenga una pila de flujo para cálculos grandes?
• ¿Qué recursos consumen las secuencias perezosas para hacer lo que hace?
• ¿En qué escenarios son ineficientes las secuencias perezosas?
• ¿En qué escenarios son más eficientes las secuencias perezosas?

Answer 1

Sé que las secuencias perezosas solo evalúan los elementos de la secuencia que se solicitan, ¿cómo hace esto?

Creo que las respuestas publicadas anteriormente ya hacen un buen trabajo explicando esta parte. Solo agregaré que el "forzado" de una secuencia perezosa es un implícito, ¡libre de paren! :-) -- Llamada de función; Quizás esta forma de pensar acerca de esto aclare algunas cosas. También tenga en cuenta que forzar una secuencia perezosa implica una mutación oculta: la fuerza forzada que está siendo forzada debe producir un valor, almacenarlo en un caché (¡mutación!) Y desechar su código ejecutable, que no será necesario nuevamente (¡otra vez mutación!) .

Sé que las secuencias perezosas solo evalúan los elementos de la secuencia que se solicitan, ¿cómo hace esto?

¿Qué hace que las secuencias perezosas sean tan eficientes que no consuman mucha pila?

¿Qué recursos consumen las secuencias perezosas para hacer lo que hace?

No consumen pila, porque consumen montón en su lugar. Una secuencia perezosa es una estructura de datos, que vive en el montón, que contiene una pequeña cantidad de código ejecutable que se puede llamar para producir más de la estructura de datos cuando sea necesario.

¿Cómo es posible que pueda ajustar las llamadas recursivas en una secuencia perezosa y que ya no obtenga una pila de flujo para cálculos grandes?

En primer lugar, como lo mencionó Dbyrne, puede obtener un SO cuando trabaje con secuencias perezosas si los propios thunks necesitan ejecutar código con una estructura de llamadas muy anidada.

Sin embargo, en cierto sentido, puede utilizar secuencias perezosas en lugar de recursión de la cola, y en la medida en que esto funcione para usted, puede decir que ayudan a evitar las SO. De hecho, lo que es más importante, las funciones que producen secuencias perezosas no deben ser recursivas; la conservación del espacio de pila con productores de secuencia perezosos surge de la pila mencionada -> transferencia de pila y cualquier intento de escribirlos de forma recursiva cola solo romperá las cosas.

La idea clave es que una secuencia perezosa es un objeto que, cuando se crea por primera vez, no contiene ningún elemento (como siempre lo hace una secuencia estricta); cuando una función devuelve una secuencia perezosa, solo este "objeto de secuencia perezosa" se devuelve a la persona que llama, antes de que tenga lugar el forzado. Por lo tanto, el marco de pila utilizado por la llamada que devolvió la secuencia perezosa se abre antes de que tenga lugar el forzado. Echemos un vistazo a una función de productor de ejemplo:

(defn foo-producer [] ; not tail recursive...
  (lazy-seq
    (cons :foo        ; because it returns the value of the cons call...
           (foo-producer)))) ; which wraps a non-tail self-call

Esto funciona porque lazy-seq devuelve inmediatamente , por lo que (cons :foo (foo-producer)) también devuelve inmediatamente y el marco de pila usado por la llamada externa a foo-producer se abre de inmediato. La llamada interna a foo-producer está oculta en la parte rest de la secuencia, que es un thunk; si / cuando ese thunk es forzado, usará brevemente su propio marco en la pila, pero luego regresará inmediatamente como se describe anteriormente, etc.

Chunking (mencionado por dbyrne) cambia esta imagen muy ligeramente, ya que se produce un mayor número de elementos en cada paso, pero el principio sigue siendo el mismo: cada paso usó un poco de pila cuando se producen los elementos correspondientes de la secuencia perezosa, entonces esa pila es reclamada antes de que tenga lugar más fuerza.

¿En qué escenarios son ineficientes las secuencias perezosas?

¿En qué escenarios son más eficientes las secuencias perezosas?

No tiene sentido ser perezoso si, de todos modos, necesitas sostener todo de una vez. Una secuencia perezosa hace una asignación de montón en cada paso cuando no está fragmentada o en cada fragmento (una vez cada 32 pasos) cuando está fragmentada; Evitar eso puede generar una ganancia de rendimiento en algunas situaciones.

Sin embargo, las secuencias perezosas permiten un modo segmentado de procesamiento de datos:

(->> (lazy-seq-producer)               ; possibly (->> (range)
     (a-lazy-seq-transformer-function) ;               (filter even?)
     (another-transformer-function))   ;               (map inc))

Hacer esto de una manera estricta asignaría un montón de almacenamiento de todos modos, porque tendría que mantener los resultados intermedios para pasarlos a la siguiente etapa de procesamiento. Además, necesitarías mantener todo alrededor, lo que en realidad es imposible en el caso de (range) , ¡una secuencia infinita! - Y cuando es posible, suele ser ineficiente.

Answer 2

Hagámoslo.

• Sé que las secuencias perezosas solo evalúan los elementos de la secuencia que se solicitan, ¿cómo hace esto?

Las secuencias perezosas (de aquí en adelante LS, porque soy un LP o persona perezosa) están compuestas de partes. La cabeza, o la parte (s, como en realidad se evalúan 32 elementos a la vez, como en Clojure 1.1, y creo que 1.2) de la secuencia que se ha evaluado, va seguida de algo llamado thunk , que es básicamente una parte de información (piense en ello como el resto de la función que crea la secuencia, sin evaluar) a la espera de ser llamada . Cuando se llama, el procesador evalúa lo mucho que se le pide, y se crea un nuevo procesador, con el contexto que sea necesario (cuánto se ha llamado ya, por lo que se puede reanudar desde donde estaba antes).

Entonces usted (take 10 (whole-numbers)) - asuma que whole-numbers es una secuencia perezosa de números enteros. Eso significa que está forzando la evaluación de thunks 10 veces (aunque internamente esto puede ser una pequeña diferencia según las optimizaciones).

• ¿Qué hace que las secuencias perezosas sean tan eficientes que no consuman mucha pila?

Esto se vuelve más claro una vez que lea la respuesta anterior (espero): a menos que llame para algo en particular, no se evalúa nada. Cuando se llama a algo, cada elemento de la secuencia puede evaluarse individualmente y luego descartarse.

Si la secuencia no es perezosa, muchas veces se mantiene en su cabeza, lo que consume espacio en el montón. Si es perezoso, se calcula y luego se desecha, ya que no se requiere para los cálculos posteriores.

• ¿Cómo es posible que pueda ajustar las llamadas recursivas en una secuencia perezosa y ya no puede obtener una pila de flujo para cálculos grandes?

Vea la respuesta anterior y considere: la macro lazy-seq ( de la documentación )

will invoke the body only the first time seq
is called, and will cache the result and return it on all subsequent
seq calls.

Echa un vistazo a la función de filter para un LS fresco que utiliza recursión:

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

• ¿Qué recursos consumen las secuencias perezosas para hacer lo que hace?

No estoy muy seguro de lo que estás preguntando aquí. Los LS requieren memoria y ciclos de CPU. Simplemente no siguen golpeando la pila y llenándola con los resultados de los cálculos necesarios para obtener los elementos de la secuencia.

• ¿En qué escenarios son ineficientes las secuencias perezosas?

Cuando se usan secuencias pequeñas que son rápidas de calcular y no se usarán mucho, lo que hace que un LS sea ineficiente porque requiere la creación de otro par de caracteres.

Con toda seriedad, a menos que esté tratando de hacer algo extremadamente eficaz, los LS son el camino a seguir.

• ¿En qué escenarios son más eficientes las secuencias perezosas?

Cuando se trata de secuencias que son enormes y solo se usan partes y partes de ellas, es cuando se obtiene el mayor beneficio al usarlas.

En realidad, es casi siempre mejor usar los LS sobre los que no son LS, en términos de conveniencia, facilidad de comprensión (una vez que se familiariza con ellos) y razonar sobre su código y velocidad.

Answer 3

Originalmente, las secuencias perezosas en Clojure se evaluaban artículo por artículo según se necesitaban. Se agregaron secuencias fragmentadas en Clojure 1.1 para mejorar el rendimiento. En lugar de una evaluación elemento por elemento, se evalúan a la vez "fragmentos" de 32 elementos. Esto reduce la sobrecarga en la que incurre la perezosa evaluación. Además, permite a clojure aprovechar las estructuras de datos subyacentes. Por ejemplo, PersistentVector se implementa como un árbol de arrays de 32 elementos. Esto significa que para acceder a un elemento, debe atravesar el árbol hasta que se encuentre la matriz apropiada. Con las secuencias fragmentadas, las matrices completas se capturan a la vez. Esto significa que cada uno de los 32 elementos puede recuperarse antes de que sea necesario volver a atravesar el árbol.

Se ha discutido sobre proporcionar una manera de forzar la evaluación artículo por elemento en situaciones donde se requiere una pereza total. Sin embargo, no creo que se haya agregado al lenguaje todavía.

¿Cómo es posible que pueda ajustar las llamadas recursivas en una secuencia perezosa y que ya no obtenga una pila de flujo para cálculos grandes?

¿Tienes un ejemplo de lo que quieres decir? Si tiene un enlace recursivo a un flojo-seq, definitivamente puede causar un desbordamiento de pila .