Scheme 中的一般记忆过程

Question

我正在尝试在 Scheme 中创建一个通用的记忆程序。这是我目前所拥有的（与 SICP 书中的练习 3.27 几乎完全相同）：

(define (memo proc)
  (let ((table (make-table)))
    (lambda (args)
      (let ((prev (lookup args table)))
        (or prev
            (let ((result (proc args)))
              (insert! args result table)
              result))))))

（'make-table'、'insert!' 和 'lookup' 过程在 SICP 书中定义）

如果我用一个只接受一个参数的过程调用这个方法，它工作得很好。我不知道该怎么做是让它与一个带有 0 个或多个参数的过程一起工作。

我找到了 link: http://community.schemewiki.org/?memoization ，但我仍然无法使用它。 link 中的过程使用应用值和调用值，尽管我对它们的工作原理有一个粗略的了解，但我似乎无法将它与我的过程集成。

 (define (mem2 proc)
   (let ((table (make-table)))
        (lambda args
          (let ((prev (lookup args table)))
            (or prev
                (call-with-values
                 (lambda () (apply proc args))
                 (lambda (result)
                   (insert! args result table)
                   result)))))))

这是我对来自 link 的程序的尝试，使用了一个列表。它几乎可以工作，但如果我有一个带有多个参数的过程，它将计算多次。假设我将参数 1 2 3 4 传递给一个随机过程。它将在 table 中保存 1 2 3 4，但不会分别保存 1、2、3 和 4 的给定结果。我想我的错误是我在哪里查找，因为我一次通过了整个列表。

编辑：添加了 mem2 不能正常工作的测试程序。

(define (add . args)
  (display "computing add of ")
  (display args) (newline)
  (if (null? args)
      0
      (+ (car args) (apply add (cdr args)))))

它将在查找 table 中保存整个 'args'。所以如果我有：

(define add (mem2 add))

(add 2 3 4)

computing add of (2 3 4)

computing add of (3 4)

computing add of (4)

9

(add 3)

computing add of (3)

Answer 1

(define (make-table)
  (vector '()))

(define (insert! key val t)
  (vector-set! t 0 (cons (cons key val) (vector-ref t 0))))

(define (lookup key t)
  (let ([result (assoc key (vector-ref t 0))])
    (and result (cdr result))))

(define (mem2 proc)
  (let ((table (make-table)))
    (lambda args
      (let ((prev (lookup args table)))
        (or prev
            (let ([result (apply proc args)])
              (insert! args result table)
              result))))))

(define (plus x y)
  (display (list "Computing sum of: " x y))
  (newline)
  (+ 1 2))

(define memo-plus (mem2 plus))

(memo-plus 1 2)
(memo-plus 1 2)

输出：

(Computing sum of:  1 2)
3
3

添加：

(define (add . args)
  (display "computing add of ")
  (display args) (newline)
  (if (null? args)
      0
      (+ (car args) (apply add (cdr args)))))

(define memo-add (mem2 add))

(memo-add 1 2 3 4)
(memo-add 1 2 3 4)

给出输出：

computing add of (1 2 3 4)
computing add of (2 3 4)
computing add of (3 4)
computing add of (4)
computing add of ()
10
10

由于在最后 10 之前没有打印任何内容，因此示例表明结果已被记忆。

Scheme 中的一般记忆过程

General memoization procedure in Scheme

scheme

memoization

sicp

r5rs