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

Me gusta Clojure. Una cosa que me molesta sobre 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 consumn mucha stack?
  • ¿Cómo puede ser que pueda envolver llamadas recursivas en una secuencia perezosa y ya no obtenga una stack sobre flujo para cálculos grandes?
  • ¿Qué recursos consumen las secuencias perezosas para hacer lo que hace?
  • ¿En qué escenarios son las secuencias perezosas ineficaces?
  • ¿En qué escenarios las secuencias perezosas son más eficientes?

Hagámoslo.

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

Las secuencias perezosas (en adelante, LS, porque soy LP o Lazy Person) están compuestas por partes. La cabeza, o la parte (s, como realmente 32 elementos se evalúan a la vez, a partir de Clojure 1.1, y creo que 1.2) de la secuencia que se ha evaluado, va seguida de algo llamado thunk , que básicamente es un trozo de información (piense en ello como el rest de su función que crea la secuencia, sin evaluar) esperando ser llamado . Cuando se invoca, el thunk evalúa todo lo que se le pide, y se crea un nuevo thunk, con el contexto necesario (cuánto se ha llamado ya, para que pueda reanudarse desde donde estaba antes).

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

¿Qué hace que las secuencias perezosas sean tan eficientes que no consumn mucha stack?

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

Si la secuencia no es floja, a menudo se está sosteniendo sobre su cabeza, lo que consume espacio en montón. Si es flojo, se calcula y luego se descarta, ya que no es necesario para cálculos posteriores.

¿Cómo es que puedes ajustar las llamadas recursivas en una secuencia perezosa y ya no obtener una stack sobre 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 usa recursividad:

 (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 [pc] (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 stack y llenándola con los resultados de los cálculos necesarios para obtener los elementos de la secuencia.

¿En qué escenarios las secuencias perezosas son ineficientes?

Cuando está usando seqs pequeños que son rápidos de computar y no se usarán mucho, convertirlo en LS es ineficiente porque requiere crear otro par de caracteres.

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

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

Cuando se trata de seqs que son enormes y solo se utilizan fragmentos de ellos, es cuando se obtiene el mayor beneficio de su uso.

En realidad, es mucho mejor usar LSs que no LS, en términos de conveniencia, facilidad de comprensión (una vez que los dominas) y razonamiento sobre tu código y velocidad.

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

Creo que las respuestas publicadas anteriormente ya hacen un buen trabajo al explicar esta parte. Solo agregaré que el “forzamiento” de una secuencia perezosa es implícito, ¡sin paren! 🙂 — Llamada de función; quizás esta forma de pensar aclarará algunas cosas. También tenga en cuenta que forzar una secuencia perezosa implica una mutación oculta: el thunk forzado necesita producir un valor, almacenarlo en un caché (¡mutación!) Y descartar su código ejecutable, que no será necesario nuevamente (¡mutación nuevamente!) .

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

¿Qué hace que las secuencias perezosas sean tan eficientes que no consumn mucha stack?

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

No consumen stack, porque consumen montón en su lugar. Una secuencia diferida es una estructura de datos, que vive en el montón, que contiene un pequeño bit de código ejecutable que se puede llamar para producir más de la estructura de datos si / cuando sea necesario.

¿Cómo puede ser que pueda envolver llamadas recursivas en una secuencia perezosa y ya no obtenga una stack sobre flujo para cálculos grandes?

En primer lugar, como lo menciona dbyrne, puede obtener un SO cuando trabaje con secuencias perezosas si los propios procesos necesitan ejecutar código con una estructura de llamada muy anidada.

Sin embargo, en cierto sentido, puede usar seqs perezosos en lugar de recurrencia de cola, y en la medida en que esto funcione para usted, puede decir que ayudan a evitar las SO. De hecho, bastante importante, las funciones que producen secuencias perezosas no deberían ser recursivas de cola; la conservación del espacio de stack con los productores de código lazy perezosos surge de la stack antes mencionada -> transferencia de montón y cualquier bash 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 diferida, solo se devuelve este “objeto de secuencia diferida” a la persona que llama, antes de que tenga lugar cualquier forzamiento. Por lo tanto, el marco de stack utilizado por la llamada que devolvió la secuencia perezosa se abre antes de que tenga lugar cualquier forzamiento. 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 vuelve inmediatamente , por lo tanto (cons :foo (foo-producer)) también regresa inmediatamente y el marco de stack utilizado por la llamada externa a foo-producer se hace saltar inmediatamente. La llamada interna a foo-producer está oculta en el rest de la secuencia, que es un thunk; si / cuando ese thunk es forzado, usará brevemente su propio frame en la stack, pero luego regresará inmediatamente como se describe arriba, etc.

Chunking (mencionado por dbyrne) cambia esta imagen muy levemente, porque se produce una mayor cantidad de elementos en cada paso, pero el principio sigue siendo el mismo: cada paso consume algo de stack cuando se producen los elementos correspondientes del seq perezoso, luego esa stack se recupera antes de que se produzca más forzamiento.

¿En qué escenarios son las secuencias perezosas ineficaces?

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

No tiene sentido ser flojo si necesitas sostener todo de una vez. Una secuencia diferida realiza una asignación de montón en cada paso cuando no se fragmenta o en cada porción, una vez cada 32 pasos, cuando se fragmenta; evitar eso puede redundar en una ganancia de rendimiento en algunas situaciones.

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

 (->> (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 mucho montón de todos modos, porque tendría que mantener los resultados intermedios para pasarlos a la siguiente etapa de procesamiento. Además, necesitaría mantener todo el asunto, lo cual es realmente imposible en el caso de (range) – ¡una secuencia infinita! – y cuando es posible, generalmente es ineficiente.

Originalmente, las secuencias perezosas en Clojure se evaluaban elemento por elemento a medida que se necesitaban. Se añadieron secuencias fragmentadas en Clojure 1.1 para mejorar el rendimiento. En lugar de la evaluación artículo por elemento, se evalúan “fragmentos” de 32 elementos a la vez. Esto reduce los gastos generales en los que incurre la evaluación perezosa. Además, permite que clojure aproveche las estructuras de datos subyacentes. Por ejemplo, PersistentVector se implementa como un árbol de 32 matrices de elementos. Esto significa que para acceder a un elemento, debe atravesar el árbol hasta que se encuentre el conjunto apropiado. Con secuencias fragmentadas, las matrices completas se toman a la vez. Esto significa que cada uno de los 32 elementos se puede recuperar antes de que el árbol necesite ser atravesado.

Se ha debatido sobre la posibilidad de forzar la evaluación elemento por elemento en situaciones en las que se requiere holgazanería. Sin embargo, no creo que se haya agregado aún al lenguaje.

¿Cómo puede ser que pueda envolver llamadas recursivas en una secuencia perezosa y ya no obtenga una stack sobre flujo para cálculos grandes?

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