Enhancement: implicit renaming macros

[GoogleCodeExporter]

One of my favorite things about Chicken Scheme is ir-macro-transformer.  I find 
it to be the most intuitive hygienic macro system yet (using it isn't any more 
complicated than the traditional unhygienic define-macro).  I've implemented 
them on top of Chibi based on er-macro-transformer from init-7.scm and put it 
through most of the Chicken Scheme tests for ir-macro-transformer (except for a 
few that wouldn't run because of missing dependent macros).

I've attached my implementation, which has been refactored since none of the 
other macros depend on it.

Original issue reported on code.google.com by [email protected] on 8 May 2012 at 4:47

Attachments:

• ir-macros.scm

[GoogleCodeExporter]

Thanks!  I realize IR macros are more convenient
in many cases, but the implementation you provide
is O(n^2) in the size of the source code.  I'll see if I
can come up with an implementation based on
sc-macro-transformer that doesn't have this issue.
Otherwise, you can wait until snow is available and
upload it there.

Original comment by [email protected] on 13 May 2012 at 9:48

• Changed state: Accepted

[GoogleCodeExporter]

I'm sort of new to Scheme and I still find it a little difficult to
reason about in terms of performance.  Can you explain how it's O(n^2)?
I had expected it to be no different than er-macro-transformer in terms
of space, with the two walks amounting to O(n) time for the renaming.

In any case, I've fixed a couple things (removed the excl list which
was vestigial from a different inject implementation, and fixed
imp-walk to properly walk vectors).  Once I have a better understanding
of the performance aspect, I can try to come up with a better algorithm
(I took this algorithm (but not the code) straight out of Chicken).

Original comment by [email protected] on 14 May 2012 at 2:12

Attachments:

• ir-macros.scm

[GoogleCodeExporter]

Any macro that walks the entire body of the
form is O(n*d), where n is the size of the
form and d is the nesting depth of the macro.

If you have a chain like:

  (mac_0 ... (mac_1 ... (mac_d ...) ... ))

and the size of the entire form is n, then
mac0 will walk the form for a cost of n,
mac_1 will then re-walk its subform for a
cost of n-1, and so on until mac_d walks
its subform for a cost of n-d, and the total
cost is:

  n + (n-1) + ... (n-d)

and in the general case d is O(n) so the
total is O(n^2).

In conceptual terms - if macros walk the body,
every enclosing macro will re-walk the same
forms.  Modern macro systems are specifically
designed to avoid this, by not walking or
digging into forms any more than they have to
(e.g. extracting as far and no further than the
"body" portion of a "let").

You won't notice the performance loss in most
cases, but some day you'll have a macro which
expands some complex form into 100 (or more)
nested macros and you will have to wait minutes
or hours for the compiler to complete, when
it should only require seconds.

It is not possible to implement IR macros
efficiently in terms of ER macros.

Original comment by [email protected] on 14 May 2012 at 8:03

[GoogleCodeExporter]

Thank you for the detailed explanation.  I understand now.

I've been thinking about this a bit, and the closest I've come
to a non-walking version divides the notion of inject from
ir-macro-transformer into two different kinds of injection: one
is capturing variables in the use environment, and one is
introducing free variables (e.g., for anaphoric macros).

I'm not entirely sure how to distinguish between them
programmatically, or how to unite them in terms of syntactic
closures.

Original comment by [email protected] on 15 May 2012 at 8:26

Attachments:

• fr-macros.scm

[GoogleCodeExporter]

Alright, so that call to strip-syntactic-closures is superfluous.
Even without introduce, identifiers in that context are not renamed
within the syntactic closure (which is not what I was expecting).

Anyways, I think that in order to get an efficient ir-macro-transformer,
syntactic closures will need to be extended with an escape mechanism.
The free variable list isn't sufficient to implement inject because
inject will allow you to keep a particular instance of an identifier
free, (inject 'it) will not affect other uses of it in the same form.
A closure over the use-env isn't sufficient because inject will allow
the injection of identifiers that aren't yet defined at the macro's
use site.

I wonder if the best way might be to add some sort of special
"environment" for syntactic closures that causes their associated
expr to be expanded unhygienicly, in which case ir-macro-transformer
could be defined like this:

(define (ir-macro-transformer f)
  (lambda (expr use-env mac-env)
    (define injections '())
    (define (inject identifier)
      (let ((cell (assq identifier injections)))
        (if cell
          (cdr cell)
          (let ((name (make-syntactic-closure (escape-env) '() identifier)))
            (set! injections (cons (cons identifier name) injections))
            name))))
    (make-syntactic-closure mac-env '() (f expr inject introduce))))

Since the injections will be closed over, it will prevent the evaluator from
looking them up in mac-env or use-env... the trick will then be to look them
up in the environment of the expanded code.

Original comment by [email protected] on 17 May 2012 at 2:34

[GoogleCodeExporter]

Original comment by [email protected] on 9 Jul 2012 at 11:28

• Added labels: Type-Enhancement
• Removed labels: Type-Defect