使用来自Land of Lisp的闭包示例进行记忆

Question

在329页的Lisp的土地,康拉德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,我可以查找结果而无需再次计算它.

所以我想知道,是否不会是更容易的功能重新命名neighbors,以old-neighbors通过编辑和重新编译它的源代码(书的314页上给出).然后可以将memoization示例简化为

(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调用函数是没有意义的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)))))))

优点是您不需要为每个函数编写memoizing代码.你只需要一个功能memoize.在这种情况下,闭包也是有意义的 - 尽管你也可以有一个存储memoize表的全局表.

注意上面的限制:比较使用EQL并且只使用函数的第一个参数进行memoize.

还有更广泛的工具来提供类似的功能.

参见例如:

• 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