12.29.04
Posted in Uncategorized at 11:25 pm by UnwashedMeme
Permalink
12.27.04
Posted in Uncategorized at 11:04 am by UnwashedMeme
I’ve been reading Paul Graham’s book
On Lisp which so far is a pretty good book, partly because it is
aimed a little bit higher than most programming texts I have read. He states in
the introduction that in this book he is trying to show what you can do with
Lisp that you cannot easily do in other languages.
One of the examples he gives in Chapter 5 is the function memoize(Figure 5.2:
pp 65):
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
val
(setf (gethash args cache)
(apply fn args)))))))
This function takes a function as an argument, creates a hash table then
returns a lambda function that closes the original function and the hash table.
When called, this lambda function checks the hash table to see if there is an
entry keyed by the argument list–args. If there is it returns that
value, otherwise it calls the original function passing it the argument list,
sets the entry in the hash table to the value returned by the function call,
and returns that value. For example (in CLisp):
CL-USER> (setq slowid (memoize #'(lambda (x) (sleep 5) x)))
#<CLOSURE :LAMBDA (&REST ARGS)
(MULTIPLE-VALUE-BIND (VAL WIN) (GETHASH ARGS CACHE)
(IF WIN VAL (SETF (GETHASH ARGS CACHE) (APPLY FN ARGS))))>
CL-USER> (time (funcall slowid 1))
Real time: 5.0 sec.
1
CL-USER> (time (funcall slowid 1))
Real time: 0.0 sec.
1
Memoization is not uncommon and this function can be repeated relatively easily
in any language with closures and first class functions. When I looked at this
though I didn’t like the separate step to memoize the function. I want to be
able to do this when I define the function initially. So I wrote a Common Lisp
macro defmemoized that defines a memoized function using the same
style as defun.
(defmacro defmemoized (sym lambda-list &body b)
`(flet ((fn ,lambda-list ,@b)) ;this defines the desired function
(let ((mfn (memoize #'fn))) ;this memoizes the function
;;do the defun pointing to the memoized function.
(defun ,sym (&rest x) (apply mfn x)))))
;;Example:
;;function foo takes parameters x, y, and z. sleeps for x seconds then returns y + z.
(defmemoized foo (x y z)
(sleep x)
(+ y z))
The macro takes parameters: sym –the name of the function we want to
declare; lambda-list — the function’s list of parameters; and b
–the function body. The &body is a keyword saying that the next
parameter should be a list of all the remaining parameters passed into the
macro; I believe it is equivalent to &rest except for the way the
system prints it back out.
The interesting part of this begins with flet . We are locally
defining the desired function and giving it the name fn. Then let mfn
be the memoization of the function refered to by fn– #’fn.
The final defun is creating the function proper. The function will be
named by the symbol that was passed into the macro. It takes a parameter list x.
It applies those parameters to the memoized version of the function closed into
its environement when it was defuned.
Let’s expand the macro with our sample function foo to see what form it is
generating, then play with it:
CL-USER> (pprint (macroexpand '(defmemoized foo (x y z) (sleep x) (+ y z))))
(FLET ((FN (X Y Z) (SLEEP X) (+ Y Z)))
(LET ((MFN (MEMOIZE #'FN))) (DEFUN FOO (&REST X) (APPLY MFN X))))
; No value
CL-USER>
(defmemoized foo (x y z)
(sleep x)
(+ y z))
FOO
CL-USER> (time (foo 1 2 3))
Real time: 1.0 sec.
5
CL-USER> (time (foo 1 2 3))
Real time: 0.0 sec.
5
So far so good. One thing I don’t fully understand yet: In the form (apply
mfn x), why isn’t mfn sharpquoted? Generally when you are
referring to functions you need to sharpquote them because you want the
function, not the evaluation of the function. I think this is related
to Common Lisp having separate function
cells and value cells . I guess in this case the let adds
the layer of indirection so that when the symbol is evaluated
the value of it is the function, hence not needing the extra #’.
One last note… from what I have read when you are writing macros you don’t
want to insert symbol names throughout because what if one of the parameters
passed into the macro is a symbol named the same. It is possible that you can
have a symbol inside the one you actually intended to reference. Eg.
CL-USER> (pprint (macroexpand '(defmemoized mfn (x y z) (sleep x) (+ y z))))
(FLET ((FN (X Y Z) (SLEEP X) (+ Y Z)))
(LET ((MFN (MEMOIZE #'FN))) (DEFUN MFN (&REST X) (APPLY MFN X))))
In this case it happens to work anyways because of the sharpquote issue
mentioned above, but that should illustrate the potential for problems. To make
it safe regardless:
(defmacro defmemoized (sym lambda-list &body b)
(let ((x (gensym)) ;generate a few symbols for internal use
(fn (gensym))
(mfn (gensym)))
`(flet ((,fn ,lambda-list ,@b)) ;this defines the desired function
(let ((,mfn (memoize #',fn))) ;this memoizes the function
;;do the defun pointing to the memoized function.
(defun ,sym (&rest ,x) (apply ,mfn ,x))))))
CL-USER> (pprint (macroexpand '(defmemoized mfn (x y z) (sleep x) (+ y z))))
(FLET ((#:G1391 (X Y Z) (SLEEP X) (+ Y Z)))
(LET ((#:G1392 (MEMOIZE #'#:G1391)))
(DEFUN MFN (&REST #:G1390) (APPLY #:G1392 #:G1390))))
All of the symbols used by the macro internally have been generated by the
system and we can count on them being unique.
Just finished writing this and thought I would Google for defmemoized… whadya
know: http://xarch.tu-graz.ac.at/autocad/stdlib/contrib/defmemoized.txt.
Just glad I didn’t Google that first or I never would have gotten the excellent
macro practice.
Permalink