cs16011@athena.ecs.csus.edu (05/16/91)
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?
pazzani@pan.ics.uci.edu (Michael Pazzani) (05/16/91)
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].
rolfl@hedda.uio.no (Rolf Lindgren) (05/16/91)
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 michaelg@neon.Stanford.EDU (Michael Greenwald) (05/17/91)
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
cs16011@athena.ecs.csus.edu (05/17/91)
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?
michaelg@neon.Stanford.EDU (Michael Greenwald) (05/18/91)
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
janson@athena.mit.edu (James A Anderson) (06/03/91)
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.