macros...

[Steve Strassmann <straz@cambridge.apple.com>]

Welcome to the world of macros. Like most sharp-edged tools, you
should use them sparingly and with care.

Here's something like what I think you wanted:

? (defmacro b-tree-insert (tree element)
   (cond ((not (boundp tree))
          `(defvar ,tree (make-node ,element)))
         ((null tree)
          `(setf ,tree (b-tree-insert-aux ,tree ,element)))
         (t
          `(b-tree-insert-aux ,tree ,element))))
B-TREE-INSERT
? (defvar foo '(23 (e 1) (g 1)))
FOO
? (defvar my-tree nil)
MY-TREE
? (macroexpand-1 '(b-tree-insert my-tree foo))
(B-TREE-INSERT-AUX MY-TREE FOO)
T
? (macroexpand-1 '(b-tree-insert some-completely-new-tree foo))
(DEFVAR SOME-COMPLETELY-NEW-TREE (MAKE-NODE FOO))
T

Here's a few things to watch out for:
 . Notice I used DEFVAR instead of SETF to introduce a new variable.
   DEFVAR also declares the variable to be special.

 . It's better to make the argument have a meaningful name like
   "element" instead of "foo". This makes your code easier to read.
   
 . It's handy to use backquote and comma (` and ,) to make up lists
   for macros to return. Use MACROEXPAND-1 and MACROEXPAND to check
   out the results.

But I guess the most important thing is, always ask yourself,
why are you using macros at all? Usually, it's to save typing, which
in this case is to avoid having to type a quote in front
of your variable names. Here's a function that does pretty much
the same thing, only you have to quote the TREE arg when you call
it. Notice the use of SET instead of SETF.

(defun b-tree-insert (tree element)
   "TREE is a symbol whose value is a tree." 
   (cond ((not (boundp tree))
          (set tree (make-node element)))
         ((null tree)
          (set tree (b-tree-insert-aux (symbol-value tree) element)))
         (t
          (b-tree-insert-aux (symbol-value tree) element))))

And you invoke it with:
(b-tree-insert 'my-tree foo)

Using a function instead of a macro also means it's easier to
write functions which call it, such as this one:

(defun update-records (tree &rest records)
  (dolist (record records)
    (b-tree-insert tree record)))

If B-TREE-INSERT were a macro, you might save yourself a little typing,
but then it's a pain to write functions which pass around trees and
call B-TREE-INSERT. Also, you should watch out about when the 
(BOUNDP TREE) test is performed: if B-TREE-INSERT is a macro, it's 
performed when you compile UPDATE-RECORDS, which is wrong.

My final piece of advice is this: you're trying to tackle two
conceptually different tasks here. One part is all the b-tree
stuff, getting the inserting and lookup to work right. The other
part is managing the names of variables, which is the defvar
and set stuff. In the long run, I think you'll find it
easier to write a library of b-tree routines that make no
assumptions about the names of trees. They just make and
modify trees, but never call set or setf or anything.

Once that code works nicely, you'll find it's much more elegant
to do the variable-name management in your application, maybe
with some differently-named functions. You'll find that you can even
re-use the b-tree code in future (more ambitious) projects
and they'll continue to work cleanly.

happy hacking!
 - steve