5

在 Scheme 中编写自动记忆器时，我遇到了几个问题。

我有一个工作记忆函数，它创建一个哈希表并检查该值是否已经计算。如果之前已经计算过，则返回该值，否则将调用该函数。

(define (memoizer fun)
  (let ((a-table (make-hash)))
    (λ(n)
      (define false-if-fail (λ() #f))
      (let ((return-val (hash-ref a-table n false-if-fail)))
        (if return-val
            return-val
            (begin
              (hash-set! a-table n (fun n))
              (hash-ref a-table n)))))))

现在我想创建一个这样的 memoize-wrapper 函数：

(define (memoize-wrapper function)
  (set! function (memoizer function)))

并希望创建一个名为 def-memo 的宏，它使用 memoize-wrapper 定义函数。例如。宏可以扩展为 (memoizer (define function-name arguments body ...) 或类似的东西。

这样我应该能够做到：

(def-memo (factorial n)
  (cond
    ((= n 1) 1)
    (else (* n (factorial (- n 1))))))

这应该创建一个记忆版本的阶乘，而不是正常的慢速阶乘。

我的问题是

  1. memoize-wrapper 工作不正常，它不调用 memoized 函数，而是调用原始函数。
  2. 我不知道如何在宏内部编写定义。如何确保我可以获得可变长度参数和可变长度主体？然后我如何定义函数并用记忆器包装它？

非常感谢。

4

1 回答 1

7

这是我在 PLT 方案中使用的：

#lang scheme

(define (memo f)
  (define mh (make-hash))
  (lambda p
    (hash-ref mh p (lambda ()
                     (hash-set! mh p (apply f p))
                     (hash-ref mh p)))))

(define-syntax-rule (defmemo (id . p) . body)
  (define id (memo (lambda p . body))))

(provide defmemo)
于 2009-06-30T22:45:37.923 回答