Зачем применять бросок CONTROL-STACK-EXHAUSTED-ERROR в большом списке?

Question

(apply #'+ (loop for i from 1 to x collect 1)) 

работает, если x имеет значение 253391, но терпит неудачу с (SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR) на 253392 *. Это на порядок меньше, чем call-arguments-limit **.

Рекурсия исчерпала стек? Если да, то в apply? Почему он не был оптимизирован?

---

* Также интересно, (apply #'max (loop for i from 1 to 253391 collect 1)) бросает ошибку, но 253390 прекрасно.

** call-arguments-limit вычисляет 4611686018427387903 (с помощью format «s ~R, оказывается, это _{четыре нониллион шестьсот одиннадцать квадриллионов шестьсот восемьдесят шесть триллионов восемнадцать миллиардов четыреста двадцать семь миллионов триста восемьдесят семь тысяч девятьсот три})

Answer 1

Что вызывает истощение стека?

Хотя рекурсия часто является вероятным виновником исчерпания стека, в данном случае это неверно. Согласно SBCL Internals Manual:

При полном вызове аргументы передаются с созданием частичного кадра на вершине стека и хранением аргументов стека в этом фрейме.

Каждый созданный элемент списка хранится в новом стеке стека, быстро изматывая стек. Предположительно, передача SBCL большего значения через –control-stack-size увеличила бы этот практический предел до количества аргументов, которые могут быть переданы в вызове функции.

Почему call-arguments-limit намного больше практического предела?

SBCL mailing list response кто-то с подобной проблемой объясняет, почему практический предел размера стека не отражается в call-arguments-limit:

условие, что вы видите здесь не из-за фундаментальные ограничения реализации, а скорее из-за конкретного выбора размера стека, который кто-то выбрал - если размер стека был больше, этот ваш вызов не был бы ошибкой. [...] Считаем, что, учитывая нашу стратегию передачи лишних аргументов в стеке, фактическое максимальное количество аргументов, проходящих в любой момент времени, зависит от состояния программы и на самом деле не является константой.

Spec говорит, что call-arguments-limit must be a constant, поэтому SBCL, похоже, имеет defined it as most-positive-fixnum.

Есть и couple ofbug reports обсуждать этот вопрос, и TODO в источнике предполагая, что по крайней мере один участник считает, что это должно быть сведен к менее абсурдным значение: определенным образом

;; TODO: Reducing CALL-ARGUMENTS-LIMIT to something reasonable to 
;; allow DWORD ops without it looking like a bug would make sense. 
;; With a stack size of about 2MB, the limit is absurd anyway. 

SBCL по реализации call-arguments-limit может иметь место для улучшения и может привести к неожиданному поведению, но он соответствует спецификации ANSI.

Практический предел варьируется в зависимости от пространства, оставшегося в стеке, поэтому определение call-arguments-limit в соответствии с этим значением не будет соответствовать требованию спецификации для постоянного значения.

Answer 2

параметры, которые могут быть переданы функции в SBCL

Вы не проходите параметр s. Вы передаете аргументы.

(defun foo (x y) (list x y)) 

x и y являются параметры функции foo.

(foo 20 22) 

20 и 22являются аргументы в вызове функции foo.

См. Переменные call-arguments-limit и lambda-parameters-limit.

SBCL и колл-аргументы предела

Если функция не может обрабатывать почти заявленное количество аргументов, то это выглядит как ошибка в SBCL. Возможно, вы захотите сообщить об этой ошибке. Возможно, им нужно изменить значение call-arguments-limit.

Тестирование

APPLY это один из способов, чтобы проверить его.

Другой:

(eval (append '(drop-params) 
       (loop for i from 1 to 2533911 collect 1))) 

Можно также использовать FUNCALL с числом аргументов рассредоточены.

Почему существует ограничение?

Стандарт Common Lisp был написан для обеспечения эффективной реализации на разных компьютерах.Считалось, что некоторые реализационные вызовы функций машинного уровня поддерживают только ограниченное количество аргументов. В стандарте указано, что число поддерживаемых аргументов может быть как 50. На самом деле некоторые реализации имеют относительно низкое количество поддерживаемых аргументов.

Таким образом, apply в Common Lisp не является инструментом для обработки списка, но для вызова функций с вычисленными аргументами.

Для списка и использования обработки вектора УМЕНЬШИТЬ вместо СОХРАНИТЬ

Если мы хотим суммировать все числа в списке, замените

(apply #'+ list)  ; don't use this 

с

(reduce #'+ list) ; can handle arbitrary long lists 

Рекурсия

применять не является оптимизированным рекурсивной функцией

Я не могу понять, почему функцию APPLY следует использовать рекурсию.

Например, если вы думаете о

(apply #'+ '(1 2 3 4 5)) 

Повторное суммирование аргументов выполняется с помощью функции + и не apply.

Это отличается от

(reduce #'+ '(1 2 3 4 5)) 

где повторный вызов функции + с двумя аргументами выполняется reduce.