scheme - 使用定义的过程作为参数与使用 lambda 表达式作为参数产生不同的结果

Question

我正在尝试记住方案中的一个过程。代码来自SICP

我的程序 fib 定义为

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                (fib (- n 2))))))

我的内存过程如下

(define (memoize f)
    (let ((table (make-table)))
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

让我们定义两个过程

(define mem-fib (memoize fib))
(define mem-fib-lambda (memoize (lambda (n)
             (display "computing fib of ")
             (display n)
             (newline)
             (cond ((= n 0) 0)
               ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

如您所见，在 mem-fib 中，我使用 fib 作为参数，但在 mem-fib-lambda 中，我使用 lambda 表达式作为参数，这几乎是相同的。

使用 5 作为参数调用此过程会产生不同的结果，其中第一个 mem-fib 将最后一个结果存储在其表中，而 mem-fib-lambda 存储沿途的每个递归计算。

(mem-fib 5)
->computing fib of 5
->computing fib of 4
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 1
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 1
->5
(mem-fib 5)
->5

和

(mem-fib-lambda 5)
->computing fib of 5
->computing fib of 4
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->5
(mem-fib-lambda 5)
->5 

我的理论是，当我调用 mem-fib 时，fib 是在另一个环境中计算的，而 mem-fib-lambda 是在它被调用的环境中计算的。

为了解决这个问题，我尝试在内存过程中复制一份

(define (memoize proc)
  (define f proc) ;; Here
    (let ((table (make-table)))
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

那没有用，所以我试着把它放在 let 表达式中。据我所知，fib 应该和 table 属于同一个框架

(define (memoize proc)
    (let ((table (make-table))
         (f proc)) ;; Here
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

那也没有做任何事情。

我错过了什么？为什么行为会有所不同？我怎样才能得到我想要的结果？

谢谢

Answer 1

问题在于，在您的第一个函数中，您正在递归调用斐波那契的非内存版本，而不是 fib 的内存版本。 解决这个问题的方法是像这样定义 fib:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))

可以说更好的方法是执行以下操作:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2))))))
(set! fib (memoize fib)) ;; but we redefine fib to be memoized

这意味着我们只使用一个名字并且它被记住了。没有同时使用两个版本的好方法，但如果您愿意，可以采用以下一种方法(如果您想比较性能或其他内容):

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))
(set! fib (lambda (n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2)))))))