common-lisp - 使用 Land of Lisp 的闭包示例进行记忆化

Question

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

(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，我可以查找结果而无需再次计算。

所以我想知道，通过编辑和重新编译它的源代码（在本书的第 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))))

从而使关闭变得不必要。

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

我能想到的原因：

1. 它具有教学意义，展示了使用闭包（之前已经解释过）可以做什么，并提供了symbol-function.
2. 即使在您不能或可能不会更改neighbors.
3. 我错过了一些东西。

Answer 1

你已经做了一些很好的观察。

一般来说，使用类似闭包的风格更可能出现在 Scheme 代码中——Scheme 开发人员经常使用函数来返回函数。

通常，正如您所检测到的，让一个 memoize 函数foo调用一个 function没有什么意义old-foo。使用全局变量减少了封装（->信息隐藏），但增加了调试程序的能力，因为人们可以更容易地检查记忆值。

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

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

(memoize 'foo)

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

使用 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