higher-order macros [Re: Python syntax in Lisp and Scheme

[james anderson]

Andreas Rossberg wrote:
> 
> Raymond Wiker wrote:
> >>
> >>I'm not terribly familiar with the details of Lisp macros but since
> >>recursion can easily lead to non-termination you certainly need tight
> >>restrictions on recursion among macros in order to ensure termination
> >>of macro substitution, don't you? Or at least some ad-hoc depth
> >>limitation.
> >
> >         Same as with function calls, you mean?
> 
> In functional languages you at least have no limitation whatsoever on
> the depth of tail calls. Is the same true for macros?

any macro which cannot be implemented as a single quasiquoted form is likely
to be implemented by calling a function which computes the expansion. the only
difference between a macro function and any "normal" defined function is that
the former is not necessarily any symbol's function value. an auxiliary
function will be a function like any other function: anonymous, defined,
available in some given lexical context only. whatever. there are no intrinsic
restrictions on the computation which it performs. it need only admit to the
reality, that the environment is that of the compiler. eg, definitions which
are being compiled in the given unit "exist" if so specified only.

i am curious whether the availability of tail call elimination can have any
effect on the space performance of a function which is, in general, being
called to compute expressions for inclusion in a larger form. my intuition
says it would not matter.

> 
> Apart from that, can one have higher-order macros? With mutual recursion
> between a macro and its argument?

what would that mean? a macro-proper's argument is generally an s-expression,
and the macro function proper is not bound to a symbol and not necessarily
directly funcallable, but i suppose one could come up with use cases for
mutual recursion among the auxiliary functions.

the generated expressions, on the other hand, often exhibit mutual references.
in this regard, one might want, for example to look at j.schmidt's meta
implementation.[1] perhaps, in some sense, the mutual references which it
generates could be considered "higher-order", but that doesn't feel right.

there's also the issue, that there is nothing which prevents a macro function
from interpreting some aspects of the argument expression as instructions for
operations to be performed at compile-time. eg. constant folding. depending on
how the macro might establish constancy, i'm not sure what "order" that is.

>    That is, can you write a fixpoint
> operator on macros?

why one would ever think of doing that is beyond me, but given the standard y
operator definition [0],

? (DEFUN Y (F)
   (   (LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G  G)) H)))
     #'(LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G  G)) 
H)))))

Y

should one feel compelled to do so, one might resort to something like

? (defmacro print* (&rest forms)
   `(progn ,@(funcall (y #'(lambda (fn)
                             #'(lambda (forms)
                                 (unless (null forms)
                                   (cons `(print ,(first forms))
                                         (funcall fn (rest forms)))))))
                      forms)))

PRINT*
? (macroexpand '(print* (list 1 2) "asdf" 'q))
(PROGN (PRINT (LIST 1 2)) (PRINT "asdf") (PRINT 'Q))
T
? (print* (list 1 2) "asdf" 'q)

(1 2) 
"asdf" 
Q 
Q
? 

> 
> I'm not saying that any of this would be overly useful. Just trying to
> refute Dirk's rather general statement about macros subsuming HOF's.
> 

hmm... i never thought of it that way.


[0] http://www.nhplace.com/kent/Papers/Technical-Issues.html
[1] http://www.cliki.net/Meta