Каков наилучший подход для оптимизированной для хвоста функции для расчета длины списка?

Question

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

(defun mylength (s)
  (labels ((mylength-inner (s x)
            (if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
          (mylength-inner s 0)))

Не оптимизированная под хвост версия?

(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))

Answer 1

Функция может быть оптимизирована с помощью хвостового вызова, если она возвращает прямой вызов самому себе или не вызывает самого себя. Функция mylength-inner вернет либо x, либо (mylength-inner (cdr s) (+ x 1)), поэтому она может быть оптимизирована для хвоста.

Это означает, что компилятор может превратить его в цикл вместо рекурсивного вызова функции. Либо верните x, либо присвойте (cdr s) s, увеличьте x и начните снова сверху. (Стандарт Scheme требует, чтобы реализации могли выполнять эту оптимизацию, в то время как стандарт Common Lisp оставляет его на усмотрение реализации. Конечно, эта оптимизация очень полезна, поэтому большинство реализаций будут делать это.)

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

Предположим, компилятор хотел превратить l в цикл. Нет проблем с присвоением (rest s) s, но куда он помещает (1 + ...)?

Answer 2

FWIW, CL не гарантирует, что оптимизирует удаленные вызовы; это зависит от реализации. SBCL поддерживает это. Это отличается от Scheme, где спецификация требует, чтобы компилятор исключал хвостовые вызовы. Если ты этого не делаешь, ты не Схема.

Кроме того, хвостовая рекурсия в CL довольно идиоматична. У нас есть макрос loop, поэтому используйте его:)

Answer 3

Пример длины списка в «учебнике» схемы будет здесь: http://www.scheme.com/tspl3/start.html#./start:h8 поиск «длины».

Answer 4

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

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

Возможно, здесь есть лучшее объяснение:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1