Как ленивые последовательности реализованы в Clojure?

Первоначально ленивые последовательности в Clojure оценивались по элементам по мере необходимости. В Clojure 1.1 были добавлены фрагментированные последовательности для повышения производительности. Вместо оценки по каждому элементу одновременно оцениваются «порции» из 32 элементов. Это снижает накладные расходы, связанные с ленивым вычислением. Кроме того, он позволяет clojure использовать преимущества базовых структур данных. Например, PersistentVector реализован как дерево из 32 массивов элементов. Это означает, что для доступа к элементу вы должны пройти по дереву, пока не будет найден соответствующий массив. С фрагментированными последовательностями захватываются целые массивы за раз. Это означает, что каждый из 32 элементов может быть извлечен до того, как потребуется повторный обход дерева.

Обсуждалось обеспечение способа принудительной оценки по каждому пункту в ситуациях, когда требуется полная лень. Однако я не думаю, что он еще добавлен в язык.

Как получилось, что вы можете заключить рекурсивные вызовы в ленивую последовательность и больше не допускать переполнения стека для больших вычислений?

У вас есть пример того, что вы имеете в виду? Если у вас есть рекурсивная привязка к lazy-seq, это определенно может вызвать переполнение стека .

Я знаю, что ленивые последовательности оценивают только элементы в той последовательности, которая запрашивается, как это делается?

Я думаю, что ранее опубликованные ответы уже хорошо объясняют эту часть . Я только добавлю, что "принудительное" выполнение ленивой последовательности является неявным - без паренов! :-) - вызов функции; возможно, такой способ мышления прояснит некоторые вещи. Также обратите внимание, что форсирование ленивой последовательности включает в себя скрытую мутацию - форсируемый преобразователь должен произвести значение, сохранить его в кеше (мутация!) И выбросить его исполняемый код, который больше не потребуется (снова мутация!) .

Я знаю, что ленивые последовательности оценивают только те элементы в последовательности, которые запрашиваются, как они это делают?

Что делает ленивые последовательности настолько эффективными, что они не потребляют много стека?

Какие ресурсы делают ленивые последовательности потребляют то, что они делают?

Они не потребляют стек, потому что вместо этого потребляют кучу.Ленивая последовательность - это структура данных, живущая в куче, которая содержит небольшой бит исполняемого кода, который может быть вызван для создания дополнительной структуры данных, если / когда это потребуется.

Почему вы можете заключить рекурсивные вызовы в ленивую последовательность и больше не получать переполнение стека для больших вычислений?

Во-первых, как упоминал dbyrne, вы можете очень хорошо получить SO при работе с ленивыми последовательностями, если Сами преобразователи должны выполнять код с очень глубоко вложенной структурой вызовов.

Однако в определенном смысле вы можете использовать ленивые последовательности вместо хвостовой рекурсии, и в той степени, в которой это работает для вас, вы можете сказать, что они помогают избежать SO. Фактически, что довольно важно, функции, производящие ленивые последовательности , не должны быть хвостовыми рекурсивными; сохранение пространства стека с помощью ленивых производителей последовательностей возникает из вышеупомянутого перехода стека → кучи, и любые попытки записать их в хвостовой рекурсивной манере только сломают ситуацию.

Ключевым моментом является то, что ленивая последовательность - это объект, который при первом создании не содержит никаких элементов (как всегда в строгой последовательности); когда функция возвращает ленивую последовательность, вызывающей стороне возвращается только этот «объект ленивой последовательности» до того, как произойдет какое-либо форсирование. Таким образом, кадр стека, использованный вызовом, который вернул ленивую последовательность, выталкивается до того, как произойдет какое-либо форсирование.Давайте посмотрим на пример функции производителя:

(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

Это работает, потому что lazy-seq немедленно возвращает , таким образом, (cons: foo (foo-maker)) также немедленно возвращается, и фрейм стека, использованный внешним вызовом foo-производителя , немедленно выталкивается. Внутренний вызов foo-производителя скрыт в части rest последовательности, которая является преобразователем; если / когда этот преобразователь принудительно используется, он на короткое время израсходует свой собственный фрейм в стеке, но затем немедленно вернется, как описано выше и т. д.

Разделение на части (упомянутое dbyrne) очень незначительно меняет эту картину, потому что большее количество элементов создается на каждом шаге, но принцип остается тем же: каждый шаг использует некоторый стек, когда создаются соответствующие элементы ленивого seq, затем этот стек восстанавливается до того, как будет выполнено дополнительное форсирование.

В каких сценариях ленивые последовательности неэффективны?

В каких сценариях ленивые последовательности наиболее эффективны?

Нет смысла лениться, если вам все равно нужно хранить все сразу. Ленивая последовательность выделяет кучу на каждом шаге, если она не разбита на фрагменты, или на каждом фрагменте - один раз через каждые 32 шага - при разбиении на фрагменты; избегание этого может привести к увеличению производительности в некоторых ситуациях.

Однако ленивые последовательности обеспечивают конвейерный режим обработки данных:

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

Выполнение этого строгого метода в любом случае выделит много кучи, потому что вам придется хранить промежуточные результаты, чтобы передать их на следующий этап обработки .Более того, вам нужно будет держать все это под рукой, что на самом деле невозможно в случае (range) - бесконечной последовательности! - а когда это возможно, обычно неэффективно.