Преобразователи Clojure: переполнение стека с [0], но не с '(0)?

Вот фрагмент кода, который дает мне StackOverflowError (сведен из реального примера в моей кодовой базе):

( ->> (range 3000)
      (mapcat #(concat [0] (take 100 (repeat %))))
      (reduce (constantly nil))
      (count))

(Примечание: этот код предназначен делать только для демонстрации проблемы или возврата нуля.)

Я могу «спасти» его одним из следующих шагов:

  1. Удалите строку reduce
  2. Изменить [0] на '(0)
  3. Добавьте (take 100000000) (или любое целое число) в любой точке между mapcat и count.

Я в основном сбит с толку таким поведением (особенно № 2). Буду признателен за любой вклад.

(У меня есть ощущение, что это может быть связано с Почему сокращение дает StackOverflowError в Clojure?, но я не могу точно сказать, как — так что, если это связано, я был бы признателен за объяснение, почему.)


thunk clojure lazy-evaluation stack-overflow
person Bosh    schedule 16.10.2014    source источник
comment
Предполагается ли вернуть 0? Интересно, что я не получаю переполнения стека, если я изменяю его на это: ( -›› (диапазон) (mapcat (fn [p] (concat [0] (взять 100 (повторить ноль))))) (взять 3000) (уменьшить (постоянно ноль)) (посчитать))   -  person Hugo    schedule 16.10.2014
comment
Да, он должен возвращать 0. (Я имею в виду, что код на самом деле не должен делать ничего, кроме как демонстрировать это поведение кратчайшим способом, который я смог найти.) count здесь только для того, чтобы продемонстрировать, что использование самой последовательности не имеет смысла. не вызвать ошибку. В вашем примере, @firthh, вы можете изменить (взять 3000) на (взять 3000000), если хотите, и это все еще работает. Вы также можете поставить (возьмите 3000) после шага уменьшения...   -  person Bosh    schedule 16.10.2014
comment
сокращение является строгим и использует постоянное пространство стека - более вероятно, что вызовы concat / mapcat складываются без оценки перед принудительным выполнением, что вызывает проблему   -  person noisesmith    schedule 16.10.2014
comment
@noisesmith, однако, это не совсем объяснение. Почему count удается, когда я удаляю reduce? И почему '(0) действует иначе? И почему обертывание concat (или mapcat) не приводит к помощи (doall)?   -  person Bosh    schedule 16.10.2014

Ответы (2)


arrow_upward
10
arrow_downward

В нормальных условиях reduce работает с использованием конструкции loop/recur и использует постоянное пространство стека. Однако вы столкнулись с неприятным краеугольным камнем, вызванным сокращением последовательности, созданной путем предоставления concat чередующихся секвенированных и нефрагментированных последовательностей (вектор [0] фрагментирован; последовательность, созданная (take 100 (repeat %)), не фрагментирована).

Когда первый аргумент concat представляет собой фрагментированную последовательность, он вернет ленивую последовательность, которая будет использовать chunk-cons для создания другой фрагментированной последовательности. В противном случае он будет использовать cons для создания неразделенной последовательности.

Между тем, реализация reduce использует протокол InternalReduce (определенный в clojure.core.protocols), который предоставляет функцию internal-reduce для структур, которые могут сокращаться более эффективно, чем с рекурсией first/next по умолчанию. Реализация internal-reduce для фрагментированных последовательностей использует функции фрагментов для использования фрагментированных элементов в цикле до тех пор, пока не останется последовательность без фрагментов, а затем вызывает internal-reduce для остатка. Реализация internal-reduce по умолчанию аналогичным образом использует first/next для потребления элементов в цикле до тех пор, пока не изменится базовый тип последовательности, а затем вызывает internal-reduce для нового типа последовательности для отправки в соответствующую оптимизированную версию. По мере того, как вы продвигаетесь по последовательности, созданной concat, чередуя фрагментированные и не фрагментированные подпоследовательности, вызовы internal-reduce накапливаются в стеке и в конечном итоге разрушают его.

Более простая иллюстрация этого случая:

;; All chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat [1]))))
10000

;; All non-chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat '(1)))))
10000

;; Interleaved chunked and non-chunked sub-seqs blows the stack
user> (reduce + (apply concat (take 10000 (interleave (repeat [1]) (repeat '(1))))))
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:60)

Изучение трассировки стека:

StackOverflowError 
    clojure.core/seq (core.clj:133)
    clojure.core/interleave/fn--4525 (core.clj:3901)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/take/fn--4232 (core.clj:2554)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.Cons.next (Cons.java:39)
    clojure.lang.RT.next (RT.java:598)
    clojure.core/next (core.clj:64)
    clojure.core/concat/cat--3925/fn--3926 (core.clj:694)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.ChunkedCons.chunkedNext (ChunkedCons.java:59)
    clojure.core/chunk-next (core.clj:660)
    clojure.core.protocols/fn--6041 (protocols.clj:101)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)

Что касается ваших обходных путей:

  • Очевидно, что отказ от reduce полностью предотвращает проблему.
  • Изменение [0] на '(0) заменяет разбитые на куски подпоследовательности на неразделенные, обходя оптимизацию для разбитых на куски последовательностей в internal-reduce и позволяя выполнять сокращение в одном цикле с постоянным пространством стека.
  • Вставка take создает новую неразделенную последовательность, полностью состоящую из cons-ячеек.
person Alex    schedule 16.10.2014
comment
Да, это точно. - person amalloy; 16.10.2014

arrow_upward
0
arrow_downward

Я думаю, проблема в mapcat, который вызывает concat, который использует cons. cons для векторов дорого (и, вероятно, потребляет стек), а для списков дешево. Вот почему переход от вектора к списку «исправляет» проблему.

person ivant    schedule 16.10.2014
comment
Можете ли вы пояснить, почему сбой происходит только на шаге reduce? Если я удаляю reduce, почему count все еще работает (который без проблем потребляет всю последовательность) - person Bosh; 16.10.2014