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 个或多个参数的过程一起工作。

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

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

这是我使用列表对链接中的过程进行的尝试。它几乎可以工作，但是如果我有一个需要多个参数的过程，它会计算它几次。假设我传递一个随机过程参数 1 2 3 4。它将在表中保存 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)))))

它将在查找表中保存整个“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 条之前没有打印任何内容，因此该示例显示结果已被内存。