Переполнение стека от рекурсивного вызова функции в Лиспе

Question

Я изучаю Лисп из книги Конрада Барского "Земля Лисп". Теперь я столкнулся с моим первым камнем преткновения, где автор говорит:

Вызывать себя таким образом не только разрешено в Лиспе, но часто настоятельно рекомендуется

после показа следующего примера функции для подсчета элементов в списке:

(defun my-length (list)
  (if list
    (1+ (my-length (cdr list)))
    0))

Когда я вызываю эту функцию my-length со списком, содержащим миллион элементов, я получаю ошибку переполнения стека. Так что либо вы никогда не ожидаете иметь такой длинный список в Лиспе (так что, возможно, мой вариант использования бесполезен), либо есть другой способ подсчета элементов в таком длинном списке. Можете ли вы пролить свет на это? (Я использую GNU CLISP на Windows, кстати).

Answer 1

Создание рекурсивных функций для работы с рекурсивными структурами данных действительно полезно в lisp. И список (в lisp) определяется как рекурсивная структура данных, поэтому с вами все должно быть в порядке.

Однако, как вы уже поняли, при обходе структуры данных на миллион элементов с использованием рекурсии также будет выделяться миллион кадров в стеке, и вы можете ожидать переполнения стека, если вы специально не попросите свою среду выполнения выделить большое количество стекового пространства. (Я понятия не имею, если или как вы могли бы сделать это в gnu clisp...).

Прежде всего, я думаю, что это показывает, что структура списка данных на самом деле не самая лучшая для всего, и в этом случае может быть лучше другая структура (однако, вы, возможно, еще не дошли до векторов в своей книге-листе;-)

Другое дело, что для того, чтобы такие большие рекурсии были эффективными, компилятор должен оптимизировать хвостовые рекурсии и преобразовывать их в итерации. Я не знаю, имеет ли clisp такую ​​функциональность, но вам нужно изменить свою функцию, чтобы она была действительно оптимизируемой. (Если "оптимизация хвостовой рекурсии" не имеет смысла, пожалуйста, дайте мне знать, и я могу найти некоторые ссылки)

Для других способов итерации, посмотрите на:

• http://www.lispworks.com/documentation/HyperSpec/Body/c_iterat.htm
• http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm

Или другие структуры данных:

• http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm

Answer 2

TCO (оптимизация хвостового вызова) в CLISP на примере Криса Тейлора:

[1]> (defun helper (acc list)
       (if list
           (helper (1+ acc) (cdr list))
           acc))

(defun my-length (list)
  (helper 0 list))

HELPER

Теперь скомпилируйте это:

[2]> (compile 'helper)
MY-LENGTH
[3]> (my-length (loop repeat 100000 collect t))

*** - Program stack overflow. RESET

Теперь выше не работает. Давайте установим низкий уровень отладки. Это позволяет компилятору делать TCO.

[4]> (proclaim '(optimize (debug 1)))
NIL

Скомпилируйте снова.

[5]> (compile 'helper)
HELPER ;
NIL ;
NIL
[6]> (my-length (loop repeat 100000 collect t))
100000
[7]> 

Работает.

Разрешение компилятору Common Lisp выполнять TCO чаще всего контролируется уровнем отладки. При высоком уровне отладки компилятор генерирует код, который использует кадр стека для каждого вызова функции. Таким образом, каждый вызов может быть отслежен и будет отображаться в обратном направлении. При более низком уровне отладки компилятор может заменить хвостовые вызовы переходами в скомпилированном коде. Эти вызовы не будут видны в обратном следе, что обычно затрудняет отладку.

Answer 3

Вы ищете хвостовую рекурсию. На данный момент ваша функция определяется как

(defun my-length (list)
  (if list
    (1+ (my-length (cdr list)))
    0))

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

Вы можете переписать его, чтобы использовать вспомогательную функцию

(defun helper (acc list)
  (if list
    (helper (1+ acc) (cdr list))
    acc))

(defun my-length (list)
    (helper 0 list))

Вспомогательная функция принимает два параметра, параметр накопления acc, который хранит длину списка до сих пор, и список list это список, который мы вычисляем длину.

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

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

Answer 4

(DEFUN nrelem(l) 
    (if (null l)
        0
       (+ (nrelem (rest l)) 1)
))