Issues with the hygienic macro system

[jpellegrini]

Hi @egallesio !
I'm opening this issue so we can track the problems with the hygienic macro system implementation.

This is what I can see...

Macros should remember their environment

(define-syntax f
  (syntax-rules ()
    ((f) a)))

(f)

The above should trigger an error, because the macro did not remember its environment. The "a" that it was referencing was "a in current module", and the local a included by the let should not be visible (this is a new local environment that did not exist a the time the macro was created).

Interestingly, Scheme9, Gambit, Cyclone and Bigloo also behave like that (but it's not according to the standard).

(define-syntax f
  (syntax-rules ()
    ((f a b) (- a b))))

(let ((f +)) (f 2 3))  ;; => should be 5;  *** STklos returns -1

Now Gambit does return 5... Cyclone and Bigloo return -1 (but the correct is 5).

(let ((x 'outer))
  (let-syntax ((m (syntax-rules ()
                    ((m a) (list x a)))))
    (let ((x 'inner))
      (cons x (m 17)))))

;; Should be (inner outer 17)
;; STklos result is (inner inner 17)

I think this problem is related to the eval issue (#410), since we'd have to eval the macro expander in the module where the macro was created.

STklos does not accept internal define-syntax

This is easy to fix, I suppose, since let-syntax already works.

Hygiene

This can be dealt with later, but I think it would be possible to either implement ER macros (there are issues with it, but I think we can circumvent them), or syntax-case (but I think a lexically-scoped define-macro along with gensym, syntax-rules and hygiene is as powerful as syntax-case, and perhaps easier -- then syntax-case can be implemented on top of this?)

The syntax-rules matcher

It's quite old (from Macros by Example), and there are some glitches. I can re-write it if it's ok.

In particular, the current implementation doesn't handle improper lists as patterns correctly (it complains about the length not being calculable). I think this is not hard to re-implement in a better way. -- fixed

It does not support templates beginning with ellipses.

Aliases, for SRFI 212

That SRFI specifies an alias macro that will work for any symbol - even those bound to macros.

STklos already has %symbol-alias, which does the right thing for global symbols (including macros!)

stklos> (define-macro (f . whatever) -1)
;; f
stklos> (f 1)
-1
stklos> (%symbol-alias 'g 'f)
stklos> (g 2)
-1

But it would be nice to be able to alias local symbols. For that, the scope structure in the compiler would have to be slightly adapted (I can do that):

Keep variable scopes and macro scopes separated as they are currently, but also create a third type of scope for aliases;

Both locals and mlocals in structure scope would be association lists:

• ALIASES: the CAR is the symbol, and the CDR points to the location

  (a . LOCATION)

  where location is either some other entry for a variable in this scope (down the scope stack), or a binding to a specific symbol in a specific module. This works for both macros and variables.
• MACROS: the CDR is the syntax object:

  (s . [#syntax ...])

• LOCAL VARS: no need for a CDR

  (v)

This would give us a way to implement that SRFI, and would repect lexical scope for both variables, macros and aliases. :)

This is not difficult to do, I can help (I can make a PR soon if it's ok).

Tests for all the above

I have some tests... I'll organize them and make a draft PR for reference.

[jpellegrini]

@egallesio is it OK if I try to implement SRFI 212 (aliases)? (I won't if you're working on the same ting, or in parts of the compiler that would conflict with it)

[egallesio]

I have already implemented this SRFI (and not committed it yet, since the tests used in the SRFI use free-identifier? and bound-identifier? ....). Anyway, a simple implementation could be:

(define-module srfi/212
  (import (only SCHEME %symbol-alias))
  (export alias)

  (define-macro (alias var1 var2)
    `(%symbol-alias ',var1 ',var2)))

(provide "srfi/212")

The first example of the SRFI document:

stklos> (define *important-global-variable* '())
    (define (setup!)
      (alias ls *important-global-variable*)
      (set! ls (cons 1 ls))
      (set! ls (cons 2 ls)))
    (setup!)
;; *important-global-variable*
;; setup!
stklos> *important-global-variable* 
(2 1)

[jpellegrini]

I have already implemented this SRFI (and not committed it yet,

That's great! :)
Did you make it work for local symbols and macros also?

[jpellegrini]

Hi @egallesio !
I think the implementation, as you showed, would only work for globals. The following would be necessary for it to actually work, no? (And it may also be useful to implement hygiene for local variables later!)

(let ((a 10))
  (alias b a)
  (set! a 20)
  b) ;; => 20
b ;; => error (not bound)

(define a 10)
(let ((b 20))
  (alias c a)
  (display 'hello)
  (display c)) ;; => hello10
c ;; => error (not bound)

(define a 10)
(let ((b 20))
  (alias a b)
  (display 'hello)
  (display a)) ;; => hello20
a ;; => 10

(define a 10)
(define d 30)
(let ((b 20))
  (alias a d)
  (display 'hello)
  (display a)) ;; => hello30
a ;; => 10

(define-syntax f
  (syntax-rules ()
    ((f) 10)))
(let ((g (lambda () 2)))
  (alias g f)
  (f)) ;; => 10

(let ((a 10)
      (b 20))
  (let-syntax ((f (syntax-rules ()
                    ((f) b))))
    (alias g f)
    (g))) ;; => 20

And the following one, which would need the work on macros remembering their environment;

(let ((a 10)
      (b 20))
  (let-syntax ((f (syntax-rules ()
                    ((f) b))))
    (let ((b 30))
      (alias g f)
      (g)))) ;; => 20 (the 'b' from f's definition env)

[jpellegrini]

Hi @egallesio !
I'm glad you're back!

I see you have implemented the static environment compiler call. That is great! I'm working on adapting macros to get syntax-rules to work as per the standard, if you don't mind.

[jpellegrini]

I'm working on adapting macros

Hm, I tried, but it seems tricky.
I thought it would be just a change in the compiler, in compile-%%define-macro, but it isn't that simple.

1. There, the environment that would have to be captured would be the environment that is being built during the compilation process (the env parameter in that procedure). Not what #%current-environment gives, -- so,
2. I tried to make the macro expand into something that uses #%current-environment, but it doesn't seem to be possible (the syntax transformer needs to capture the environment in the program text where the macro is used).

I'm sure this is possible, just can't see exactly how.

[egallesio]

Hi @jpellegrini,

I'm glad you're back!

Thanks. Not completely operational, but I'm here.

Hm, I tried, but it seems tricky.

It is!! My idea was the same as yours, and I broke my teeth on it. I'm not sure that there is a way to have something this way. I started something with alpha conversion of the code and it is promising
For instance

(let ((x 'outer))
  (let-syntax ((m (syntax-rules ()
                    ((m a) (list x a)))))
    (let ((x 'inner))
      (cons x (m 17)))))

is rewritten in

(let ((x$1 'outer))
  (let-syntax ((m (syntax-rules ()
                    ((m a$2) (list x$1 a$2)))))
    (let ((x$3 'inner))
      (cons x$3 (m 17)))))     => (inner outer 17)

We'll see how it goes, but it is probably the way to go.
More on it later, but I'm still slow for the moment.

[jpellegrini]

I think there is another simple way to implement the environment handling for macros. I'll try in the next days.

[egallesio]

I think there is another simple way to implement the environment handling for macros. I'll try in the next days.

If you have it, I'll be happy to use it. Alpha conversion is quite simple in principle, and I have a running prototype. But integrating it into the current code is not so simple (a lot of edge cases, and it will cost everywhere to correct the pathological cases, such as the inner/outer example above, or the ones that define variables with syntax names).

Thanks for your help.

[jpellegrini]

If you have it, I'll be happy to use it.

Sorry, there were other things happening here, and I couldn't work on this. I'll do that now.
The idea is:

1. Create append-environment, which appends two static envs (given two scope structures env-A, env-B, create a new one with the bindings of A and B).
2. Change one line in compile:

         ((find-syntax-in-env first env)
          ;; --- Macro call
          (compile (%macro-expand e env) env epair tail?))

becomes

         ((find-syntax-in-env first env)
          ;; --- Macro call
          (compile (%macro-expand e (append-environment env (syntax-environment e)) env epair tail?))

[jpellegrini]

Hm, that seems to be a little more complex than I thought. Because I had to change the syntax struct in C, and then there is a bootstrapping issue...

This is what I did:

struct syntax_obj {
  stk_header header;
  SCM name;
  SCM expander_src;
  SCM expander;
  SCM module;
  SCM env;          // <== here!
};

#define SYNTAXP(p)         (BOXED_TYPE_EQ((p), tc_syntax))
#define SYNTAX_NAME(p)     (((struct syntax_obj *) (p))->name)
#define SYNTAX_SOURCE(p)   (((struct syntax_obj *) (p))->expander_src)
#define SYNTAX_EXPANDER(p) (((struct syntax_obj *) (p))->expander)
#define SYNTAX_MODULE(p)   (((struct syntax_obj *) (p))->module)
#define SYNTAX_ENV(p)      (((struct syntax_obj *) (p))->env)

and also

DEFINE_PRIMITIVE("%make-syntax", make_syntax, subr4,
                 (SCM name, SCM src, SCM expander, SCM mod, SCM env))   // <== here!

But then,

make[1]: Enterinmake[1]: Entering directory '/home/jeronimo/pkg/scheme/STklos-jpellegrini/lib'
*** Boot 0
#[condition &error-message 7fd225e8bec0]: bad environment '#[module stklos]'
**** FATAL ERROR: no handler present!
ABORT

😕

[jpellegrini]

I had to change the syntax struct in C

See #862 (draft pull erquest)...

[rrthomas]

An update on this issue: %symbol-alias was removed by commit acaae56. So what's the current best way to make an alias of a global symbol? I can see various references to aliases in the documentation and code, including the promising-looking %symbol-link, but it's not obvious.

[jpellegrini]

@egallesio did you see the message before this one?