New expander and ambiguous bindings

[Brian Mastenbrook]

In the scope sets document (https://www.cs.utah.edu/~mflatt/scope-sets-5/pattern-macros.html#%28part._intdef%29) it is claimed that the following is ambiguous:

(define-syntax-rule (def-m m given-x)
(begin
(define x 1)
(define-syntax-rule (m)
(begin
(define given-x 2)
x))))

(def-m m x)
(m)

Rather confusingly, it is only ambiguous when `def-m' is used in the same definition context as where `def-m' is defined; the following is accepted with the same interpretation as the old expander:

(let ()
(def-m m x)
(m))

But the following provokes an ambiguous binding error:

;; tested with 6.2.900.17--2015-09-29(3154908/a)
(def-m m x)
(let ()
(m))

I can't follow why this should be the case given the reasoning for why the first example is ambiguous: "Absent the (define x 1) definition generated by def-m, the final x reference should refer to the definition generated from (define given-x 2)"; however, in the second permutation with the `let' surrounding just the use of `m', this would never be the case in the old expander, because that definition is not part of the same definition context.

After playing with various permutations of this, I encountered a behavior that seems like a clear violation of referential transparency:

(define x 'outer)

(define-syntax-rule (def-m m given-x)
(define-syntax-rule (m)
(begin
(define given-x 'inner)
x)))

(def-m m x)
(let ()
(m))

Under the old expander, this yields 'outer; under the new expander, it yields 'inner. Under both expanders, the following yields 'outer:

(let ()
(def-m m x)
(let ()
(m)))

The definition introduced by (define given-x 'inner) should never capture the use of `x' in `m', at least according to my mental model: either a given use of `m' should provoke a duplicate binding error, or it should refer to the outer `x'. I'm unable to find any convincing rationalization for why it would behave otherwise. What am I missing?

--
Brian Mastenbrook
br...@mastenbrook.net
http://brian.mastenbrook.net/

[Matthias Felleisen]

On Sep 29, 2015, at 7:20 PM, Brian Mastenbrook <br...@mastenbrook.net> wrote:

After playing with various permutations of this, I encountered a behavior that seems like a clear violation of referential transparency:

(define x 'outer)

(define-syntax-rule (def-m m given-x)
 (define-syntax-rule (m)
   (begin
     (define given-x 'inner)
     x)))

(def-m m x)
(let ()
 (m))

Under the old expander, this yields 'outer; under the new expander, it yields 'inner. Under both expanders, the following yields 'outer:

Up to this point, I would have said “obvious, let me explain” but the idea that wrapping a let () around the last expression changes its expansion blew my mind. I’d say it’s a bug. 

Think of the two-directional substitution I mentioned in Manifesto. Here is the next step: 

(define x 'outer)

(define-syntax-rule

  (def-m m given-x)

  (define-syntax-rule

    (m)

    (begin

      (define given-x 'inner)

      x)))

(define-syntax-rule

    (m)

    (begin

      (define x ‘inner) ;; <— the ‘x’ that is placed here is *the* x that is define-d above 

;; you want this to catch the next x because it is the *same* x and it was explicitly passed in 

      x))

(let ()

    (m))

So I will wait for Matthew to explain the let-wrapped expression. — Matthias

[Matthew Flatt]

At Tue, 29 Sep 2015 18:20:38 -0500, Brian Mastenbrook wrote:
> In the scope sets document
> (https://www.cs.utah.edu/~mflatt/scope-sets-5/pattern-macros.html#%28part._intd
> ef%29) it is claimed that the following is ambiguous:
>
> (define-syntax-rule (def-m m given-x)
> (begin
> (define x 1)
> (define-syntax-rule (m)
> (begin
> (define given-x 2)
> x))))
>
> (def-m m x)
> (m)
>
> Rather confusingly, it is only ambiguous when `def-m' is used in the same
> definition context as where `def-m' is defined; the following is accepted with
> the same interpretation as the old expander:
>
> (let ()
> (def-m m x)
> (m))

The relevant feature of the original example is that `def-m` and `m`
are defined in the same definition context. If you put the definition
of `m` in a more nested context, then it defeats the attempt at
ambiguity.

> After playing with various permutations of this, I encountered a
> behavior that seems like a clear violation of referential
> transparency:
>
> (define x 'outer)
>
> (define-syntax-rule (def-m m given-x)
> (define-syntax-rule (m)
> (begin
> (define given-x 'inner)
> x)))
>
> (def-m m x)
> (let ()
> (m))
>
> Under the old expander, this yields 'outer; under the new expander, it yields
> 'inner.
>

> The definition introduced by (define given-x 'inner) should never capture the
> use of `x' in `m', at least according to my mental model: either a given use
> of `m' should provoke a duplicate binding error, or it should refer to the
> outer `x'. I'm unable to find any convincing rationalization for why it would
> behave otherwise. What am I missing?

Let's simplify a little, since the line between the definition and use
of `m` is irrelevant:

(define x 'outer)

(define-syntax-rule (def-and-use-m given-x)
(begin

(define-syntax-rule (m)
(begin
(define given-x 'inner)
x))

(m)))

(def-and-use-m x)

The old expander gives 'outer, the new one gives 'inner. The results
are the same if you wrap a `(let () ....)` around `(m)`.


When you step back, it sure looks non-hygienic, because

(define-syntax-rule (def-and-use-m given-x)
(begin

(define-syntax-rule (m)
(begin
(define given-x 'inner)
x))

(m)))

looks like a reference to a `x` that should never be captured by any
`given-x`. The catch is that it's a free `x` with respect to the
context of `def-and-use-m`. In a context that allows both a definition
and a use of `def-and-use-m`, it can turn out that `given-x` is exactly
the identifier that the free `x` should refer to.

If you put `(def-and-use-m x)` under a `(let () ....)`, then can never
be the same `x`. But after `m` is defined in the same context as
`def-and-use-m`, it doesn't matter whether a use `(m)` is under a `(let
() ....)`.


For this kind of example, the difference between the old and new
expanders boils down to whether the following is true:

if `x` refers to a particular binding, then absent any other bindings
with the name "x", a macro introduction of `x` also refers to the
same binding

That's true for the next expander, because a macro introduction is just
an extra scope. It's false for the old expander, because various mark
and rename orderings matter (and benefits of the new expander often
have to do with avoiding dependencies on order).

[Brian Mastenbrook]

On 09/29/2015 09:23 PM, Matthew Flatt wrote:
> When you step back, it sure looks non-hygienic, because
>
> (define-syntax-rule (def-and-use-m given-x)
> (begin
> (define-syntax-rule (m)
> (begin
> (define given-x 'inner)
> x))
> (m)))
>
> looks like a reference to a `x` that should never be captured by any
> `given-x`. The catch is that it's a free `x` with respect to the
> context of `def-and-use-m`. In a context that allows both a definition
> and a use of `def-and-use-m`, it can turn out that `given-x` is exactly
> the identifier that the free `x` should refer to.

I'm afraid I'm still not following. To avoid confusing myself with
multiple issues, I'll start with a version of `m' that does not involve
splicing:

(define x 'outer)

(define-syntax-rule (def-and-use-m given-x)
(begin
(define-syntax-rule (m)

(let ()

(define given-x 'inner)
x))
(m)))

(def-and-use-m x)

As before, the old expander returns `outer' and the new expander returns
`inner'.

The reason that this seems to violate hygiene to me is that if I change
the definition of `m' to an ordinary procedure definition, I get 'outer
from both expanders. It seems to me to be the very essence of hygiene
that lexical capture works in macros the same way that it works in
ordinary definitions, and I'm surprised that such minor transformations
of the program are affecting the result in ways that don't seem to match
my mental model for how things "should" work.

However, I admit that I have internalized the old rules in order to be
able to reason about macro-generating macros, and am no longer able to
understand the confusion I once had about these things in the
marks-and-wraps model. Perhaps I just need to get used to the new model.

--
Brian Mastenbrook
br...@mastenbrook.net
https://brian.mastenbrook.net/

[Matthew Flatt]

You're right, and I was confused in my response before. Whether the
definition of `given-x` is splicing should matter, and 'outer is the
correct result above.

I'm fixing a bug in the implementation's handling of use-site scopes,
and that makes your example above work correctly. The bug is a holdover
from an earlier, broken idea of how to handle use-site scopes. Getting
rid of it --- bringing the implementation in line with the paper ---
solves the problem while the core test suite still passes and the main
distribution builds.

Thanks very much for pushing through the details and making sure the
implementation is right!


I think the examples in the paper are still correct, and it's still the
case that

(let ()
(def-m m x)
(m))

resolves the ambiguity. However, with the repaired expander, it's also
the case that

(def-m m x)
(let ()
(m))

resolves the ambiguity, in contrast to my earlier response. The
ambiguity depends (as originally intended) on a single definition
context shared by `def-m`, `m`, and `given-x`.

Similarly, it's still the case that

(define x 'outer)

(define-syntax-rule (def-m m given-x)

(define-syntax-rule (m)
(begin
(define given-x 'inner)

x)))

(def-m m x)
(m)

produces 'inner with the new expander and 'outer with the old one.
Again, though, the result is 'outer when adding a `(let () ....)`
around the last two lines, around just the `(m)`, or in place of the
`(begin ....)` within the definition of `m` --- any of which introduces
a more nested context for the definition of `given-x`.

[Brian Mastenbrook]

On 09/30/2015 07:55 AM, Matthew Flatt wrote:
> I'm fixing a bug in the implementation's handling of use-site scopes,
> and that makes your example above work correctly. The bug is a holdover
> from an earlier, broken idea of how to handle use-site scopes. Getting
> rid of it --- bringing the implementation in line with the paper ---
> solves the problem while the core test suite still passes and the main
> distribution builds.

Thanks!

> I think the examples in the paper are still correct, and it's still the
> case that
>
> (let ()
> (def-m m x)
> (m))
>
> resolves the ambiguity. However, with the repaired expander, it's also
> the case that
>
> (def-m m x)
> (let ()
> (m))
>
> resolves the ambiguity, in contrast to my earlier response. The
> ambiguity depends (as originally intended) on a single definition
> context shared by `def-m`, `m`, and `given-x`.

This makes sense to me now.

> Similarly, it's still the case that
>
> (define x 'outer)
>
> (define-syntax-rule (def-m m given-x)
> (define-syntax-rule (m)
> (begin
> (define given-x 'inner)
> x)))
>
> (def-m m x)
> (m)
>
> produces 'inner with the new expander and 'outer with the old one.
> Again, though, the result is 'outer when adding a `(let () ....)`
> around the last two lines, around just the `(m)`, or in place of the
> `(begin ....)` within the definition of `m` --- any of which introduces
> a more nested context for the definition of `given-x`.

I've gone back and forth on this a few times in my head, but I think
I've settled on believing that this makes sense. I will give tomorrow's
snapshot a try and see if my current mental model matches reality.