bindings for free identifiers in (ice-9 syncase)

bindings for free identifiers in (ice-9 syncase)

[Julian Graham]

Hi Guilers,

Alright, I've been banging my head against this for several weeks now
and only just had the time to sit down and research this: If you use a
symbol in an `(ice-9 syncase)' macro definition that's bound in the
lexical closure in which that definition lives, then that binding
should be the one that gets used at transformation time.  At least,
that's how I interpret the following bit of R5RS:

"If a macro transformer inserts a free reference to an identifier, the
reference refers to the binding that was visible where the transformer
was specified, regardless of any local bindings that may surround the
use of the macro."

...but that's not what Guile seems to do.  (I'm fiddling around in
1.9.0 HEAD, because the VM is awesome and because there are some
already-committed syncase fixes that have been useful to me...)  If
you create the following module:

(define (foo-module)
  #:use-module (ice-9 syncase)
  #:export-syntax (foo-macro))

(define (foo-function) (display "Hello, world!"))

(define-syntax foo-macro
  (lambda (stx)
    (syntax-case stx ()
      ((_) (syntax (foo-function))))))

...and then import `(foo-module)' into the REPL or somewhere else,
evaluating `(foo-macro)' throws an error because `foo-function' can't
be found.  What am I doing wrong?


Regards,
Julian

Re: bindings for free identifiers in (ice-9 syncase)

[Andreas Rottmann]

Julian Graham <joolean@gmail.com> writes:

> Hi Guilers,
>
> Alright, I've been banging my head against this for several weeks now
> and only just had the time to sit down and research this: If you use a
> symbol in an `(ice-9 syncase)' macro definition that's bound in the
> lexical closure in which that definition lives, then that binding
> should be the one that gets used at transformation time.  At least,
> that's how I interpret the following bit of R5RS:
>
> "If a macro transformer inserts a free reference to an identifier, the
> reference refers to the binding that was visible where the transformer
> was specified, regardless of any local bindings that may surround the
> use of the macro."
>
> ...but that's not what Guile seems to do.  (I'm fiddling around in
> 1.9.0 HEAD, because the VM is awesome and because there are some
> already-committed syncase fixes that have been useful to me...)  If
> you create the following module:
>
> (define (foo-module)
>   #:use-module (ice-9 syncase)
>   #:export-syntax (foo-macro))
>
> (define (foo-function) (display "Hello, world!"))
>
> (define-syntax foo-macro
>   (lambda (stx)
>     (syntax-case stx ()
>       ((_) (syntax (foo-function))))))
>
> ...and then import `(foo-module)' into the REPL or somewhere else,
> evaluating `(foo-macro)' throws an error because `foo-function' can't
> be found.  What am I doing wrong?
>
Nothing, this is a deficiency in Guile:
https://savannah.gnu.org/bugs/?20941. I wonder why it is marked as
"invalid", though.

Regards, Rotty

Re: bindings for free identifiers in (ice-9 syncase)

[Julian Graham]

This does strike me as a serious problem (and it's a spanner in the
works for implementing R6RS libraries).  In effect, isn't the bug
saying that Guile's syncase macros aren't totally hygienic?  That is,
in my example, if you provide your own binding for `foo-function' in
the REPL environment, then that will be used in the evaluation of the
transformed expression instead of the one in `(foo-module)', which is
certainly *not* the intent of the macro author.

However, as a novice who's spent some time poking around in
ice-9/boot-9.scm and `(ice-9 syncase)', I'm sort of confused about why
this is hard -- isn't this metadata available?  The transformer should
have access to the closure in which it was created, and at creation
time, we certainly know which identifiers are free and which ones
aren't -- and we can look up the variables bound to the free ones in
the transformer's lexical closure.

The real issue with modules is that they hide bindings, not variables.
 If you have the variable, you can use it, no matter which module is
current.


On Thu, Mar 19, 2009 at 12:32 PM, Andreas Rottmann <a.rottmann@gmx.at> wrote:
> Julian Graham <joolean@gmail.com> writes:
>
>> Hi Guilers,
>>
>> Alright, I've been banging my head against this for several weeks now
>> and only just had the time to sit down and research this: If you use a
>> symbol in an `(ice-9 syncase)' macro definition that's bound in the
>> lexical closure in which that definition lives, then that binding
>> should be the one that gets used at transformation time.  At least,
>> that's how I interpret the following bit of R5RS:
>>
>> "If a macro transformer inserts a free reference to an identifier, the
>> reference refers to the binding that was visible where the transformer
>> was specified, regardless of any local bindings that may surround the
>> use of the macro."
>>
>> ...but that's not what Guile seems to do.  (I'm fiddling around in
>> 1.9.0 HEAD, because the VM is awesome and because there are some
>> already-committed syncase fixes that have been useful to me...)  If
>> you create the following module:
>>
>> (define (foo-module)
>>   #:use-module (ice-9 syncase)
>>   #:export-syntax (foo-macro))
>>
>> (define (foo-function) (display "Hello, world!"))
>>
>> (define-syntax foo-macro
>>   (lambda (stx)
>>     (syntax-case stx ()
>>       ((_) (syntax (foo-function))))))
>>
>> ...and then import `(foo-module)' into the REPL or somewhere else,
>> evaluating `(foo-macro)' throws an error because `foo-function' can't
>> be found.  What am I doing wrong?
>>
> Nothing, this is a deficiency in Guile:
> https://savannah.gnu.org/bugs/?20941. I wonder why it is marked as
> "invalid", though.
>
> Regards, Rotty
>

Re: bindings for free identifiers in (ice-9 syncase)

[Neil Jerram]

Andreas Rottmann <a.rottmann@gmx.at> writes:

> Nothing, this is a deficiency in Guile:
> https://savannah.gnu.org/bugs/?20941. I wonder why it is marked as
> "invalid", though.

Regardless of how it's marked, I'm still hoping to get to this soon.

    Neil

Re: bindings for free identifiers in (ice-9 syncase)

[Neil Jerram]

Julian Graham <joolean@gmail.com> writes:

> This does strike me as a serious problem (and it's a spanner in the
> works for implementing R6RS libraries).  In effect, isn't the bug
> saying that Guile's syncase macros aren't totally hygienic?  That is,
> in my example, if you provide your own binding for `foo-function' in
> the REPL environment, then that will be used in the evaluation of the
> transformed expression instead of the one in `(foo-module)', which is
> certainly *not* the intent of the macro author.

Completely agree.  I don't think there's any doubt that current
behaviour is wrong.

> However, as a novice who's spent some time poking around in
> ice-9/boot-9.scm and `(ice-9 syncase)', I'm sort of confused about why
> this is hard -- isn't this metadata available?  The transformer should
> have access to the closure in which it was created, and at creation
> time, we certainly know which identifiers are free and which ones
> aren't -- and we can look up the variables bound to the free ones in
> the transformer's lexical closure.

The problem is some combination of

- how lexical identifiers are memoized (as a pair of numbers I, J,
  meaning the Ith variable in the Jth level up from the current
  lexical environment)

- the fact that at any given point, the evaluator is only aware of one
  lexical environment

- that the macro transformation process doesn't memoize top-level
  variables at the time of the transformation.

I would guess it's mostly the last point.

Regards,
        Neil

Re: bindings for free identifiers in (ice-9 syncase)

[Andy Wingo]

Hi Julian,

Just to add to the melee, I have been thinking hard about this too.
Somehow output produced by a macro must have its free identifiers scoped
in the module that was current when the macro was defined.

This could mean that syntax objects need a new field, and that output
should be serialized with the `@@' syntax, but I don't know right now.

I really want this within a couple of months though. But I would of
course be delighted to find that someone else has already implemented
this!

BTW if you haven't read it, I recommend the "Beautiful Code" paper on
syntax-case. See http://www.cs.indiana.edu/~dyb/pubs.html.

Andy
-- 
http://wingolog.org/

Re: bindings for free identifiers in (ice-9 syncase)

[Neil Jerram]

Andy Wingo <wingo@pobox.com> writes:

> Hi Julian,
>
> Just to add to the melee, I have been thinking hard about this too.
> Somehow output produced by a macro must have its free identifiers scoped
> in the module that was current when the macro was defined.

I've been reaching that conclusion too.  (For others following this,
I've appended some notes / a draft email to explain why, after my
sig.)  There are a couple of relevant bits of R6RS.  From section 7.1:

  Bindings defined with a library are not visible in code outside of
  the library, unless the bindings are explicitly exported from the
  library. An exported macro may, however, implicitly export an
  otherwise unexported identifier defined within or imported into the
  library. That is, it may insert a reference to that identifier into
  the output code it produces.

And from section 9.2:

  If a macro transformer inserts a free reference to an identifier,
  the reference refers to the binding that was visible where the
  transformer was specified, regardless of any local bindings that may
  surround the use of the macro. 

I don't believe there's any guidance from the specs prior to R6RS,
because none of them had modules/libraries.

> This could mean that syntax objects need a new field, and that output
> should be serialized with the `@@' syntax, but I don't know right now.

It also means, I think, that a module/library has to have a lexical
effect.  Basically the reader needs to know what the current module is
at any point, and to mark each read identifier with that module.

Guile's modules are technically determined at eval time, so don't
conform to that.  On the other hand, the common practice, using
(define-module ...), and the fact that Guile reads and evaluates forms
from a file (or stdin) sequentially, together could give us a close
approximation to the necessary lexical effect.

Regards,
        Neil



Notes on the lexical effect thing, or "Hmmm...  I remember now that
this problem is actually harder than it looks."

It helps to consider define-macro, defmacro and
procedure->memoizing-macro first.  With all of these, it's clear that
you are really defining a procedure that will transform the supplied
expression into an expanded expression.  For example:

(define (foo-function a)
  ...)

(define-macro (foo-macro arg)
  `(foo-function ,arg))

(export-syntax foo-macro)

and then in another module, a call

(foo-macro bar)

will be expanded to

(foo-function bar)

At this point, the programmer thinks it is obvious that foo-function
should be looked up in the environment of the (define-macro ...) call,
and that bar should be looked up in the environment of the (foo-macro
...) call.  But as far as Guile is concerned, it now sees just
(foo-function bar), and has no idea that the environments for
foo-function and bar should be different.

And the same applies to (ice-9 syncase), because Guile's
implementation of syncase (from Dybvig) also boils down to defining a
transformer procedure.