I'm trying to understand the power of various macro systems more
clearly. Is this view correct:
+------------------------------------------------------+
| define | in terms of |
| this |---------------------------------------|
| | syntax-rules | syntax-case | defmacro |
| | | | +gensym |
|--------------+--------------+-------------+----------|
| syntax-rules | :-) | + | |
|--------------+--------------+-------------+----------|
| syntax-case | - | :-) | |
|--------------+--------------+-------------+----------|
| defmacro | - | + | :-) |
| +gensym | | | |
+------------------------------------------------------+
And what about the two gaps? No clear answer?
·············@yahoo.com (David Fisher) wrote:
>
> +------------------------------------------------------+
> | define | in terms of |
> | this |---------------------------------------|
> | | syntax-rules | syntax-case | defmacro |
> | | | | +gensym |
> |--------------+--------------+-------------+----------|
> | syntax-rules | :-) | + | |
> |--------------+--------------+-------------+----------|
> | syntax-case | - | :-) | |
> |--------------+--------------+-------------+----------|
> | defmacro | - | + | :-) |
> | +gensym | | | |
> +------------------------------------------------------+
>
> And what about the two gaps? No clear answer?
Whenever you compare the expressive power of two systems or
constructs, you have to formulate the question very carefully.
For example, you can write a preprocessor that translates C++
into Scheme, and vice versa. Does that make C++ and Scheme
equally expressive?
Here's what I think: You can definitely implement both
SYNTAX-RULES and SYNTAX-CASE using DEFMACRO + GENSYM, but I
doubt whether you can use DEFMACRO+GENSYM to implement a
SYNTAX-RULES that interacts properly with all correct
implementations of SYNTAX-CASE, and I doubt whether you can
use DEFMACRO+GENSYM to implement a SYNTAX-CASE that interacts
properly with all correct implementations of SYNTAX-RULES.
In other words, I think SYNTAX-RULES and SYNTAX-CASE need to
be defined together so they will play nice with each other.
If I'm right, what this implies for your question is that you
can't really separate the two blank boxes from each other.
Will
··········@verizon.net (William D Clinger) writes:
> ·············@yahoo.com (David Fisher) wrote:
>>
>> +------------------------------------------------------+
>> | define | in terms of |
>> | this |---------------------------------------|
>> | | syntax-rules | syntax-case | defmacro |
>> | | | | +gensym |
>> |--------------+--------------+-------------+----------|
>> | syntax-rules | :-) | + | |
>> |--------------+--------------+-------------+----------|
>> | syntax-case | - | :-) | |
>> |--------------+--------------+-------------+----------|
>> | defmacro | - | + | :-) |
>> | +gensym | | | |
>> +------------------------------------------------------+
>>
>> And what about the two gaps? No clear answer?
>
> Whenever you compare the expressive power of two systems or
> constructs, you have to formulate the question very carefully.
> For example, you can write a preprocessor that translates C++
> into Scheme, and vice versa. Does that make C++ and Scheme
> equally expressive?
>
> Here's what I think: You can definitely implement both
> SYNTAX-RULES and SYNTAX-CASE using DEFMACRO + GENSYM, but I
> doubt whether you can use DEFMACRO+GENSYM to implement a
> SYNTAX-RULES that interacts properly with all correct
> implementations of SYNTAX-CASE, and I doubt whether you can
> use DEFMACRO+GENSYM to implement a SYNTAX-CASE that interacts
> properly with all correct implementations of SYNTAX-RULES.
> In other words, I think SYNTAX-RULES and SYNTAX-CASE need to
> be defined together so they will play nice with each other.
>
> If I'm right, what this implies for your question is that you
> can't really separate the two blank boxes from each other.
I thought you could implement SYNTAX-RULES using SYNTAX-CASE. So why
not just implement SYNTAX-CASE on DEFMACRO+GENSYM and then
SYNTAX-RULES using that SYNTAX-CASE? I'd still call that implementing
SYNTAX-RULES with DEFMACRO+GENSYM.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> wrote:
> I thought you could implement SYNTAX-RULES using SYNTAX-CASE. So why
> not just implement SYNTAX-CASE on DEFMACRO+GENSYM and then
> SYNTAX-RULES using that SYNTAX-CASE? I'd still call that implementing
> SYNTAX-RULES with DEFMACRO+GENSYM.
Yes, but this doesn't construct a SYNTAX-RULES that plays nice with
some predefined SYNTAX-CASE. It constructs a SYNTAX-RULES that plays
nice with a SYNTAX-CASE that would have to replace any predefined
SYNTAX-CASE. If you were to implement SYNTAX-RULES as you describe
in a system that already contained macros that had been defined using
the predefined SYNTAX-CASE, then your implementation of SYNTAX-RULES
would break things.
For that matter, I doubt whether DEFMACRO+GENSYM can implement
SYNTAX-RULES in a way doesn't break macros that had already been
defined using a predefined SYNTAX-RULES.
If the rules of the game say you can't break existing macros, et
cetera, then you get a more interesting and perhaps even a more
useful notion of expressive power. You can escape from the Turing
tarpit where all sufficiently powerful constructs are equivalent.
To give an example of the Turing tarpit, the original poster wrote
that SYNTAX-RULES cannot implement DEFMACRO+GENSYM. That wouldn't
be true in the absence of rules that disallow a change of
representation, because SYNTAX-RULES is Turing-complete. So the
original poster must be assuming some rules, and I'm saying we
have to make those rules explicit before his question can make
sense.
Will
William D Clinger wrote:
> If the rules of the game say you can't break existing macros, et
> cetera, then you get a more interesting and perhaps even a more
> useful notion of expressive power. You can escape from the Turing
> tarpit where all sufficiently powerful constructs are equivalent.
>
> To give an example of the Turing tarpit, the original poster wrote
> that SYNTAX-RULES cannot implement DEFMACRO+GENSYM.
> That wouldn't be true in the absence of rules that disallow a change
> of representation, because SYNTAX-RULES is Turing-complete.
> So the original poster must be assuming some rules, and I'm saying
> we have to make those rules explicit before his question can make
> sense.
I agree that explicit rules are needed. But in this case, any solution that
has to enter the Turing tarpit to achieve a solution is going to be revealed
by all the black sticky stuff on it, i.e. the solution will be large, messy,
and intractable.
This will be the case for an implementation of one of the other macro
systems using SYNTAX-RULES; and it will be the case for an implementation of
one of the other systems using DEFMACRO+GENSYM, assuming we are talking
about a restricted DEFMACRO+GENSYM, as opposed to full Lisp/Scheme (which
would have to be one of those explicit rules).
OTOH, concise and tractable implementations of both DEFMACRO and
SYNTAX-RULES in terms of SYNTAX-CASE already exist, which I don't think is a
coincidence. The reason that's possible is simply that SYNTAX-CASE is
essentially a superset of both of the other systems, so has to do very
little to implement them without getting dirty (insert pun about hygiene
here); whereas both DEFMACRO and SYNTAX-RULES are sufficiently
special-purpose so as not to be particularly good Turing machines, and they
do not already include the specific functionality included in the other
macro systems, so would have to implement it by resorting to
Turing-completeness, which would be impractical.
Anton
··········@verizon.net (William D Clinger) writes:
> Peter Seibel <·····@javamonkey.com> wrote:
>> I thought you could implement SYNTAX-RULES using SYNTAX-CASE. So why
>> not just implement SYNTAX-CASE on DEFMACRO+GENSYM and then
>> SYNTAX-RULES using that SYNTAX-CASE? I'd still call that implementing
>> SYNTAX-RULES with DEFMACRO+GENSYM.
>
> Yes, but this doesn't construct a SYNTAX-RULES that plays nice with
> some predefined SYNTAX-CASE. It constructs a SYNTAX-RULES that plays
> nice with a SYNTAX-CASE that would have to replace any predefined
> SYNTAX-CASE. If you were to implement SYNTAX-RULES as you describe
> in a system that already contained macros that had been defined
> using the predefined SYNTAX-CASE, then your implementation of
> SYNTAX-RULES would break things.
Okay. I'll admit I haven't been following all the ins and outs of this
thread so I'm not sure what question the OP was interested in. But the
thing that I was interested in was what the correct layering would be.
That is, assume one is implementing a lisp and wants to provide all
three macro systems there are two questions.
a) Is it possible to provide all three by providing one, building the
next using it, and then the next on top of one of the other two? (As
opposed to having to implement all three in terms of some other, more
primitive facility that must be built into the language core.)
b) Assuming the answer to (a) is "yes", is there a natural best
layering or even a required layering.
Based on what I have seen in this thread, it seems that DEFMACRO is
the most "primitive" (in the sense of providing the ability to do both
good and ill) and would be the best candidate for the lowest layer. On
top if it, one could implement SYNTAX-CASE and then SYNTAX-RULES is
simply sugar over SYNTAX-CASE. Is that more or less right?
> To give an example of the Turing tarpit, the original poster wrote
> that SYNTAX-RULES cannot implement DEFMACRO+GENSYM. That wouldn't be
> true in the absence of rules that disallow a change of
> representation, because SYNTAX-RULES is Turing-complete.
A change of representation of what? I've seen (but not really
understood) some of the threads on c.l.s. where Oleg someone or other
makes some Scheme macro system do crazy stuff but that seems along the
lines of the stupid C++ tricks people can do with the C++ template
system. Is that what you're talking about?
For instance, if SYNTAX-RULES is Turing-complete, I suppose that means
on top of a Lisp with SYNTAX-RULES (only) one could then, in
SYNTAX-RULES implement a Lisp interpreter or compiler that supports
all three (including a reimplementation of SYNTAX-RULES). But I would
not describe this as implementing SYNTAX-CASE and DEFMACRO+GENSYM "on
top of" SYNTAX-RULES since the original SYNTAX-RULES is only used in
the interpreter or compiler for the new language and is not available
in that language.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> That is, assume one is implementing a lisp and wants to provide all
> three macro systems there are two questions.
>
> a) Is it possible to provide all three by providing one, building the
> next using it, and then the next on top of one of the other two?
> (As opposed to having to implement all three in terms of some other,
> more primitive facility that must be built into the language core.)
Yes, SYNTAX-CASE has demonstrated this in multiple implementations of
Scheme.
> b) Assuming the answer to (a) is "yes", is there a natural best
> layering or even a required layering.
The layering in the case of SYNTAX-CASE is that both DEFMACRO and
SYNTAX-RULES, as well as even QUASIQUOTE, can be implemented in terms of
SYNTAX-CASE - so there are two layers, SYNTAX-CASE and everything else.
> Based on what I have seen in this thread, it seems that DEFMACRO is
> the most "primitive" (in the sense of providing the ability to do both
> good and ill) and would be the best candidate for the lowest layer.
If by DEFMACRO you mean writing syntax transformers using the full power of
Lisp (or Scheme), then certainly DEFMACRO is a candidate for the lowest
layer. However, the OP seemed to be thinking of a more restricted DEFMACRO,
implied by the description DEFMACRO+GENSYM - otherwise his question would
not be very interesting (because you can implement any system easily using
full Lisp/Scheme).
> On top if it, one could implement SYNTAX-CASE and then SYNTAX-RULES
> is simply sugar over SYNTAX-CASE. Is that more or less right?
Except that any realistic implementation of SYNTAX-CASE in terms of DEFMACRO
is really going to be an implementation of SYNTAX-CASE in terms of full
Lisp/Scheme. You're not going to be implementing anything "in terms of"
DEFMACRO in the same way that you can implement DEFMACRO in terms of
SYNTAX-CASE.
To get an idea of what I'm talking about, take a look at the portable syntax
case implementation source at:
http://www.scheme.com/syntax-case/6.9a/psyntax.ss
There are some macros at the top, but page down through the code until you
get to the purely procedural bits. There's a lot of that. Any
implementation of SYNTAX-CASE "in terms of DEFMACRO" is going to have to
duplicate all this non-macro functionality. If it simply does this using
full Lisp/Scheme, then you are not implementing SYNTAX-CASE in terms of
DEFMACRO in the same sense that you can implement DEFMACRO in terms of
SYNTAX-CASE. The latter can be done with a small macro that does not resort
to any significant general Lisp/Scheme code.
(Scott Miller posted a DEFMACRO implementation in almost pure SYNTAX-CASE,
with the only use of ordinary Scheme being APPLY).
> > To give an example of the Turing tarpit, the original poster wrote
> > that SYNTAX-RULES cannot implement DEFMACRO+GENSYM. That wouldn't be
> > true in the absence of rules that disallow a change of
> > representation, because SYNTAX-RULES is Turing-complete.
>
> A change of representation of what? I've seen (but not really
> understood) some of the threads on c.l.s. where Oleg someone or other
> makes some Scheme macro system do crazy stuff but that seems along the
> lines of the stupid C++ tricks people can do with the C++ template
> system. Is that what you're talking about?
Can't speak for Will, but if you tried to implement another macro system
using a *restricted* DEFMACRO+GENSYM, as opposed to full Lisp/Scheme, then
yes, you would end up performing crazy Turing tricks in which you were using
syntax transformation to achieve Turing completeness.
> For instance, if SYNTAX-RULES is Turing-complete, I suppose that means
> on top of a Lisp with SYNTAX-RULES (only) one could then, in
> SYNTAX-RULES implement a Lisp interpreter or compiler that supports
> all three (including a reimplementation of SYNTAX-RULES). But I would
> not describe this as implementing SYNTAX-CASE and DEFMACRO+GENSYM "on
> top of" SYNTAX-RULES since the original SYNTAX-RULES is only used in
> the interpreter or compiler for the new language and is not available
> in that language.
By the same token, you can't implement anything useful "on top of"
DEFMACRO+GENSYM alone. For DEFMACRO+GENSYM to be practically useful, you
need important parts of full Lisp/Scheme - it's not very useful as a
standalone, self-contained system.
Anton
"Anton van Straaten" <·····@appsolutions.com> writes:
> If by DEFMACRO you mean writing syntax transformers using the full
> power of Lisp (or Scheme), then certainly DEFMACRO is a candidate
> for the lowest layer. However, the OP seemed to be thinking of a
> more restricted DEFMACRO, implied by the description DEFMACRO+GENSYM
> - otherwise his question would not be very interesting (because you
> can implement any system easily using full Lisp/Scheme).
Well, again I don't know what the OP had in mind but I'm to dense to
separate DEFMACRO+GENSYM from the rest of Lisp. To me the whole point
of DEFMACRO is it gives me a hook into the compiler and lets me extend
the compiler using "full Lisp". I'm not aware of how to do *anything*
with DEFMACRO without some recourse to the rest of the language.
I suppose you could write macros that expand into literal
s-expressions. Or if one considers backquote/unquote as primitives
along the lines of literal s-expressions (as opposed to syntactic
sugar for list-building language operations) then you could write
macros that interpolate their arguments into simple templates. But
that's hardly what I think of when someone says "DEFMACRO".
>> For instance, if SYNTAX-RULES is Turing-complete, I suppose that means
>> on top of a Lisp with SYNTAX-RULES (only) one could then, in
>> SYNTAX-RULES implement a Lisp interpreter or compiler that supports
>> all three (including a reimplementation of SYNTAX-RULES). But I would
>> not describe this as implementing SYNTAX-CASE and DEFMACRO+GENSYM "on
>> top of" SYNTAX-RULES since the original SYNTAX-RULES is only used in
>> the interpreter or compiler for the new language and is not available
>> in that language.
>
> By the same token, you can't implement anything useful "on top of"
> DEFMACRO+GENSYM alone. For DEFMACRO+GENSYM to be practically useful,
> you need important parts of full Lisp/Scheme - it's not very useful
> as a standalone, self-contained system.
So here's what I thought was the difference. This may be complete bunk
as I don't really know all the ins and outs of SYNTAX-RULES but maybe
by exposing my ignorance you can make an example of me for others ;-)
- DEFMACRO is *designed* to give the macro writer access to the full
language. The whole point is to take an arbitrary s-expr data
structure and turn it into legal code, using the full language at
compile time. Thus implementing a transformation that turns data
that happens to be a SYNTAX-CASE or SYNTAX-RULES expression into
appropriate code that implements their semantics is "on top of"
DEFMACRO as much as any macro defined with DEFMACRO is. Those
macros can be used in programs being interpreted/compiled in by the
system in which DEFMACRO is implemented.
- SYNTAX-RULES is designed to support certain kinds of common data
transformations and can be used to define macros that transform a
subset of the universe of possible s-expressions to a subset of
possible language expressions. But there are transformations it can
not express. (Is this true? This could be the root of my
misconception.) That it is *also* Turing complete and thus can be
used to implement an interpreter or compiler for a language that is
identical to the host language doesn't really do much unless
there's a way for it to gain access to the whole of the enclosing
program and shove it through this new interpreter or compiler.
Does this make sense?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
The relative expressive power of these three macro systems has been
well explained over in comp.lang.scheme by a person who chose not to
cross-post to comp.lang.lisp. While respecting his decision not to
cross-post, I'm going to refer you to his post in comp.lang.scheme.
Peter Seibel <·····@javamonkey.com> wrote:
> - DEFMACRO is *designed* to give the macro writer access to the full
> language. The whole point is to take an arbitrary s-expr data
> structure and turn it into legal code, using the full language at
> compile time. Thus implementing a transformation that turns data
> that happens to be a SYNTAX-CASE or SYNTAX-RULES expression into
> appropriate code that implements their semantics is "on top of"
> DEFMACRO as much as any macro defined with DEFMACRO is. Those
> macros can be used in programs being interpreted/compiled in by the
> system in which DEFMACRO is implemented.
There is no question but that DEFMACRO plus the full power of Scheme
or Common Lisp can implement both SYNTAX-RULES and SYNTAX-CASE, but
it cannot implement them in a way that is guaranteed to be compatible
with macros that were defined using a Scheme system's native SYNTAX-RULES.
In other words, DEFMACRO cannot implement either SYNTAX-RULES or
SYNTAX-CASE without "recompiling" the system's macro libraries.
If that is against the rules of the game, as it should be lest
we fall into the Turing tarpit, then DEFMACRO is not as
expressive as either SYNTAX-RULES or SYNTAX-CASE.
SYNTAX-CASE, by contrast, can implement both SYNTAX-RULES and
DEFMACRO without requiring any of the system's macro libraries
to be "recompiled". Thus SYNTAX-CASE is more expressive than
both SYNTAX-RULES and DEFMACRO, in this precise technical sense.
SYNTAX-RULES, on the other hand, cannot implement either
SYNTAX-CASE or DEFMACRO without requiring all of the system's
internal representations to change. Thus SYNTAX-RULES is
strictly less expressive than SYNTAX-CASE, and its expressiveness
is incomparable with that of DEFMACRO: expressiveness is not a
total order, but a partial order.
> - SYNTAX-RULES is designed to support certain kinds of common data
> transformations and can be used to define macros that transform a
> subset of the universe of possible s-expressions to a subset of
> possible language expressions. But there are transformations it can
> not express. (Is this true? This could be the root of my
> misconception.)
That's true. What you may be missing is that there are also
transformations that DEFMACRO cannot express, because DEFMACRO
is not privy to the macro technology that was used to define
the standard macro libraries, and is thus unable to achieve
compatibility with them.
> That [SYNTAX-RULES] is *also* Turing complete and thus can be
> used to implement an interpreter or compiler for a language that is
> identical to the host language doesn't really do much unless
> there's a way for it to gain access to the whole of the enclosing
> program and shove it through this new interpreter or compiler.
Exactly. That's why we're interested in comparing expressive
power, and that's why expressive power is defined in terms of
what you're able to do without having full access to the rest
of the program, and without being able to recompile the standard
libraries.
Will
··········@verizon.net (William D Clinger) writes:
> That's true. What you may be missing is that there are also
> transformations that DEFMACRO cannot express, because DEFMACRO is
> not privy to the macro technology that was used to define the
> standard macro libraries, and is thus unable to achieve
> compatibility with them.
Are you talking about syntax objects? (I'm guessing here.) I assume
the input is still plain old s-expressions. But isn't the output also.
Now I'm confused. What transformation from s-expressions to
s-expressions can't I achieve with the full power of Lisp or Scheme at
my disposal? (BTW, what's the most authoritative "spec" of SYNTAX-CASE
so I can try to fix some of my ignorance about it.)
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> wrote:
> ··········@verizon.net (William D Clinger) writes:
>
> > That's true. What you may be missing is that there are also
> > transformations that DEFMACRO cannot express, because DEFMACRO is
> > not privy to the macro technology that was used to define the
> > standard macro libraries, and is thus unable to achieve
> > compatibility with them.
>
> Are you talking about syntax objects? (I'm guessing here.)
For example.
> I assume
> the input is still plain old s-expressions. But isn't the output also.
Not with SYNTAX-RULES or SYNTAX-CASE. Their inputs and outputs also
include contextual information that the macro system uses to resolve
names properly. DEFMACRO has no access to this extra information,
so it cannot be used to implement anything compatible with it.
> Now I'm confused. What transformation from s-expressions to
> s-expressions can't I achieve with the full power of Lisp or Scheme at
> my disposal?
Your mistake lies in assuming that transformations from s-expressions
to s-expressions are powerful enough to express a SYNTAX-RULES that
would be compatible with existing macros. Globally, the R5RS macro
system might transform S-expressions to S-expressions; in some systems
it does, in some systems it doesn't. Locally, however, an R5RS macro
transformer must accept additional inputs and produce additional
outputs. In some systems these inputs and outputs are encoded as
S-expressions that wouldn't be legal in Scheme code, but in other
systems they aren't encoded in S-expression form at all.
I think the best way for you to understand the issues is to implement
SYNTAX-RULES via DEFMACRO in some implementation of Scheme that supports
DEFMACRO, and then see what breaks and how. Exactly what breaks and
how is going to depend on details of the implementation of both the
native SYNTAX-RULES and your version.
> (BTW, what's the most authoritative "spec" of SYNTAX-CASE
> so I can try to fix some of my ignorance about it.)
Probably "The Scheme Programming Language", second edition, by Dybvig
et al. See http://www.scheme.com/csug/syntax.html#g2154 for online
documentation.
Will
··········@verizon.net (William D Clinger) writes:
> Not with SYNTAX-RULES or SYNTAX-CASE. Their inputs and outputs also
> include contextual information that the macro system uses to resolve
> names properly. DEFMACRO has no access to this extra information,
> so it cannot be used to implement anything compatible with it.
It seems to me that the &ENVIRONMENT argument to DEFMACRO would be the
repository for this extra information. Although there is currently no
standard way to access it, I imagine that one can be designed.
Joe Marshall <···@ccs.neu.edu> wrote:
> > Not with SYNTAX-RULES or SYNTAX-CASE. Their inputs and outputs also
> > include contextual information that the macro system uses to resolve
> > names properly. DEFMACRO has no access to this extra information,
> > so it cannot be used to implement anything compatible with it.
>
> It seems to me that the &ENVIRONMENT argument to DEFMACRO would be the
> repository for this extra information. Although there is currently no
> standard way to access it, I imagine that one can be designed.
Of course. No one has questioned the fact that an implementor can
provide compatible versions of SYNTAX-RULES, SYNTAX-CASE, and DEFMACRO.
The only real point here is that you can't implement SYNTAX-RULES with
DEFMACRO without crossing the abstraction barrier that hides the
implementation of macros that were defined using the native macro
system.
The Common Lispers are having a hard time understanding that because,
in Common Lisp, all of the predefined macros were defined using some
equivalent of DEFMACRO anyway.
The Schemers are having a hard time understanding how the existence
of packages in Common Lisp can possibly be relevant to the question
of whether SYNTAX-RULES can be implemented in Scheme using DEFMACRO.
I think the best solution is to laugh at this whole thread, and to
cease the cross-posting.
Will
··········@verizon.net (William D Clinger) writes:
> Peter Seibel <·····@javamonkey.com> wrote:
>> ··········@verizon.net (William D Clinger) writes:
>>
>> > That's true. What you may be missing is that there are also
>> > transformations that DEFMACRO cannot express, because DEFMACRO is
>> > not privy to the macro technology that was used to define the
>> > standard macro libraries, and is thus unable to achieve
>> > compatibility with them.
>>
>> Are you talking about syntax objects? (I'm guessing here.)
>
> For example.
What else?
>> I assume the input is still plain old s-expressions. But isn't the
>> output also.
>
> Not with SYNTAX-RULES or SYNTAX-CASE. Their inputs and outputs also
> include contextual information that the macro system uses to resolve
> names properly. DEFMACRO has no access to this extra information, so
> it cannot be used to implement anything compatible with it.
So that extra information is encoded in some sort of opaque data
objects right? So is there a way to explain SYNTAX-CASE itself in
terms of layers? I.e. there's a layer that defines the data types used
to represent the inputs and outputs along with the operations on these
data types. Then SYNTAX-CASE is built on top of those objects, adding
the pattern matching and templating functionality.
If that's the case, then it seems the reason one can't implement a
compatible SYNTAX-CASE with DEFMACRO is that the API to those syntax
objects is not public and therefore I, as a DEFMACRO user trying to
implement SYNTAX-CASE, have to instead write my own version of them
which won't interoprate with the ones built into an existing
SYNTAX-CASE implementation.
So maybe a related question to the ones we've been discussing is, What
parts of the thing we've been calling "SYNTAX-CASE" would have to be
put into the lower layer and made publically accessible before its a
SMOP to implement SYNTAX-CASE using DEFMACRO?
>> Now I'm confused. What transformation from s-expressions to
>> s-expressions can't I achieve with the full power of Lisp or Scheme at
>> my disposal?
>
> Your mistake lies in assuming that transformations from s-expressions
> to s-expressions are powerful enough to express a SYNTAX-RULES that
> would be compatible with existing macros. Globally, the R5RS macro
> system might transform S-expressions to S-expressions; in some systems
> it does, in some systems it doesn't. Locally, however, an R5RS macro
> transformer must accept additional inputs and produce additional
> outputs. In some systems these inputs and outputs are encoded as
> S-expressions that wouldn't be legal in Scheme code, but in other
> systems they aren't encoded in S-expression form at all.
And the SYNTAX-CASE "spec" intentionally leaves not only the
representation undefined but the API to those objects?
Looking briefly at _The Scheme Programming Language_ I see that the
SYNTAX procedure (function? macro? whatever?) is described as being
like QUOTE. But it seems that it's not really a stand-alone operator
since it only make sense within the context of a SYNTAX-CASE clause
since it needs to know about the "pattern variables" which are not
passed to it directly. (I think that's why I've never been able to
wrap my head around SYNTAX-CASE despite actually having read several
of Dybvig's papers: there always seems to be this layer of magic that
isn't explained. I guess I'll have to look at an actual implementation
some time. Admitedly, it took my quite some time to fully grok how all
the parts of DEFMACRO fit together so it's likely that I just haven't
put enough skull sweat into it yet.)
>> (BTW, what's the most authoritative "spec" of SYNTAX-CASE
>> so I can try to fix some of my ignorance about it.)
>
> Probably "The Scheme Programming Language", second edition, by
> Dybvig et al. See http://www.scheme.com/csug/syntax.html#g2154 for
> online documentation.
Is the 3rd ed. okay too?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> Looking briefly at _The Scheme Programming Language_ I see that the
> SYNTAX procedure (function? macro? whatever?) is described as being
> like QUOTE. But it seems that it's not really a stand-alone operator
> since it only make sense within the context of a SYNTAX-CASE clause
> since it needs to know about the "pattern variables" which are not
> passed to it directly.
SYNTAX is a macro, more like QUASIQUOTE than QUOTE, except that it does
implicit unquoting of pattern variables. It can be used standalone, but
then there would be no pattern variables so it would act like a version of
QUOTE which returns a syntax object. You might do that if you needed a
literal syntax object for some reason (although I don't recall ever having
done that).
You can introduce pattern variables outside of syntax-case, e.g. using
with-syntax:
(with-syntax ((foo (syntax bar)))
(syntax-object->datum (syntax (ha ha foo)))) ;==> (ha ha bar)
Again, normal usage would be inside syntax-case, or at least inside
define-syntax, but it's possible to do direct manipulations of syntax
(objects) outside of those contexts. If you're debugging a syntax-case
macro, you might do some of this kind of stuff at the repl prompt.
> (I think that's why I've never been able to
> wrap my head around SYNTAX-CASE despite actually having read
> several of Dybvig's papers: there always seems to be this layer of
> magic that isn't explained.
There really isn't anything truly magical - just macros, specifically
SYNTAX-CASE, WITH-SYNTAX, LET-SYNTAX, LETREC-SYNTAX, SYNTAX, QUASISYNTAX,
UNSYNTAX, UNSYNTAX-SPLICING; and support functions like SYNTAX-OBJECT->DATUM
and DATUM->SYNTAX-OBJECT. I know what you mean about Dybvig's papers - I
think they tend to treat these operations as pure abstractions, and so don't
explicitly say "they're just macros that work like so" - that's either
assumed, or considered irrelevant.
I don't think the issue that Will has raised implies anything hidden,
either. One point is simply this (which I think you recognize, but I'll be
explicit): there are only two operations which construct syntax objects,
namely SYNTAX and DATUM->SYNTAX-OBJECT. Both of these are part of the
implementation of SYNTAX-CASE. If a reimplementation of SYNTAX-CASE using
DEFMACRO didn't use either of these constructors (since using them would be
cheating), then its syntax objects would be incompatible with those of a
preexisting SYNTAX-CASE system, unless the reimplementation had sufficient
knowledge & access to the internals of the SYNTAX-CASE implementation to be
able to "forge" compatible syntax objects. I don't think this issue has any
particularly deep implications, positive or negative (although of course I
could be missing something).
Anton
"Anton van Straaten" <·····@appsolutions.com> writes:
> Peter Seibel wrote:
>> Looking briefly at _The Scheme Programming Language_ I see that the
>> SYNTAX procedure (function? macro? whatever?) is described as being
>> like QUOTE. But it seems that it's not really a stand-alone
>> operator since it only make sense within the context of a
>> SYNTAX-CASE clause since it needs to know about the "pattern
>> variables" which are not passed to it directly.
>
> SYNTAX is a macro, more like QUASIQUOTE than QUOTE, except that it
> does implicit unquoting of pattern variables. It can be used
> standalone, but then there would be no pattern variables so it would
> act like a version of QUOTE which returns a syntax object. You might
> do that if you needed a literal syntax object for some reason
> (although I don't recall ever having done that).
>
> You can introduce pattern variables outside of syntax-case, e.g.
> using with-syntax:
>
> (with-syntax ((foo (syntax bar)))
> (syntax-object->datum (syntax (ha ha foo)))) ;==> (ha ha bar)
Okay, so I'm almost there, I think. Now my question is, if SYNTAX is
just a macro, how does it know that FOO is a pattern variable. That's
the part that's still opaque to me: it seems that either WITH-SYNTAX
has to squirrel away the information "foo is a pattern var" somewhere
that the implementation of SYNTAX will know to look or WITH-SYNTAX
itself has to implement a code walker that looks for SYNTAX calls and
turns them into something that is passed a list of pattern variables.
Or I'm missing something else.
> I don't think the issue that Will has raised implies anything
> hidden, either. One point is simply this (which I think you
> recognize, but I'll be explicit): there are only two operations
> which construct syntax objects, namely SYNTAX and
> DATUM->SYNTAX-OBJECT. Both of these are part of the implementation
> of SYNTAX-CASE. If a reimplementation of SYNTAX-CASE using DEFMACRO
> didn't use either of these constructors (since using them would be
> cheating), then its syntax objects would be incompatible with those
> of a preexisting SYNTAX-CASE system, unless the reimplementation had
> sufficient knowledge & access to the internals of the SYNTAX-CASE
> implementation to be able to "forge" compatible syntax objects. I
> don't think this issue has any particularly deep implications,
> positive or negative (although of course I could be missing
> something).
Well, I'm not sure it has any deep implications either. But let my try
to explain back what I'm hearing:
- DEFMACRO operates at the level of "raw" s-expressions and can hook
into the compiler to perform any s-expression to s-expression
transformation.
- SYNTAX-CASE requires a new data type, a syntax object, that
supports a small handful of operations.
- The implementation of these objects is part of the implementation
of SYNTAX-CASE. But the objects themselves are opaque and the
semantics of SYNTAX-CASE requires access to internals of these
objects that is not otherwise exposed.
- So, using DEFMACRO (and the rest of Lisp) we could implement these
syntax objects and then write macros using DEFMACRO that create and
manipulate these objects and implement SYNTAX-CASE.
- Or, we could take an existing SYNTAX-CASE implementation and by
frequent use of SYNTAX-OBJECT->DATUM followed up by a final call to
DATUM->SYNTAX-OBJECT, write macros that deal with code primarily as
s-expressions, just the way DEFMACRO macros do.
Because the opaque syntax objects implemented in our
SYNTAX-CASE-in-DEFMACRO implementation are different than those in
another SYNTAX-CASE implementation that happens to be loaded in the
same Lisp, there's a sense in which an "interoperable" SYNTAX-CASE can
*not* be implemented with DEFMACRO. Which is quite a different--and,
to me, less interesting--statement than "SYNTAX-CASE can't be
implemented with DEFMACRO". By the same token, you can't implement an
interoperable SYNTAX-CASE using SYNTAX-CASE. That is, if we want to
write a new coresident SYNTAX-CASE but we are not allowed to use the
existing SYNTAX-OBJECT->DATUM and DATUM->SYNTAX-OBJECT functions, then
the best we can do is the same thing we did with DEFMACRO, use the
rest of Lisp to implement our own opaque syntax objects that will work
fine in the context of our new SYNTAX-CASE implementation but won't
interoperate with any other SYNTAX-CASE implemention. Does that make
sense?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> Okay, so I'm almost there, I think. Now my question is, if SYNTAX is
> just a macro, how does it know that FOO is a pattern variable. That's
> the part that's still opaque to me: it seems that either WITH-SYNTAX
> has to squirrel away the information "foo is a pattern var" somewhere
> that the implementation of SYNTAX will know to look
Well, in principle, that could be done even if SYNTAX is "just a macro". I
don't think you really need to think of it otherwise to understand its
usage. For example, WITH-SYNTAX might define FOO as an ordinary lexical
variable, containing a value which responds with #t to a (hypothetical) type
predicate PATTERN-VAR?. The SYNTAX macro would examine its arguments
looking for pattern vars to expand.
However, there's more to it, which is that expansions of SYNTAX take into
account the lexical environment into which it is expanding, in order to deal
with hygiene. That part does entail some "magic":
> or WITH-SYNTAX
> itself has to implement a code walker that looks for SYNTAX calls and
> turns them into something that is passed a list of pattern variables.
> Or I'm missing something else.
Now you've gone and peeked behind the curtain. :) The SYNTAX-CASE system
acts as a macro compiler phase for Scheme implementations which support it.
It compiles whole programs, it's not just invoked when macros are invoked.
See the first few paragraphs of section 5 of Dybvig's "Writing Hygienic
Macros with Syntax-Case" for info. Key quote:
"The expander traverses the input expression, expanding any macro it
encounters and handling core forms such as LAMBDA, IF, and QUOTE. The
expander maintains a lexical compile-time environment that contains
information about lexically visible identifiers: macro keywords, lexical
variable names, and pattern variable names."
This is where the issue of Felleisen-expressibility, which was raised in a
c.l.scheme-only post in this thread, comes in. Since syntax-case knows
about the whole program, it can do things which, to do with defmacro+Lisp,
would require that defmacro get access to the whole program, or at least
enough of it.
> Well, I'm not sure it has any deep implications either. But let my try
> to explain back what I'm hearing:
>
> - DEFMACRO operates at the level of "raw" s-expressions and can hook
> into the compiler to perform any s-expression to s-expression
> transformation.
>
> - SYNTAX-CASE requires a new data type, a syntax object, that
> supports a small handful of operations.
>
> - The implementation of these objects is part of the implementation
> of SYNTAX-CASE. But the objects themselves are opaque and the
> semantics of SYNTAX-CASE requires access to internals of these
> objects that is not otherwise exposed.
Agreed.
> - So, using DEFMACRO (and the rest of Lisp) we could implement these
> syntax objects and then write macros using DEFMACRO that create and
> manipulate these objects and implement SYNTAX-CASE.
Yes, modulo the issue of needing knowledge of the lexical environment into
which macros are expanded. IOW, a DEFMACRO implementation of SYNTAX-CASE
has some messy work to do - but it's the same sort of messy work that
existing SYNTAX-CASE implementations do.
> - Or, we could take an existing SYNTAX-CASE implementation and by
> frequent use of SYNTAX-OBJECT->DATUM followed up by a final call to
> DATUM->SYNTAX-OBJECT, write macros that deal with code primarily as
> s-expressions, just the way DEFMACRO macros do.
This is how implementations of DEFMACRO in SYNTAX-CASE work. I'm not sure
if you're saying that you could do a "parallel" SYNTAX-CASE in DEFMACRO this
way - I suppose you could, but I'm not sure where you're going with that.
> Because the opaque syntax objects implemented in our
> SYNTAX-CASE-in-DEFMACRO implementation are different than those in
> another SYNTAX-CASE implementation that happens to be loaded in the
> same Lisp, there's a sense in which an "interoperable" SYNTAX-CASE can
> *not* be implemented with DEFMACRO. Which is quite a different--and,
> to me, less interesting--statement than "SYNTAX-CASE can't be
> implemented with DEFMACRO".
Agreed. But, one of the things I've been trying to get at is that even the
more interesting question - whether/why it's harder to implement SYNTAX-CASE
using DEFMACRO than vice-versa - is not all *that* interesting, at least not
if the underlying reasons are taken into account:
First, the main reason that a SYNTAX-CASE implementation of DEFMACRO is so
short, is that SYNTAX-CASE includes a superset of the DEFMACRO machinery. I
don't think the shortness of this implementation tells you very much, other
than that.
Second, the main reason it's "harder" to implement SYNTAX-CASE with DEFMACRO
than vice versa, is that DEFMACRO alone doesn't give you access to
information about the environment into which macros are expanded. To get
that access requires special measures. To be fair, you might simply decree
that SYNTAX-CASE in DEFMACRO gets to do what other SYNTAX-CASE
implementations do, which is process the whole program - in which case, life
will be about as simple for the DEFMACRO version of SYNTAX-CASE as it is for
any other SYNTAX-CASE implementation.
However, one might choose to disallow this on the grounds that you'd no
longer be "embedding" the SYNTAX-CASE implementation in Lisp. In that case,
the DEFMACRO version would be forced to resort to tricky stuff, like
redefining binding forms, or maybe redefining EVAL or the reader. In this
case, the implementation using DEFMACRO becomes harder. But it's obvious
why that happens - DEFMACRO is being prevented from using a technique that
other SYNTAX-CASE implementations use - so the resulting difference doesn't
seem very interesting.
> By the same token, you can't implement an
> interoperable SYNTAX-CASE using SYNTAX-CASE. That is, if we want to
> write a new coresident SYNTAX-CASE but we are not allowed to use the
> existing SYNTAX-OBJECT->DATUM and DATUM->SYNTAX-OBJECT functions, then
> the best we can do is the same thing we did with DEFMACRO, use the
> rest of Lisp to implement our own opaque syntax objects that will work
> fine in the context of our new SYNTAX-CASE implementation but won't
> interoperate with any other SYNTAX-CASE implemention. Does that make
> sense?
It makes sense to me.
Anton
Peter Seibel wrote:
> (BTW, what's the most authoritative "spec" of SYNTAX-CASE
> so I can try to fix some of my ignorance about it.)
There's a "portable syntax-case" implementation which is certainly an
authoritative spec:
http://www.scheme.com/syntax-case/
See the papers and book chapters referenced on that page. In addition, see
"Writing Hygienic Macros in Scheme with Syntax-Case":
http://citeseer.ist.psu.edu/dybvig92writing.html
or ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/iucstr356.ps.gz
This paper gives a good intro to the system.
Anton
Peter Seibel wrote:
> "Anton van Straaten" <·····@appsolutions.com> writes:
>
> > If by DEFMACRO you mean writing syntax transformers using the full
> > power of Lisp (or Scheme), then certainly DEFMACRO is a candidate
> > for the lowest layer. However, the OP seemed to be thinking of a
> > more restricted DEFMACRO, implied by the description DEFMACRO+GENSYM
> > - otherwise his question would not be very interesting (because you
> > can implement any system easily using full Lisp/Scheme).
>
> Well, again I don't know what the OP had in mind but I'm to dense to
> separate DEFMACRO+GENSYM from the rest of Lisp. To me the whole point
> of DEFMACRO is it gives me a hook into the compiler and lets me extend
> the compiler using "full Lisp". I'm not aware of how to do *anything*
> with DEFMACRO without some recourse to the rest of the language.
The OP, David Fisher, has said various things (including in some earlier
threads, some of which I believe only appeared on c.l.scheme) which
indicated that he was thinking of something more restricted than DEFMACRO
plus the rest of Lisp. If he *was* thinking of the whole of Lisp, then the
answer to his question would be trivial: you can implement SYNTAX-CASE or
SYNTAX-RULES on top of Lisp with DEFMACRO - no problem - but much of the
implementation would be in the form of ordinary procedures, and have nothing
to do with DEFMACRO, as is the case with existing implementations of these
systems.
I agree that DEFMACRO mainly provides a hook into the compiler. But as
such, any such hook into the compiler would be sufficient for the purpose,
if you can use the whole of Lisp to do the necessary work. No question is
raised about relative power or expressiveness - you're simply comparing Lisp
to Lisp. Syntax-rules is just as capable as defmacro of implementing
everything procedurally.
> I suppose you could write macros that expand into literal
> s-expressions. Or if one considers backquote/unquote as primitives
> along the lines of literal s-expressions (as opposed to syntactic
> sugar for list-building language operations) then you could write
> macros that interpolate their arguments into simple templates.
Right, I think that's the sort of thing that might have been meant.
> But that's hardly what I think of when someone says "DEFMACRO".
I agree, which is why various people asked for refinement of the question.
> > By the same token, you can't implement anything useful "on top of"
> > DEFMACRO+GENSYM alone. For DEFMACRO+GENSYM to be practically
> > useful, you need important parts of full Lisp/Scheme - it's not very
> > useful as a standalone, self-contained system.
>
> So here's what I thought was the difference. This may be complete bunk
> as I don't really know all the ins and outs of SYNTAX-RULES but maybe
> by exposing my ignorance you can make an example of me for others ;-)
>
> - DEFMACRO is *designed* to give the macro writer access to the full
> language. The whole point is to take an arbitrary s-expr data
> structure and turn it into legal code, using the full language at
> compile time.
The latter paragraph is just as true of SYNTAX-CASE, though.
> Thus implementing a transformation that turns data
> that happens to be a SYNTAX-CASE or SYNTAX-RULES expression
> into appropriate code that implements their semantics is "on top of"
> DEFMACRO as much as any macro defined with DEFMACRO is.
Right, but that's where the definitional question comes in. SYNTAX-CASE can
use procedural code to implement DEFMACRO, but it doesn't need to - it can
implement DEFMACRO purely in terms of core operations in the syntax-case
system, such as SYNTAX-OBJECT->DATUM and DATUM->SYNTAX-OBJECT. There's no
corresponding situation for DEFMACRO. It's because of this inequity that
people have been saying that there's no issue implementing DEFMACRO in terms
of SYNTAX-CASE, whereas there are issues implementing SYNTAX-CASE in terms
of DEFMACRO - even if those issues are only in being clear about defining
what is meant by DEFMACRO.
> - SYNTAX-RULES is designed to support certain kinds of common data
> transformations and can be used to define macros that transform a
> subset of the universe of possible s-expressions to a subset of
> possible language expressions. But there are transformations it can
> not express. (Is this true? This could be the root of my
> misconception.)
There are transformations which SYNTAX-RULES is not designed to express, for
example transformations that break hygiene and capture variables from the
macro's usage environment. There are others that are simply difficult to
express within the constraints of the pure pattern-matching and template
substitution mechanism which SYNTAX-RULES offers. Both of these limitations
can be worked around, although in some cases the resulting solutions can be
impractical.
> That it is *also* Turing complete and thus can be
> used to implement an interpreter or compiler for a language that is
> identical to the host language doesn't really do much
The Turing-completeness doesn't mean that you have to write a language to
take advantage of it. You can make use of the Turing completeness in more
direct ways. However, the results do tend to be not very satisfactory as a
practical technique.
> unless
> there's a way for it to gain access to the whole of the enclosing
> program and shove it through this new interpreter or compiler.
There are ways to gain such access - for example, by redefining basic
constructs. Oleg showed how to write "dirty" macros (non-hygienic, among
other things) with SYNTAX-RULES, in this post:
http://groups.google.com/groups?selm=7eb8ac3e.0203271253.74bb0819%40posting.
google.com
This was achieved by redefining binding forms, like LAMBDA and LET. For all
I know, this technique may even be practical - I'm not sure if anyone has
tried to use it seriously. But again, while technically thought-provoking
and impressive, it doesn't seem to be a particularly satisfactory way to
write real macros.
> Does this make sense?
Yes. I think any confusion arises from the lack of precision in the
original question.
Anton
"Anton van Straaten" <·····@appsolutions.com> wrote in message news:<···················@newsread2.news.atl.earthlink.net>...
> The OP, David Fisher, has said various things (including in some earlier
> threads, some of which I believe only appeared on c.l.scheme) which
> indicated that he was thinking of something more restricted than DEFMACRO
> plus the rest of Lisp. If he *was* thinking of the whole of Lisp, then the
> answer to his question would be trivial: you can implement SYNTAX-CASE or
> SYNTAX-RULES on top of Lisp with DEFMACRO - no problem - but much of the
> implementation would be in the form of ordinary procedures, and have nothing
> to do with DEFMACRO, as is the case with existing implementations of these
> systems.
I meant that you can use all of the language available to you, but
only with the macro systems that are given here. So, you don't need to
be "compatible with other macro systems that exist in the language"
(because they don't).
For concreteness, let's focus on the upper right corner of the table
and let's say we are talking about Scheme with no macros facilities
other than DEFMACRO and GENSYM.
Hypothesis 1 is that there exists a code fragment S in this language,
such that for any code fragment P in full R5RS (using SYNTAX-RULES),
the program S + P (S is followed by P) will behave exactly as P would
in R5RS language.
Hypothesis 2 is that there exists a code fragment S in this language,
such that for any code fragments P1 in R5RS sans macros and P2 in full
R5RS, the program P1 + S + P2 will behave exactly as P1 + P2 would in
R5RS.
(I hope this doesn't leave much room for nitpicking about clarity)
My, possibly incorrect, interpretation of what Oleg wrote is
hypothesis 2 is wrong.
Further, I think hypothesis 1 is also wrong if one imposes size
limitations on S (let's say a couple of pages), but correct if no such
limit is imposed. In fact, the minimum possible S is what is most
interesting, IMHO.
D.
P.S. How does all this relate to Kolmogorov complexity? That is the
question! The input of a macro is the "old language" and the output is
the "new language", so the minimum size of a macro doing such
transformation must be the difference in the language complexities.
</outrage> :-)
David Fisher wrote:
> I meant that you can use all of the language available to you, but
> only with the macro systems that are given here. So, you don't need to
> be "compatible with other macro systems that exist in the language"
> (because they don't).
>
> For concreteness, let's focus on the upper right corner of the table
> and let's say we are talking about Scheme with no macros facilities
> other than DEFMACRO and GENSYM.
>
> Hypothesis 1 is that there exists a code fragment S in this language,
> such that for any code fragment P in full R5RS (using SYNTAX-RULES),
> the program S + P (S is followed by P) will behave exactly as P would
> in R5RS language.
>
> Hypothesis 2 is that there exists a code fragment S in this language,
> such that for any code fragments P1 in R5RS sans macros and P2 in full
> R5RS, the program P1 + S + P2 will behave exactly as P1 + P2 would in
> R5RS.
>
> (I hope this doesn't leave much room for nitpicking about clarity)
>
> My, possibly incorrect, interpretation of what Oleg wrote is
> hypothesis 2 is wrong.
I don't see what problem you have in mind for Hypothesis 2. Given defmacro
and access to the full underlying language, there should be no problem
achieving this. This could be achieved using what Oleg described as "a
trivial define-macro that merely invokes Al Petrofsky's portable R5RS
macro-expander on A."
> Further, I think hypothesis 1 is also wrong if one imposes size
> limitations on S (let's say a couple of pages), but correct if no such
> limit is imposed.
Yes, I agree. But I think it's important to recognize that the only reason
that syntax-case can implement defmacro in fewer lines than the reverse is
that syntax-case is essentially a superset of defmacro, which for example
already contains conversion operators to convert between defmacro's syntax
abstraction and syntax-case - so that such conversion does not need to be
reimplemented as part of an implementation of defmacro. I don't think the
relative lengths of these system's implementations of each other is very
meaningful, because of the differences in the nature of the two systems.
> In fact, the minimum possible S is what is most interesting, IMHO.
Why?
> P.S. How does all this relate to Kolmogorov complexity? That is the
> question! The input of a macro is the "old language" and the output is
> the "new language", so the minimum size of a macro doing such
> transformation must be the difference in the language complexities.
> </outrage> :-)
Ah, if that's what you're getting at, then shouldn't you be taking into
account the size of the implementation of the base macro system, too? For
example, you should compare the size of the implementation of syntax-case
plus an implementation of defmacro in terms of it, to the size of an
implementation of demacro plus the size of an implementation of syntax-case
on top of that. Otherwise, you're unfairly handicapping defmacro by
excluding syntax-case's complex implementation (on the order of 3000 lines)
from the comparison on the syntax-case side, but including that
implementation on the defmacro side. The result of this unfair comparison
seems meaningless to me.
There are still problems with such a comparison, for example the fact that
the syntax-case SYNTAX macro, which performs template substitution, is
comparable to QUASIQUOTE, so in the defmacro case the size of the
implementation of QUASIQUOTE should be taken into account. In short:
> (I hope this doesn't leave much room for nitpicking about clarity)
I'd say there's a way to go yet in order to make this question meaningful.
Anton
"Anton van Straaten" <·····@appsolutions.com> wrote in message news:<··················@newsread2.news.atl.earthlink.net>...
> David Fisher wrote:
> > I meant that you can use all of the language available to you, but
> > only with the macro systems that are given here. So, you don't need to
> > be "compatible with other macro systems that exist in the language"
> > (because they don't).
> >
> > For concreteness, let's focus on the upper right corner of the table
> > and let's say we are talking about Scheme with no macros facilities
> > other than DEFMACRO and GENSYM.
> >
> > Hypothesis 1 is that there exists a code fragment S in this language,
> > such that for any code fragment P in full R5RS (using SYNTAX-RULES),
> > the program S + P (S is followed by P) will behave exactly as P would
> > in R5RS language.
> >
> > Hypothesis 2 is that there exists a code fragment S in this language,
> > such that for any code fragments P1 in R5RS sans macros and P2 in full
> > R5RS, the program P1 + S + P2 will behave exactly as P1 + P2 would in
> > R5RS.
> >
> > (I hope this doesn't leave much room for nitpicking about clarity)
>
> I'd say there's a way to go yet in order to make this question meaningful.
>
Why? What is it in the above that you consider ambiguous?
> I don't see what problem you have in mind for Hypothesis 2. Given defmacro
> and access to the full underlying language, there should be no problem
> achieving this. This could be achieved using what Oleg described as "a
> trivial define-macro that merely invokes Al Petrofsky's portable R5RS
> macro-expander on A."
Wrong. He wrote that to use it, it would suffice to wrap the pieces of
code that use SYNTAX-RULES, for example A, as in (foo A). The
formulation of hypothesis 2 clearly precludes such possibility.
In my summary of Oleg's article, I included Felleisen-expressiveness
verbatim:
+------------------------------------------------------+
| | Felleisen-expressible in terms of |
| this |---------------------------------------|
| is | syntax-rules | syntax-case | defmacro |
| | | | +gensym |
|--------------+--------------+-------------+----------|
| syntax-rules | :-) | + | - |
|--------------+--------------+-------------+----------|
| syntax-case | - | :-) | - |
|--------------+--------------+-------------+----------|
| defmacro | - | + | :-) |
| +gensym | | | |
+------------------------------------------------------+
You were unhappy with it. Did you consider "Felleisen-expressible" to
be an ill-defined term as well?
David Fisher wrote:
> > > Hypothesis 1 is that there exists a code fragment S in this language,
> > > such that for any code fragment P in full R5RS (using SYNTAX-RULES),
> > > the program S + P (S is followed by P) will behave exactly as P would
> > > in R5RS language.
> > >
> > > Hypothesis 2 is that there exists a code fragment S in this language,
> > > such that for any code fragments P1 in R5RS sans macros and P2 in full
> > > R5RS, the program P1 + S + P2 will behave exactly as P1 + P2 would in
> > > R5RS.
> > >
> > > (I hope this doesn't leave much room for nitpicking about clarity)
> >
> > I'd say there's a way to go yet in order to make this question
meaningful.
> >
>
> Why? What is it in the above that you consider ambiguous?
Not so much ambiguous, as not particularly meaningful. I've pointed out
what I see as problems with comparing DEFMACRO to SYNTAX-CASE - they're two
quite different sorts of systems. Others have also pointed this out. To
compare the systems, you're going to have to be quite careful about what
you're comparing, and how, and even why.
Attempting to compare the sizes of the respective implementations is an
example: the two-page limitation you mentioned would be an unreasonable
limit to impose on an implementation of your S, because if you include the
pieces needed for a fair or meaningful comparison, none of the systems would
satisfy that. Further, a more meaningful comparison, in which neither
system is unfairly handicapped, is likely to find that it doesn't make much
difference which system is implemented first, so it's not just a question of
increasing the implementation size limit.
> > I don't see what problem you have in mind for Hypothesis 2. Given
defmacro
> > and access to the full underlying language, there should be no problem
> > achieving this. This could be achieved using what Oleg described as "a
> > trivial define-macro that merely invokes Al Petrofsky's portable R5RS
> > macro-expander on A."
>
> Wrong. He wrote that to use it, it would suffice to wrap the pieces of
> code that use SYNTAX-RULES, for example A, as in (foo A). The
> formulation of hypothesis 2 clearly precludes such possibility.
That intent wasn't clear to me, and I'm not sure that it's been achieved.
Oleg gave one example of how a globally-aware transformation could be
achieved, but there are other ways to achieve that - for example, redefining
key forms. This, for example, is how Oleg achieved "non-hygienic"
syntax-rules macros in Scheme. An implementation of S along these lines
could also satisfy your hypothesis 2.
Besides, as I've just observed in a reply to Peter Seibel, if you don't
allow the DEFMACRO-based system to do what other SYNTAX-CASE implementations
do, namely process entire programs, then it's not surprising that an
implementation using DEFMACRO has a more difficult job (or even impossible,
depending on the constraints imposed).
> In my summary of Oleg's article, I included Felleisen-expressiveness
> verbatim:
<table snipped>
> You were unhappy with it.
I wasn't unhappy with that table - if you check my response to that post,
you'll see I responded on the question of the inventors of syntax-case, the
generality of syntax-case, and the question of inclusion in standards. I
didn't comment on the table because it appeared to be a correct summary of
Oleg's post, and didn't seem to warrant any discussion. This thread has
mostly been discussing other speculations, assumptions and claims which go
beyond what your revised table implies.
> Did you consider "Felleisen-expressible" to be an ill-defined term as
well?
No, I think it's a very useful term and concept, especially since it proves
that Lisps and their macro systems are foremost among the most expressive
languages in the universe, which matches my intuition nicely!
However, I see a couple of points related to the Felleisen-expressibility
issue as it relates to expressing SYNTAX-CASE in a Lisp with DEFMACRO:
First, for SYNTAX-CASE to _not_ be Felleisen-expressible in a Lisp with
DEFMACRO implies, as I've said, that you are handicapping the implementation
by forbidding it to do anything that would allow it to obtain global
knowledge about the program. In particular, you are forbidding it to use a
key implementation technique used by other SYNTAX-CASE implementations.
This raises questions about the point and/or validity of such a comparison.
Second, it should be kept in mind that the greater Felleisen-expressiveness
of SYNTAX-CASE vs. a restricted Lisp with DEFMACRO is not the reason that a
SYNTAX-CASE implementation of DEFMACRO is so short, even though
superficially it might be tempting to make that connection. Any conclusions
related to a measure like Kolmogorov complexity in this regard would be
erroneous, unless a more meaningful comparison was made, e.g. one in which
takes into account the size of the SYNTAX-CASE implementation on *both*
sides.
Anton
On Tue, 16 Mar 2004 08:18:06 -0800, William D Clinger wrote:
> So the original poster must be assuming some rules, and I'm saying we
> have to make those rules explicit before his question can make sense.
I think everybody more or less agrees which solutions would qualify and
which don't, the problem is only with formalizing this. For example I
would not accept a solution which would reimplement a complete interpreter
of the host language.
In practice a macro system A can be defined in terms of a macro system B
if a core Lisp/Scheme implementation equipped with B can be enhanced by a
library which provides A, which looks as integrated with the language as
it would be if implemented in the compiler proper (except some possible
incantation to use the library).
Are there cases when this depends on some unspeficied details, e.g. which
subset of the language is exactly provided, and both choices are fair?
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
I'll try to summarize what ····@pobox.com wrote:
+------------------------------------------------------+
| | Felleisen-expressible in terms of |
| this |---------------------------------------|
| is | syntax-rules | syntax-case | defmacro |
| | | | +gensym |
|--------------+--------------+-------------+----------|
| syntax-rules | :-) | + | - |
|--------------+--------------+-------------+----------|
| syntax-case | - | :-) | - |
|--------------+--------------+-------------+----------|
| defmacro | - | + | :-) |
| +gensym | | | |
+------------------------------------------------------+
I don't fully understand SYNTAX-CASE yet, but it must be one really
general macro system if it can express the other two so easily. Who
invented it and when? It seems strange that neither Scheme, nor CL
standards include it. Is there anything even more general (in some
undefined, but common sense) than SYNTAX-CASE?
David Fisher wrote:
> I'll try to summarize what ····@pobox.com wrote:
>
> +------------------------------------------------------+
> | | Felleisen-expressible in terms of |
> | this |---------------------------------------|
> | is | syntax-rules | syntax-case | defmacro |
> | | | | +gensym |
> |--------------+--------------+-------------+----------|
> | syntax-rules | :-) | + | - |
> |--------------+--------------+-------------+----------|
> | syntax-case | - | :-) | - |
> |--------------+--------------+-------------+----------|
> | defmacro | - | + | :-) |
> | +gensym | | | |
> +------------------------------------------------------+
>
> I don't fully understand SYNTAX-CASE yet, but it must be one really
> general macro system if it can express the other two so easily. Who
> invented it and when?
Bob Hieb and R. Kent Dybvig (& Carl Bruggeman?) were the immediate
inventors, afaik, but it didn't just spring out of nowhere - it built on a
long history. Dybvig's 1992 paper about it references Will Clinger,
Jonathan Rees, Eugene Kohlbecker, Dan Friedman, Matthias Felleisen, and
Bruce Duba. See http://library.readscheme.org/page3.html for important
papers in the history & literature of macros.
Syntax-case's "generality" is no mystery. Its closeness to syntax-rules was
deliberate - syntax-rules is basically just the pattern matching and
template substitution part of syntax-case, without the procedural
capabilities and without the first-class syntactic abstraction in the form
of syntax objects. Syntax-case's ability to implement defmacro easily stems
from the fact that its syntax objects are a superset of defmacro's list
representation of syntax. Since syntax-case includes operations to convert
back and forth between its own syntax objects and the traditional list
representation of syntax, defmacro becomes easy to implement.
In some respects, syntax-case is still a cop-out if you're thinking in terms
of purely rule-based transformational systems (like syntax-rules). To go
beyond what syntax-rules supports, syntax-case falls back mainly on
procedural code.
> It seems strange that neither Scheme, nor CL
> standards include it.
Not so strange. With great power comes some complexity, at least in this
case. Syntax-case presents some real challenges for module systems and
phase management in compilation, for example. I suspect a future revision
of the Scheme standard might very well standardize something a bit more
powerful/expressive than syntax-rules, but without going as far as something
equivalent to full syntax-case. That doesn't stop implementations from
using syntax-case, though - many of them do, to excellent effect. What PLT
have been doing with it in their DrScheme IDE and related tools is
ground-breaking.
> Is there anything even more general (in some
> undefined, but common sense) than SYNTAX-CASE?
For certain values of that "undefined, but common sense", the answer is yes;
for other values, the answer is no. ;-)
Anton
Anton van Straaten wrote:
> David Fisher wrote:
>>It seems strange that neither Scheme, nor CL
>>standards include it.
But syntax-case was invented after R5RS was written - right?
> Not so strange. With great power comes some complexity, at least in this
> case. Syntax-case presents some real challenges for module systems and
> phase management in compilation, for example. I suspect a future revision
> of the Scheme standard might very well standardize something a bit more
> powerful/expressive than syntax-rules, but without going as far as something
> equivalent to full syntax-case.
You have a point.
--
Jens Axel S�gaard
Jens Axel S�gaard <······@soegaard.net> wrote:
> But syntax-case was invented after R5RS was written - right?
Wrong. SYNTAX-CASE was invented just a year or two after its
authors had invented the low-level macro system described in
the appendix of the R4RS. We delayed the publication of the
R4RS by a year so we could include that low-level system
instead of the one Jonathan Rees had invented. When its own
designers abandoned it, we were left with an R4RS appendix
that was far more complex and intimidating than it would have
been had it described only SYNTAX-RULES. That was a mistake.
We didn't want to make the same kind of mistake in the R5RS,
especially since the macro system was being moved into the
main body of the report, so we described only SYNTAX-RULES.
Now that most implementations of Scheme support SYNTAX-CASE
in addition to SYNTAX-RULES, it might be appropriate to add
SYNTAX-CASE to the R6RS, possibly in some kind of appendix.
Will
William D Clinger wrote:
> Jens Axel S�gaard <······@soegaard.net> wrote:
>>But syntax-case was invented after R5RS was written - right?
> Wrong. SYNTAX-CASE was invented just a year or two after its
> authors had invented the low-level macro system described in
> the appendix of the R4RS. We delayed the publication of the
> R4RS by a year so we could include that low-level system
> instead of the one Jonathan Rees had invented. When its own
> designers abandoned it, we were left with an R4RS appendix
> that was far more complex and intimidating than it would have
> been had it described only SYNTAX-RULES. That was a mistake.
Okay. Thanks for the explanation.
> We didn't want to make the same kind of mistake in the R5RS,
> especially since the macro system was being moved into the
> main body of the report, so we described only SYNTAX-RULES.
>
> Now that most implementations of Scheme support SYNTAX-CASE
> in addition to SYNTAX-RULES, it might be appropriate to add
> SYNTAX-CASE to the R6RS, possibly in some kind of appendix.
Agree.
--
Jens Axel S�gaard
David Fisher wrote:
> I'll try to summarize what ····@pobox.com wrote:
>
> +------------------------------------------------------+
> | | Felleisen-expressible in terms of |
> | this |---------------------------------------|
> | is | syntax-rules | syntax-case | defmacro |
> | | | | +gensym |
> |--------------+--------------+-------------+----------|
> | syntax-rules | :-) | + | - |
> |--------------+--------------+-------------+----------|
> | syntax-case | - | :-) | - |
> |--------------+--------------+-------------+----------|
> | defmacro | - | + | :-) |
> | +gensym | | | |
> +------------------------------------------------------+
Such a comparison isn't very helpful because it misses the important
point: syntax-rules/syntax-case provide a different style ("paradigm")
to implement macros than defmacro does.
This means that an answer to the question "What is the most general
macro system?" doesn't help you much in determining which macro system
you should use. Most languages can be implemented in terms of each other
- this doesn't tell you which language to use either.
syntax-rules/syntax-case provide a declarative style while defmacro
allows you to use whatever style a Lisp can provide you. Since
quasiquotation plays very well in conjunction with defmacro, the most
natural thing to do is to use it as a basis for expressing
transformations of s-expressions, and this is what most books teach you
about defmacro. However, the point of defmacro is that you can use all
of Lisp, including any library.
For example, the common-idioms library provides a DESTRUCTURING-CASE for
Common Lisp with which you can basically use the same style as in
syntax-rules. (see http://www.cliki.net/common-idioms )
Now this sounds like defmacro is the most general macro system, which
would contradict some of the earlier statements in this thread. This is
because I have taken the point of view of considering only the proposed
programming styles. syntax-rule/syntax-case additionally take care of
some so-called "hygiene" issues (name capture, referential transparency)
which are harder to solve within a defmacro. This is the only reason why
moving from Lisp-based macros to something like syntax-rules/syntax-case
is thought of as necessary. However, if you prefer a different style for
expressing macros, syntax-rules/syntax-case doesn't seem to help you a
lot. There are more general ways to solve hygiene issues (for example by
making use of the package system in Common Lisp).
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
>>>>> "Pascal" == Pascal Costanza <········@web.de> writes:
Pascal> There are more general ways to solve hygiene issues (for
Pascal> example by making use of the package system in Common Lisp).
The Common Lisp macros and the package system don't address all the
hygiene issues addressed by SYNTAX-RULES/SYNTAX-CASE, and they do so
in a decidedly technical, tricky, and unintuitive way which, in my
experience, causes more hassle than it solves problems in day-to-day
programming. (I'm not even going to start talking about the staging
issues which are a complete nightmare in Common Lisp.)
--
Cheers =8-} Mike
Friede, V�lkerverst�ndigung und �berhaupt blabla
Michael Sperber wrote:
>>>>>>"Pascal" == Pascal Costanza <········@web.de> writes:
>
> Pascal> There are more general ways to solve hygiene issues (for
> Pascal> example by making use of the package system in Common Lisp).
>
> The Common Lisp macros and the package system don't address all the
> hygiene issues addressed by SYNTAX-RULES/SYNTAX-CASE,
Yes, they do, AFAICS at the moment.
- Name capture is just a matter of switching the default behavior. With
defmacro, you have to use gensyms to avoid name capture, and with
syntax-case you have to use datum->syntax-object to ensure name capture.
- Referential transparency for global bindings is simple. Just put your
global definitions in your own packages.
- Referential transparency for local bindings can be dealt with by
modifying the reader. As a result of a recent discussion in c.l.l, I
have written a modification that allows you to say, for example, the
following.
(let ((x 5))
(macrolet
((test (y) `(list x ,y)))
(let ((!!x 55))
(test x))))
=> (5 55)
The notation "!!" ensures that the subsequent symbol is a fresh, and
therefore unique one, so the two different x don't clash with each other
in the example above.
A better way to write this example is this.
(let ((x 5))
(macrolet
((test (y) `(list x ,y)))
{(let ((!x 55))
(test x))}))
=> (5 55)
The curly braces define a new package environment[1], and the "!"
notation ensures a fresh symbol in the current package. Outside of the
braces, the old package is in effect again. The difference between "!"
and "!!" is that "!" checks for an already present symbol in the current
package while "!!" forces a new symbol. This means that the following is
not legal because of the missing braces.
(let ((x 5))
(let ((!x 55))
(print x)))
This is a more general way to deal with hygiene issues because it
doesn't restrict the kinds of macro systems people are allowed to use.
Pascal
[1] The braces are only significant for the reader but not passed to the
Lisp evaluator/compiler.
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
>>>>> "Pascal" == Pascal Costanza <········@web.de> writes:
Pascal> Michael Sperber wrote:
>> The Common Lisp macros and the package system don't address all the
>> hygiene issues addressed by SYNTAX-RULES/SYNTAX-CASE,
Pascal> Yes, they do, AFAICS at the moment.
Pascal> [...] with syntax-case you have to use datum->syntax-object to
Pascal> ensure name capture. [...]
What you're saying is that *you* address the hygiene issues, not the
macro system.
--
Cheers =8-} Mike
Friede, V�lkerverst�ndigung und �berhaupt blabla
Michael Sperber wrote:
> What you're saying is that *you* address the hygiene issues, not the
> macro system.
Right.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Michael Sperber wrote:
>>>>>>"Pascal" == Pascal Costanza <········@web.de> writes:
>
>
> Pascal> Michael Sperber wrote:
>
>
>>>The Common Lisp macros and the package system don't address all the
>>>hygiene issues addressed by SYNTAX-RULES/SYNTAX-CASE,
>
>
> Pascal> Yes, they do, AFAICS at the moment.
>
> Pascal> [...] with syntax-case you have to use datum->syntax-object to
> Pascal> ensure name capture. [...]
>
> What you're saying is that *you* address the hygiene issues, not the
> macro system.
>
What he is saying is that, with SYNTAX-CASE and friends *you* have to
address the name-capture, when that is needed.
It's the other side of the medal. Both sides are interesting and you
can have it both ways in a given implementation of CL or Scheme.
Cheers
--
Marco
Pascal Costanza <········@web.de> wrote in message news:<···········@newsreader2.netcologne.de>...
> - Referential transparency for local bindings can be dealt with by
> modifying the reader. As a result of a recent discussion in c.l.l, I
> have written a modification that allows you to say, for example, the
> following.
>
> (let ((x 5))
> (macrolet
> ((test (y) `(list x ,y)))
> (let ((!!x 55))
> (test x))))
> => (5 55)
> The notation "!!" ensures that the subsequent symbol is a fresh, and
> therefore unique one, so the two different x don't clash with each other
> in the example above.
Or, here is something that uses standard read syntax:
(let ((x 5))
(macrolet ((test (y) `(list x ,y)))
(let ((#1=#:BUFFALO 55))
(test #1#))))
The read syntax #:BUFFALO produces a new, unique uninterned symbol
(whose name happens to be "BUFFALO" but that is completely
irrelevant). The read syntax #1=<OBJ> causes the reader to retain
<OBJ> in relation to the number 1, so later that object can be
repeated using the syntax #1#.
So effectively, your meta-variables become numbered items like #1# #2#
and so on.
I propose the following read syntax to simplify this:
\def\macro=#1#2#3{blah #1 #2 ...}
:)
I am sorry that I have to chime in again with a crosspost, but I feel
the need to clarify something, mainly because I am puzzled that
apparently people think this was a Common Lisp vs. Scheme thing (as in
"us vs. them"). This is nonsense.
Pascal Costanza wrote:
> - Referential transparency for local bindings can be dealt with by
> modifying the reader. As a result of a recent discussion in c.l.l, I
> have written a modification that allows you to say, for example, the
> following.
[...]
> (let ((x 5))
> (macrolet
> ((test (y) `(list x ,y)))
> {(let ((!x 55))
> (test x))}))
> => (5 55)
>
> The curly braces define a new package environment[1], and the "!"
> notation ensures a fresh symbol in the current package. Outside of the
> braces, the old package is in effect again.
To clarify: This just happens to be implemented with packages in Common
Lisp. It is not significant that CL packages are used here. It could be
implemented differently.
The main idea is that this approach requires from the programmer not
more cooperation than to mark the identifiers as fresh that he _already_
thinks of as fresh anyway. If he does not mark an identifier as fresh in
a binding construct, this means that an already existing identifier is
rebound. I think the difference between rebinding an existing and a
fresh identifier should be significant.
An only slightly modified suggestion would be to reverse the default:
Instead of requiring the programmer to mark fresh identifiers, she could
be required to mark rebindings of existing symbols specially, but by
default binding constructs introduce fresh identifiers. This would mean
that the example above could be rewritten as follows:
(let ((x 5))
(macrolet
((test (y) `(list x ,y)))
(let ((x 55))
(test x))))
...and still should yield (5 55). If one would want to rebind an
existing identifier, one would have to write, for example, this:
(let ((x 5))
(macrolet
((test (y) `(list x ,y)))
(let ((=x 55)) ;; rebind 'x introduced above
(test x))))
=> (55 55)
I stand by my claim that this would be a more general solution for
hygiene issues because it would work for any macro system that you might
come up with.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Pascal Costanza <········@web.de> wrote in message news:<···········@newsreader2.netcologne.de>...
> I stand by my claim that this would be a more general solution for
> hygiene issues because it would work for any macro system that you might
> come up with.
By the way, have you ever seen the university offices of some of these
macro hygiene nutcases? Or their clothes?
Personal hygiene, *then* macro hygiene, guys.
:)
···@ashi.footprints.net (Kaz Kylheku) writes:
> Pascal Costanza <········@web.de> wrote in message news:<···········@newsreader2.netcologne.de>...
>> I stand by my claim that this would be a more general solution for
>> hygiene issues because it would work for any macro system that you might
>> come up with.
>
> By the way, have you ever seen the university offices of some of these
> macro hygiene nutcases? Or their clothes?
>
> Personal hygiene, *then* macro hygiene, guys.
Maybe it's easier to change your name than your underwear.
--
~jrm
Pascal Costanza wrote:
> I am sorry that I have to chime in again with a crosspost, but I feel
> the need to clarify something, mainly because I am puzzled that
> apparently people think this was a Common Lisp vs. Scheme thing (as in
> "us vs. them"). This is nonsense.
I agree, we (or some of us at least) are trying not to play that game. It
doesn't achieve anything useful, and it inhibits learning.
> The main idea is that this approach requires from the programmer not
> more cooperation than to mark the identifiers as fresh that he _already_
> thinks of as fresh anyway. If he does not mark an identifier as fresh in
> a binding construct, this means that an already existing identifier is
> rebound. I think the difference between rebinding an existing and a
> fresh identifier should be significant.
>
> An only slightly modified suggestion would be to reverse the default:
> Instead of requiring the programmer to mark fresh identifiers, she could
> be required to mark rebindings of existing symbols specially, but by
> default binding constructs introduce fresh identifiers. This would mean
> that the example above could be rewritten as follows:
>
> (let ((x 5))
> (macrolet
> ((test (y) `(list x ,y)))
> (let ((x 55))
> (test x))))
>
> ...and still should yield (5 55). If one would want to rebind an
> existing identifier, one would have to write, for example, this:
>
> (let ((x 5))
> (macrolet
> ((test (y) `(list x ,y)))
> (let ((=x 55)) ;; rebind 'x introduced above
> (test x))))
> => (55 55)
>
> I stand by my claim that this would be a more general solution for
> hygiene issues because it would work for any macro system that you might
> come up with.
I don't consider this completely satisfactory, although for a somewhat
orthogonal reason to the point you're getting at. By way of explanation,
I'll respond to the following earlier statement:
> - Name capture is just a matter of switching the default behavior.
> With defmacro, you have to use gensyms to avoid name capture,
> and with syntax-case you have to use datum->syntax-object to
> ensure name capture.
There's more to it than just which mechanism you use to ensure or avoid name
capture. There's an important difference in the kinds of mechanism used.
In the defmacro case, all references to "pattern variables" (or the
equivalent thereof) have to be unquoted - similar to the situation in shell
languages and languages like Perl, where variable references have to be
unquoted with $ to distinguish them from the surrounding text, which is
assumed to be literal.
In the syntax-case case, pattern variables can be declared up front, either
in a pattern, or in a with-syntax form. Once declared, pattern variables
are automatically handled correctly in templates, and no unquoting is
needed.
You could, in principle, reverse the default behavior of name capture with
syntax-case, and still retain this substitution mechanism. I believe this
mechanism has advantages. I used defmacro before I ever used syntax-rules
and syntax-case, and I still use QUASIQUOTE regularly for things like
embedded XML-as-S-expressions, but I still make mistakes forgetting to
unquote or re-quasiquote things; or I use unquote when I should have used
unquote-splicing, or vice-versa.
I find the syntax-case approach to template substitution quite liberating,
because it requires little thought or care to author templates that work
first time. This may be considered a subjective thing, although I'd argue
that the subjective issue is whether the extra cognitive work involved with
QUASIQUOTE bothers you or not. (Anyone who hasn't worked with the
alternative may not recognize the extra work they do when authoring
quasiquote expressions.)
I also find it easier to read templates written in syntax-case style.
Although syntax-case supports quasiquote equivalents for syntax
(QUASISYNTAX, UNQUOTE-SYNTAX etc.), and has abbreviations for them (#` #,
#,@), I like to convert most such occurrences to use with-syntax instead,
turning the QUASISYNTAX into a pure SYNTAX template. The resulting template
shows the form of the output macro better, because for example generated
lists in the output can appear as (name ...) instead of as inline map or
list expressions, or single unquoted names like: ,somelist.
Using a pattern match for the input pattern and a properly constructed
template for the output pattern means that you can see at a glance how the
input form maps to the output form - it's like a high-level declaration of
the macro's behavior. Done properly, you could use these input & output
forms directly in documentation for a macro, and they often require little
other explanation.
So, when comparing the systems, we should remember that not only is their
default hygiene behavior opposite, but their template substitution
mechanisms are different too. These are more or less orthogonal issues.
Just to make this all a little more concrete, I recently converted a
defmacro macro written by someone else, to syntax-case. A nice example of
the difference can be seen in the following line:
`(,,k "descriptor" ,',supers ,',labels . ,,args)
Which converted to one of the following, depending on how you choose to
write it:
(syntax (k "descriptor" supers labels arg (... ...))
(syntax (k "descriptor" (super ...) (label ...) arg (... ...))
In converting, I didn't even try to think about what punctuation orgies like
,', mean - my quasiquote skills at that level are rusty, not having had to
be used for years - but I just wrote the converted version the way I
expected it to be, and it worked.
Anton
Anton van Straaten wrote:
> Pascal Costanza wrote:
>
>>The main idea is that this approach requires from the programmer not
>>more cooperation than to mark the identifiers as fresh that he _already_
>>thinks of as fresh anyway. If he does not mark an identifier as fresh in
>>a binding construct, this means that an already existing identifier is
>>rebound. I think the difference between rebinding an existing and a
>>fresh identifier should be significant.
[...]
>>I stand by my claim that this would be a more general solution for
>>hygiene issues because it would work for any macro system that you might
>>come up with.
>
> I don't consider this completely satisfactory, although for a somewhat
> orthogonal reason to the point you're getting at.
[...]
> So, when comparing the systems, we should remember that not only is their
> default hygiene behavior opposite, but their template substitution
> mechanisms are different too. These are more or less orthogonal issues.
Yes, I was focusing only on the hygiene part. The pattern matching stuff
is indeed interesting, and I can imagine to make use of it at least for
simple macros. I can only speculate whether they are also useful for
complex macros, so I will just believe you that that's the case for the
time being. ;)
It would be interesting to play with the defaults for hygiene by making
non-macro code cooperate a little better with macros, and see how this
would go along with the pattern matching mechanism.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Pascal Costanza wrote:
> Yes, I was focusing only on the hygiene part. The pattern matching stuff
> is indeed interesting, and I can imagine to make use of it at least for
> simple macros. I can only speculate whether they are also useful for
> complex macros, so I will just believe you that that's the case for the
> time being. ;)
There's good evidence readily available: take a look at PLT Scheme, for
example. It makes heavy use of syntax-case in many complex macros. For
example, its modules, units, and contracts system are all based on
syntax-case macros. Here's an example, picked more or less at random:
http://download.plt-scheme.org/scheme/plt/collects/mzlib/contract.ss
That file is >2700 lines, almost all macros and their support functions,
including macro-generating macros (with no comma-quote-comma shenanigans
required). It doesn't use the quasisyntax feature anywhere - all of the
syntax templates use the idiom I described previously, namely setting up
pattern variables, and then using the SYNTAX form in which pattern variables
are implicitly substituted.
Anton
Anton van Straaten wrote:
> Pascal Costanza wrote:
>
>>Yes, I was focusing only on the hygiene part. The pattern matching stuff
>>is indeed interesting, and I can imagine to make use of it at least for
>>simple macros. I can only speculate whether they are also useful for
>>complex macros, so I will just believe you that that's the case for the
>>time being. ;)
>
> There's good evidence readily available: take a look at PLT Scheme, for
> example. It makes heavy use of syntax-case in many complex macros.
I will definitely do that as soon as time permits.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
[Follow-up to comp.lang.lisp]
Michael Sperber <·······@informatik.uni-tuebingen.de> wrote in message news:<···············@informatik.uni-tuebingen.de>...
> (I'm not even going to start talking about the staging
> issues which are a complete nightmare in Common Lisp.)
Where can I learn more about these then?
David Fisher wrote:
> I'm trying to understand the power of various macro systems more
> clearly. Is this view correct:
>
> +------------------------------------------------------+
> | define | in terms of |
> | this |---------------------------------------|
> | | syntax-rules | syntax-case | defmacro |
> | | | | +gensym |
> |--------------+--------------+-------------+----------|
> | syntax-rules | :-) | + | |
> |--------------+--------------+-------------+----------|
> | syntax-case | - | :-) | |
> |--------------+--------------+-------------+----------|
> | defmacro | - | + | :-) |
> | +gensym | | | |
> +------------------------------------------------------+
>
> And what about the two gaps? No clear answer?
Sitarams syntax-rules for Common Lisp must give a +
in the top one. (And I think there is one in SLIB too?)
--
Jens Axel S�gaard
David Fisher wrote:
> I'm trying to understand the power of various macro systems more
> clearly. Is this view correct:
>
> +------------------------------------------------------+
> | define | in terms of |
> | this |---------------------------------------|
> | | syntax-rules | syntax-case | defmacro |
> | | | | +gensym |
> |--------------+--------------+-------------+----------|
> | syntax-rules | :-) | + | |
> |--------------+--------------+-------------+----------|
> | syntax-case | - | :-) | |
> |--------------+--------------+-------------+----------|
> | defmacro | - | + | :-) |
> | +gensym | | | |
> +------------------------------------------------------+
>
> And what about the two gaps? No clear answer?
What do you mean by defmacro+gensym? Presumably you have in mind something
more restricted than full Scheme. To use gensym effectively, though, you
might need LET. What about QUASIQUOTE, UNQUOTE, and UNQUOTE-SPLICING? What
about MAP?
If you restrict defmacro to a typical subset of Scheme/Lisp which supports
basic s-exp transformations, including all the above-mentioned operations,
you still don't have anything that's very good at general computational
tasks. To implement syntax-case, one of the first things you need to do is
define the syntax object abstraction which it depends on. Defining this in
terms of a restricted defmacro, even if possible, would be silly.
If you don't restrict defmacro, then an implementation of syntax-case "in
terms of" defmacro would not end up depending on the defmacro part very much
at all, except possibly for pattern-matching and destructuring of the
superficial syntactic forms. All the real implementation work would be done
in full Scheme.
Syntax-case is capable of implementing defmacro without resorting to full
Scheme because it is a high-level system which subsumes the functionality of
defmacro. You don't so much build defmacro using syntax-case, as expose the
inherent defmacro functionality in syntax-case. That's why the
implementation can be so short.
The reverse isn't true: the core defmacro functionality doesn't subsume
syntax-case, and building syntax-case requires general-purpose computational
capabilities which a restricted defmacro doesn't provide.
BTW, the above should also provide a clue as to why syntax-case is
considered the high-level system, and defmacro the low-level one (to address
a point raised in the prior incarnation of this thread).
Anton
Anton van Straaten wrote:
> The reverse isn't true: the core defmacro functionality doesn't subsume
> syntax-case, and building syntax-case requires general-purpose computational
> capabilities which a restricted defmacro doesn't provide.
There is no "core defmacro functionality". The whole point of defmacro
is that you can use all of your Lisp dialect in your macros.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Pascal Costanza wrote:
>
> Anton van Straaten wrote:
>
> > The reverse isn't true: the core defmacro functionality doesn't subsume
> > syntax-case, and building syntax-case requires general-purpose
computational
> > capabilities which a restricted defmacro doesn't provide.
>
> There is no "core defmacro functionality". The whole point of defmacro
> is that you can use all of your Lisp dialect in your macros.
I addressed this in the first paragraph of the post you responded to:
> What do you mean by defmacro+gensym? Presumably you have in
> mind something more restricted than full [Lisp]. To use gensym
> effectively, though, you might need LET. What about QUASIQUOTE,
> UNQUOTE, and UNQUOTE-SPLICING? What about MAP?
I've further addressed this in my replies to Peter Seibel.
To summarize: syntax-case similarly allows you to use all of the underlying
language in your macros. If the OP's question was asking "can I implement
macro system Y using macro system X, when macro system X gives access to the
full power of the underlying language", then the answer is obviously yes.
But in this case, the other systems would not be implemented "in terms of"
defmacro - demacro would be a relatively minor part of the implementation.
By contrast, defmacro can be implemented purely in terms of the syntax-case
macro system, without resorting to the full underlying language. This was
the distinction I was getting at.
Will Clinger has proposed an additional constraint to make the question more
interesting, which is that such a macro implementation should interact well
with, in effect, an *additional* macro system which pre-exists in the
language in question. However, the original question did not mention this
issue, and in the absence of further clarification, it can reasonably be
excluded as a possibility.
I, like Will, assumed that the question wasn't about the trivial issue of
whether Lisp is as Turing-complete as Lisp, and assumed a constraint. I
based this constraint on things hinted at in a prior version of this thread
on c.l.scheme, with the subject "define-syntax + syntax-case <->
define-macro".
Specifically, David Fisher asked about implementing other macro systems
using a "set of primitives" which included "DEFINE-MACRO + LET-MACRO +
LETREC-MACRO + GENSYM". In the current thread, he reduced this to
"defmacro+gensym". He seemed to be thinking of defmacro in terms of some
restricted subset of full Lisp/Scheme, although if that's the case, he has
yet to make clear what usable subset he had in mind.
Anton