来自 Land of Lisp 的带有闭包示例的记忆

Question

在 Land of Lisp 的第 329 页，Conrad Barski 使用以下示例代码解释了 memoization 的技术

(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 函数时，我将结果保存到散列 table 中，以便下次调用 neighbors 时具有相同的值pos，我可以只看结果，不用再计算了。

所以我想知道，通过编辑和重新编译它的源代码（在书的第 314 页给出），将函数 neighbors 重命名为 old-neighbors 是否会更容易。那么记忆示例可以简化为

(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))))

因此不需要关闭。

所以我的问题是：这样做的原因是什么？

我能想到的原因：

它具有教学意义，展示了闭包可以做什么（之前已经解释过）并提供了 symbol-function.
即使在您不能或不能更改 neighbors 的源代码的情况下，此技术也适用。
我遗漏了一些东西。

Answer 1

你观察得很好。

通常，在 Scheme 代码中更容易找到使用闭包的风格 - Scheme 开发人员经常在其中使用函数来 return 函数。

一般来说，正如您所发现的，记忆函数 foo 调用函数 old-foo 没有什么意义。使用全局变量减少了封装（->信息隐藏），但增加了调试程序的能力，因为可以更轻松地检查记忆值。

一个类似但可能更有用的模式是这样的：

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

(memoize 'foo)

where ˋmemoizeˋ 会像这样

(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。在这种情况下，闭包也是有意义的——尽管你也可以有一个全局 table 存储 memoize tables.

注意上面的限制：比较使用 EQL 并且只使用函数的第一个参数来记忆。

还有更广泛的工具可以提供类似的功能。

参见示例：

使用上面的 memoize：

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

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

第一次调用 arg 10 运行三秒：

CL-USER 24 > (foo 10)
1024

第二次调用 arg 10 运行得更快：

CL-USER 25 > (foo 10)
1024

第一次调用 arg 2 运行三秒：

CL-USER 26 > (foo 2)
4

第二次调用 arg 2 运行得更快：

CL-USER 27 > (foo 2)
4

带有 arg 10 的第三次调用运行速度很快：

CL-USER 28 > (foo 10)
1024

来自 Land of Lisp 的带有闭包示例的记忆

Memoization with a closure example from Land of Lisp

common-lisp

memoization

land-of-lisp