"Bindings as sets of scopes"

[jariji]

Hi I want to bring this research to your attention because I think it's really cool and potentially applicable here.

Matthew Flatt, of Racket, has developed a new system for expanding macros that yields simpler scoping rules: "bindings as sets of scopes". It has since been adapted elsewhere such as in the Lean theorem prover.

Paper: https://www-old.cs.utah.edu/plt/publications/popl16-f.pdf
Code: https://github.com/mflatt/expander
Talk (very friendly, with colored diagrams): https://www.youtube.com/watch?v=Or_yKiI3Ha4

[c42f]

Thanks, I talked to some lovely and extremely helpful racketeers at JuliaCon last year before embarking on this project.

My impression is that Racket's macro expansion is famously tricky (idk, that's my impression?) because Racket tries really hard to not execute the user's top level module code, but also to expand macros. Having both those things is impossible but you can get a lot closer to "not execute top level code" than we do in Julia.

However, Julia takes the less safe but radically simpler option of just executing all module top-level statements in order, always. Thus we escape nearly all the complexity of the Racket macro expander. IIUC.

Can you comment on whether the above work is mainly another way to approach this hard problem of "not execute top level code if at all possible"?

[jariji]

It's a theory of hygiene, generalizing the concepts of lexical scope to resolve names properly in even complicated macro situations. IIUC you've done some work to improve Julia's hygiene issues already; this model might help simplify the work in that area.

[c42f]

Ok thanks!

I've currently got a system here which seems to work: JuliaLang/JuliaSyntax.jl#329

The summary is that any syntax manipulated during macro expansion carries the module it was defined within. This is used to disambiguate local and global identifiers and seems to solve hygiene issues automatically without any need for esc(). In that PR it's expressed as nested hygenic_scope syntactic forms and passed to Julia's existing macro expander to turn references into GlobalRef and renamed locals.

In JuliaLowering I'll be incorporating the hygenic scope resolution into lowering's resolve_scopes! pass. In fact, I'm just starting to work on that.

[c42f]

I've listened to the youtube talk a couple of times.

It's certainly not about Racket's pass system as I initially suspected - it's "just" about hygiene. But hygiene is hard so the talk is quite thought provoking, thanks again for posting.

I suspect we don't need a lot of the complexity they have there. Not least because we don't plan to support macros defined in local scope ("macro closures" in a sense - macros which capture local lexically scoped bindings).

However a lot of the basic problems are the same and they have a really interesting solution.

My solution for Julia is evolving into a system of "scope layers" (or "scope masks"? name TBD?), which kind of add an extra dimension to lexical scope resolution, a bit like the 3D diagram they use to explain their solution early in the talk. It's still in early prototyping, though. I hope to avoid the complexity of the full "set of scopes" machinery they describe but it may yet prove necessary.

[jariji]

Sounds good, I'm glad I shared it then. Cheers.

[c42f]

So, I'm still thinking about this, and I've yet to find a situation where Julia needs something more than a simple "scope coloring" provided by scope_layer.

One subtle issue is macros which define macros. For example,

module A

some_global = "global in A"

macro foo(name, body)
    quote
        macro $name()
            quote
                some_global, $$body
            end
        end
    end
end

end

module B
using ..A

another_global = "global in B"
A.@foo bar another_global
end

expansion = B.@bar()

Presumably expansion should be the tuple "global in A", "global in B" ? However I still think we can deal with this with the scope layer system, though it involves the quoted syntax in the body of @bar having properties which can't be represented in the surface syntax. (Eg, do we expand the $$body part into a globalref?)

[tecosaur]

If we're mentioning Racket-land, I'd be curious to know if you've seen what Rhombus (an experimental Racket project) is doing?

Here's a paper on its macros (also by Matthew Flat, but this one is from 2023 not 2015): Rhombus: A New Spin on Macros without All the Parentheses.

Matthew also gave a status update talk on Rhombus a few months ago: https://www.youtube.com/watch?v=OLgEL4esYU0 in which he shares the one-liner sales pitch of Rhombus as a way of making Racket macro technology more accessible.

[tecosaur]

In particular, I'd like to highlight the example from 13-14 minutes into Matt's talk, where there's the Rhombus macro

defn.macro 'datatype $name
            | $variant($field, ...)
            | ...':
  'class $name():
     nonfinal
   class $variant($field, ...):
     extends $name
   ...'

with example usage

datatype Expr
| Lambda(ids::List.of(String), body::Expr)
| App(f::Expr, args::List.of(Expr))
| Var(id::String)
| Const(n::Int)
| Let(id::String, rhs::Expr, body::Expr)

that's it! The (current) equivalent Julia code would (I think) be

macro datatype(ex::Expr)
    (Meta.isexpr(ex, :call, 3) && ex.args[1] == :(:)) ||
        throw(ArgumentError("datatype macro expects a 'name: args...' expression, not $ex"))
    name = ex.args[2]
    args = ex.args[3]
    out = Expr[]
    push!(out, :(abstract type $name end))
    while !isnothing(args)
        thisarg, args = if Meta.isexpr(args, :call, 3) && args.args[1] == :(|)
            args.args[3], args.args[2]
        elseif Meta.isexpr(args, :call)
            args, nothing
        else
            throw(ArgumentError("datatype macro expects a 'arg(field::Type...)' argument form, not $args"))
        end
        subname = thisarg.args[1]
        subtype = Expr(
            :struct, false, :($subname <: $(esc(name))),
            Expr(:block, map(
                a -> if a isa Symbol
                    :($a::Any)
                elseif Meta.isexpr(a, :(::), 2)
                    esc(a)
                else
                    throw(ArgumentError("datatype macro expects a 'arg(field::Type...)' argument form, not $a"))
                end,
                thisarg.args[2:end])...))
        push!(out, subtype)
    end
    Expr(:block, out...)
end

@datatype(Expr:
    Lambda(ids::Vector{String}, body::Expr) |
    App(f::Expr, args::Vector{Expr}) |
    Var(id::String) |
    Const(n::Int) |
    Let(id::String, rhs::Expr, body::Expr))

...I think I prefer the Rhombus macro 😅.

Furthermore, I don't think many people would disagree with the suggestion that Rhombus's macro is:

• Easier to read/understand
• Easier to reason about
• Easier to maintain
• Easier to implement correctly

[c42f]

I think I prefer the Rhombus macro

Absolutely. Isn't the main difference here that we don't have pattern matching of ASTs in Julia? We should have that, at some stage.

But this is a separate issue from hygiene which is the main subject of this issue?

[tecosaur]

Absolutely. Isn't the main difference here that we don't have pattern matching of ASTs in Julia? We should have that, at some stage.

In this example, the pattern matching and not needing to worry about hygiene (no :($subname <: $(esc(name))) or esc(a)) are the main differences.

But this is a separate issue from hygiene which is the main subject of this issue?

Somewhat 😅, I'm under the impression that looking at Rhombus there's more than just the hygiene approach (it inherits Racket's, and the paper cites Towards the Essence of Hygiene) that we might want to take inspiration from. Since Racket has come up here, I thought I'd add a comment before making a new issue.

[c42f]

Well, I've got a simple kind of "scope coloring" system in JuliaLowering and it seems to meet our needs so I guess I'll close this.

In JuliaLowering, we "color" each symbol in the AST - one color for symbols from the scope outside the macro invocation and a new unique color for any symbols emitted by each macro expansion. Symbols get a color regardless of whether they define a new binding in form like let or are just uses of a binding. After macro expansion, scope resolution resolves the symbol identity based on (name,color) pairs and on the normal nesting of the binding forms in the expanded AST.

I've tried several times to construct counter examples where this doesn't work but haven't been able to find any yet, even presuming we had local macros (to be clear there's no plans to implement those). That might just be due to my lack of experience with local macros though.

[tecosaur]

Nice! Would it be worth putting the other comments/thoughts around macros in another issue?