macros: expand declined form in outer env.

This patch implements a new requirement which clarifies what
happens when a macro declines to expand a form.

To decline expanding a form means to return the original form
(same object) without returning it. The expander detects this
situation with an eq comparison on the input and output.

The current behavior is that no further attempts are made to
expand the form. This is problematic for various reasons.  In
code which is expanded more than once, this can lead to the
expansion being different between the expansion passes.  In
the first pass, a local macro M might decline to expand a
form. In the second pass, the local macro definition no longer
exists, and the form does get expanded by a global macro M.
This kind of instability introduces a flaw into complex macros
which expand their argument material more than once.

The new requirement is that if a macro definition declines to
expand a macro, then a search takes place through the outer
lexical scopes, and global scope, for the innermost macro
definition which will expand the form.  The search tries every
macro in turn, stopping if a macro is found which doesn't
decline the expansion, or after passing the global scope.

* eval.c (expand_macro): Implement new searching behavior.

* txr.1: Documented the expansion declining mechanism
under defmacro and macrolet.

* tests/011/macros-3.tl: New file.

* tests/011/macros-3.expected: New file.

4 files changed, 63 insertions, 1 deletions

diff --git a/eval.c b/eval.c
index deed3ede..ab7518f6 100644
--- a/eval.c
+++ b/eval.c
@@ -1911,6 +1911,20 @@ static val expand_macro(val form, val mac_binding, val menv)
 {
   val expander = cdr(mac_binding);
   val expanded = funcall2(expander, form, menv);
+  if (form == expanded) {
+    val sym = car(form);
+    val up_binding = mac_binding;
+
+    while (menv && up_binding == mac_binding) {
+      menv = menv->e.up_env;
+      up_binding = lookup_mac(menv, sym);
+    }
+
+    if (up_binding && up_binding != mac_binding)
+      return expand_macro(form, up_binding, menv);
+
+    return form;
+  }
   set_origin(expanded, form);
   return expanded;
 }
diff --git a/tests/011/macros-3.expected b/tests/011/macros-3.expected
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/tests/011/macros-3.expected
diff --git a/tests/011/macros-3.tl b/tests/011/macros-3.tl
new file mode 100644
index 00000000..bf7cf9a6
--- /dev/null
+++ b/tests/011/macros-3.tl
@@ -0,0 +1,12 @@
+(load "../common")
+
+(defmacro m () 42)
+
+(test
+  (macrolet ((m (:form f) f))
+    (let ((n 3))
+      (macrolet ((m (:form f) f))
+        (let ((n 3))
+          (macrolet ((m (:form f) f))
+            (m))))))
+  42)
diff --git a/txr.1 b/txr.1
index fc187aec..645c4e04 100644
--- a/txr.1
+++ b/txr.1
@@ -30165,13 +30165,34 @@ The return value of the macro is the macro expansion. It is substituted in
 place of the entire macro call form. That form is then expanded again;
 it may itself be another macro call, or contain more macro calls.
 
-.TP* "Dialect Note:"
+A global macro defined using
+.code defmacro
+may decline to expand a macro form. Declining to expand is achieved by
+returning the original unexpanded form, which may be captured using the
+.code :form
+parameter. When a global macro declines to expand a form, the form is
+taken as-is. At evaluation time, it will be treated as a function call.
+Note: when a local macro defined by
+.code macrolet
+declines, more complicated requirements apply; see the description of
+.codn macrolet .
+
+.TP* "Dialect Notes:"
 A macro in the global namespace introduced by
 .code defmacro
 may co-exist with a function of the same name introduced by
 .codn defun .
 This is not permitted in ANSI Common Lisp.
 
+ANSI Common Lisp doesn't describe the concept of declining to expand, except in
+the area of compiler macros. Since TXR Lisp allows global macros and functions
+of the same name to co-exist, ordinary macros can be used to optimize functions
+in a manner similar to Common Lisp compiler macros. A macro can be written
+of the same name as a function, and can optimize certain cases of the function
+call by expanding them to some alternative syntax. Cases which it doesn't
+optimize are handled by declining to expand, in which case the form remains
+as the original function call.
+
 .TP* Example:
 
 .cblk
@@ -30248,6 +30269,21 @@ macros to have any visibility to any surrounding lexical variable bindings,
 which are only instantiated in the evaluation phase, after expansion is done
 and macros no longer exist.
 
+A local macro defined using
+.code defmacro
+may decline to expand a macro form. Declining to expand is achieved by returning the original
+unexpanded form, which may be captured using the
+.code :form
+parameter. When a local macro declines to expand a form, the macro definition
+is temporarily hidden, as if it didn't exist in the lexical scope. If another
+macro of the same name is thereby revealed (a global macro or another local macro
+at a shallower nesting level), then an expansion is tried with that macro.  If
+no such macro is revealed, or if a lexical function binding of that name is
+revealed, then no expansion takes place; the original form is taken as-is.
+When another macro is tried, the process repeats, resulting in a search which
+proceeds as far as possible through outer lexical scopes and finally the
+global scope.
+
 .coNP Function @ macro-form-p
 .synb
 .mets (macro-form-p < obj <> [ env ])