React in some way to Flatt's "Binding as a set of scopes" work in Racket

[masak]

There's a paper, a talk, and a GitHub repository with lots of branches, and an extended version of the paper, as a Scribble documentation page, and (edit) a seminar/course.

Let's call the most-recent view on how macro hygiene could work "the #​410 consensus". (I still fully intend to write this up as a blog post, but right now issue #410 is the most authoritative explanation of an actual mechanism for macro hygiene. Maybe "consensus" is a bit of an exaggeration, as the parties in agreement are myself and no-one else in particular.)

Flatt's solution is centered around a partial order of scopes, while the #​410 consensus is quite clearly still a tree of scopes.

In order to close this issue, answer these questions:

• Are there cases that Flatt's "set of scopes" hygiene handles that the #​410 consensus doesn't?
• Are there cases that the #​410 consensus handles but Flatt's "set of scopes" hygiene doesn't?
• Are there cases handled by both systems, but where they come to different conclusions?

It's possible that "set of scopes" hygiene is the style of hygiene out there that most resembles the #​410 consensus. For that reason alone, it's useful to understand how they differ, exactly, and whether one can be said to be objectively better than the other.

[masak]

This post seems to make an honest attempt at explaining the set-of-scopes idea. I should make an honest attempt at understanding the post.

[masak]

Adding this documentation page about Racket's syntax model for later/deeper perusal. I was linked to that one via the Turnstile paper and my curiosity about the #%app construct.

[masak]

This Sweet.js paper seems to make the claim that Sweet.js also uses the "set of scopes" system of hygiene. (It doesn't make that claim very strongly, IMO. It just cites Flatt's 2002 paper, and Hieb/Dybvig's 1992 paper.)

[masak]

From the seminar/course, around the 16-minute mark:

De Bruijn indices don't work [for this kind of macro hygiene]. They're a form of renaming. It's just a particularly opaque kind of renaming. And we're trying to avoid renaming. It's also missing this extra dimension [the one where macros inject code from elsewhere] — even in renaming systems you need to have that extra dimension for things to work, so we just focus on the extra dimension.

[masak]

From the extended version of the paper:

Roughly, every binding form and macro expansion creates a scope, and each fragment of syntax acquires a set of scopes that determines binding of identifiers within the fragment. In a language without macros, each scope set is identifiable by a single innermost scope. In a language with macros, identifiers acquire scope sets that overlap in more general ways.

I would say that "the #410 consensus" is based on renaming (using Flatt's terminology). As #410 itself points out, renaming and unique variables and direct lookup and gensyms are all different aspects of the same mechanism.

But "set of scopes" does a different thing, which can maybe be described as generalizing de Bruijn indexing from (handwave) a tree to a DAG. In a tree, a de Bruijn index is enough to uniquely identify an ancestor binder on the path up to the root from your current variable reference in the tree. In a DAG, it obviously isn't — but a set of scopes is enough information — you can follow all the paths up to the root from your variable reference, and find the binder with the "best" set of scopes compared to your variable reference's set of scopes (namely the uniquely-biggest subset of the variable reference's set of scopes).

As to how it can be a DAG in the first place — macro invocations now introduce their own scopes, which are a new kind of thing, a "non-surrounding scope", as it were. So your parent is not just your innermost surrounding binder, it's also one or more macro expansions that your variable "came from".

[masak]

I created a private GitHub repo with a toy programming language called "xor" (named after the "flip the scope bit" technique which is central to Flatt's whole set-of-scopes approach to hygiene), in order to focus in on exactly the mechanics behind set-of-scopes hygiene, and nothing else.