使用定义的过程作为参数与使用 lambda 表达式作为参数产生不同的结果
Using a defined procedure as argument yields different result than using a lambda-expression as argument
我正在尝试记住方案中的一个过程。代码来自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 将最后一个结果存储在其 table 中，而 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))))))
那也没有做任何事情。
我错过了什么？为什么行为会有所不同？我怎样才能得到我想要的结果？
谢谢
问题在于，在您的第一个函数中，您正在递归调用斐波那契的非记忆版本，而不是 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)))))))
这是解决此问题的另一种方法。这是在 Racket 中，而不是在 Scheme 中，对此我深表歉意（它可能是 Scheme，除非我不知道哈希表在 Scheme 中是如何工作的）。
首先，这是一个 Racket 函数，用于在其第一个参数上记忆任意数量参数的函数。马上就会明白为什么我们需要允许额外的参数。
(define (memoize f (table (make-hasheqv)))
;; Memoize a function on its first argument.
;; table, if given, should be a mutable hashtable
(λ (k . more)
;; hash-ref! looks up k in table, and if it is not there
;; sets it to be the result of calling the third argument (or
;; to the third argument if it's not callable). thunk just makes
;; a function of no arguments.
(hash-ref! table k
(thunk (apply f k more)))))
现在有诀窍：不是将 fib 定义为递归函数，而是将 fib/c 定义为 非 递归函数，它知道如何做斐波那契数列计算的一步，然后将平底船转移到另一个函数来完成剩下的工作。它还会像您的函数一样告诉您它在做什么。
(define (fib/c n c)
;; fib/c does one step of the fibonacci calculation,
;; calling c to do the remaining steps.
(printf "fib of ~A~%" n)
(if (<= n 2)
1
(+ (c (- n 1) c)
(c (- n 2) c))))
基于此我们可以很容易地定义 fib/u，一个未记忆的斐波那契函数，它具有您期望的糟糕性能，只需将 fib/c 本身作为其第二个参数传递：
(define (fib/u n)
;; unmemoized fib
(fib/c n fib/c))
但现在我们可以记忆它，并定义一个记忆版本，fib/m（在这里你明白为什么我需要 memoize 来允许多个参数：我们需要继续传递记忆版本功能下降：
(define (fib/m n)
;; and here's a memoized fib
(let ((fib/m (memoize fib/c)))
(fib/m n fib/m)))
现在（4 是第一个不同的情况）：
> (fib/u 4)
fib of 4
fib of 3
fib of 2
fib of 1
fib of 2
3
> (fib/m 4)
fib of 4
fib of 3
fib of 2
fib of 1
3
并删除印刷：
> (time (fib/u 40))
cpu time: 8025 real time: 7962 gc time: 26
102334155
> (time (fib/m 40))
cpu time: 1 real time: 1 gc time: 0
102334155
请注意，这种编写非递归函数并将其转换为递归函数的方法与 Y 的推导方式密切相关（尽管这些通常非常纯粹并且坚持使用具有只有一个参数，所以你最终得到 (λ (f) (λ (n) ... (f ...) ...)) 而不是 (λ (n c) ... (c ...) ...)。事实证明这是一个非常有用的技巧。
我正在尝试记住方案中的一个过程。代码来自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 将最后一个结果存储在其 table 中，而 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))))))
那也没有做任何事情。
我错过了什么？为什么行为会有所不同？我怎样才能得到我想要的结果？
谢谢
问题在于，在您的第一个函数中，您正在递归调用斐波那契的非记忆版本，而不是 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)))))))
这是解决此问题的另一种方法。这是在 Racket 中，而不是在 Scheme 中，对此我深表歉意（它可能是 Scheme，除非我不知道哈希表在 Scheme 中是如何工作的）。
首先，这是一个 Racket 函数，用于在其第一个参数上记忆任意数量参数的函数。马上就会明白为什么我们需要允许额外的参数。
(define (memoize f (table (make-hasheqv)))
;; Memoize a function on its first argument.
;; table, if given, should be a mutable hashtable
(λ (k . more)
;; hash-ref! looks up k in table, and if it is not there
;; sets it to be the result of calling the third argument (or
;; to the third argument if it's not callable). thunk just makes
;; a function of no arguments.
(hash-ref! table k
(thunk (apply f k more)))))
现在有诀窍：不是将 fib 定义为递归函数，而是将 fib/c 定义为 非 递归函数，它知道如何做斐波那契数列计算的一步，然后将平底船转移到另一个函数来完成剩下的工作。它还会像您的函数一样告诉您它在做什么。
(define (fib/c n c)
;; fib/c does one step of the fibonacci calculation,
;; calling c to do the remaining steps.
(printf "fib of ~A~%" n)
(if (<= n 2)
1
(+ (c (- n 1) c)
(c (- n 2) c))))
基于此我们可以很容易地定义 fib/u，一个未记忆的斐波那契函数，它具有您期望的糟糕性能，只需将 fib/c 本身作为其第二个参数传递：
(define (fib/u n)
;; unmemoized fib
(fib/c n fib/c))
但现在我们可以记忆它，并定义一个记忆版本，fib/m（在这里你明白为什么我需要 memoize 来允许多个参数：我们需要继续传递记忆版本功能下降：
(define (fib/m n)
;; and here's a memoized fib
(let ((fib/m (memoize fib/c)))
(fib/m n fib/m)))
现在（4 是第一个不同的情况）：
> (fib/u 4)
fib of 4
fib of 3
fib of 2
fib of 1
fib of 2
3
> (fib/m 4)
fib of 4
fib of 3
fib of 2
fib of 1
3
并删除印刷：
> (time (fib/u 40))
cpu time: 8025 real time: 7962 gc time: 26
102334155
> (time (fib/m 40))
cpu time: 1 real time: 1 gc time: 0
102334155
请注意，这种编写非递归函数并将其转换为递归函数的方法与 Y 的推导方式密切相关（尽管这些通常非常纯粹并且坚持使用具有只有一个参数，所以你最终得到 (λ (f) (λ (n) ... (f ...) ...)) 而不是 (λ (n c) ... (c ...) ...)。事实证明这是一个非常有用的技巧。