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

そしてうまくいけば、関数を memoize-wrapper で定義する def-memo というマクロを作成します。例えば。マクロは (memoizer (define function-name arguments body ...) などに展開できます。

だから私はできるはずです：

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

通常の遅いものではなく、階乗のメモ化されたバージョンを作成する必要があります。

私の問題は、

  1. memoize-wrapper が正しく動作していません。メモ化された関数を呼び出すのではなく、元の関数を呼び出します。
  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 に答える