9.2. Evaluating Macros
Consider how PScm::Closure::Function::Apply() works. It
evaluates its arguments in the passed-in environment then gives
the results to its parent PScm::Closure::_apply() method.
That _apply() method extends the
environment that was captured when the closure was created with bindings
of those actual arguments to its formal arguments. Then it evaluates
its body in that extended environment and returns the result.
Here again is PScm::Closure::Function's Apply()
method:
39 sub Apply { 40 my ($self, $form, $env) = @_; 41 42 my $evaluated_args = $form->map_eval($env); 43 return $self->_apply($evaluated_args); 44 }
And here again is the private _apply() method in the base
PScm::Closure class:
17 sub _apply { 18 my ($self, $args) = @_; 19 20 my $extended_env = 21 $self->{env}->ExtendUnevaluated($self->{args}, $args); 22 return $self->{body}->Eval($extended_env); 23 }
Any implementation of macros will share something in common with this implementation of functions, but there will be differences. Obviously a macro should be passed its arguments unevaluated. That way it can perform whatever (list) operations it likes on that structure. Then when it returns a new form, it is that form that gets evaluated.
In fact it's as simple as that, and here's
the Apply() method for PScm::Closure::Macro:
55 sub Apply { 56 my ($self, $form, $env) = @_; 57 58 my $new_form = $self->_apply($form); 59 return $new_form->Eval($env); 60 }
Compare that with the Apply() method from
PScm::Closure::Function above.
Functions evaluate their arguments, then evaluate their body with those arguments bound. Macros don't evaluate their arguments, they evaluate their body with their unevaluated arguments bound, then they re-evaluate the result. This is quite subtle. Macros perform substitutions on their arguments, but the result of those substitutions must be subsequently evaluated for the macro to have had the desired effect.
To finish off this part of the implementation, we must remember
that in Section 5.3 we made closures printable,
and since macros are a new kind of closure, we must supply the supporting
_symbol() method in PScm::Closure::Macro for the
PScm::Closure::as_string() method to find. This _symbol() method
returns the symbol macro so that if a macro is printed
it will display as
(macro ‹args› ‹body›). Here's the
new PScm::Closure::Macro::_symbol() method.
62 sub _symbol { 63 PScm::Expr::Symbol->new('macro'); 64 }
9.2.1. Trying it out
Just for fun, let's take a look at how we might attack the problem
which introduced this section: implementing let in terms
of lambda. Remember that any let expression has an equivalent
lambda form, so here's a use of macro that translates one into
the other:
(let* ((mylet
(macro (bindings body)
(let* ((names (cars bindings))
(values (cadrs bindings)))
(cons (list (quote lambda) names body) values)))))
(mylet ((a 1)
(b 2))
(list a b)))
This code uses let* (remember we're pretending that we
don't have let) to bind mylet to a macro definition, then
it uses mylet in the body of the let*. It makes use of some
supporting functions that we'll define presently, but first let's try
to get a feel for what it is doing. As stated above, the symbol macro
introduces a macro definition. The arguments to mylet will be the
same as those to let, namely a list of bindings and a body to
execute with those bindings in place. It has to separate the bindings
(symbol-value pairs) into two lists, one of the symbols and one of the
values. It might be useful in the following discussion to refer
to Figure 9.1 which shows the internal structure
of the mylet form that we'll be rearranging.
mylet internal structure
The mylet macro uses a function cars to extract the car of each
binding (the symbol) into the list called names.
Here's the definition of cars:
(letrec (...
(cars
(lambda (lst)
(map car lst)))
...)
...)
It uses another yet to be defined function map, which
does the same as Perl's built in map: it applies a function
to each element of a list and returns a new list of the results23. map is surprisingly easy to implement
in PScheme:
(letrec ((map
(lambda (op lst)
(if lst
(cons (op (car lst))
(map op (cdr lst)))
())))
...)
It's a recursive function, hence the need for letrec to
bind it. Passed a function and list of zero or more bindings,
if the list is empty it returns the empty list, otherwise it cons-es
the result of calling the function on the car of the list with
to the result of calling itself on the rest (cdr) of the list.
So for example if lst is
((a 1) (b 2)), then (map car lst) would return the list
(a b), and that is exactly what the cars function does.
cadrs24 is very similar. It walks the
list collecting the second component of each sublist (the values of
the bindings). So for example given the list ((a 1) (b 2)),
cadrs will return the list (1 2).
(letrec (...
(cadrs
(lambda (lst)
(map (lambda (x) (car (cdr x))) lst)))
...)
...)
Again it makes use of map this time passing it an anonymous
function that will take the car of the cdr of its argument. This is
very much in the style of real Scheme programming now: constructing
lambda expressions on the fly and passing them to other functions as arguments,
I hope you are aquiring a taste for it. Anyway here's the whole mylet
definition plus some code that calls it.
(let* ((mylet
(letrec ((map
(lambda (op lst)
(if lst
(cons (op (car lst))
(map op (cdr lst)))
())))
(cars
(lambda (lst)
(map car lst)))
(cadrs
(lambda (lst)
(map (lambda (x) (car (cdr x))) lst))))
(macro (bindings body)
(let* ((names (cars bindings))
(values (cadrs bindings)))
(cons (list (quote lambda) names body)
values))))))
(mylet ((a 1)
(b 2))
(list a b)))
After collecting the names into one list and the values into
another, the mylet macro builds:
((lambda (‹names›) (‹body›)) ‹values›)
Where ‹names›, ‹body› and ‹values› are expanded using the appropriate magic:
(cons (list (quote lambda) names body) values)
A point worth noting is that the constructed mylet
macro is a true closure, since it has captured the definitions of
the cars and cadrs functions and executes in an outer
environment (the let*) where those functions are not visible.
9.2.2. An Improvement
The macro substitution system demonstrated so far is pretty crude,
after all it requires the programmer to directly manipulate low-level
list structures, rather than just supplying an “example” of how
the transformation is to be performed. In fact the topic of macro
expansion as provided by a full Scheme implementation is deserving of
a book to itself. Apart from the templating ability, there are also issues
of avoiding variable collision (so-called hygenic macros)
so that full Scheme macros are much closer to the idea of
C++'s inline functions than they are to C's
#define25.
However there is one simple addition that we can make, which will
greatly improve the usefulness of macros, and that involves an
extension to the quote special form that we introduced in
Section 8.1. If you remember quote
just returns its argument, preventing unwanted evaluation.
This already has proved useful in the construction of macros, as we have
seen above.
Now one perfect use of quote would be to provide
templates for macros, if we could arrange that parts
of the quoted template could be substituted before the quoted
template is returned. To that purpose we introduce a keyword
unquote which marks a section of a quoted form for
evaluation. Perhaps an example might make this clear:
> (let ((x "rain") > (y "spain") > (z "plain")) > (quote > (the (unquote x) > in (unquote y) > falls mainly on the (unquote z)))) (the "rain" in "spain" falls mainly on the "plain")
The let bindings bind x to the string "rain"
etc. That is not the important part. The important part is the body of the
let where the use of the unquote keyword allows evaluation
of the contained expressions (x etc.) despite their being inside
a quote.
How can this help us with macro definitions? Well in a big way!
consider this macro definition of a while loop:
(define while
(macro (test body)
(quote (letrec
((loop
(lambda ()
(if (unquote test)
(begin
(unquote body)
(loop))
()))))
(loop)))))
It uses a few features that aren't available yet, like
define and begin (which just executes one
expression after another), and it would seem to be in danger
of running out of stack, but I hope you can see that
essentially the quote and unquote
are doing all of the work building the body of the macro.
The quoted result is shown in bold, with the internal
substitutions unbolded again.
Implementing unquote is easy, but it's
a little different from the normal special forms and
primitives we've seen up to now. I've been careful to
only refer to it as a “keyword”, because it means
nothing special outside of a quoted expression.
We'll obviously have to change the way quote
works to make this happen, so lets start by looking at
the changed PScm::SpecialForm::Quote::Apply().
132 sub Apply { 133 my ($self, $form, $env) = @_; 134 return $form->first->Quote($env); 135 }
Rather than just returning its first argument, it now calls
a new method Quote() on it, passing Quote()
the current environment. Quote()
essentially just makes a copy of the expressions concerned,
but it keeps an eye out for unquote symbols.
Now this method
will be implemented in the PScm::Expr classes as follows:
The default Quote() in PScm::Expr
just returns $self:
41 sub Quote { $_[0] }
The Quote() in PScm::Expr::List::Pair
is where most of the decision making happens.
133 sub Quote { 134 my ($self, $env) = @_; 135 if ($self->[FIRST]->is_unquote) { 136 return $self->[REST]->first->Eval($env); 137 } else { 138 return $self->quote_rest($env); 139 } 140 }
On
Line 135
it checks to see if the first element of the list is
the symbol unquote (is_unquote.)
If it is then it evaluates the second element
in the current environment and returns it. If the first
element
is
not
unquote
then it hands over control to a helper routine
quote_rest().
Here's quote_rest().
142 sub quote_rest { 143 my ($self, $env) = @_; 144 return $self->Cons( 145 $self->[FIRST]->Quote($env), 146 $self->[REST]->quote_rest($env) 147 ); 148 }
It just walks the list, recursively, constructing a copy
as it goes by calling Quote() on each
element and calling Cons() on the quoted
subexpression and the result of the recursive call26.
The PScm::Expr::List::Null package
inherits Quote() from PScm::Expr,
which just returns $self,
and PScm::Expr also has a
quote_rest() method which also just returns
$self and usefully terminates the recursion
of the non-empty PScm::Expr::List quote_rest()
method.
43 sub quote_rest { $_[0] }
That just leaves that is_unquote()
method. Well since only a symbol could possibly be
unquote, we can put a default is_unquote()
method at the top of the expression type hierachy, in
PScm::Expr, which just returns false:
12 sub is_unquote { 0 }
Then for PScm::Expr::Symbol only, we override that
with a method that checks to see if its value()
is the string "unquote":
182 sub is_unquote { 183 my ($self) = @_; 184 return $self->value eq "unquote"; 185 }
That completes our re-implementation of quote
to allow the recognition of the unquote keyword,
but we're not quite done yet.
quote and unquote turn out to be so useful in
the definition of macros that PScheme provides shorthand
syntactic sugar for these forms. The construct
'‹expression› (note the single quote) gets expanded to
(quote ‹expression›), and similarily
the construct ,‹expression› with a leading comma
gets expanded to (unquote ‹expression›).
This is fairly easy to do, so let's see what changes we
need to make to the reader to make this happen.
First here's the changes to PScm::Read::_next_token().
66 sub _next_token { 67 my ($self) = @_; 68 69 while (!$self->{Line}) { 70 $self->{Line} = $self->{FileHandle}->getline(); 71 return undef unless defined $self->{Line}; 72 $self->{Line} =~ s/^\s+//s; 73 } 74 75 for ($self->{Line}) { 76 s/^\(\s*// && return PScm::Token::Open->new(); 77 s/^\)\s*// && return PScm::Token::Close->new(); 78 s/^\'\s*// && return PScm::Token::Quote->new(); 79 s/^\,\s*// && return PScm::Token::Unquote->new(); 80 s/^\.\s*// && return PScm::Token::Dot->new(); 81 s/^([-+]?\d+)\s*// 82 && return PScm::Expr::Number->new($1); 83 s/^"((?:(?:\\.)|([^"]))*)"\s*// && do { 84 my $string = $1; 85 $string =~ s/\\//g; 86 return PScm::Expr::String->new($string); 87 }; 88 s/^([^\s\(\)]+)\s*// 89 && return PScm::Expr::Symbol->new($1); 90 } 91 die "can't parse: $self->{Line}"; 92 }
The change is very simple. You can see that on
Lines 78–79
if it strips a leading quote or comma, it returns an equivalent token object.
Those new token types are both in PScm/Token.pm, here's
PScm::Token::Quote.
29 package PScm::Token::Quote; 30 31 use base qw(PScm::Token); 32 33 sub is_quote_token { 1 }
It inherits from PScm::Token and a default
is_quote_token() there returns false.
The equivalent PScm::Token::Unquote deliberately
inherits from PScm::Token::Quote rather than just
PScm::Token so it gets the overridden is_quote_token()
method, and supplies an additional is_unquote_token() method
returning true. Again a default is_unquote_token() in
PScm::Token returns false.
36 package PScm::Token::Unquote; 37 38 use base qw(PScm::Token::Quote); 39 40 sub is_unquote_token { 1 }
The upshot of this is that both PScm::Token::Quote
and PScm::Token::Unquote return true for is_quote_token(),
but only PScm::Token::Unquote returns true for
is_unquote_token(). Finally, let's see how the reader
PScm::Read::Read() makes use of these new token objects.
17 sub Read { 18 my ($self) = @_; 19 20 my $token = $self->_next_token(); 21 return undef unless defined $token; 22 23 if ($token->is_quote_token) { 24 my $expr = $self->Read; 25 die "syntax Error" 26 unless defined($expr) && $expr->is_expr; 27 return new PScm::Expr::List( 28 $token->is_unquote_token 29 ? new PScm::Expr::Symbol('unquote') 30 : new PScm::Expr::Symbol('quote'), 31 $expr 32 ); 33 } 34 35 if ($token->is_open_token) { 36 return $self->read_list(); 37 } else { 38 return $token; 39 } 40 }
The additional code on
Lines 23–33
checks to see if the token is a quote or unquote token, and if so
reads the next expression, checks that it is valid and returns a new
PScm::Expr::List containing the appropriate quote
or unquote symbol and the expression read afterwards.
The is_expr() method is defined to be true in PScm::Expr
and false in PScm::Token, and its use here stops dubious
constructs like “')”.
So we now have a convenient shorthand for quote and
unquote. To demonstrate it in action, here's that while
macro again, this time using the new tokens.
(define while
(macro (test body)
'(letrec
((loop
(lambda ()
(if ,test
(begin
,body
(loop))
()))))
(loop))))
We'll be making significant use of macro,
quote and unquote in subsequent chapters,
so it's worth familiarizing yourself now with this new
idiom27.
9.2.3. One Last Addition
Sometimes given a quoted expression, you'd really just like to have
it evaluated. It may have been passed as an argument, or it may have
been constructed in some other way. What you need is another round of
evaluation. This is supplied by the special form eval.
eval really does do just that. For example:
> (eval '(* 2 2)) 4
The quote stopped the first round of evaluation, but eval
got another try at it. Here's another example:
> (eval (list '* 4 4)) 16
eval is quite simple. It is a special form because it needs
access to an environment in which to perform the evaluation (remember
primitives have their arguments evaluated for them and so don't need an
environment.) It evaluates its first argument in the current environment
(special forms don't have their arguments evaluated for them,)
then it evaluates the result a second time, this time in the top-level
environment. Here's PScm::SpecialForm::Eval:
93 package PScm::SpecialForm::Eval; 94 95 use base qw(PScm::SpecialForm); 96 97 sub Apply { 98 my ($self, $form, $env) = @_; 99 $form->first()->Eval($env)->Eval($env->top); 100 }
You can see that the second round of evaluation is done in the
context of the top-level environment obtained by calling a new
method top() on the current environment. That top()
method is also very simple:
14 sub top { 15 my ($self) = @_; 16 if ($self->{parent}) { 17 return $self->{parent}->top; 18 } else { 19 return $self; 20 } 21 }
It just checks to see if it has a parent, calling top()
recursively on that if it has, and returning itself if it hasn't.
One thing to watch out for with eval: the code that
is evaluated is not a closure. Any variables in that code
will be looked up in the top-level environment, not the one where
the expression was constructed, nor the one that is current
when eval is called. For example:
> (let ((* -)) > (* 3 3)) 0 > (let ((* -)) > (eval '(* 3 3))) 9
Nonetheless eval is a useful tool in your kit, we'll
see it in action in later chapters.