On 28 Oct 2009, at 3:36 pm, David Rush wrote:
> But my question (and
> challenge) is there a semantically sound way to model macros that
> returns them to their place inside EVAL? I am thinking in terms of an
> operator that can extend the reduction rules of the operational
> semantics f the language - perhaps that's daft in the way that I frame
> it, but it is certainly how the code *could* be (and certainly was)
> structured in some MCIs.
Yes, I think there is.
First, some definitions. I think we can take it as a given that a
desirable feature of a macro system is that macro expansions should be
decidable "before run time". It's overspecifying to call that "compile
time", "link time", or "tea time"; but being able to decide the macro-
expansion of a bit of code before we run it is desirable since it lets
us test the macro expansions in the lab, and it lets us actually
compile programs, rather than needing to keep the AST representation
present at run-time and change the semantics of the language as it is
unravelled (ok, this *can* be compiled - by caching executable
representations of AST subtrees, for example - but that's not an
implementation tradeoff everyone will enjoy).
That desire for being able to expand all the macros away before run
time, revealing a semantically equivalent program without any macros
in it (and from which all the macro definitions can therefore be
stripped or ignored), is part of what makes fexprs bad.
It's also tied to another desirable property, that of being easy to
reason about. Macros whose expansions can change at run time open up
the potential for some terrible obfuscations of the meaning of a
program.
So, I think that macros that can be decided without knowing the run-
time state of the program sit in a sweet spot of balancing power
versus decidability. For the rare cases where you really do want to
expand macros at run time - you know where eval is :-)
On the other hand, one can go to the extreme in the other direction:
you can produce a macro system that has no relationship whatsoever
with the semantics of Scheme. A sort of "M4 for sexprs". Allowing just
define-syntax at the top level and let-syntax elsewhere, with syntax-
rules, produces this; you could write a macro-expansion function that
takes a list of sexprs, some of which may be define-syntax, the rest
of which may contain let-syntax or calls to defined macros, and return
an expanded form - and use it for Scheme source code just as well as
for SXML representations of HTML documents.
This is the direction Scheme implementations seem to have taken; and
where they introduce "low-level" macros that contain Scheme source
code such as syntax-case, ER, synclos, and dirty old defmacro, they
tend to eval the bodies of those macros in a constructed environment.
Tricks like eval-when, define-for-syntax, and import phases are used
to make helpers available to macros, providing definitions that are
inserted into that expand-time environment. But you can't still macro-
expand SXML, even if you wrapped it in appropriate module forms, as
hygienic macros need to be aware of binding forms; they look out for
lambda (and let and friends, if they haven't just been expanded into
lambdas).
But there are other options!
For a start, you can macroexpand as you walk the code, whether that
code-walk is for compilation or interpretation. The difference being
that the compilation code-walk will not know the values of all
symbols, while an interpretation codewalk will.
A compilation (or, indeed, any pre-run-time) code-walk will be able to
know the values of symbols that refer to things that are bound to
constants (or to expressions that, given only what we know at compile
time, reduce to constants) - in other words, not symbols that are ever
the target of set!, nor symbols that are the arguments to a lambda
unless we are inlining an application of the lambda to known arguments
(so we have concrete values to put in place).
But, particularly if we restrain ourselves from too much set!, that
still gives us a lot. The semantics of the following program are
obvious:
(define (foo x)
(x 3.14159))
(define-syntax wibble (er-macro-transformer
(lambda (form rename compare)
`(,(rename 'sin) ,(cadr form)))))
(define (wobble x) (* x 2))
(write (foo wobble))
(write (foo wibble))
Even if the 3.14159 in foo was not knowable at run time, let's say
it's some variable 'bar' defined in some outer scope, the meaning of
the final writes is still clearly, after a little inlining (of both
macros and procedures):
(write (sin bar))
(write (* bar 2))
Expanding macros like this requires getting deep down and dirty into
the semantics of the Scheme program; we need to do some of that to be
hygienic, but we need it even more if macros are to be treated more as
first-class citizens.
What if we wrote:
(write (foo (if baz wobble wibble)))
...where baz is another run-time value? We could tell the user they've
used a macro in a way that can't be expanded statically - or perhaps
we could go a little further, and rewrite that to:
(write (if baz (foo wobble) (foo wibble)))
...which can be statically expanded into:
(write (if baz (sin bar) (* bar 2)))
From this, I think that Scheme should be trying to move away from
mutation. Perhaps make set! *optional*, and make cons cells immutable
(with an optional mutable cons cell). Likewise for vectors and
structures, perhaps. And then trade off the gains this gives you in
the ease of static analysis to do more clever static analysis. A bit
of type analysis won't go amiss, either :-)
ABS
--
Alaric Snell-Pym
Work: http://www.snell-systems.co.uk/
Play: http://www.snell-pym.org.uk/alaric/
Blog: http://www.snell-pym.org.uk/archives/author/alaric/
_______________________________________________
r6rs-discuss mailing list
r6rs-discuss@lists.r6rs.org
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
