Памятка с примером закрытия из Land of Lisp

Question

На странице 329 Земли Лиспа Конрад Барски объясняет технику запоминания с помощью следующего примера кода

(let ((old-neighbors (symbol-function 'neighbors))
      (previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

Идея хорошая: когда я звоню neighbors функция, я сохраняю результат в хеш-таблицу, чтобы при следующем вызове neighbors с тем же значением posЯ могу просто посмотреть результат, не вычисляя его снова.

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

(let ((previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

или, поворачивая previous в глобальную переменную *previous-neighbors* заранее, даже в

(defun neighbors (pos)
  (or (gethash pos *previous-neighbors*)
      (setf (gethash pos *previous-neighbors*) (funcall old-neighbors pos))))

таким образом делая закрытие ненужным.

Итак, мой вопрос: в чем причина, чтобы сделать это таким образом?

Причины, которые я мог представить:

1. Это дидактический пример, показывающий, что можно сделать с помощью замыкания (которое было объяснено ранее), и пример symbol-function,
2. Этот метод применим даже в ситуациях, когда вы не можете или не можете изменить исходный код neighbors,
3. Я что-то упустил.

Answer 1

Вы сделали несколько хороших наблюдений.

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

Как правило, как вы обнаружили, не имеет смысла иметь функцию памятки foo вызов функции old-foo, Использование глобальных переменных уменьшает инкапсуляцию (-> скрытие информации), но увеличивает возможность отладки программы, так как можно легче проверить записанные значения.

Подобный, но потенциально более полезный шаблон будет выглядеть так:

(defun foo (bar)
  <does some expensive computation>)

(memoize 'foo)

Где "запоминать" было бы что-то вроде этого

(defun memoize (symbol)
  (let ((original-function (symbol-function symbol))
        (values            (make-hash-table)))
    (setf (symbol-function symbol)
          (lambda (arg &rest args)
            (or (gethash arg values)
                (setf (gethash arg values)
                      (apply original-function arg args)))))))

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

Обратите внимание на ограничения выше: сравнение использует EQL и только первый аргумент функции для запоминания.

Есть также более обширные инструменты для обеспечения аналогичной функциональности.

Смотрите, например:

• https://github.com/fare/fare-memoization

• https://github.com/sharplispers/cormanlisp/blob/master/examples/memoize.lisp

• https://github.com/AccelerationNet/function-cache

Используя мой memoize сверху:

CL-USER 22 > (defun foo (n)
               (sleep 3)
               (expt 2 n))
FOO

CL-USER 23 > (memoize 'foo)
#<Closure 1 subfunction of MEMOIZE 40600008EC>

Первый звонок с арг 10 работает три секунды:

CL-USER 24 > (foo 10)
1024

Второй звонок с арг 10 работает быстрее:

CL-USER 25 > (foo 10)
1024

Первый звонок с арг 2 работает три секунды:

CL-USER 26 > (foo 2)
4

Второй звонок с арг 2 работает быстрее:

CL-USER 27 > (foo 2)
4

Третий звонок с Арг 10 работает быстро:

CL-USER 28 > (foo 10)
1024