🚀 go-pugleaf

In article <1991May15.203735.3850@csusac.csus.edu> cs16011@athena.ecs.csus.edu writes:
>
>Hello, I have got an exam question in my Franz Lisp class about whether
>macros can be recursive or not.  I have check my textbook and Franz Lisp
>Interpreter's online manual here on campus but found no mentioning about
>whether this is possible or not.  If macros can be recursive, can anyone
>please give me an example for supporting the claim?


(defmacro append* (&rest args)
    (if (null (cddr args))
	`(append ,@args)
      `(append ,(car args) (append* ,@(cdr args)))))

[Of course, this isn't necessary since append now takes more than two args].

In article <1991May15.203735.3850@csusac.csus.edu> cs16011@athena.ecs.csus.edu writes:

   Hello, I have got an exam question in my Franz Lisp class about whether
   macros can be recursive or not.  I have check my textbook and Franz Lisp
   Interpreter's online manual here on campus but found no mentioning about
   whether this is possible or not.  If macros can be recursive, can anyone
   please give me an example for supporting the claim?

A macro is, at some time, expanded.  It's just a template for a function, an
idea, not a function per se.

Now recursivity demands that one at some time prior to application of the
function need not know how many times the function will call itself.  A macro
must know that.  Hence, a macro can only be tail-recursive (i. e. an implied
for).  Macros in TeX, as an example, are not recursive. 

Now if the macro could calculate its number of expansions during calculation,
there still would have to be an effective algorithm that could do that _prior_
to expansion.

Some of my assumptions here are ...loose... I eagerly await being corrected. 

Rolf Lindgren		| 	"The opinions expressed above are 
616 Bjerke Studentheim	|  	 not necessarily those of anyone"	
N-0589 OSLO 5		|             rolfl@hedda.uio.no 

In comp.lang.lisp.franz you write:

>In article <1991May15.203735.3850@csusac.csus.edu> cs16011@athena.ecs.csus.edu writes:

>   Hello, I have got an exam question in my Franz Lisp class about whether
>   macros can be recursive or not.  I have check my textbook and Franz Lisp
>   Interpreter's online manual here on campus but found no mentioning about
>   whether this is possible or not.  If macros can be recursive, can anyone
>   please give me an example for supporting the claim?

>A macro is, at some time, expanded.  It's just a template for a function, an
>idea, not a function per se.

No, a macro >is< a function, that happens to be called by the
interpreter, or compiler, on a piece of code.  It returns another
piece of code.  There are no real restrictions on the function
definition of a macro.  That is, macro definition can certainly be
recursive.

But I don't think that's what he's asking.  

(I'm a little confused about the fact that this is an exam question.
Is someone trying to get an answer for a question on a take home
exam?  Net ethics?  I hope this isn't the case.)

Anyway, I assume he's asking whether a macro can be >expanded<
recursively.  Here too the answer is yes.  The result of a macro
expansion is again macroexpanded, so the behavior of a macro is
essentially unlimited.  (As long as the expansion eventually
terminates, that is).

Some mildy bizarre recursive macro examples follow:

(defmacro fibn-inline (n)
  (if (< n 2)
      1
      `(+ (fibn-inline ,(- n 1))
          (fibn-inline ,(- n 2)))))

Or 

(defmacro unroll (repeat-count form &rest forms)
  (if (zerop repeat-count)
      (cons 'progn forms)
      `(unroll ,(1- repeat-count) ,form ,form ,@forms))) 

>Now recursivity demands that one at some time prior to application of the
>function need not know how many times the function will call itself.  A macro
>must know that.  Hence, a macro can only be tail-recursive (i. e. an implied
>for).  Macros in TeX, as an example, are not recursive. 

The first example above isn't tail recursive.

>Now if the macro could calculate its number of expansions during calculation,
>there still would have to be an effective algorithm that could do that _prior_
>to expansion.

>Some of my assumptions here are ...loose... I eagerly await being corrected. 

>Rolf Lindgren		| 	"The opinions expressed above are 
>616 Bjerke Studentheim	|  	 not necessarily those of anyone"	
>N-0589 OSLO 5		|             rolfl@hedda.uio.no 

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".  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.  Other than this idea,
he has not provided any concrete evidence that it cannot be done.
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?

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

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".  When I tried to tackle that question I

[stuff deleted]

I hate to play the net.cop here, but this guy is obviously looking for the
answer to some assignment.

>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

[more stuff deleted]

The best way to really learn this stuff is to TRY IT!  Lisp is the most
interactive language in the world.  After a couple of answers were posted,
you should have jumped on the computer and checked them out instead of 
asking for clarification.

------------------------------------------------------------------------------
Dan Corbett
Dept. of Computer Science
University of Technology, Sydney
Sydney, New South Wales, Australia
------------------------------------------------------------------------------

i must admit that i did not understand all of what 
 rolfl@hedda.uio.no (Rolf Lindgren) intended in
 <ROLFL.91May16102939@hedda.uio.no>,
but, since two weeks have now passed since the date of the original posting,
i don't feel any qualms about correcting what appears to have been an
erroneous claim. to wit:
 " Hence, a macro can only be tail-recursive (i. e. an implied for)."

there are two senses in which a macro might be recursive:
 a) either the first-pass expansion contains another instance of the same
    form, or
 b) the code which produces the expansion contains an instance of that
    form,

i do not believe that tail-recursion figures in the matter. for example:
 
(defmacro and-inwards (&rest forms)
    (if (consp forms)
	`(if (and-inwards ,@(butlast forms))
	  ,@(last forms))
	(if (null forms)
	    t
	    forms)))

is recursive in the sense of (a) and is effective, while

(defmacro or-backwards (&rest forms)
    (or-backwards (and (consp forms) `(or ,@forms)) nil))

though tail recursive in the sense of (b), results in infinite recursion.

yours.
james.