Expanding Macros with Values Instead of Names

In Implementing Arc Global Variables with an Arc Table I described how it was a small change to modify Arc3.1 so that global variables were stored in a plain Arc table.

This is nice for taking an axiomatic approach to language design, since there’s now one less feature needed to implement the core language: Arc3.1 uses both Racket namespaces and Arc tables, and with this change Arc no longer has a dependency on namespaces.

A module system for functions can now be built using the core language, rather than having to be built into it.

For example, suppose I use alref in my code but not assoc, and perhaps I even want to use the name assoc for something else in my own code.

(def assoc (key al)
  (if (atom al)
      (and (acons (car al)) (is (caar al) key))
       (car al)
      (assoc key (cdr al))))

(def alref (al key)
  (cadr (assoc key al)))

I can load a library which implements assoc and alref into its own module (that is, use a different Arc table for its global variables), and then copy only alref into my own globals.

(= lib (copy globals))
(load "assoc.arc" lib)
(= globals!alref lib!alref)

I now have a reference to alref, which in turn has a reference to assoc, which is in its global variables but not mine.

Using these primitives I can create my own module system, defining perhaps require and export, or however I’d like my module system to work.

Sadly though while this works fine for functions, it breaks down for macros.

Suppose I’d like to use the after macro,

(mac after (x . ys)
  `(protect (fn () ,x) (fn () ,@ys)))

but I don’t myself use protect, and so I’d rather not have to import it as well.

If I try

(= globals!after lib!after)

I can go ahead and use the macro...

(after (open-and-process-it) (close-it))

but it will expand into code which uses protect:

  (fn () (open-and-process-it))
  (fn () (close-it)))

Since my code doesn’t have a reference to protect (or I’d like to be able to use “protect” in my own code for something else), that reference to protect isn’t referring to the “protect” in the library.

In Scheme the solution is “hygienic” macros: since macros operate on expressions, the macro expander can automatically rename things like “protect” so that they don’t conflict with what I might be using “protect” for:

  (fn () (open-and-process-it))
  (fn () (close-it)))

where “gs4926-protect” is some unique name that doesn’t conflict with any of the names I’m using. I’d still need to have “gs4926-protect” in my own globals (which may make having the ability to have separate global variables fairly useless if everything can be renamed anyway), but at least I can use “protect” for something of my own.

Hygienic macros turn out to be pretty painful to use, and so for some of us it’s a solution worse than the problem. It’s annoying if a library is making use some name like “protect” which I want to use myself, but I can just go into the library and rename “protect” in that library to something else if I want to.

In Clojure the backquote character ` is a “syntax quote”, which expands plain symbols into “fully qualified symbols” which include a namespace:

user=> `(a b c)
(user/a user/b user/c)

and `(protect ...) in the library would expand into something like (lib/protect ...), where “lib” is the namespace of the library.

Like hygienic macros, Clojure’s syntax quote solves the problem of name clashes by renaming. It’s a nicer solution than hygienic macros, though it does come at the cost of making ` no longer a simple abbreviation for creating lists.

In Arc:

arc> `(a ,(+ 3 4) b)
(a 7 b)
arc> (list 'a (+ 3 4) 'b)
(a 7 b)
arc> (is (car `(a)) 'a)

In Clojure:

user=> `(a ~(+ 3 4) b)
(user/a 7 user/b)
user=> (= (first `(a)) 'a)

It’s a shame, as we have a small set of language axioms...

which seems to almost work for a module system... but doesn’t quite manage it for macros.

In the expansion of the after macro, we want “protect” to refer to the “protect” function in the library:

  (fn () (open-and-process-it))
  (fn () (close-it)))

while not clashing with my using “protect” for something else in my code.

With hygienic macros “protect” is automatically renamed to some unique name that doesn’t clash with my code, and in Clojure the name is made unique by prefixing it with a namespace.

And with that unique name, the code is able to get a reference to the function value, and to call it.

(mac after (x . ys)
  `(protect (fn () ,x) (fn () ,@ys)))

Since the end result that’s needed is to get at the function value, rather than having the macro expand into the name of the function (and then later to get the value from name), why not instead have the macro expand into the function value itself...?

(mac after (x . ys)
  `(,protect (fn () ,x) (fn () ,@ys)))

This violates the principle that macros transform source code expressions into source code expressions. If we look at the macro expansion:

arc> (macex1 '(after (open-and-process-it) (close-it)))
(#<procedure:protect> (fn nil (open-and-process-it)) (fn nil (close-it)))

that’s no longer a source code expression that we could type into an editor or save to a file. It has the procedure value in the first list element:

arc> (type (car (macex1 '(after (open-and-process-it) (close-it)))))

Arc3.1 doesn’t like it either...

arc> (after (open-and-process-it) (close-it))
Error: "Bad object in expression #<procedure:protect>"

An error which is generated by the compiler:

(define (ac s env)
  (cond ((string? s) (ac-string s env))
        ((literal? s) s)
        ((eqv? s 'nil) (list 'quote 'nil))
        (#t (err "Bad object in expression" s))))

Oh, but we can fix that! :-)

(define (ac s env)
  (cond ((string? s) (ac-string s env))
        ((literal? s) s)
        ((eqv? s 'nil) (list 'quote 'nil))
        (#t s)))

Now anything that isn’t otherwise recognized by the compiler is passed through unchanged, much like strings and numbers are.

arc> (mac after (x . ys)
  `(,protect (fn () ,x) (fn () ,@ys)))
#(tagged mac #<procedure: after>)

arc> (def open-and-process-it () (prn "open and process it") nil)
#<procedure: open-and-process-it>

arc> (def close-it () (prn "close it") nil)
#<procedure: close-it>

arc> (after (open-and-process-it) (close-it))
open and process it
close it

There’s another change to make if we also want to also be able to not only inject function values into the expansion of a macro, but also to be able to inject macro values.

(mac n-of (n expr)
  (w/uniq ga
    `(,let ,ga nil
       (,repeat ,n (,push ,expr ,ga))
       (,rev ,ga))))

Arc3.1 looks to see if a symbol is a macro by checking whether there’s a global variable of that name, which has a macro as its value.

; returns #f or the macro function

(define (ac-macro? fn)
  (if (symbol? fn)
      (let ((v (namespace-variable-value (ac-global-name fn)
                                         (lambda () #f))))
        (if (and v
                 (ar-tagged? v)
                 (eq? (ar-type v) 'mac))
            (ar-rep v)

To allow macro values to be injected into expressions, ac-macro? needs to be extended to also return true when fn is itself a macro value.

In summary, to review our language axioms:

By dropping one of our axioms, we can build a module system that works for both functions and macros entirely on top of these simpler features, and without having to do any renaming.