Re: Implementing Memorize

[Georg Bauhaus <sb463ba@l1-hrz.uni-duisburg.de>]

Lutz Donnerhacke <lutz@iks-jena.de> wrote:
: In order to implement a generic memorize, I tried the following
:  (see <slrnbpajhj.ns.lutz@taranis.iks-jena.de> for the context)

To mention some more context, this has come up in a language war
in de.comp.lang.misc where someone presented:

;;;; -*- Mode: Lisp; Syntax: Common-Lisp -*-
;;;; Code from Paradigms of AI Programming
;;;; Copyright (c) 1991 Peter Norvig
;;; ==============================

;;;; The Memoization facility:

(defun memo (fn &key (key #'first) (test #'eql) name)
  "Return a memo-function of fn."
  (let ((table (make-hash-table :test test)))
    (setf (get name :memo) table)
    #'(lambda (&rest args)
        (let ((k (funcall key args)))
          (multiple-value-bind (val found-p)
              (gethash k table)
            (if found-p val
                (setf (gethash k table) (apply fn args))))))))

(defun memoize (fn-name &key (key #'first) (test #'eql))
  "Replace fn-name's global definition with a memoized version."
  (clear-memoize fn-name)
  (setf (symbol-function fn-name)
        (memo (symbol-function fn-name)
              :name fn-name :key key :test test)))