The Unwashed Meme

• Chris Double has a post about
  debugging Sisc Scheme web applications hosted in Jetty. I lust after
  that interactivity, especially the part about not taking down the webapp for
  every little change.
• Chris Double weighs in with the
  size of serialized continuation state: 5KB to 100KB. In our system
  (not continuation based) I’ve seen it run over a megabyte, but that tends to
  only be when we are saving query results on the users session… something we
  generally try to avoid. Normally we see it in the same range that he does.
• Bill Clementson has
  apparently been writing about
  Continuations for complex web applications (or maybe it is
  Synchronous Web Programming) for a while. I’d seen one or two of
  these, but it looks like I know have a lot of good reading. As complex web apps
  are what I am mostly programming, how to make the environment more powerful and
  easier to develop for is a big issue.
• Bill Clementson also wrote about Domain
  Specific Languages and
  Metaprogramming
  recently. At work we have recently been talking about using more dynamic
  languages, probably Python, to generate a lot of code for the static
  languages we work with, hopefully we can just remove some of that staticness
  altogether.
• It looks like they put the entire Lightweight
  Languages 2004
  conference online that should be some viewing goodness. The talk about the
  love-child of Rest and Continuations looks especially interesting– I might be
  paraphrasing a bit.
• Successful Lisp is
  available in print, but more importantly it is available
  online! Near the end of chapter 4
  (the “Simple Macros” section) he gives an excellent example of how common lisp
  macros are really nice. This is one of the better introductory examples I’ve
  seen. It doesn’t take very long to understand, and it does offer positive
  improvement over what can be done with functions alone.
• Elegant Lisp
  Programs: From the abstract it looks like we’re in for a rollicking good
  time:
  

  Call a program “elegant” if no smaller program has the same
  output. … For any computational task there is at least one elegant program,
  perhaps more. Nevertheless, we present a Berry paradox proof that it is
  impossible to prove that any particular large program is elegant. … This
  establishes an extremely concrete and fundamental limitation on the power of
  formal mathematical reasoning.

  It is always fun to see just how
  broken everything really is.

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.