Rules governing order of macro expansion in Common Lisp

defmacro is documented at http://clhs.lisp.se/Body/m_defmac.htm but the documentation is not entirely clear on exactly when things happen. By experiment with Clisp, I have found the following (assuming all macros and functions defined at top level):

• Straight top-level code can only call macros and functions that have been defined earlier.

• Code within a macro or function, or generated by a macro, can call any function it likes, including one define later (as expected from the need to support mutual recursion).

• Code within a macro can only call a macro defined earlier than the calling site of the first macro.

• Code generated by a macro can call a macro defined later.

Is it the case that Clisp is just following the specification, or is there any variation between implementations in this regard?

Is the exact intended set of rules, and the rationale behind them, documented anywhere?

You are asking about macro expansion - but I'd like to clarify how functions are handled first.

Pay attention to when the calls and the defines actually happens. In your second point you say code within a function can call a function that is defined later. This isn't strictly true.

In languages like C++ you declare and define functions and then compile your app. Ignoring inlining, templates, lambdas and other magic..., when compiling a function, the declarations of all other functions used by that function need to be present - and at link time, the compiled definitions need to be present - all before the program starts running. Once the program starts running, all functions are already fully prepared and ready to be called.

Now in Lisp, things are different. Ignore compilation for now - let's just think about an interpreted environment. If you run:

;; time 1
    (defun a () (b))
;; time 2
    (defun b () 123)
;; time 3
    (a)
    

At time 1 your program has no functions.

The first defun then creates a function (lambda () (b)), and associates it with the symbol a. This function contains a reference to the symbol b, but at this point in time it is not calling b. a will only call b when a itself gets called.

So, at time 2 your program has one function, associated with the symbol a, but it has not been executed yet.

Now the second defun creates a function (lambda () 123), and associates it with the symbol b.

At time 3 your program has two functions, associated with the symbols a and b, but neither has been called yet.

Now you call a. During its execution, it looks for the function associated with the symbol b, finds that such a function already exists at this point in time, and calls it. b executes and returns 123.

Let's add more code:

    ;; time 4
        (defun b () 456)
    ;; time 5
        (a)

After time 4, a new defun creates a function returning 456, and associates it with the symbol b. This replaces the reference b was holding to the function returning 123, which will then be garbage collected (or whatever you implementation does to take out the trash).

Calling a (or more correctly, the lambda referenced by the function attribute of the symbol a), will now result in a call to a function that returns 456.

If, instead, we had originally written:

;; time 1
    (defun a () (b))
;; time 2
    (a)
;; time 3
    (defun b () 123)

... this would not have worked, because after time 2 when we call a, it can't find a function associated with the symbol b and so it will fail.

Now - compile, eval-when, optimisation and other magic can do all kinds of funky things different from what I've described above, but make sure you first have a grasp of these basics before worrying about that more advanced stuff.

1. Functions are only created at the time that defun is called. (The interpreter doesn't "look ahead in the file".)
2. One of the attributes of a symbol is a reference to a function. (The function itself doesn't actually have a name.)
3. Multiple symbols can reference the same function. ((setf (symbol-function 'd) (symbol-function 'b)))
4. Defining a function a that calls function b (speaking colloquially), is OK as long as the symbol b has an associated function by the time a is called. (It is not required at the time of defunning a.)
5. A symbol can refer to different functions at different times. This affects any functions "calling" that symbol.

The rules for macros are different (their expansions are static after "read" time), but many of the principles remain the same (Lisp doesn't "look ahead in the file" to find them). Understand that Lisp programs are far more dynamic and "run-time" than most (lesser ;-) ) languages you may be used to. Understand what happens when during execution of a Lisp program, and the rules governing macro expansion will start making sense.