<P>
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 2 ch 12: Macros</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 2:
<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT
<H1>Macros</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls2.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/v2ch12.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v2-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v2ch11/v2ch11.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v2ch13/v2ch13.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-2">MIT
Press web page for <CITE>Computer Science Logo Style</CITE></A>
</TABLE></TABLE>
<HR>
<P>I mentioned that the versions of <CODE>for</CODE> and <CODE>foreach</CODE> shown in
Chapter 10 don't work if their instruction templates include <CODE>stop</CODE> or
<CODE>output</CODE> commands. The problem is that we don't want, say, <CODE>foreach</CODE>
to stop; we want the procedure that <EM>invoked</EM> <CODE>foreach</CODE> to stop.
<P>What we need to fix this problem is a way for a subprocedure to <EM>make
its caller</EM> carry out some action. That is, we want something like <CODE>
run</CODE>, but the given expression should be run in a different context.
Berkeley Logo includes a mechanism, called <EM>macros,</EM> to allow
this solution. As I write this in 1996, no other version of Logo has
macros, although this capability is commonly provided in most versions
of Logo's cousin, the programming language Lisp.<SUP>*</SUP>
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Readers who are
familiar with Lisp macros should take note that Logo macros do not
prevent argument evaluation.</SMALL></BLOCKQUOTE></SMALL><P><H2><CODE>Localmake</CODE></H2>
<P>Before we fix <CODE>for</CODE> and <CODE>foreach</CODE>, and even before I explain in
detail what a macro is, I think it's best to start with a simple but
practical example. Throughout this book I've been using a command
called <CODE>localmake</CODE> that creates a local variable and assigns it a
value. The instruction
<P><PRE>localmake "fred 87
</PRE>
<P>is an abbreviation for the two instructions
<P><PRE>local "fred
make "fred 87
</PRE>
<P>Any version of Logo will allow those two separate instructions.
It's tempting to write a procedure combining them:
<P><PRE>to localmake :name :value ;; wrong!
local :name
make :name :value
end
</PRE>
<P>What's wrong with this solution? If you're not sure, define <CODE>localmake</CODE>
as above and try an example, like this:
<P><PRE>to trial
localmake "fred 87
print :fred
end
? <U>trial</U>
fred has no value in trial
[print :fred]
</PRE>
<P>When <CODE>trial</CODE> invokes <CODE>localmake</CODE>, a local variable named
<CODE>fred</CODE> is created <EM>inside the invocation of</EM> <CODE>localmake</CODE>!
That variable is then assigned the value 87. Then <CODE>localmake</CODE> returns
to <CODE>trial</CODE>, and <CODE>localmake</CODE>'s local variables disappear. Back in
<CODE>trial</CODE>, there is no variable named <CODE>fred</CODE>.
<P>Here's the solution. If <CODE>localmake</CODE> is an ordinary procedure, there's
no way it can create a local variable in its caller. So we have to define
<CODE>localmake</CODE> as a special kind of procedure:
<P><PRE>.macro localmake :name :value
output (list "local (word "" :name) "make (word "" :name) :value)
end
</PRE>
<P>The command <CODE>.macro</CODE> is like <CODE>to</CODE>, except that the
procedure it defines is a macro instead of an ordinary procedure.
(It's a Logo convention that advanced primitives that could be
confusing to beginners have names beginning with a period.)
<P>It's a little hard to read exactly what this procedure does, so for
exploratory purposes I'll define an ordinary procedure with the same body:
<P><PRE>to lmake :name :value
output (list "local (word "" :name) "make (word "" :name) :value)
end
? <U>show lmake "fred 87</U>
[local "fred make "fred 87]
</PRE>
<P>As you see from the example, <CODE>lmake</CODE> outputs a list
containing the instructions that we would like its caller to carry out.
<P>The macro <CODE>localmake</CODE> outputs the same list of instructions. But,
because <CODE>localmake</CODE> is a macro, that output is then <EM>evaluated</EM>
by the procedure that called <CODE>localmake</CODE>. If <CODE>trial</CODE> is run
using the macro version of <CODE>localmake</CODE> instead of the ordinary procedure
version that didn't work, the effect is as if <CODE>trial</CODE> contained a <CODE>
local</CODE> instruction and a <CODE>make</CODE> instruction in place of the one
<CODE>localmake</CODE> invocation. (If you defined the incorrect version of
<CODE>localmake</CODE>, you can say
<P><PRE>erase "localmake
</PRE>
<P>and then the official version will be reloaded from the library
the next time you use it.)
<P>You may find the expression <CODE>(word "" :name)</CODE> that appears twice
in the definition of <CODE>localmake</CODE> confusing. At first glance, it
seems that there is already a quotation mark in the first input to
<CODE>localmake</CODE>, namely, <CODE>"fred</CODE>. But don't forget that that quotation
mark is not part of the word! For example, when you say
<P><PRE>print "fred
</PRE>
<P>Logo doesn't print a quotation mark. What the quotation mark
means to Logo is "use the word that follows as the value for this input,
rather than taking that word as the name of a procedure and invoking that
procedure to find the input value." In this example, the first input
to <CODE>localmake</CODE> is the word <CODE>fred</CODE> itself, rather than the result
of invoking a procedure named <CODE>fred</CODE>. If we want to construct an
instruction such as
<P><PRE>local "fred
</PRE>
<P>based on this input, we must put a quotation mark in front of
the word explicitly.
<P>In fact, so far I've neglected to deal with the fact that a similar
issue about quotation may arise for the value being assigned to the
variable. In the <CODE>trial</CODE> example I used the value 87, a number,
which is <EM>self-evaluating;</EM> when a number is typed into Logo as
an expression, the number itself is the value of the expression.
But if the value is a non-numeric word, then a quotation mark must be
used for it, too. The version of <CODE>localmake</CODE> shown so far would
fail in a case like
<P><PRE>localmake "greeting "hello
</PRE>
<P>because the macro would return the list
<P><PRE>[local "greeting make "greeting hello]
</PRE>
<P>which, when evaluated, would try to invoke a procedure named
<CODE>hello</CODE> instead of using the word itself as the desired value.
<P>The most straightforward solution is to write a procedure that will
include a quotation mark only when it's needed:
<P><PRE>.macro localmake :name :value
output (list "local (quoted :name) "make (quoted :name) (quoted :value))
end
to quoted :thing
if numberp :thing [output :thing]
if listp :thing [output :thing]
output word "" :thing
end
</PRE>
<P>A somewhat less obvious solution, but one I find more appealing, is to
avoid the entire issue of quotation by putting the inputs to <CODE>make</CODE>
in a list, which we can do by using <CODE>apply</CODE>:
<P><PRE>.macro localmake :name :value
output (list "local (word "" :name) "apply ""make (list :name :value))
end
</PRE>
<P>On the other hand, it may take some thinking to convince
yourself that the <CODE>""make</CODE> in that version is correct!
<P>
<P><H2>Backquote</H2>
<P>Even a simple macro like <CODE>localmake</CODE> is very hard to read, and hard
to write correctly, because of all these invocations of <CODE>list</CODE> and <CODE>
word</CODE> to build up a structure that's partly constant and partly variable.
It would be nice if we could use a notation like
<P><PRE>[local "NAME apply "make [NAME VALUE]]
</PRE>
<P>for an "almost constant" list in which only the words in
capital letters would be replaced by values of variables.
<P>
<P>That particular notation can't work, because in Logo the case of letters
doesn't matter when a word is used as the name of something. But we do
have something almost as good. We can say
<P><PRE>`[local ,[word "" :name] apply "make [,[:name] ,[:value]]]
</PRE>
<P>The first character in that line, before the opening bracket,
is a <EM>backquote,</EM> which is probably near the top left corner
of your keyboard. To Logo, it's just an ordinary character, and happens
to be the name of a procedure in the Berkeley Logo library. The list
that follows the backquote above is the input to the procedure.
<P>What the <CODE>`</CODE> procedure does with its input list is to make a copy,
but wherever a word containing only a comma (<CODE>,</CODE>) appears, what
comes next must be a list, which is <CODE>run</CODE> to provide the value
for that position in the copy. I've put the commas right next to the
lists that follow them, but this doesn't matter; whenever Logo sees
a bracket, it delimits the words on both sides of the bracket, just as
if there were spaces around the bracket.
<P>So if <CODE>:name</CODE> has the value <CODE>fred</CODE> and <CODE>:value</CODE> has the value 87,
then this sample invocation of <CODE>`</CODE> has the value
<P><PRE>[local "fred apply "make [fred 87]]
</PRE>
<P>Like macros, backquote is a feature that Berkeley Logo borrows from Lisp.
It's not hard to implement:
<P><PRE>to ` :backq.list
if emptyp :backq.list [output []]
if equalp first :backq.list ", ~
[output fput run first butfirst :backq.list
` butfirst butfirst :backq.list]
if equalp first :backq.list ",@ ~
[output sentence run first butfirst :backq.list
` butfirst butfirst :backq.list]
if wordp first :backq.list ~
[output fput first :backq.list ` butfirst :backq.list]
output fput ` first :backq.list ` butfirst :backq.list
end
</PRE>
<P>This procedure implements one feature I haven't yet described. If the
input to <CODE>`</CODE> contains the word <CODE>,@</CODE> (comma atsign), then the
next member of the list must be a list, which is <CODE>run</CODE> as for comma,
but the <EM>members</EM> of the result are inserted in the output, instead
of the result as a whole. Here's an example:
<P><PRE>? <U>show `[start ,[list "a "b] middle ,@[list "a "b] end]</U>
[start [a b] middle a b end]
</PRE>
<P>
Using backquote, we could rewrite <CODE>localmake</CODE> a little more readably:
<P><PRE>.macro localmake :name :value
output `[local ,[word "" :name] apply "make [,[:name] ,[:value]]]
end
</PRE>
<P>In practice, though, I have to admit that the Berkeley Logo
library doesn't use backquote in its macro definitions because it's
noticeably slower than constructing the macro with explicit calls to <CODE>
list</CODE> and <CODE>word</CODE>.
<P>By the way, this implementation of backquote isn't as complex as some
Lisp versions. Most importantly, there is no provision for <EM>nested</EM>
backquotes, that is, for an invocation of backquote within the input
to backquote. (Why would you want to do that? Think about a macro whose
job is to generate a definition for another macro.)
<P><H2>Implementing Iterative Commands</H2>
<P>It's time to see how macros can be used to implement iterative control
structures like <CODE>for</CODE> and <CODE>foreach</CODE> correctly. I'll concentrate
on <CODE>foreach</CODE> because it's simpler to implement, but the same ideas
apply equally well to <CODE>for</CODE>.
<P>Perhaps the most obvious approach is to have the <CODE>foreach</CODE> macro
output a long instruction list in which the template is applied to each
member of the list. That is, if we say
<P><PRE>foreach [a b c] [print ?]
</PRE>
<P>then the <CODE>foreach</CODE> macro should output the list
<P><PRE>[print "a print "b print "c]
</PRE>
<P>To achieve precisely this result we'd have to look through
the template for question marks, replacing each one with a possibly
quoted datum. Instead it'll be easier to generate the uglier but
equivalent instruction list
<P><PRE>[apply [print ?] [a] apply [print ?] [b] apply [print ?] [c]]
</PRE>
<P>this way:
<P><PRE>.macro foreach :data :template
output map.se [list "apply :template (list ?)] :data
end
</PRE>
<P>(To simplify the discussion, I'm writing a version of <CODE>foreach</CODE>
that only takes two inputs. You'll see in a moment that the implementation
will be complicated by other considerations, so I want to avoid unnecessary
complexity now. At the end I'll show you the official, complete
implementation.)
<P>This version works correctly, and it's elegantly written. We could stop
here. Unfortunately, this version is inefficient, for two reasons. First,
it uses another higher order procedure, <CODE>map.se</CODE>, to construct the list of
instructions to evaluate. Second, for a large data input, we construct
a very large instruction list, using lots of computer memory, just so that
we can evaluate the instructions once and throw the list away.
<P>Another approach is to let the <CODE>foreach</CODE> macro invoke itself recursively.
This is a little tricky; you'll see that <CODE>foreach</CODE> does not actually
invoke itself within itself. Instead, it constructs an instruction list
that contains another use of <CODE>foreach</CODE>. For example, the instruction
<P><PRE>foreach [a b c] [print ?]
</PRE>
<P>will generate the instruction list
<P><PRE>[apply [print ?] [a] foreach [b c] [print ?]]
</PRE>
<P>Here's how to write that:
<P><PRE>.macro foreach :data :template
output `[apply ,[:template] [,[first :data]]
foreach ,[butfirst :data] ,[:template]]
end
</PRE>
<P>In this case the desired instruction list is long enough
so that I've found it convenient to use the backquote notation to
express my intentions. If you prefer, you could say
<P><PRE>.macro foreach :data :template
output (list "apply :template (list (first :data))
"foreach (butfirst :data) :template)
end
</PRE>
<P>This implementation (in either the backquote version or
the explicit list constructor version) avoids the possibility of
constructing huge instruction lists; the constructed list has only
the computation for the first datum and a recursive <CODE>foreach</CODE> that
handles the entire rest of the problem.
<P>But this version is still slower than the non-macro implementation
of <CODE>foreach</CODE> given in Chapter 10. Constructing an instruction
list and then evaluating it is just a slower process than simply doing
the necessary computation within <CODE>foreach</CODE> itself. And that
earlier approach works fine unless the template involves <CODE>stop</CODE>,
<CODE>output</CODE>, or <CODE>local</CODE>. We could have our cake and eat it too if
we could find a way to use the non-macro approach, but notice when
the template tries to stop its computation. This version is quite a bit
trickier than the ones we've seen until now:
<P><PRE>.macro foreach :data :template
catch "foreach.catchtag ~
[output foreach.done runresult [foreach1 :data :template]]
output []
end
to foreach1 :data :template
if emptyp :data [throw "foreach.catchtag]
apply :template (list first :data)
.maybeoutput foreach1 butfirst :data :template
end
to foreach.done :foreach.result
if emptyp :foreach.result [output [stop]]
output list "output quoted first :foreach.result
end
</PRE>
<P>To help you understand how this works, let's first consider what happens
if the template does not include <CODE>stop</CODE> or <CODE>output</CODE>. In that
case, the program structure is essentially this:
<P><PRE>.macro simpler.foreach :data :template
catch "foreach.catchtag ~
[this.stuff.never.invoked run [simpler.foreach1 :data :template]]
output []
end
to simpler.foreach1 :data :template
if emptyp :data [throw "foreach.catchtag]
apply :template (list first :data)
simpler.foreach1 butfirst :data :template
end
</PRE>
<P>The instruction list that's evaluated by the <CODE>catch</CODE> runs
a smaller instruction list that invokes <CODE>simpler.foreach1</CODE>. That
procedure is expected to output a value, which is then used as the input
to some other computation (namely, <CODE>foreach.done</CODE> in the actual version).
But when <CODE>simpler.foreach1</CODE> reaches its base case, it doesn't output
anything; it <CODE>throw</CODE>s back to the instruction after the <CODE>catch</CODE>,
which outputs an empty list. So all of the work of <CODE>foreach</CODE> is done
within these procedures; the macro outputs an empty instruction list, which
is evaluated by the caller of <CODE>foreach</CODE>, but that evaluation has no
effect.
<P>Now forget about the <CODE>simpler</CODE> version and return to the actual
<CODE>foreach</CODE>. What if the template carries out a <CODE>stop</CODE> or <CODE>
output</CODE>? If that happens, <CODE>foreach1</CODE> will never reach its base
case, and will therefore not <CODE>throw</CODE>. It will either stop or
output a value. The use of <CODE>.maybeoutput</CODE> in <CODE>foreach1</CODE> is
what makes it possible for <CODE>foreach1</CODE> to function either as a command
(if it stops) or as an operation (if it outputs) without causing an error
when it invokes itself recursively. If the recursive invocation stops,
so does the outer invocation. If the recursive invocation outputs a value,
the outer invocation outputs that value.
<P><CODE>Foreach</CODE> invoked <CODE>foreach1</CODE> using Berkeley Logo's <CODE>runresult</CODE> primitive
operation. <CODE>Runresult</CODE> is just like <CODE>run</CODE>, except that it always
outputs a value, whether or not the computation that it runs produces
a value. If so, then <CODE>runresult</CODE> outputs a one-member list containing
the value. If not, then <CODE>runresult</CODE> outputs an empty list.
<P>The output from <CODE>runresult</CODE> is used as input to <CODE>foreach.done</CODE>,
whose job is to construct an instruction list as the overall output from
the <CODE>foreach</CODE> macro. If the input to <CODE>foreach.done</CODE> is empty,
that means that the template included a <CODE>stop</CODE>, and so <CODE>foreach</CODE>
should generate a <CODE>stop</CODE> instruction to be evaluated by its caller.
If the input isn't empty, then the template included an <CODE>output</CODE>
instruction, and <CODE>foreach</CODE> should generate an <CODE>output</CODE> instruction
as its return value.
<P>This version is quite fast, and handles <CODE>stop</CODE> and <CODE>output</CODE>
correctly. It does not, however, handle <CODE>local</CODE> correctly; the
variable will be local to <CODE>foreach1</CODE>, not to the caller. It was
hard to decide which version to use in the Berkeley Logo library, but
slowing down every use of <CODE>foreach</CODE> seemed too high a price to pay
for <CODE>local</CODE>. That's why, for example, procedure <CODE>onegame</CODE> in
the solitaire program of Chapter 4 includes the instructions
<P><PRE>local map [word "num ?] :numranks
foreach :numranks [make word "num ? 4]
</PRE>
<P>instead of the more natural
<P><PRE>foreach :numranks [localmake word "num ? 4]
</PRE>
<P>That single instruction would work with the first implementation
of <CODE>foreach</CODE> in this chapter, but doesn't work with the actual
Berkeley Logo implementation!
<P><H2>Debugging Macros</H2>
<P>It's easy to make mistakes when writing a macro, because it's hard to keep
straight what has to be quoted and what doesn't, for example. And it's
hard to debug a macro, because you can't easily see the instruction list
that it outputs. You can't say
<P><PRE>show foreach ...
</PRE>
<P>because the output from <CODE>foreach</CODE> is <EM>evaluated,</EM> not
passed on to <CODE>show</CODE>.
<P>One solution is to trace the macro.
<P><PRE>? <U>trace "foreach</U>
? <U>foreach [a b c] [print ?]</U>
( foreach [a b c] [print ?] )
a
b
c
foreach outputs []
? <U>foreach [a b 7 c] [if numberp ? [stop] print ?]</U>
( foreach [a b 7 c] [if numberp ? [stop] print ?] )
a
b
foreach outputs [stop]
Can only use stop inside a procedure
</PRE>
<P>In this case, I got an error message because, just as the
message says, it doesn't make sense to use <CODE>stop</CODE> in a template
unless this invocation of <CODE>foreach</CODE> is an instruction inside
a procedure definition. Here I invoked <CODE>foreach</CODE> directly at
the Logo prompt.
<P>The Berkeley Logo library provides another solution, a
<CODE>macroexpand</CODE> operation that takes as its input a Logo expression beginning
with the name of a macro. It outputs the expression that the macro would
output, without causing that expression to be evaluated:
<P><PRE>? <U>show macroexpand [foreach [a b 7 c] [if numberp ? [stop] print ?]]</U>
a
b
[stop]
</PRE>
<P>This time I didn't get an error message, because the instruction
list that <CODE>foreach</CODE> outputs wasn't actually evaluated; it became the
input to <CODE>show</CODE>, which is why it appears at the end of the example.
<P><CODE>Macroexpand</CODE> works by using <CODE>define</CODE> and <CODE>text</CODE> to define,
temporarily, a new procedure that's just like the macro it wants to expand,
but an ordinary procedure instead of a macro:
<P><PRE>to macroexpand :expression
define "temporary.macroexpand.procedure text first :expression
...
end
</PRE>
<P>You might enjoy filling in the rest of this procedure, as an
exercise in advanced Logo programming, before you read the version
in the library.
<P>(What if you want to do the opposite, defining a macro with the same text
as an ordinary procedure? Berkeley Logo includes a <CODE>.defmacro</CODE> command,
which is just like <CODE>define</CODE> except that the resulting procedure is a
macro. We don't need two versions of <CODE>text</CODE>, because the text of a
macro looks just like the text of an ordinary procedure. To tell the
difference, there is a primitive predicate <CODE>macrop</CODE> that takes a word
as input, and outputs <CODE>true</CODE> if that word is the name of a macro.)
<P><H2>The Real Thing</H2>
<P>Here is the complete version of <CODE>foreach</CODE>, combining the macro
structure developed in this chapter with the full template flexibility
from Chapter 10.
<P><PRE>.macro foreach [:foreach.inputs] 2
catch "foreach.catchtag ~
[output foreach.done runresult [foreach1 butlast :foreach.inputs
last :foreach.inputs 1]]
output []
end
to foreach1 :template.lists :foreach.template :template.number
if emptyp first :template.lists [throw "foreach.catchtag]
apply :foreach.template firsts :template.lists
.maybeoutput foreach1 butfirsts :template.lists ~
:foreach.template :template.number+1
end
to foreach.done :foreach.result
if emptyp :foreach.result [output [stop]]
output list "output quoted first :foreach.result
end
</PRE>
<P>And here, without any discussion, is the actual library version of
<CODE>for</CODE>. This, too, combines the ideas of this chapter with
those of Chapter 10.
<P><PRE>.macro for :for.values :for.instr
localmake "for.var first :for.values
localmake "for.initial run first butfirst :for.values
localmake "for.final run item 3 :for.values
localmake "for.step forstep
localmake "for.tester (ifelse :for.step < 0
[[(thing :for.var) < :for.final]]
[[(thing :for.var) > :for.final]])
local :for.var
catch "for.catchtag [output for.done runresult [forloop :for.initial]]
output []
end
to forloop :for.initial
make :for.var :for.initial
if run :for.tester [throw "for.catchtag]
run :for.instr
.maybeoutput forloop ((thing :for.var) + :for.step)
end
to for.done :for.result
if emptyp :for.result [output [stop]]
output list "output quoted first :for.result
end
to forstep
if equalp count :for.values 4 [output run last :for.values]
output ifelse :for.initial > :for.final [-1] [1]
end
</PRE>
<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v2ch11/v2ch11.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v2ch13/v2ch13.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>