Hey,
Just passed the first test of this macro. Don't know if it works so
well, but I thought I'd post it. I think it's potentially useful. I
wish there was a place on the net that had a bunch of little goodies
like this one. I think this is a neato idea, and can speed up lots of
different types of functions.
(defmacro defmemoized (name param-list &rest body)
(let* ((docstring (and (stringp (car body)) (> (length body) 1) (car body)))
(param-length (length param-list))
(test-function (if (< param-length 2) #'eql #'equal))
(hash-key (if (< param-length 2)
(car param-list)
`(list ,@param-list))))
(if docstring (setq body (cdr body)))
`(let ((cache (make-hash-table :test ,test-function)))
(defun ,name ,param-list
(or (gethash ,hash-key cache)
(setf (gethash ,hash-key cache)
,@body))))))
so with this, you can do something like:
(defmemoized fact (n)
(if (= n 0)
1
(* n (fact (1- n)))))
Macroexpanded once, it will yield
(let ((cache (make-hash-table :test #<function eql>)))
(defun fact (n)
(or (gethash n cache) (setf (gethash n cache) (if (= n 0) 1 (* n (fact (1- n))))))))
In the example, the function `fib' is non-ideal because it uses
recursion, but at at least it's memoized. pretty cool, in my opinion,
though no computer-science breakthroughs here.
dave
David Bakhash <·····@bu.edu> writes:
> Hey,
>
> Just passed the first test of this macro. Don't know if it works so
> well, but I thought I'd post it. I think it's potentially useful. I
> wish there was a place on the net that had a bunch of little goodies
> like this one. I think this is a neato idea, and can speed up lots of
> different types of functions.
[macro deleted]
Neat. Check out Norvig's Paradigms of AI where he has done something
similar.
CMU AI archives is the place to look for little goodies.
Unfortunately, it appears to be stagnant if not dead, which is too
bad. (I would volunteer to help revive it, but don't think I could
do it all by myself.)
I note that Peter Van Eynde has lots of little goodies that he's built
and packaged for CMUCL. See the linux directory in
www.cons.org/cmucl.
Ray
btw, that defmemoized goody was inspired by the function `memoize' in
Graham's book. But it's cooler as a macro.
Anyway, mine is not as robust because if the value stored in the cache
is `nil', mine will re-evaluate it. I forgot that (gethash) returns
multiple values, the latter one being whether or not it found what it
was looking for.
dave
David Bakhash wrote:
>
> btw, that defmemoized goody was inspired by the function `memoize' in
> Graham's book. But it's cooler as a macro.
>
> Anyway, mine is not as robust because if the value stored in the cache
> is `nil', mine will re-evaluate it. I forgot that (gethash) returns
> multiple values, the latter one being whether or not it found what it
> was looking for.
>
> dave
Why is it 'cooler?' What would one use your macro for?
fon