toward a new Racket macro expander
383 views
Skip to first unread message
Matthew Flatt
Feb 26, 2015, 12:26:35 PM2/26/15
to d...@racket-lang.org
I've been working on a new macro expander for Racket, and I'm starting
to think that it will work. The new expander is not completely
compatible with the current expander --- and that will be an issue if
we eventually go forward with the change --- but most existing code
still works.
Here's a report on my current experiment:
http://www.cs.utah.edu/~mflatt/scope-sets/
The goals for a new expander are
1. to replace a complicated representation of syntax objects with a
simpler one (and, as a result, avoid some performance and
submodule-re-expansion problems that have been too difficult to fix
with the current expander);
2. to find a simpler model of binding than the current one, so that
it's easier to explain and reason about scope and macros; and
3. to implement the new expander in Racket instead of C.
I have possibly succeeded on 1, possibly succeeded to some degree on 2,
and temporarily given up on 3.
(I know it sounds crazy to continue with a C implementation of macro
expansion. Goals 1 and 2 were impossible for me without being able to
try ideas at scale, though, and it was too daunting to tackle a full
reimplementation of the expander and a restructuring of the VM at the
same time. Continuing in the comfortable-for-only-me C environment was
the way to make progress for now, and I look forward to tackling 3 as a
next step.)
I've pushed my current implementation to the "scope" branches of
https://github.com/mflatt/racket
https://github.com/mflatt/compiler [for `raco decompile` updates]
I don't recommend bothering with the implementation, for now, unless
you're especially interested in trying some examples. The current
version builds well enough to run DrRacket, but there some build
errors. I have a lot of work to do, still.
to think that it will work. The new expander is not completely
compatible with the current expander --- and that will be an issue if
we eventually go forward with the change --- but most existing code
still works.
Here's a report on my current experiment:
http://www.cs.utah.edu/~mflatt/scope-sets/
The goals for a new expander are
1. to replace a complicated representation of syntax objects with a
simpler one (and, as a result, avoid some performance and
submodule-re-expansion problems that have been too difficult to fix
with the current expander);
2. to find a simpler model of binding than the current one, so that
it's easier to explain and reason about scope and macros; and
3. to implement the new expander in Racket instead of C.
I have possibly succeeded on 1, possibly succeeded to some degree on 2,
and temporarily given up on 3.
(I know it sounds crazy to continue with a C implementation of macro
expansion. Goals 1 and 2 were impossible for me without being able to
try ideas at scale, though, and it was too daunting to tackle a full
reimplementation of the expander and a restructuring of the VM at the
same time. Continuing in the comfortable-for-only-me C environment was
the way to make progress for now, and I look forward to tackling 3 as a
next step.)
I've pushed my current implementation to the "scope" branches of
https://github.com/mflatt/racket
https://github.com/mflatt/compiler [for `raco decompile` updates]
I don't recommend bothering with the implementation, for now, unless
you're especially interested in trying some examples. The current
version builds well enough to run DrRacket, but there some build
errors. I have a lot of work to do, still.
Anthony Carrico
Feb 26, 2015, 4:13:48 PM2/26/15
to d...@racket-lang.org
On 02/26/2015 12:26 PM, Matthew Flatt wrote:
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
The utah.edu admins start to panic, suspecting an in progress dos
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
attack, but it is just ~mflatt getting slashdoted...
--
Anthony Carrico
David Vanderson
Feb 26, 2015, 10:54:16 PM2/26/15
to Matthew Flatt, d...@racket-lang.org
On 02/26/2015 12:26 PM, Matthew Flatt wrote:
> I've been working on a new macro expander for Racket, and I'm starting
> to think that it will work. The new expander is not completely
> compatible with the current expander --- and that will be an issue if
> we eventually go forward with the change --- but most existing code
> still works.
>
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
>
>
> The goals for a new expander are
>
> 1. to replace a complicated representation of syntax objects with a
> simpler one (and, as a result, avoid some performance and
> submodule-re-expansion problems that have been too difficult to fix
> with the current expander);
>
> 2. to find a simpler model of binding than the current one, so that
> it's easier to explain and reason about scope and macros; and
>
> 3. to implement the new expander in Racket instead of C.
>
> I have possibly succeeded on 1, possibly succeeded to some degree on 2,
> and temporarily given up on 3.
>
Thank you! I'm still trying to understand how the current expansion
> to think that it will work. The new expander is not completely
> compatible with the current expander --- and that will be an issue if
> we eventually go forward with the change --- but most existing code
> still works.
>
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
>
>
> The goals for a new expander are
>
> 1. to replace a complicated representation of syntax objects with a
> simpler one (and, as a result, avoid some performance and
> submodule-re-expansion problems that have been too difficult to fix
> with the current expander);
>
> 2. to find a simpler model of binding than the current one, so that
> it's easier to explain and reason about scope and macros; and
>
> 3. to implement the new expander in Racket instead of C.
>
> I have possibly succeeded on 1, possibly succeeded to some degree on 2,
> and temporarily given up on 3.
>
process works. This seems easier to reason about, so for me you're
hitting goal 2. And the comparison is helping me understand the current
process as well.
Thanks,
Dave
Neil Toronto
Mar 6, 2015, 11:01:01 AM3/6/15
to Matthew Flatt, d...@racket-lang.org
On 02/26/2015 12:26 PM, Matthew Flatt wrote:
> I've been working on a new macro expander for Racket, and I'm starting
> to think that it will work. The new expander is not completely
> compatible with the current expander --- and that will be an issue if
> we eventually go forward with the change --- but most existing code
> still works.
>
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
I'm enjoying reading this so far. Scope sets correspond with how I've
> to think that it will work. The new expander is not completely
> compatible with the current expander --- and that will be an issue if
> we eventually go forward with the change --- but most existing code
> still works.
>
> Here's a report on my current experiment:
>
> http://www.cs.utah.edu/~mflatt/scope-sets/
fuzzily thought about identifier bindings anyway. (I've never liked
thinking in terms of marks.) It's nice to see it more formalized.
I suppose you could say lexical scopes are monotone w.r.t. the subset
relation. Nonmonotonicity means an identifier might resolve to somewhere
else.
If two different bindings' scope sets are subsets of the same scope,
which references are ambiguous?
Neil ⊥
Matthew Flatt
Mar 6, 2015, 12:53:58 PM3/6/15
to Neil Toronto, d...@racket-lang.org
At Fri, 06 Mar 2015 11:00:57 -0500, Neil Toronto wrote:
> If two different bindings' scope sets are subsets of the same scope,
> which references are ambiguous?
Sorry, I don't understand the question. Two scope sets are always both
> If two different bindings' scope sets are subsets of the same scope,
> which references are ambiguous?
subsets of, for example, the union of the two sets; that doesn't imply
any ambiguity.
BTW, the solution to the problem described in section 3 doesn't work,
because it doesn't handle the case of a definition--use pair that is
introduced by a macro. I have a refinement that seems to work, so far;
it involves adding a scope for the original pieces of a macro use, as
well as a scope for the introduced pieces, but the original-piece
scopes have to be remembered and removed from any identifier that is
used for a binding in the same definition context. Some smaller details
have also changed. More soon.
Matthew Flatt
Mar 9, 2015, 12:10:11 PM3/9/15
to d...@racket-lang.org
Here's an updated version of my report on the macro experiment:
http://www.cs.utah.edu/~mflatt/scope-sets-2/
The main change is section 3, which presents a different solution than
before for the problem of using a macro in the same context where the
macro is defined. The old solution didn't work for a variant of the
example where both the macro definition and its use are
macro-introduced:
(define-syntax-rule (gen)
(begin
(define-syntax identity
(syntax-rules ()
[(_ misc-id)
(lambda (x)
(let ([misc-id 'other])
x))]))
(identity x)))
(gen)
With the old approach, `(gen)` would get a use-site scope, but
`(identity x)` wouldn't, and so the `x` provided to `identity` would
still capture (or create an ambiguous binding for) the `x` introduced
by `identity`. The new approach solves that problem by tying the
use-site scope to a macro invocation --- essentially symmetric to the
introduced-by-macro scope for a macro invocation --- instead of the
entire definition context. Some extra bookkeeping is needed to enable
macros that expand to definitions of use-site identifiers, but I think
it holds together.
This approach pushes a little more complexity into macros like `class`
and `unit` that manipulate definition contexts, but mostly they just
apply a new `syntax-local-...` function to identifiers that will be
moved into binding positions. We don't have a lot of those macros, and
adjusting them has been easy.
I've updated the "scope" branch at https://github.com/mflatt/racket. To
make the main distribution build, I've had to change various packages
in ways that aren't backward-compatible; I've forked the following
repos and given them "scope" branches at my GitHub account:
compatibility
drracket
r5rs
redex
compiler
macro-debugger
racklog
scribble
Authors and maintainers of those repos might want to check the kinds of
changes I'm having to make.
I still don't recommend trying to run the new macro expander, yet.
Although `raco setup` now builds all bytecode without error, running
and building documentation doesn't yet work, mostly because the story
on top-level evaluation is not yet right (I think).
http://www.cs.utah.edu/~mflatt/scope-sets-2/
The main change is section 3, which presents a different solution than
before for the problem of using a macro in the same context where the
macro is defined. The old solution didn't work for a variant of the
example where both the macro definition and its use are
macro-introduced:
(define-syntax-rule (gen)
(begin
(define-syntax identity
(syntax-rules ()
[(_ misc-id)
(lambda (x)
(let ([misc-id 'other])
x))]))
(identity x)))
(gen)
With the old approach, `(gen)` would get a use-site scope, but
`(identity x)` wouldn't, and so the `x` provided to `identity` would
still capture (or create an ambiguous binding for) the `x` introduced
by `identity`. The new approach solves that problem by tying the
use-site scope to a macro invocation --- essentially symmetric to the
introduced-by-macro scope for a macro invocation --- instead of the
entire definition context. Some extra bookkeeping is needed to enable
macros that expand to definitions of use-site identifiers, but I think
it holds together.
This approach pushes a little more complexity into macros like `class`
and `unit` that manipulate definition contexts, but mostly they just
apply a new `syntax-local-...` function to identifiers that will be
moved into binding positions. We don't have a lot of those macros, and
adjusting them has been easy.
I've updated the "scope" branch at https://github.com/mflatt/racket. To
make the main distribution build, I've had to change various packages
in ways that aren't backward-compatible; I've forked the following
repos and given them "scope" branches at my GitHub account:
compatibility
drracket
r5rs
redex
compiler
macro-debugger
racklog
scribble
Authors and maintainers of those repos might want to check the kinds of
changes I'm having to make.
I still don't recommend trying to run the new macro expander, yet.
Although `raco setup` now builds all bytecode without error, running
and building documentation doesn't yet work, mostly because the story
on top-level evaluation is not yet right (I think).
Matthew Flatt
Mar 25, 2015, 4:32:07 PM3/25/15
to d...@racket-lang.org
An update:
http://www.cs.utah.edu/~mflatt/scope-sets-3/
The write-up is mostly new from section 5 through section 11:
5 First-Class Definition Contexts
6 Rename Transformers
7 Modules and Phases
8 The Top Level
9 The Syntax-Function Zoo
10 Compatibility with the Current Racket Expander
11 Debugging Support
Section 7 was in the earlier drafts as section 5, but it was wrong.
Section 10 was formerly 8, but it's revised and expanded.
On the implementation side, `make` now completes without error
(including documentation). It uses about the same space and time as the
current expander, but just slightly more of each; I'm optimistic about
further improvement. The core Racket tests pass, but it's not hard to
find other tests that fail.
Here are the packages that I've forked to address incompatibilities
(mostly small changes) where the starred ones are new or updated since
my last report:
compatibility
drracket
r5rs
redex
compiler *
macro-debugger *
racklog
scribble *
typed-racket *
htdp *
While working on performance, I ended up converting the implementation
of immutable hash tables from AVL trees to HAMTs. The change was a
substantial improvement for representing scope sets, but most anything
that uses immutable hash tables can benefit.
After I get more tests passing and update documentation, I'll encourage
you to try it out --- maybe two weeks from now.
http://www.cs.utah.edu/~mflatt/scope-sets-3/
The write-up is mostly new from section 5 through section 11:
5 First-Class Definition Contexts
6 Rename Transformers
7 Modules and Phases
8 The Top Level
9 The Syntax-Function Zoo
10 Compatibility with the Current Racket Expander
11 Debugging Support
Section 7 was in the earlier drafts as section 5, but it was wrong.
Section 10 was formerly 8, but it's revised and expanded.
On the implementation side, `make` now completes without error
(including documentation). It uses about the same space and time as the
current expander, but just slightly more of each; I'm optimistic about
further improvement. The core Racket tests pass, but it's not hard to
find other tests that fail.
Here are the packages that I've forked to address incompatibilities
(mostly small changes) where the starred ones are new or updated since
my last report:
compatibility
drracket
r5rs
redex
compiler *
macro-debugger *
racklog
scribble *
typed-racket *
htdp *
While working on performance, I ended up converting the implementation
of immutable hash tables from AVL trees to HAMTs. The change was a
substantial improvement for representing scope sets, but most anything
that uses immutable hash tables can benefit.
After I get more tests passing and update documentation, I'll encourage
you to try it out --- maybe two weeks from now.
Gustavo Massaccesi
Mar 26, 2015, 2:53:01 PM3/26/15
to Matthew Flatt, Racket Devs
I'm still not sure that this is related, but in the old system two
equal consecutive marks cancel. But if you compose two markers, the
"composed" mark doesn't cancel when it's applied twice. For example:
;---
#lang racket
(define A (make-syntax-introducer))
(define B (make-syntax-introducer))
(define (AB x) (A (B x)))
(free-identifier=? #'x (A (A #'x))) ;==> #t
(bound-identifier=? #'x (A (A #'x))) ;==> #t
(free-identifier=? #'x (AB (AB #'x))) ;==> #t
(bound-identifier=? #'x (AB (AB #'x))) ;==> #f
;---
Does this change? (Is this related?)
Gustavo
> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/20150325203205.986B46501BC%40mail-svr1.cs.utah.edu.
> For more options, visit https://groups.google.com/d/optout.
equal consecutive marks cancel. But if you compose two markers, the
"composed" mark doesn't cancel when it's applied twice. For example:
;---
#lang racket
(define A (make-syntax-introducer))
(define B (make-syntax-introducer))
(define (AB x) (A (B x)))
(free-identifier=? #'x (A (A #'x))) ;==> #t
(bound-identifier=? #'x (A (A #'x))) ;==> #t
(free-identifier=? #'x (AB (AB #'x))) ;==> #t
(bound-identifier=? #'x (AB (AB #'x))) ;==> #f
;---
Does this change? (Is this related?)
Gustavo
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/20150325203205.986B46501BC%40mail-svr1.cs.utah.edu.
> For more options, visit https://groups.google.com/d/optout.
Matthew Flatt
Mar 26, 2015, 2:57:00 PM3/26/15
to Gustavo Massaccesi, Racket Devs
Yes, this changes. The new expander produces #t instead of #f in that
last case.
The old expander has some ordering constraints that are not properly
explained anywhere and are difficult to reason about. Those constraints
go away in the new expander.
> https://groups.google.com/d/msgid/racket-dev/CAPaha9OrYjSYM-xuhRNvGjaXcdyHUx0xG5
> ufy4RSD0VDup9%2B%3DA%40mail.gmail.com.
last case.
The old expander has some ordering constraints that are not properly
explained anywhere and are difficult to reason about. Those constraints
go away in the new expander.
> ufy4RSD0VDup9%2B%3DA%40mail.gmail.com.
Matthew Flatt
Mar 26, 2015, 3:06:57 PM3/26/15
to Racket Devs
I forgot to mention that Tim Disney has already(!) implemented
a set-of-scopes variant of sweet.js:
https://github.com/mozilla/sweet.js/pull/461
a set-of-scopes variant of sweet.js:
https://github.com/mozilla/sweet.js/pull/461
Reply all
Reply to author
Forward
0 new messages