Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!stanford.edu!neon.Stanford.EDU!michaelg
From: michaelg@neon.Stanford.EDU (Michael Greenwald)
Newsgroups: comp.lang.lisp.franz
Subject: Re: Lisp Macros
Message-ID: <1991May17.171652.18636@neon.Stanford.EDU>
Date: 17 May 91 17:16:52 GMT
References: <1991May15.203735.3850@csusac.csus.edu> <1991May17.053812.18600@csusac.csus.edu>
Organization: Computer Science Department, Stanford University, Ca , USA
Lines: 48

cs16011@athena.ecs.csus.edu writes:


>Thanks for all the information!  Let me clarify my question a little bit.
>My instructor asks "whether macros can be recursive in Lisp and if so or
>not so, support one's answer".  

I hate to be a stickler, but you're not trying to get the answer to an
assignment over the net, are you? 

>					When I tried to tackle that question I
>thought that since macro expansion was a two-step process in which the
>first phase will build a template of "to-be-evaulated" code while the
>second phase will evaluate the code built, and also because the Lisp
>interpreter will try to expand the first element of the built code
>further if it is a macro name (or if it is just a regular Lisp primitive
>then the code will be evaulated and the result returned), then it seems
>logical that I can have recursive macros merely by controlling how the
>"to-be-evaluated" code is composed during phase one.  On the other hand,
>my instructor thinks that recursive macros will have the problem of
>unable to exit but keep on expanding forever.  

No, the particular expansion depends on the rest of the expression.
Since each expansion alters (rather, "should alter", or else you have
infinite recursion) the rest of the form, you can have an exit
condition based on the form.  The state and the arguments are encoded
in the program structure.  The reason that this does not provide
strictly tail-recursive macros is that you can embed subforms inside
the form you are constructing: eg 
 (fibn-inline <n>) => (+ (fibn-inline <(- n 1)>)
                         (fibn-inline <(- n 2)>))

where (numberp n) must be T, and  appropriate termination conditions
(and expansions) are in the macro

>						Other than this idea,
>he has not provided any concrete evidence that it cannot be done.

But he has said it is >impossible< to construct arbitrary recursive
macros? 

>I have not contrived any recursive macros before and think it be more
>appropriate to learn from worldwide Lisp experts here.  Can macros have
>double recursion or just single tail recursion or NO recursion at all?

Any kind of recursion at all.  (One of the examples I posted last time
(fibn-inline) was >not< tail recursive.)  The append* example, and the
unroll-loop were both examples of recursive macros that worked.  You