I have the following code for memoization, cribbed directly from
Norvig's PAIP:
(defmacro defun-memo (fn args &body body)
"Define a memoized function."
`(eval-when (:compile-toplevel) (memoize (defun ,fn ,args . ,body))))
(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)))
(defun clear-memoize (fn-name)
"Clear the hash table from a memo function."
(let ((table (get fn-name 'memo)))
(when table (clrhash table))))
Under CMUCL, I used this code a bunch, although I had some
difficulties I never quite understood relating to optimization and
recompilation. Under ACL, I'm having a tough time getting it to work
at all. It seems that often (though not always) the functions I
memoize end up not being found by the system.
More specifically, I have all of the above code, compiled, in a .fasl
file that gets loaded in my Lisp at startup time. Then I'd use it,
for instance, in a file foo.lisp, by saying something like:
(defun-memo cached-array (n)
(declare (type fixnum n))
(make-array n :element-type 'double-float))
Under ACL, when I compile and load the file and try to run code, I
often (again, not always) get an error that foo::cached-array is an
undefined function.
I'm guessing this has something to do with when macros are expanded
and compilation interactions, but I can't seem to build a mental model
to explain what's going on. I've tried adding :compile-toplevel and
:load-toplevel inside eval-when's in various places, but I'm really
just guessing and don't understand what's going on. Nothing seems to
help consistently, and it's especially frustrating because from my
perspective it doesn't seem consistent --- sometimes it will work, and
sometimes it won't.
Any help in understanding these issues would be appreciated.
Cheers,
rif
> From: "rif" <···@mit.edu>
> Newsgroups: comp.lang.lisp
> Sent: Sunday, April 06, 2003 7:58 PM
> Subject: memoization and compilation
>
> I have the following code for memoization, cribbed directly from
> Norvig's PAIP:
>
> (defmacro defun-memo (fn args &body body)
> "Define a memoized function."
> `(eval-when (:compile-toplevel)
> (memoize (defun ,fn ,args . ,body))))
The EVAL-WHEN shouldn't be there (and in my copy of PAIP, p273, is not
there).
You just want:
(defmacro defun-memo (fn args &body body)
"Define a memoized function."
`(memoize (defun ,fn ,args . ,body)))
Is that better?
(I haven't looked any further, but if this doesn't make things work
then I suggest that you check carefully that you have transcribed
things from PAIP correctly.)
"Simon Katz" <·····@nomistech.com> writes:
> > From: "rif" <···@mit.edu>
> > Newsgroups: comp.lang.lisp
> > Sent: Sunday, April 06, 2003 7:58 PM
> > Subject: memoization and compilation
> >
> > I have the following code for memoization, cribbed directly from
> > Norvig's PAIP:
> >
> > (defmacro defun-memo (fn args &body body)
> > "Define a memoized function."
> > `(eval-when (:compile-toplevel)
> > (memoize (defun ,fn ,args . ,body))))
>
>
> The EVAL-WHEN shouldn't be there (and in my copy of PAIP, p273, is not
> there).
> You just want:
>
> (defmacro defun-memo (fn args &body body)
> "Define a memoized function."
> `(memoize (defun ,fn ,args . ,body)))
>
> Is that better?
>
> (I haven't looked any further, but if this doesn't make things work
> then I suggest that you check carefully that you have transcribed
> things from PAIP correctly.)
Sorry. The eval-when wasn't there originally. I put it in in an
attempt to avoid problems. The problems persist with and without the
eval-when.
rif
> > The EVAL-WHEN shouldn't be there (and in my copy of PAIP, p273, is not
> > there).
> > You just want:
> >
> > (defmacro defun-memo (fn args &body body)
> > "Define a memoized function."
> > `(memoize (defun ,fn ,args . ,body)))
> >
> > Is that better?
> > (I haven't looked any further, but if this doesn't make things work
> > then I suggest that you check carefully that you have transcribed
> > things from PAIP correctly.)
Just to clarify, the problems were originally observed WITHOUT the
:eval-when. I don't think the problem is a transcription error from
PAIP, as I simply downloaded the code off the net and copied part of
the file. I think the problem is a misunderstanding on my part of
when things are compiled and evaluated, possibly including an
interaction with the way the memoization works by setf'ing
(symbol-function fn-name).
Are you suggesting that with the code as given by PAIP, I should
always (in all conforming CL implementations) be able to load a
compiled file containing the memoization code, and then compile and
use additional files that memoize functions, without having to use any
eval-when's?
I really want to understand this.
Cheers,
rif
From: Tim Bradshaw
Subject: Re: memoization and compilation
Date:
Message-ID: <ey3d6jyprzw.fsf@cley.com>
* rif wrote:
> (defmacro defun-memo (fn args &body body)
> "Define a memoized function."
> `(eval-when (:compile-toplevel) (memoize (defun ,fn ,args . ,body))))
I think that this (modulo the EVAL-WHEN) *should* work, although I
haven't thought hard. But a much safer version of this macro is
(defmacro defun-memo (fn args &body body)
`(progn
(defun ,fn ,args ,@body)
(memoize ',fn)))
This lets the DEFUN remain unambiguously at toplevel, with the
memoization happening at load time.
I'm almost certain that the issue in the original code is that the
DEFUN is not at toplevel.
--tim