syntax rules implementation issues

[jpellegrini]

STklos introduces identical symbols in different phases of macro expansion using syntax rules:

(define-syntax f
  (syntax-rules (k)
    ((f) #f)
    ((f k) 'K)
    ((f k x ...) (a (f x ...)))))

Here's the STklos expansion:

stklos> (macro-expand* '(f k k k))
(a (a 'K))

some other implementations will return

(a.0 (a.1 'K))

I rewrote some macros for SRFI-156 and SRFI-41 using define-macro, but it feels like the wrong way to go... As far as I could see, SRFI-86 would also need some macro rewriting (and its implementation is quite large).

[jpellegrini]

Perhaps, when fixing this, it would be nice to consider using the new macro-related SRFis by Marc Nieper-Wißkirchen?
https://srfi.schemers.org/?keywords=syntax

[egallesio]

Hi @jpellegrini.

It is clear that the macro system must be rewritten, but hygienic macros are far above my head. This is why the implementation of macro is so poor in STklos 😞 .

About this bug, I have found that there is already a kludge in the source that I have added for this problem ( it was added in 2002 from the comment, and I don't remember all the story). By using a %% in front of the symbol, it will be gensymed.

So

(define-syntax f
  (syntax-rules (k)
    ((f) #f)
    ((f k) 'K)
    ((f k x ...) (%%a a %%a (f x ...)))))

stklos> (macro-expand '(f k k k))
(G200 a G200 (f k k))

I know that this is far form ideal, but in the meantime you could perhaps use this turnaround.

[jpellegrini]

Thanks @egallesio ! :)
I'll try to rework this PR today to use that, then...

[jpellegrini]

Anyway - where is the macro code of STklos located?

[egallesio]

Anyway - where is the macro code of STklos located?

The code for non hygienic macro is in the compiler and the code for hygienic macro is in lib/mbe.stk

[jpellegrini]

Ok, I understand how it works now...

I am reviewing the macro system options and SRFIs, articles, etc, related to them. It may take a while, but if you don't mind @egallesio , I'd like to try to come up with a new implementation for STklos.

[egallesio]

I am reviewing the macro system options and SRFIs, articles, etc, related to them. It may take a while, but if you don't mind @egallesio , I'd like to try to come up with a new implementation for STklos.

This would be really great!!!

[jpellegrini]

It seemsthat Marc is planning to work on a general, portable implementation of a macro system, which would be updated when new macro features arise (in new SRFIs for example). If that is the case, then it would be better to wait and incorporate it, no?

[jpellegrini]

It seems that Marc is planning

Marc Nieper-Wißkirchen, I meant. Sorry, was in a hurry!

[jpellegrini]

While we don't get a better system, would it be OK to use alexpander?
It seems like it will work, and it implements SRFI-46.

[jpellegrini]

SUMMARY

I am studying the STklos compiler in order to propose a new hygienic macro implementation.

syntax-rules would require that

1. nested macros are allowed, in lexical-scope discipline, mixed with closures
2. different phases of macro expansion need to rename identifiers differently
3. the variables inside macros obey lexical scope, but free references in the macro body would need to refer to variables visible in the defining context.

About (1)

(let (...)
  (define-syntax m
    (syntax-rules ()
       ...))
  (let (...)
    (define-syntax n
      (syntax-rules ()
       ... ;; m can be used here
       ))
      (let (...)
        ... (n) ... (m)  ;; both can be used here

About (2):

(define-syntax f
  (syntax-rules (k)
    ((f) #f)
    ((f k) 'K)
    ((f k x ...) (a (f x ...)))))

should expand to (a.1 (a.2 'K)), with different "a"s.

About (3):

(let ((y 5))
  (lambda ()
    (define-syntax m
      (syntax-rules ()
        ((...) (... x ... y ...)))) 
    ...
    (let ((x 10))
      (m)  ;; <-- this macro should NOT see the x inside the previous let!
              ;; the x that it sees is the global x!
              ;; but it does see the y defined in the first let.

And for this code:

(define y 11)

(define-syntax x
  (syntax-rules ()
    ((x) y)))

(let ((y 22)) (x))

STklos answers 22, but it shouldn't. Some other Schemes also do this, but the standard says that if a free variable is introduced by syntax-rules, it should be bound to the value that is visible at the moment that the macro is created. So the environment when the macro is created should be used to bind variables in macro creation... What STklos does (Cyclone and some other, I forget which ) is to just rewrite the pattern -- but then the binding of y above will not be the same as before (11).
Macros need to be eval'ed. But eval doesn't see the environment where the macro is defined, so we'd need to make the macro code access the local variables from where it was defined.

I have an idea of how to implement this, and will be working more on it in the next days.

Remark: STklos' define-macro does not use the local variables visible when the macro is defined. Hence, since syntax-rules is being translated into define-macro, it won;t work unless the compiler code that deals with define-macro is changed.

[jpellegrini]

I'm a bit slow these days - health and personal problems together. That, and I have also been studying ways to get a nice hygienic macro system. I'll be back soon!

[egallesio]

Very sad to read that you're not well. Hope that things will go better for you very soon.
I was not too active too, especially on this issue, and I'm very late to answer you. I have to reread all your comment and I have some idea that should (perhaps) simplify the problem. However, I have not found yet the time to test it.

[jpellegrini]

The idea for handling free variables in macros is this:

Include two primitives, %local-ref and %global-ref. These are interpreted directly by the compiler.

case I: the free reference is bound to a local var where the macro is created.

When compiling, this:

(let ((a 5)
  (define-syntax f
    (syntax-rules ()
      ((f) a)))
  (let ((a 6))
    (f)))

would create an expander for f like

(f) --> (%local-ref a) ;; but it really refers to that first `a` on the stack

and later, the macro would be compiled as if, in the macro call, a reference was made to the deep a (=5), and not the shallow one (=6).

case II: the free variable refers to a global in the current module -- either bound or yet undefined.

(let ((a 5)
  (define-syntax f
    (syntax-rules ()
      ((f) x)))  ;; x, not a! but x is not a local var
  (let ((x 6))
    (f)))

This would create an expander for f as

(f) --> (%global-ref x module-foo)

so that, when the compiler finds the (f), it will not refer to the local x, because (f) was transformed into a reference to a local x (which may or may not be bound, doesn't matter).

[jpellegrini]

Then, it would be simple to do the renaming part. That can be done outside the compiler, and is no big deal

[lassik]

I'm a bit slow these days - health and personal problems together. That, and I have also been studying ways to get a nice hygienic macro system. I'll be back soon!

Take care! Hope things will turn out for the better. Your dedication to Scheme is very admirable.

[jpellegrini]

case II

Oh. (%global-ref) is actually the same as symbol-value, so only %local-ref is needed.

(define-macro f
  (lambda () `(symbol-value 'x ,(current-module))))

(let ((x 10))
  (f)) ;; as we want: will NOT use the new binding introduced by the let

[jpellegrini]

The problem is that DEEP-LOCAL-REF is relative to the current frame, going downwards into the stack, and we need an absolute reference to "x in the n-th frame from the bottom and going upwards". Is it really the case for a new VM instruction, maybe?

This local reference issue is also related to SRFI-154 (First class dynamic extent)

A new VM instruction that saves the current frame and module list could be used to implement both SRFI-154 and hygienic macros.

Or, we could try to implement %local-ref so that the compiler would do some juggling in order to find the correct reference... But a new VM instruction feels cleaner. What do you think?

[jpellegrini]

Actually, it seems easy to change it in the compiler, no changes to the VM! Working on it...

[jpellegrini]

%%local-alias is not hard to add, it seems (see PR #106 )...

[jpellegrini]

Now the rest could be done by integrating the matching part of alexpander or eiod, using gensym for renaming and with a few adaptations. I'll work on this in the next days (still not able to work at full speed... but I'm not gone!)

[jpellegrini]

For full compliance with the standards, it would also be necessary to have a similar %syntax-alias.

> (define-syntax let (syntax-rules () ((let a b c) (+ a b c))))
> (let 2 3 4)
9

If I remember correctly, the standard does not forbid that. Some Schemes allow redefinition of lambda, let, etc (Chibi does); others do not. But even if not allowing to redefine those, the same scoping rules would need to work for hygienic macros -- all the issues with variables arise with syntax too, but the solution then is very similar. Working on it.

[jpellegrini]

One more thing: the correct implementation would probably need to include macro names in the same stack as variable names, since the standard treats symbol binding scope the same way, regardless of their being boud to a value or to a macro transformer:

;; should be SYNTAX                         ==> but STklos returns PROCEDURE
(let ((f (lambda () 'PROCEDURE)))
  (define-syntax f
    (syntax-rules ()
      ((f) 'SYNTAX)))
  (f))

;; SHOULD BE PROCEDURE
(let ()
  (define-syntax f
    (syntax-rules ()
      ((f) 'SYNTAX)))
  (let ((f (lambda () 'PROCEDURE)))
    (f)))

STklos does the right thing here:

(require "full-syntax")
(define (f) 'PROCEDURE)
(let-syntax ((f (syntax-rules ()
                    ((f) 'SYNTAX))))
    (f))  
    ==> SYNTAX (ok)

but full-syntax let-syntaxandletrec-syntax-- it does not fix the localdefine-syntaxissue. Also, it seems thatlet-syntax` in STklos only works in top level?

(let ((f (lambda () 'PROCEDURE)))
  (let-syntax ((f (syntax-rules ()
                    ((f) 'SYNTAX))))
    (f)))
**** Error:
let-syntax: cannot be used here. You must load the file "full-syntax" to access it: (let-syntax unquote args)
	(type ",help" for more information)

(full-syntax was already loaded)

If you're ok with this, I can try to put informaion about macros in the env stack that is passed to the compiler procedures (and which, up to now, only contains information about variable bindings).

[jpellegrini]

@egallesio can you confirm this?

*expander-published* holds names of syntax exported from modules.

export-syntax is undocumented (because it isn't ready?) and:
calls %%publish-syntax
translates into compile-%%pubsyntax
calls (expander-published-add! x)

But the macros are visible anyway (?)

Even if defined with syntax-rules.

stklos>
(define-module mo
  (export var j)
  (define var 10)
  (define bar 20)
  (define-macro (h) ''hhh)
  (define-macro (j) ''jjj))

stklos> (h)
hhh

Not complaining, just asking. I'm trying to understand all macro-expansion code in order to propose a good syntax-rules implementation!

[egallesio]

Hi @jpellegrini,

• As you have seen, all the macros are defined at the global level. This is not a good thing, but it was on my TODO list to avoid this since the beginning of STklos (20 years ago!!!) . It is not comfortable but, surprisingly, we can live with that without too much problems, and this probably explains my lazyness.

• I have tried t keep macros names in a different name space than other symbols to avoid to use them as variables. This was an error and should be changed. For instance, Chibi just forbids to dereference a macro name, and Gauche returns a #<macro> when a macro name is dereferenced.

To answer your questions:

*expander-published* holds names of syntax exported from modules.

Yep!

export-syntax is undocumented (because it isn't ready?)

Because I'm not very proud of it 🙄 and I think that more (really more) work
is needed here. It was a kludge needed for compiled files. Export should be
used here but as said before, macros are not in the symbol table. Yes, it is
definitively a mess.

If you look at the compiled version of a file foo containing

(define-macro (add-macro x y)
  `(+ ,x ,y))
(export-syntax add-macro)
(provide "foo")

You will see that it contains

; A -*- Scheme -*- generated file *DO NOT EDIT**
STklos (:version "1.50" :globals () :expanders ((add-macro lambda (x y) `(+ ,x ,y))))
#(+ x y apply add-macro "foo" provide)
32
... bytecode ...

The :expanders key contains the source of all expanders that are exported
by the file.

Consider the following file use.stk

(require "foo")
(print (add-macro 1 3))

If this file is compiled to a file, when building the binary, the compiler needs to know that add-macro used should be compiled as an addition and not to a function call to add-macro. Consequently, require needs (at compile time!) to load the file and read the foo.ostk file to know the macros it defines. Of course, such a mechanism is just need for global macros (local macros, when implemented, are expanded during the compilation of the file and don't exist after that.

But the macros are visible anyway (?)

Yes since they are global 😞

Allowing, clean local macros is probably the first job to do (as well as enter them in the symbol table and don't use anymore a global table of macros).

Not complaining, just asking. I'm trying to understand all macro-expansion code in order to propose a good syntax-rules implementation!

Didn't take it as a complaint at all. Any help, on hygienic macros is warmly welcome.

Do you think that your define-syntax could be (as in mbe.stk) rewritten in a define-macro?

[egallesio]

Not sure that my explanation is clear. Tell me if it is not the case.

[jpellegrini]

Thanks @egallesio I understand it now! Due to personal problems I'll be a bit slow not, but I'll be working on it! FIrst local define-macros then hygienic macros.

Do you think that your define-syntax could be (as in mbe.stk) rewritten in a define-macro?

Yes, a wrapper over define-macro after we get local macros. Not using the MBE code, but something else -- the expansion part would certainly be different, and the pattern matching part could be updated to include SRFI-46.

[egallesio]

Thanks to you Geronimo,

I will be slow too since I have a lot of courses in this period. But if your define-syntax is a wrapper around the actual define-macro, perhaps I can concentrate on a proper implementation of local macros so that you can continue on the define-syntax implementation. Connecting both works should be easy just after (I hope so). What do you think?

[jpellegrini]

perhaps I can concentrate on a proper implementation of local macros so that you can continue on the define-syntax implementation. Connecting both works should be easy just after (I hope so). What do you think?

That would be greata! I was willing to study the define-macro implementation and work on local macros, but that would be a lot of work. If you can get define-macro to behave lexically scoped, that would be wonderful. The hygiene part with renaming etc I can do easily later.

Meanwhile I can concentrate on Debian packaging! (There are some PRs related to that, by the way)

[jpellegrini]

a proper implementation of local macros

I suppose it would work like this -
each module (including the standard "stklos" module) has a list of bound names. each name can be aither syntax or variable (it would be possible to split syntax into "macro" (user-defind) and "special form" (embedded in the compiler).
then, symbols are stacked in lexical-scope discipline.
With that and gensym, implementing syntax-rules is easy.

It would be cool if syntax symbols were more like vars -- for example, they could have docstrings... And there could be a special form syntax? in the compiler (butI'm not sure about this last one)

[jpellegrini]

I had an idea, which would not be too invasive to the compiler. I'll work on it more later.

[jpellegrini]

Hi @egallesio !
I am focusing on this now. I think there is a simple way to add lexically-scoped macros to STklos, in a quite non-intrusive way. I'll come back later with a PR...

[egallesio]

That would be great, I have tried a solution some time ago, but failed miserably. Waiting for the PR 😉

[jpellegrini]

I am overworked at the moment, and although the solution I have partially implemented is simple, it may take some more time to come up with the PR...

[egallesio]

I am overworked at the moment, and although the solution I have partially implemented is simple, it may take some more time to come up with the PR...

Don't worry @jpellegrini; after all, it is more than 20 years that STklos has such macros 😉

[jpellegrini]

An update: I think I got most of the basics done. Implemented macros with lexical scope, which works the same way as other identifiers in STklos; but the renaming/hygiene part is not yet done (however it should be fairly easy after this).

There's just one glitch I need to fix in the code before I get this first part done (right now the new let-syntax includes one level in the lexical hierarchy and the compiler gets confused; I'm fixing it)

No more glitches! It seems to be working fine.
From this point, it would be somewhat simple to implement explicitly-renaming macros, syntax case and syntax-rules.
I'll keep working on it.

[jpellegrini]

Ok so I have written tests, and found that everything works perfectly in the REPL, but global macros used as arguments to functions do not in the tests, and not when I compile them in files either.

I'll have to study compile-file and include-file to understand why it isn't working. - fixed

@egallesio if you want I may send the PR or put it in a branch in my Github fork so you can see what I'm doing.

Anyway, here's a description of what I've done (it's not very organized yet but should be clear enough).

Short summary:

• The representation of the environment by the compiler has been
  augmented: it used to be a list of lists of symbols, where each
  inner list represented one level of lexical scope.
  It is now essentially the same, except that instead of a symbol,
  we may also store a pair there:

  • x (a symbol) means x is bound in the lexical level
  • (x . obj) (a pair) means x is bound to a lexically-scoped
    macro, and obj is a <syntax> structure.

• compile now accepts one more argument, "module" (and because of that,
  several other functions require it also).
  This allows us to tell in which module the VM was when the compile
  function was called.
  Why?
  When a local macro is compiled, its expander needs to be compiled
  in the environment of the original macro definition, and that includes
  the module that was active! - not needed

• The compiler now checks for more possibilities of macro use before checking
  for special forms and function calls:

  • use of a macro created with define-macro
  • use of a GLOBAL macro created with %define-syntax
  • use of a LOCAL macro created with %let-syntax

Extended summary

GLOBAL MACROS

A global macro needs to be DEFINEd first, so it will have been
computed and can be stored in a global variable. So its value will
be a structure, containing the expander.
When the compiler finds a global variable of this type, it just
expands and compiles the expanded form.

Scheme implementation usually do not allow SET!-ing a variable that
is bound to a macro transformer, but it may be interesting to be
able to change the transformer of a macro.

When the compiler finds a global macro being used,

(define-syntax f ...)
...
(f ...)   <= f is bound to a <syntax> structure!

then it will call f's expander on that form and call itself
recursively.

LOCAL MACROS

A local macro needs to have its identifier inserted in the same
stack structure that holds the names of variables, so lexical
scope works as intended (identifiers for variables -- used at execution
time -- and macros -- expanded at compile time -- may shadow each other).
Also, local macros defined in outermost code should be available for use
in macro code in innermost code:

(define-syntax h ...)

(let-syntax ((g ...))
  ...
    (let-syntax ((f ... ,(g ...) ...))  <= f may refer to g and h

The local macro name is kept on the environment stack by the compiler
as a pair (not a symbol), so that it's clear it's a macro. The pair
is (name macro-obj), where macro-obj is an instance of <syntax>

When the compiler finds a reference to an identifier,

• if it is stored as a symbol, compile reference-to-variable
• if it is stored as a pair, run the expander (which is stored
  along with the macro name), then recursively run the compiler.

ENVIRONMENTS: HOW EXPANDERS ARE COMPILED

A macro expander should use the environment in which it was defined.
So, compiled-expander should be compiled as

(eval expander module)

When f makes a reference to a macro not in its local environment,
then the global environment should be used. But since we have modules,
the global environment is not unique, so the expander is compiled in
the module where the macro was defined.

References to other local macros are dealt with when expanding: the
compiler expands the car of a form and starts over, with the same environment.

LOCAL MACROS USING GLOBAL MACROS

If a global macro has been defined, then it is available as the value
of a global variable, in a module. So, since a local macro must
have access to that global macro, we computed the expander calling
eval in it, on that module (as mentioned before).

Caveat: it is possible to change the content of the global macro
after the local macro has been defined, but before it has been
used.

WE DO NOT KEEP TRACK OF GLOBAL/LOCAL DISTINCTION

It's not necessary.

NAME REWRITING, HYGIENE ETC

We DO NOT yet deal with those issues here. They can be dealt with
separatelty later, maybe with the help of an ALIAS compiler macro.

[egallesio]

Hi @jpellegrini,

That is really great news. 🙌
Your approach is similar to the one, I had implemented before and, as you, I had problems with .ostk files. In fact, .ostk files contains the definitions of macros that are defined in the header of the .ostk file. When, imported, the compiler needs to read the header to "know" the symbols bound to macros. Hence, the compiler, can macro-expand forms using one of these symbols in their car. Adding, a new kind of macro will probably imply that the format of the .ostk must be adapted (a version tag present at the beginning of the file should permit to manage several versions of the .ostk format).

[jpellegrini]

Hi @egallesio !

In fact, .ostk files contains the definitions of macros that are defined in the header of the .ostk file

Right! And I've made the new macros be variables in modules, and... If the file being compiled creates a module, there is some extra difficulty added. Anyway, there will be some solution for that. :)

[jpellegrini]

Hi @egallesio !

I've been working on this.

I think we could use the current ostk file format, but extended.
One thing I noticed is that currently macros are not isolated in modules. So this won’t work:

(define-module a
 (define-macro (one) -1)
 (export-syntax one)
)

(define-module b
 (define-macro (one) +1)
 (export-syntax one)
)

(provide "one")

Since the proposal for new macros would be to have them represented as structs, then I thought we could do it this way:

• since macros are used all over STklos, we can't just replace the current define-macro. So we could support both methods before fully changing;
• macros (both old and new) would be listed along with the exported symbols of a module, so export would also export macros. Since macros will be variables of the type <syntax>, when we export the symbol, we also export the macro. If the module has been loaded and evaluated, then the macro will work when it is imported;
• when a file is compiled, it would list, for each module, the symbols that are macros, and their start and end points in the bytecode, so the compiler can instantiate those macros and use them to do the expansion

#:expanders ((module-name (name start end)
                          (name start end) ; new-style macro
                          (name expander)  ; old-style macro
                          ...)
             (module-name (name start end)
                          (name start end)
                          ...)
             ...)

The "old style" macros would be the ones we have today. The "new style" macros would be the new ones, with lexical scope (on top of which we'll have syntax-rules, etc). If we do it this way we won't break things that currently work. It would be possible to tell the difference:

• between old and new ostk files, because in the new ones, the expanders is a list of lists -- oops, in the old one it was already
• between old and new macros, because their description are lists with either two (for old macros) or three (for new macros) elements

Also, do you think we can somehow add a version number to the ostk files? (I mean version of the ostk format -- we'd go from "version 1" to "version 2" now) So STklos can either adapt or refuse to read an old version of ostk?

What do you think?

One further idea: there could be two procedures used to write/read the macro struct from/to bytecode, that could also read/write arbitrary Scheme objects, serialize and unserialize. I have written a prototype that serializes closures (with their environments, because one can easily grab frames in the STklos C code -- that is really nice!)

[jpellegrini]

Better yet, don't change the format of #expanders, but add another, #syntax, for the new macros. It would be fully backwards compatible!

[egallesio]

That is really really cool.
Thanks, @jpellegrini, for all this great work.

Using a special tag such as #expanders is definitively the way to go. When everything is OK with your implementation, we can drop the old one and replace it by yours!!!

Just a thing, if you take the position of the start and end of the definition of the macro: are you able to find the values of the constants used by the macro and don't you'll have to patch it?

[jpellegrini]

Ok @egallesio ! I'll be slowly working on it (I got some work issues to deal with).

Just a thing, if you take the position of the start and end of the definition of the macro: are you able to find the values of the constants used by the macro and don't you'll have to patch it?

The macro has an expander, which is just a closure. The code for serializing closures would do two things:

• also include whatever local variables needed, by including their frames (!) -- but I think that in the case of exported macros this won't be necessary, because they will have no local environment (can't export local symbols, local variables and hence local expanders)
• also include a list of global symbols used by it. If the macro uses global x, then we may either let the user create a local x (and warn if x is unbound when importing the macro) or... let the user serialzie the module where the macro was 😀 this is something we'll be able to work on later

I'll first create the serializing code, make a separate PR for it, then use it in the macro PR.