Почему функция apply жалуется на длинные списки?

Question

В рамках некоторых эйлеровых трудностей я пытаюсь закодировать Сито Эратосфена с помощью колеса факторизации. Мой код до сих пор:

(defun ring (&rest content)
"Returns a circular list containing the elements in content.
 The returned list starts with the first element of content."
   (setf (cdr (last content)) content))

(defun factorization-wheel (lst)
"Returns a circular list containing a factorization 
 wheel using the list of prime numbers in lst"
   (let ((circumference (apply #'* lst)))
     (loop for i from 1 to circumference
           unless (some #'(lambda (x) (zerop (mod i x))) lst)
             collect i into wheel
           finally (return (apply #'ring 
                             (maplist 
                                 #'(lambda (x) ; Takes exception to long lists (?!)
                                     (if (cdr x)
                                         (- (cadr x) (car x))
                                         (- circumference (car x) -1)))
                                 wheel))))))

(defun eratosthenes (n &optional (wheel (ring 4 2)))
"Returns primes up to n calculated using
 a Sieve of Eratosthenes and a factorization wheel"
   (let* ((candidates (loop with s = 1
                            for i in wheel
                            collect (setf s (+ i s))
                            until (> s n))))
       (maplist #'(lambda (x) 
                    (if (> (expt (car x) 2) n)     
                        (return-from eratosthenes candidates))
                    (delete-if 
                        #'(lambda (y) (zerop (mod y (car x)))) 
                        (cdr x))) 
                candidates)))

Я получил следующий результат для колес длиннее 6 элементов. Я действительно не понимаю, почему:

21 > (factorization-wheel '(2 3 5 7 11 13))
(16 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 ...)
21 > (factorization-wheel '(2 3 5 7 11 13 17))
> Error: Too many arguments.
> While executing: FACTORIZATION-WHEEL, in process listener(1).

Алгоритм, кажется, работает нормально в противном случае и производит простые числа с колесами, имеющими 6 или меньше элементов.

По-видимому apply или же ring поднимите их носы, когда им передают длинные списки.

Но не должен ли список считаться одним аргументом? Я признаю, что я полностью сбит с толку. Любой вклад приветствуется.

Answer 1

ANSI Common Lisp позволяет реализациям ограничивать максимальное количество аргументов, которые могут быть переданы функции. Этот предел задается параметром call-arguments-limit, он может быть не более 50.

Для функций, которые ведут себя как операторы алгебраических групп, подчиняющиеся ассоциативному свойству (+, listи другие), мы можем обойти ограничение, используя reduce уничтожить список ввода, рассматривая функцию как двоичную.

Например, чтобы добавить большой список номеров: (reduce #'+ list) скорее, чем (apply #'+ list),

Примечания о reduce

В Common Lisp, reduce будет работать, даже если список пуст. Немногие другие языки дают вам это, и это на самом деле не происходит от reduce: это не будет работать для всех функций. Но с + мы можем написать (reduce #'+ nil) и он рассчитывает ноль, так же, как (apply #'+ nil),

Это почему? Поскольку + Функция может быть вызвана с нулевыми аргументами, а при вызове с нулевыми аргументами она возвращает единичный элемент для аддитивной группы: 0, Это ласточкин хвост с reduce функция.

На некоторых других языках fold или же reduce Функция должна иметь начальное начальное значение (например, 0) или же непустой список. Если не указано ни того, ни другого, это ошибка.

Общий Лисп reduce, если ему дан пустой список и нет :initial-value, вызовет функцию ядра без аргументов и использует возвращаемое значение в качестве начального значения. Поскольку это значение является единственным значением (список пуст), это значение возвращается.

Следите за функциями со специальными правилами для самого левого аргумента. Например:

(apply #'- '(1)) -> -1  ;; same as (- 1), unary minus semantics.

(reduce #'- '(1)) -> 1  ;; what?

Что происходит, когда reduce дается список из одного элемента, он просто возвращает элемент без вызова функции.

В основном это основано на математическом предположении, упомянутом выше, что если нет :initial-value поставляется тогда f ожидается поддержка (f) -> i, где i некоторый элемент идентичности по отношению к f, чтобы (f i x) -> x, Это используется в качестве начального значения при сокращении одноэлементного списка, (reduce #'f (list x)) -> (f (f) x) -> (f i x) -> x,

- функция не подчиняется этим правилам. (- a 0) означает "вычесть ноль из a"и так дает a, в то время как (- a) аддитивная обратная aвероятно, по чисто прагматическим, нотационным причинам (а именно, не заставляя программистов на Лисп писать (- 0 a) просто чтобы перевернуть знак, просто ради - вести себя более последовательно под reduce а также apply). - Функция также не может быть вызвана с нулевыми аргументами.

Если мы хотим взять список чисел и вычесть их все из некоторого значения xшаблон для этого:

(reduce #'- list-of-numbers :initial-value x)