identifier used out of context

[Sorawee Porncharoenwase]

Hi Racketeers,

I’m creating a macro that collects values in the internal-definition context. E.g.,

($list 
 1
 (define x 2)
 x)

should evaluate to '(1 2).

Here’s my implementation, and it kinda works:

#lang racket

(begin-for-syntax
  (define ((do-it gs ctx) e)
    (let loop ([e e])
      (define e-expanded (local-expand e (list gs) #f ctx))
      (syntax-case e-expanded (begin define-syntaxes define-values)
        [(begin body ...)
         #`(begin #,@(map loop (syntax->list #'(body ...))))]
        [(define-values ids e)
         (begin
           (syntax-local-bind-syntaxes (syntax->list #'ids) #f ctx)
           e-expanded)]
        [(define-syntaxes ids e)
         (begin 
           (syntax-local-bind-syntaxes (syntax->list #'ids) #'e ctx)
           #'(begin))]
        [e #'(set! acc (cons e acc))]))))

(define-syntax ($list stx)
  (define gs (gensym))
  (define ctx (syntax-local-make-definition-context))
  (syntax-case stx ()
    [(_ body ...)
     #`(let ([acc '()])
         #,@(map (do-it gs ctx) (syntax->list #'(body ...)))
         (reverse acc))]))

($list 1
       (define x 2)
       x)

There are problems though. If I change define to define2 as follows:

(define-syntax-rule (define2 x y)
  (define-values (x) y))

($list 1
       (define2 x 2)
       x)

Then I get the “identifier used out of context” error. This doesn’t make sense to me at all. My define2 should be very similar to define…

There’s also another weird problem:

($list 1
       (define-syntax (x stx) #'2)
       x)

The above works perfectly, but by wrapping x with #%expression, I get the “identifier used out of context” error again.

($list 1
       (define-syntax (x stx) #'2)
       (#%expression x))

What did I do wrong?

Thanks!

[Sorawee Porncharoenwase]

Ah, apparently I need syntax-local-identifier-as-binding. Here’s a revised code that passes the tests.

(begin-for-syntax
  (define ((do-it gs ctx) e)
    (let loop ([e e])
      (define e-expanded (local-expand e
                                       (list gs)
                                       (list #'begin
                                             #'define-syntaxes
                                             #'define-values)
                                       ctx))
      (syntax-parse e-expanded
        #:literals (begin define-syntaxes define-values)
        [(begin body ...) #`(begin #,@(map loop (attribute body)))]
        [(define-values (x ...) e)
         #:with (x* ...) (map syntax-local-identifier-as-binding
                              (attribute x))
         (syntax-local-bind-syntaxes (attribute x) #f ctx)
         #'(define-values (x* ...) e)]
        [(define-syntaxes (x ...) e)
         #:with (x* ...) (map syntax-local-identifier-as-binding
                              (attribute x))
         (syntax-local-bind-syntaxes (attribute x) #'e ctx)
         #'(define-syntaxes (x* ...) e)]
        [e #'(set! acc (cons e acc))]))))

Still not sure if there’s still anything wrong. In particular, do I need to expand e in define-syntaxes? And do I need to use prop:liberal-define-context for gs? (I don’t understand what liberal expansion is even after reading the docs several times) Both of these are done in the implementation of block, but without them, it seems to work equally well.

[Michael Ballantyne]

Explicitly expanding `e` would ensure that the expansion work only has to happen once, rather than twice. Even so, the fully-expanded syntax will be expanded again in `syntax-local-bind-syntaxes` and in the expansion.

As far as I've seen, the only thing that liberal define contexts control is whether definitions of functions that accept keyword arguments expand to a normal `define-values` with runtime handling of keywords, or expand to a collection of macros and function definitions that allow a more efficient calling convention for first-order calls. The latter expansion doesn't work for contexts like `class` where function definitions are re-interpreted in a way that adds indirection, so it is only enabled in contexts that opt-in.

I see more bug in your macro: as its very first task, it should check if `(syntax-local-context)` is `'expression`. If not, it should expand to `(#%expression <the-original-call>)`. This ensures that its expansion is delayed until the second pass of the surrounding definition context so that names bound by later definitions are available. 

[Sorawee Porncharoenwase]

Thank you so much, Michael! This is very helpful.

I can see that when this form is used within another internal definition context, then my version and your version will expand in different order, and I agree that yours makes more sense. I am unable to come up with a program where this difference is significant though (e.g., one fails while the other doesn’t). “so that names bound by later definitions are available” seems to suggest that things like this is not supposed to work on my version:

(let ()
  ($list (define (f x) (g x))
         (println f))
  (define (g x) x)
  (void))

but it actually does…

I also have another question. When should I use internal-definition-context-track? Normally, internal definitions are expanded into letrec-syntaxes+values, so the bindings don’t actually disappear. So I am curious why internal-definition-context-track is needed.

Thanks again.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/748eead8-76b9-43bc-94da-2c832ba8896do%40googlegroups.com.

[Michael Ballantyne]

>  I am unable to come up with a program where this difference is significant though

Here's an example:

(define-syntax-rule (m) 'old)

(let ()

  ($list

   (m))

  (define-syntax-rule (m) 'new))

> So I am curious why internal-definition-context-track is needed.

A similar example shows the need here:

($list
  (define-syntax-rule (m) 5)
  (m))

Without `internal-definition-context-track` you'll miss the arrow for `m`. While `m` does indeed get rebound in the `letrec-syntaxes+values`, that binding has an extra scope, so the reference to `m` (recorded in an `'origin` property on `5`) doesn't match. 

On Sunday, June 7, 2020 at 12:18:26 AM UTC-6, Sorawee Porncharoenwase wrote:

Thank you so much, Michael! This is very helpful.

I can see that when this form is used within another internal definition context, then my version and your version will expand in different order, and I agree that yours makes more sense. I am unable to come up with a program where this difference is significant though (e.g., one fails while the other doesn’t). “so that names bound by later definitions are available” seems to suggest that things like this is not supposed to work on my version:

(let ()
  ($list (define (f x) (g x))
         (println f))
  (define (g x) x)
  (void))

but it actually does…

I also have another question. When should I use internal-definition-context-track? Normally, internal definitions are expanded into letrec-syntaxes+values, so the bindings don’t actually disappear. So I am curious why internal-definition-context-track is needed.

Thanks again.

To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.

[Sorawee Porncharoenwase]

Perhaps I missed something, but the error in the first example is because there’s no expression at the end of let. If I use this code instead, it seems to work fine, with the arrow of m pointing to the “new” one.

(define-syntax-rule (m) 'old)

(let ()
  (list+ (m))
  (define-syntax-rule (m) 'new)
  (void))

The second example perfectly shows why I need internal-definition-context-track, however. Thank you very much.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/ae981bda-94d3-43d2-ae23-a41f5160aa0ao%40googlegroups.com.

[Michael Ballantyne]

Hah! You're right. The arrow points to the inner definition. But it's even worse than that---the value comes from the outer definition! At least for `block`, which is what I'm testing with as I haven't copied down your code. Try this:

#lang racket

(require racket/block)

(define-syntax-rule (m) (displayln 'old))

(let ()

  (block (m))

  (define-syntax-rule (m) 'new)

  (void))

(and with your macro rather than block)

On Sunday, June 7, 2020 at 4:27:24 PM UTC-6, Sorawee Porncharoenwase wrote:

Perhaps I missed something, but the error in the first example is because there’s no expression at the end of let. If I use this code instead, it seems to work fine, with the arrow of m pointing to the “new” one.

(define-syntax-rule (m) 'old)

(let ()
  (list+ (m))
  (define-syntax-rule (m) 'new)
  (void))

The second example perfectly shows why I need internal-definition-context-track, however. Thank you very much.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/ae981bda-94d3-43d2-ae23-a41f5160aa0ao%40googlegroups.com.

[Sorawee Porncharoenwase]

Wow, so block is currently buggy?!

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/30972297-14f6-4cf9-8821-de5753f3dacfo%40googlegroups.com.

[Alexis King]

On Jun 7, 2020, at 17:44, Sorawee Porncharoenwase <sorawe...@gmail.com> wrote:

Wow, so block is currently buggy?!

This issue isn’t with `block`, per se (though `block` could cooperate more nicely with definition context expansion to avoid this problem). You can reproduce it without any first-class definition contexts at all:

    #lang racket

    (define-syntax-rule (m) (displayln 'old))

    (let ()

      (m)

      (define-syntax-rule (m) 'new)

      (void))

Arguably, the real issue is the mechanism behind Check Syntax. Check Syntax collects information about uses and bindings from the fully-expanded program, but that is not straightforward for macro uses and local macro bindings, since those go away after expansion. So the expander annotates the program with information about disappeared identifier uses and disappeared local bindings using the 'origin, 'disappeared-use, and 'disappeared-binding syntax properties.

The hope is that the binding structure of the source program can be reconstructed from the fully-expanded program by inspecting identifiers’ scopes. This seems plausible, since the scopes of a fully-expanded program dictate the binding structure of runtime variables by definition. However, this example reveals a flaw in that logic: resolution of macro bindings also involves a temporal component, since the compile-time binding table evolves as the program is expanded.

Frankly, this temporal dependency is unsatisfying. For runtime bindings, we enjoy predictable recursive definition contexts and inter-module lexical binding, courtesy of the module system. But to paraphrase Matthew, resolution of compile-time bindings is “distressingly like the top level,” since it requires interleaving of expansion and evaluation in a similar way.

I think this suggests that perhaps there is something fundamentally incomplete in our model of macroexpansion. However, it seems impossible to solve this problem without somehow restricting the macro language: the status quo allows macros to both (a) expand to absolutely anything via arbitrary procedural logic and (b) perform arbitrary side-effects, which allows them to observe expansion order. A more restrictive model could require macros to declare more information up front (which would allow the macroexpander to learn more about the binding structure of a program without fully expanding macros) or could provide access to state through restricted channels in such a way that the expander could “speculatively” expand a macro, then go back later and change its mind.

Of course, these would both require radical, deeply incompatible changes to the Racket macro system, so I do not expect them to actually be implemented! But perhaps they can be food for thought.

Alexis

[Michael Ballantyne]

As Alexis notes, getting the arrows right in general is tricky. But `block` is also currently buggy in that it does not expand to `#%expression` when not in an expression context. (`block` is buggy in at least one other way as well, but that needs a deeper fix: https://github.com/racket/racket/issues/3198)

On Sunday, June 7, 2020 at 4:45:34 PM UTC-6, Sorawee Porncharoenwase wrote:

Wow, so block is currently buggy?!

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/30972297-14f6-4cf9-8821-de5753f3dacfo%40googlegroups.com.

[Anthony Carrico]

On 6/7/20 9:23 PM, Alexis King wrote:
>     #lang racket
>     (define-syntax-rule (m) (displayln 'old))
>     (let ()
>       (m)
>       (define-syntax-rule (m) 'new)
>       (void))

I think you meant:

(define-syntax-rule (m) (displayln 'old))
(let ()
(m)

(define-syntax-rule (m) (displayln 'new))
(m)
(void))

which prints:

old
new

And as usual, Alexis points right to the heart of the problem. All the
way back in Dybvig's psyntax expander, definition contexts are partially
expanded to uncover definitions, and then fully expanded in a second
step. Flatt's papers dig deeper (I hope he is reading this thread). I
will quote one thing directly from Alexis, "resolution of macro bindings
also involves a /temporal/ component, since the compile-time binding

table evolves as the program is expanded."

I'd love to hear your idea of a satisfying semantics to aim for, even if
it doesn't match scheme/racket historical semantics. In the meantime,
I'll draw your attention to another community which has evolved a
potential solution to the "hopeless top level":

Nix is a lazy functional language which is primarily used to define
binding contexts--very much like our "hopeless" definition
contexts--primarily for unix package configuration. The concept of an
"overlay" has emerged (this term might be overloaded in Nix).

An overlay represent a step in the fixed point definition of a binding
context.

Recall the Alexis quote, "resolution of ... bindings ... involves a
/temporal/ component," well in Nix an overlay is a step in the fixed
point definition of a binding context.

It probably isn't proper to call this "temporal", but it is a sequence
of definition contexts which lead to the ultimate desired set of
definitions (the "fixed point" of the computation).

As a racket procedure, an overlay would be defined something like this:

(define (overlay self super) ...etc...)

Overlay is a function ("macro"). It takes two sets of bindings, and
produces a third. Self and super are the conventional names (not great
names) for the parameters.

In the overlay system, a binding context is defined by chaining together
a bunch of overlays. Something like this:

(letrec ((super0 (combine initial (overlay0 self initial)))
(super1 (combine super0 (overlay1 self super0)))
(super2 (combine super1 (overlay2 self super1)))
;; etc...
(final superN))
;; "self" is the desired binding context.
;; "superX" are the staged binding contexts along the way.
self)

Now of course just like with macros, there can be overlay producing
overlays etc. If you look at an overlay as a macro, it has simultaneous
access to the entire structure of the of the bindings via the two
handles, self and super, together with whatever bindings are stashed
away by other overlays. You could imagine a sequence of bindings
contexts in which one definition of cc, compiles the next, bootstrapping
a compiler from its initial version, for example, or even one version of
an overlay bootstrapping another overlay.

There are conventions making use of self and super when writing an
overlay. You, and your downstream peers in the chain, will be overriding
the ones in super, if you provide something from self, you know it is
the stable final result.

Isn't there some solid semantics for a hopeful top level in this idea?

--
Anthony Carrico

[Anthony Carrico]

On 6/9/20 12:57 PM, Anthony Carrico wrote:
> (letrec ((super0 (combine initial (overlay0 self initial)))
> (super1 (combine super0 (overlay1 self super0)))
> (super2 (combine super1 (overlay2 self super1)))
> ;; etc...
> (final superN))
> ;; "self" is the desired binding context.
> ;; "superX" are the staged binding contexts along the way.
> self)

Oops, sorry, I change the identifier from "final" to "self", but forgot
to change the binding:

(letrec ((super0 (combine initial (overlay0 self initial)))
(super1 (combine super0 (overlay1 self super0)))
(super2 (combine super1 (overlay2 self super1)))
;; etc...

(self superN))