Recursive Macros
Theo R.
macros? Consider the following. I'm trying to see if we can use
patterns to generate a factorial. Its probably not the best candidate
for a macro, but its mainly to improve my understanding of macros.
;; First Attempt
(define-syntax fact
(syntax-rules ()
((_ 0) 0)
((_ 1) 1)
((_ n) (* n (fact (- n 1))))))
;; Second Attempt
(define-syntax fact
(syntax-rules ()
((_ 0) 0)
((_ 1) 1)
((_ n) '(let ((m (- n 1)))
(* n (fact m))))))
;; Third Attempt
(define-syntax fact
(syntax-rules ()
((_ 0) 0)
((_ 1) 1)
((_ n) '(let ((m (- n 1)))
(* n (fact m))))))
(display (fact 0))
(newline)
(display (fact 1))
(newline)
(display (fact 2))
(newline)
In the first 2 cases, the scheme interpreter never comes back. In the
3rd case, it prints
0
1
(let ((m (- 2 1))) (* 2 (fact m)))
So, m has not been evaluated. Is there anyway to force the evaluation
in the macro itself?
--
Theo
Ramana
Your Second Attempt looks the same as your Third Attempt. I'm guessing
it didn't have the quote.
Here's one way to think about syntax-rules macros. Before evaluating
your code, each call to a macro in your code is replaced with the code
in the macro template corresponding to its pattern. After all that
code replacement is finished, the resulting code is evaluated. In the
case of your examples:
(display (fact 0)) contains a macro call (fact 0) which in all your
attempts is replaced by the template 0. Therefore the final code to be
evaluated is (display 0) (which prints the 0).
Similarly (display (fact 1)) contains a macro call (fact 1) and in all
cases the code ends up as (display 1).
(display (fact 2)) contains a macro call (fact 2). In your first
attempt this is replaced yielding (display (* 2 (fact (- 2 1)))). This
code is not yet ready for evaluation because it contains another macro
call, namely (fact (- 2 1)). This matches the third pattern since n is
a "catch-all" pattern variable (unlike 0 and 1 which are match-only
constants). Therefore the resulting code is (display (* 2 (* (- 2 1)
(fact (- (- 2 1) 1)))))). However this again is not ready for
evaluation since it contains another call to fact. You see an infinite
loop because your code is never evaluated: macro expansion is looping.
In your second version (assuming it doesn't have a quote) you run into
a similar problem.
In your third version (display (fact 2)) becomes (display (quote (let
((m (- 2 1))) (* 2 (fact m))))) which is ready for evaluation (the
apparent call to fact is actually just a symbol in a quoted list).
display prints the list. (Don't be put off by my use of the quote
form. The code after macro expansion and before evaluation can
equivalently be written (display '(let ((m (- 2 1))) (* 2 (fact
m))))).
Theo R.
expansion.
>
> Here's one way to think about syntax-rules macros. Before evaluating
> your code, each call to a macro in your code is replaced with the code
> in the macro template corresponding to its pattern. After all that
> code replacement is finished, the resulting code is evaluated. In the
> case of your examples:
>
> (display (fact 0)) contains a macro call (fact 0) which in all your
> attempts is replaced by the template 0. Therefore the final code to be
> evaluated is (display 0) (which prints the 0).
>
> Similarly (display (fact 1)) contains a macro call (fact 1) and in all
> cases the code ends up as (display 1).
>
> (display (fact 2)) contains a macro call (fact 2). In your first
> attempt this is replaced yielding (display (* 2 (fact (- 2 1)))). This
> code is not yet ready for evaluation because it contains another macro
> call, namely (fact (- 2 1)). This matches the third pattern since n is
> a "catch-all" pattern variable (unlike 0 and 1 which are match-only
> constants). Therefore the resulting code is (display (* 2 (* (- 2 1)
> (fact (- (- 2 1) 1)))))). However this again is not ready for
> evaluation since it contains another call to fact. You see an infinite
> loop because your code is never evaluated: macro expansion is looping.
As I thought as well. So, is there no way to make a macros refer to
themselves and have a valid base class?
>
> In your second version (assuming it doesn't have a quote) you run into
> a similar problem.
>
> In your third version (display (fact 2)) becomes (display (quote (let
> ((m (- 2 1))) (* 2 (fact m))))) which is ready for evaluation (the
> apparent call to fact is actually just a symbol in a quoted list).
> display prints the list. (Don't be put off by my use of the quote
> form. The code after macro expansion and before evaluation can
> equivalently be written (display '(let ((m (- 2 1))) (* 2 (fact
> m))))).
--
Theo
Pascal J. Bourguignon
> I'm trying to understand macros. Is it possible to have recursive
> macros?
It is perfectly possible to define recursive macros. The following
problem you have is not with recursive macros but with mixing run-time
with macro-expansion time.
Here is an example of a recursive macro:
(define-syntax compose
(syntax-rules ()
((_ f) f)
((_ f g ...) (lambda (x) (f ((compose g ...) x))))))
((compose (lambda (x) (* 2 x))
(lambda (x) (+ 1 x))
(lambda (x) (* x x))) 2)
--> 10
> Consider the following. I'm trying to see if we can use
> patterns to generate a factorial. Its probably not the best candidate
> for a macro, but its mainly to improve my understanding of macros.
> [...]
> So, m has not been evaluated. Is there anyway to force the evaluation
> in the macro itself?
No, there is no way to force the evaluation of m in the macro, because
the value of m will be known next week (when the user will enter its
value), while the macro is being expanded by the compiler right now.
But as soon as time travel technology will be practicable, we will
include it in scheme to be able to do so.
In the meantime, all you could do is to check that m is a literal
integer, and in which case, calls at macroexpansion time a factorial
function to substitute the result, and if it is a run-time expression,
then defer to run-time.
I'm not too good with hygienic macros, so I'll show you as an example
of what I mean with defmacro:
(defun fact* (x) (if (< x 1) 1 (* x (fact* (- x 1)))))
(defmacro fact (m)
(if (integer? m) ; macro-expansion time
(fact* m) ; macro-expansion time
`(fact* ,m))) ; run-time
--
__Pascal Bourguignon__
leppie
>
> As I thought as well. So, is there no way to make a macros refer to
> themselves and have a valid base class?
You are dealing with syntax, not values.
(fact m) will never reduce to either base case.
You will either need to find a way to represent computations in syntax-
rules, or use another macro-expander.
Cheers
leppie
Aaron W. Hsu
>As I thought as well. So, is there no way to make a macros refer to
>themselves and have a valid base class?
As some people have already pointed out, the input to a macro is *not*
the actual values of the syntax. syntax-rules is turing complete in that
you can transform the input into just about any other input, but this
doesn't mean that you can evaluate that code using the macro system.
There are other ways of doing this that allow you to manage the order of
evaluation and such. In other words, use macros for syntactic
transformations, and functions for actually computing.
On the other hand, things like CPS macros do have some interesting
capabilities. There are also procedural macro systems that maintain
hygiene, like SYNTAX-CASE, which can do more than SYNTAX-RULES can.
SYNTAX-CASE is standardized in R6RS now, and if you want a little more
from your macro system, you can look at it. However, it is still
operating at the syntactic level, and you're not evaluating your code,
just transforming it.
Aaron W. Hsu
Aaron W. Hsu
>I'm trying to understand macros. Is it possible to have recursive
>macros? Consider the following. I'm trying to see if we can use
>patterns to generate a factorial. Its probably not the best candidate
>for a macro, but its mainly to improve my understanding of macros.
The main problem you are having is in the distinction between how macros
work and what they do, compared to procedures. Procedures do computating
on Scheme values. MAcros operate on Scheme syntax. That is, one
transforms different Scheme values into other values, while macros
transform Scheme syntax into other Scheme syntax.
With this in mind, can you discover a transformation that continues to
reduce the term m in (factorial m)? Not really, because M is just a
literal identifier. You can't evaluate it, since that happens way down
the road.
On the other hand, with a slightly more powerful macro system and some
limitations on your input, you can do something kinda cool.
Let's say we have a macro that, given another macro and a number, can
expand into that other macro and an encoding of the number. In that
case, it is possible to do the actual factorial example purely in
syntax-rules. In other words, we encode the number in the syntax. This
requires the extra bootstrapping of a procedural macro system, but this
illustrates something to you, I hope. This is all standard R6RS Scheme.
#! /usr/bin/env scheme-script
(import (rnrs base) (rnrs syntax-case) (rnrs io simple))
(define-syntax factorial
(syntax-rules ()
[(_) 0]
[(_ tick) 1]
[(_ tick rest ...)
(* (decode tick rest ...) (factorial rest ...))]))
(define-syntax decode
(syntax-rules ()
[(_) 0]
[(_ tick) 1]
[(_ tick rest ...) (+ 1 (decode rest ...))]))
(define-syntax expand/encoded
(lambda (x)
(define (make-ticks count)
(if (zero? count)
'()
(cons #'dummy (make-ticks (- count 1)))))
(syntax-case x ()
[(_ op val)
(let ([count (syntax->datum #'val)])
(assert (and (integer? count) (positive? count)))
(with-syntax ([(ticks ...) (make-ticks count)])
#'(op ticks ...)))])))
(display (expand/encoded factorial 5))
(newline)
So, here, you can see we use the more sophisticated SYNTAX-CASE macro
system to initial extract a literal value from the syntax (which must
already exist in the synstax), and then we use a syntax/expand-time
procedure 'make-ticks' to convert that literal value into a list of
ticks the length of which equals the literal value. Given this encoding
of a number, syntax-rules can then perform all the operations it needs
to do, in order to expand into an expression that will evaluate into
120. It's not efficient, but this should give you some idea of macros,
and it's a good exercise.
Notice that the syntax-rules factorial doesn't evaluate anything, it
just transforms its input into something else, which later on will be
evaluated.
Aaron W. Hsu
Ramana
And if you want to ignore syntax-case for a while, then you can use
the pure syntax-rules parts of Aaron's example by encoding the number
yourself. For example to calculate the factorial of 5 by macro
expansion:
(factorial tick tick tick tick tick)
--> after expansion
(* (+ '1 (+ '1 (+ '1 (+ '1 '1))))
(* (+ '1 (+ '1 (+ '1 '1)))
(* (+ '1 (+ '1 '1)) (* (+ '1 '1) '1))))
--> after evaluation
120