accidental variable capture about klister HOT 12 CLOSED

I think it would be helpful to explicitly separate out a few points.

Why does letrec need an extra scope?

A naïve hygiene algorithm built on sets of scopes runs into trouble with recursive macros. The example given in the paper is this one:

(letrec-syntax ([identity (syntax-rules ()
                            [(_ misc-id)
                             (lambda (x)
                               (let ([misc-id 'other])
                                 x))])])
  (identity x))

We can explain this problem intuitively. The issue is that we usually think of letrec’s bindings, RHSs, and body as all being in the same scope. If this is true, then the x identifier in the letrec-syntax body is actually in the same scope as the identity RHS, so it can bind the x in the macro.

However, our intuition tells us that this should not be allowed because the body of a letrec is really in a more nested scope than the RHSs. In a language without macros, it is okay to treat the body of a letrec as having the same scope as its RHSs because there is no way for a binding identifier in the body to be moved into a location where it could bind an expression in the letrec’s RHS, but in a language with macros, this is possible. Therefore, we can’t get away with this imprecision, and we have to be explicit about the fact that the letrec body is really a more nested scope.

Adding an additional scope to the letrec body corrects the problem by explicitly making it a more nested scope that the RHSs. Issue solved.

A body scope is not enough for definition contexts

The above solution works for letrec-syntax, but when we try to generalize it to recursive definition contexts, we run into a new problem. Consider the above example adapted to use a definition context:

(define-syntax-rule (identity misc-id)
  (lambda (x)
    (let ([misc-id 'other])
      x)))

(identity x)

We fixed letrec by making a distinction between the body and the RHSs, but with a recursive definition context, there is no such distinction.

Let’s go back to intuitions. Why are we confident that the use of x in the macro body should refer to the lambda-bound x, not the let-bound x? I think there are two possible explanations one can come up with:

1. The lambda-bound x is lexically more local: the let-bound x is in scope (since it originates from an enclosing definition context), it’s just shadowed by the lambda-bound x.

2. The let-bound x does not appear in binding position in the definition context, so it is “more local” than the definition context RHSs and is not in scope at the macro-introduced use of x.

It is important to understand that these two explanations are not equivalent notions of hygiene, as they disagree on the behavior of the following program:

(define-syntax-rule (not-identity misc-id)
  (let ([misc-id 'other])
    x))

(not-identity x)

Here, I’ve removed the lambda altogether. Under the first interpretation, this program should be accepted, since the let-bound x is in scope at x’s use, and there is no longer any more local binding to shadow it. Under the second interpretation, this program should be rejected with an unbound identifier error, since the let-bound x is not in scope at the macro-introduced use of x.

Which of these two arguments is correct is up for debate, as there is no formal definition of lexical scope in the presence of arbitrary macros. However, I think the second explanation is compelling, since it preserves the spirit of the distinction we made for letrec: just as the body of letrec is “more nested” than the RHSs, the body forms of a definition context are similarly “more nested”.

The problem with this explanation is that it is impossible to determine whether or not an identifier appears “in binding position” without expanding macros. Consider the following modified program:

(define-syntax-rule (define-other x)
  (define x 'other))

(define-syntax-rule (not-identity misc-id)
  (begin
    (define-other misc-id)
    x))

(not-identity x)

When we expand not-identity, we have no way of knowing whether x is “in binding position” in (define-other x). We only learn this once we expand define-other and discover that, in fact, it is.

One way to think about this is that we must pessimistically assume that no identifiers in a definition context are in binding position until we expand enough to discover a define or define-syntax form. At this point, the bound identifier must “puncture” the more nested scope that it originated from so that it is made visible everywhere in the definition context.¹

In sets of scopes, this “puncturing” naturally corresponds to pruning of scopes, but what scopes do we prune? We still can’t have a single body scope that we apply to the entire definition context, since that would also apply to other RHSs.

Finally, use-site scopes

We can’t have a single, monolithic body scope like we did for letrec, so our only option is to have many body scopes. We need to keep the contents of each form expanded directly in the context distinct from each other, so we generate a distinct scope for each macro application.

To handle the “puncturing” of define, we must keep track of all of the generated scopes that were produced by expansion of a macro that appears immediately in the body of the definition context. That is, there would be no need to track the use site scope generated for the expansion of identity in the following, modified program:

(define-syntax-rule (identity misc-id)
  (lambda (x)
    (let ([misc-id 'other])
      x)))

(#%expression (identity x))

Since the expansion of identity cannot introduce new definitions, it can’t possibly “puncture” its use site scope, so there is no need to track the scope. But we do still need to introduce the scope, since otherwise we’d run into the binding issue from before (since the x in the macro use site still does not have any additional scopes).

Answers to your questions

With all of that context, the answers to your questions should hopefully be clearer. Still, let me go through and answer them explicitly.

At first I interpreted this last paragraph to mean that all use-site scopes must be removed from all binding sites.

Certainly not! These scopes should only be removed when they have been “punctured”. Forms like lambda or letrec don’t allow expansion in binding positions (ignoring the definition context in their body), so there is no way for this puncturing to occur there.

Taking a closer look at the difference between the m1 and define-identity examples, my second interpretation is that it is only define which should remove the use-site scopes, not let.

This is closer, but it is still not quite right. define should not prune all use-site scopes, only “punctured” ones: the ones that were introduced for macroexpansions directly in the definition context.

But I don't understand why this is the desired behaviour. My flawed intuition says that the x use site should refer to whatever x is bound to at define-five's definition site, as that's what it means to avoid accidental capture!

Ah, but recursive definition contexts are just that: recursive! Consider the following example:

(define-syntax-rule (define-printable-struct name-id fields
                      #:get-contents get-contents-expr)
  (struct name-id fields
    #:property prop:custom-write
    (λ (self out mode)
      (define contents (get-contents-expr self))
      (fprintf out "#<~a:~a>" 'name-id
               (if (annotated? contents)
                   (annotated-value contents)
                   contents)))))

(define-printable-struct annotated (value metadata)
  #:get-contents annotated-value)

In this example, the macro is used to define a struct that has a custom-write procedure attached to it. The custom-write procedure has a bit of special logic that checks if the value returned by get-contents-expr is an instance of annotated?, in which case it just prints the value, not the metadata.

As it happens, we then decide to use this very same macro to define the annotated struct in the first place! This is totally reasonable, since define-printable-struct is defined in the same recursive definition context where it is used, so annotated? and annotated-value are in scope in its expansion. Other uses of the macro may appear in totally different scopes, but hygiene will ensure that annotated? and annotated-value in the body will always refer to the ones defined at the macro’s definition.

This time, my flawed intuition says that the x use site after the (define misc-id 6) should still refer to "defined six", while the x use site after the (define-six x) call should refer to 6.

This works out because the "defined six" definition of x is more local than the other definition. That is, it essentially follows from argument 1 way back in the second section of this comment (since argument 2 no longer applies).

Possibility 1: add the use-site scope to the declaration environment

Yes, this is what Racket does. Each distinct definition context tracks its own set of use site scopes while it is partially expanding body forms.

Possibility 2: remove the use-site scopes later

I don’t think I really understand this proposal, but it smells fishy to me. You shouldn’t be changing the scopes on bindings after they’ve already been bound!

Possibility 3: negative scopes

This also smells fishy to me, but I haven’t thought about it enough to say terribly meaningfully whether it would work one way or the other. I’d be surprised if you could get it to handle all the complicated scoping patterns discussed in this comment, but I’d be happy to be proven wrong!

from klister.

At first glance, this looks like yet another bug in our scope set implementation. However, I think the issue is deeper than that: if I calculate the scope sets by hand according to my understanding of the scope set algorithm, I expect Klister's behaviour, not Racket's! This means I don't even understand the scope set algorithm :(

Here is my understanding of the scope set algorithm. When m1 is expanded, the m1 scope is added to stx, so we have

(let [x{m1} 2]
  (list x{m1}))

(I am only including the scope sets on the occurrences of x, for succinctness)

Then, m1 splices in an x which does not have the m1 scope:

(let [x 1]
  (let [x{m1} 2]
    (list x{m1} x)))

Then, when m1 returns the above Syntax, the m1 scope is flipped everywhere, so that it is only the x introduced by m1 which has the m1 scope, instead of everything else having it.

(let [x{m1} 1]
  (let [x 2]
    (list x x{m1})))

Then, the outer let is expanded and the let scope is added both to the outer let binding site and to its body; that is, the let1 scope is added to everything.

(let [x{m1,let1} 1]
  (let [x{let1} 2]
    (list x{let1} x{m1,let1})))

Then, the inner let is expanded and the let2 scope is added both to the inner let binding site and to its body.

(let [x{m1,let1} 1]
  (let [x{let1,let2} 2]
    (list x{let1,let2} x{m1,let1,let2})))

Then, the x{let1,let2} use site is resolved. The only candidate is the x{let1,let2} binding site, so the value is 2. The x{m1,let1} binding site is not a candidate because {m1,let1} is not a subset of {let1,let2}.

Finally, the x{m1,let1,let2} use site is resolved. Both binding sites are candidates, because {m1,let1} and {let1,let2} are both subsets of {m1,let1,let2}. In this example, this leads to an exception about x being ambiguous, because both subsets have the same size.

Correspondingly, in the second example, when we resolve the x{m2,let1,let2,let3} use site, both x{m2,let1} and x{let1,let2,let3} being candidates. In this case, x is not ambiguous because the second subset is bigger than the first; but that's not what we want, because x{let1,let2,let3} comes from stx, it was not introduced by the macro!

from klister.

Tagging @david-christiansen, our scope set expert :)

from klister.

I think I have a solution, but I worry about straying away from the path which is documented in the literature.

My solution is "negative scopes". That is, I think that instead of a set of scopes, in which each scope can either be present (1) or absent(0), I think there should be a third possibility in which a scope is forbidden (-1). The semantics of a forbidden scope is that if a scope is present at the binding site but forbidden at the use site, then that binding site is not a candidate binding for that use site.

Currently, each macro invocation has a scope, which is present in the pieces of code inserted by the macro, absent outside of the macro's call site, and also absent in the pieces of code which the macro copied from its input. I propose that the scope should instead be forbidden from the pieces of code copied from its input.

Binding sites introduced by the macro would continue to only be visible by use sites introduced by the macro, because the binding site includes the macro's scope and thus its scope set can only be a subset of scope sets which also include that scope. More importantly, binding sites copied from the input would no longer be visible to the use sites introduced by the macro, because the binding site has the macro scope present while the use site now has it forbidden. And using a forbidden scope instead of an absent scope would have no other effect because forbidden scopes only affect binding sites which use that scope, and the binding sites in the previous sentence are the only binding sites with the macro's scope.

from klister.

This looks to me to be a consequence of us not pruning scopes in quote, cf section 4.2 in https://www.cs.utah.edu/plt/popl16/popl16-paper50.pdf .

from klister.

I don't think that's it; when I convert the examples from section 4.2 to Klister, they give the intended results as defined in that section:

#lang "prelude.kl"
(import (shift "prelude.kl" 1))

(define-macros
  ([m1 (lambda (stx)
         (let [id 'x]
           (pure
             `(let [,id 1]
               x))))]))

-- (let [x a]
--   x)
-- =>
-- 1
(example
  (m1))


(define-macros
  ([m2 (lambda (stx)
         (>>= (free-identifier=? (let [x 1] 'x)
                'x)
           (lambda (r)
             (case r
               [(true)
                (pure '(true))]
               [(false)
                (pure '(false))]))))]))

-- (false)
(example
  (m2))

from klister.

I think you’re missing use-site scopes.

from klister.

Thanks for taking a look! I confirm that the Klister version of the example in that use-site scopes documentation fails in Klister too:

#lang "prelude.kl"
(import (shift "prelude.kl" 1))
(import (shift "list.kl" 1))

(define-macros
  ([m1 (lambda (stx)
     (case (open-syntax stx)
       [(list-contents (list _ misc-id))
        (pure `(lambda (x)
                 (let [,misc-id 'other]
                   x)))]))]))

-- (lambda (x{m1,lambda1})
--   (let [x{lambda1,let2} 'other]
--     x{m1,lambda1,let2}))  -- {m1,lambda1} and {lambda1,let2} are both subsets
--                           -- of size 2, so we get "Ambiguous identifier
--                           -- in phase p0: x"
(example
  (m1 x))

from klister.

I have partially implemented use-site scopes, and that has fixed the problem with m1. Thanks again, @lexi-lambda!

Unfortunately, I still need help. I am now struggling with the second part of the Racket documentation of use-site scopes, which says that use-site scopes should be removed from binding sites:

(define-syntax-rule (define-identity id)
  (define id (lambda (x) x)))

(define-identity f)
(f 5)

If the expansion of define-identity f adds a scope e_use to the use-site f, the resulting definition of f{e_use} does not bind the f in f 5.

[...]

To support macros that expand to definitions of given identifiers, a definition context must keep track of scopes created for macro uses, and it must remove those scopes from identifiers that end up in binding positions (effectively moving them back to the definition scope). In the define-identity [example], the use-site scope is removed from the binding [identifier] f, so [it is] treated the same as if [its definition] appeared directly in the source.

At first I interpreted this last paragraph to mean that all use-site scopes must be removed from all binding sites. Unfortunately, that version of the code reverts to failing on m1. It's not too hard to see why: that version does absolutely nothing!

-- without use-site-macros.
(lambda (x{m1,lambda1})
  (let [x{lambda1,let2} 'other]
    x{m1,lambda1,let2}))  -- ambiguous: {m1,lambda1} and {lambda1,let2} are both subsets of size 2

-- with use-site-macros on both binding sites and the use sites.
(lambda (x{m1,lambda1})
  (let [x{m1-use,lambda1,let2} 'other]
    x{m1,lambda1,let2}))  -- unambiguous: only {m1,lambda1} is a subset

-- with use-site-macros, but only on the use sites.
-- note: misc-id doesn't have any use sites!
(lambda (x{m1,lambda1})
  (let [x{lambda1,let2} 'other]
    x{m1,lambda1,let2}))  -- ambiguous: {m1,lambda1} and {lambda1,let2} are both subsets of size 2

Taking a closer look at the difference between the m1 and define-identity examples, my second interpretation is that it is only define which should remove the use-site scopes, not let. That works for both examples! However, I have two problems with that implementation: it feels wrong, and that doesn't match Racket's behaviour.

First, here's why the strip-use-site-scopes-from-define implementation feels wrong. The Racket documentation gives the following example:

In

(define-syntax-rule (define-five misc-id)
  (begin
    (define misc-id 5)
    x))

(define-five x)

the introduced x should refer to an x that is defined in the enclosing scope, which turns out to be the same x that appears at the use site of define-five.

I understand that if define strips off the use-site scope, then yes, the x use-site will refer to the misc-id binding:

-- with use-site macros, except on define's binding sites.
(begin
  (define x{define1} 5)
  x{define-five,define1}))  -- unambiguous: only {define1} is a subset

But I don't understand why this is the desired behaviour. My flawed intuition says that the x use site should refer to whatever x is bound to at define-five's definition site, as that's what it means to avoid accidental capture!

Second, here's why the strip-use-site-scopes-from-define implementation does not match Racket's behaviour. The following example attempts to recreate the same problem as m1, but using define instead of let and lambda:

#lang racket
(define-syntax-rule (define-six misc-id)
  (begin
    (define x "defined six")
    (define misc-id 6)
    x))
(define-six x)
x

This time, my flawed intuition says that the x use site after the (define misc-id 6) should still refer to "defined six", while the x use site after the (define-six x) call should refer to 6. This time, Racket's behaviour matches my flawed intuition, as the above code outputs what I expect:

"defined six"
6

But with Klister's strip-use-site-scopes-from-define implementation, the first use site is ambiguous:

-- with use-site macros, except on define's binding sites.
(begin
  (define x{define-six,define1} "defined six")
  (define x{define1,define2} 6)
  x{define-six,define1,define2})  -- ambiguous: {define-six,define1} and {define1,define2} are both subsets of size 2

Thus, despite implementing use-site scopes, Klister is still having accidental variable capture issues which Racket doesn't have.

from klister.

Another problem with only removing the use-site scopes from define calls is that the use-site macros remain on the output of macros in a pattern position:

(define-syntax-rule (list2 x y)
  (:: x (:: y (nil))))

-- (case (list 1 2)
--   [(:: a{list2-use,pattern1} (:: b{list2-use,pattern2} (nil)))
--    (list a{pattern1,pattern2} b{pattern1,pattern2})])  -- not in scope
(example
  (case (list 1 2)
    [(list2 a b)
     (list a b)]))

from klister.

Let's see, I want the (define-six x) example to generate

(begin
  (define x{define-six,define1} "defined six")
  (define x{define-six-use,define1,define2} 6)
  x{define-six,define1,define2})  -- unambiguous: only {define-six,define1} is a subset

so that x{define-six,define1,define2} is unambiguous, but I also want the x after the (define-six x) call to refer to this x{define-six-use,define1,define2}. How? I see a few possibilities.

Possibility 1: add the use-site scope to the declaration environment

In the same way that (define x{define1} 5) adds the define1 scope to the declaration environment, allowing subsequent x use sites to be able to refer to this x{define1}, perhaps (define-six x) should add the define-six-use scope to the declaration environment, thus allowing subsequent x use sites to be able to refer to x{define-six-use,define1,define2}?

I guess this is only needed when the macro is called in a declaration position? And pattern positions, I guess. And type-pattern positions.

What about calls to expand-syntax? I guess our version of expand-syntax will require the caller to specify the Problem being solved, and thus that calls to expand-syntax with the module, expression, and type problems will keep their use-site scopes, while calls with the declaration, pattern, and type-pattern problems will not?

Possibility 2: remove the use-site scopes later

What if the x is (define x 6) was x{define-six-use,define1,define2} while the macro is expanding, but x{define1,define2} afterwards? This would allow the x{define-six,define1,define2} inside the macro to correctly resolve to the x{define-six,define1}, and it would allow the x{define1,define2} after the (define-six x) call to resolve to 6.

Possibility 3: negative scopes

Recall my proposal for negative scopes, above: the identifiers which come from the call site should be tagged with a "forbidden" scope instead of a use-site scope, and what that means is that if a scope is present at the binding site but forbidden at the use site, then that binding site is not a candidate binding for that use site. The other way around is allowed: if a scope is present at the use site but forbidden at the binding site, then that candidate behaves as if the forbidden scope was absent.

This solves all the examples in a way which matches Racket's behaviour, even in the one case in which Racket diverges from my flawed intuition:

(lambda (x{m1,lambda1})
  (let [x{anti-m1,lambda1,let2} 'other]
    x{m1,lambda1,let2}))  -- unambiguous: only {m1,lambda1} is a candidate

(define f{anti-define-five,define1} (lambda (x) x))
(f{define1} 5)  -- unambiguous: only f{anti-define-five,define1} is a candidate

-- this is the case where Racket and my flawed intuition differ
(begin
  (define x{anti-define-five,define1} 5)
  x{define-five,define1})  -- unambiguous: only x{anti-define-five,define1} is a candidate
(define-five x)
x{define1}  -- unambiguous: only x{anti-define-five,define1} is a candidate

(begin
  (define x{define-other-five,define1} 5)
  x{anti-define-five,define1})  -- not in scope

(begin
  (define x{define-six,define1} "defined six")
  (define x{anti-define-six,define1,define2} 6)
  x{define-six,define1,define2})  -- unambiguous: only x{define-six,define1} is a candidate
(define-six x)
x{define1,define2}  -- unambiguous: only x{anti-define-six,define1,define2} is a candidate

(case (list 1 2)
  [(:: a{anti-list2,pattern1} (:: b{anti-list2,pattern2} (nil)))
   (list a{pattern1,pattern2} b{pattern1,pattern2})])  -- unambiguous

from klister.

Thanks a million for this very detailed explanation! I especially like how you explained why use-site scopes need to be added and removed, and not just how, as this allows me to adapt the argument to Klister's slightly-different situation: Klister's definition contexts are not recursive.

Why does let* need an extra scope

Since Klister's definition contexts are not recursive, it is let*, not let-rec, which is the let variant whose semantics are the closest to the Klister's definition contexts. Or just let when there is only one definition:

#lang racket

(let-syntax ([identity (syntax-rules ()
                         [(_ misc-id)
                          (lambda (x)
                            (let ([misc-id 'other])
                              x))])])
  ((identity x) 5))  ; => 5

#lang "prelude.kl"
(import (shift "prelude.kl" 1))
(import (shift "list.kl" 1))

(example
  (let-syntax [identity
               (lambda (stx)
                 (case (open-syntax stx)
                   [(list-contents (list _ misc-id))
                    (pure `(lambda (x)
                             (let [,misc-id 'other]
                               x)))]))]
    ((identity x) 5)))  -- => 5

Because let-syntax is not recursive, the body has an extra scope which the RHS doesn't have, and that scope allows the body to see identity.

A "body" scope after definition contexts

Since Klister's definition contexts are not recursive, the code after the define is inside a new scope, which allows that code to see the newly-defined identifier. In theory, the x in (identity x) should then definitely be more local than the define-syntax-rule RHS, and thus should not be a candidate for the x use site inside the let. Unfortunately, this is not the case.

#lang racket

(define-syntax-rule (identity misc-id)
  (lambda (x)
    (let ([misc-id 'other])
      x)))

((identity x) 5)  ; => 5

#lang "prelude.kl"
(import "define-syntax-rule.kl")

(define-syntax-rule (identity misc-id)
  (lambda (x)
    (let [misc-id 'other]
      x)))

-- (lambda (x{define-macros1,identity1,lambda1})
--   (let [x{define-macros1,lambda1,let1} 'other]
--    x{define-macros1,identity1,lambda1,let1}))  -- ambiguous:
--                                                -- {define-macros1,identity1,lambda1}
--                                                -- and {define-macros1,lambda1,let1}
--                                                -- are both subsets of size 3
(example
  ((identity x) 5))

The problem is that define-macros (to which define-syntax-rules desugars) makes the same mistake as the naive let-rec which does not add a separate scope for its body. define-macros allows several macros to be defined at once, and each of those macros can generate code containing calls to any of the other macros. In order to accomplish this, a single scope is used for all the RHSs, and that same scope is also added to the code which follows the define-macros call, so that this code can refer to the newly-defined macros. The problem is that define-macros should be adding a second scope to the code which follows the define-macros call, to act like the let-rec body scope, but it does not.

After fixing this bug, the example behaves as expected.

#lang "prelude.kl"
(import "define-syntax-rule.kl")

(define-syntax-rule (identity misc-id)
  (lambda (x)
    (let [misc-id 'other]
      x)))

(example
  ((identity x) 5))  -- => 5

Finally, no use-site scopes

We can just add a single body scope after every definition, therefore there is no need for use-site scopes, and thus no complicated puncturing logic either. Hurray! The reason we decided that our definition contexts should not be recursive is because we were hoping that they would be easier to implement, and I am glad to see that it paid off.

from klister.