An easy-looking macro with a deep portability issue

My first example is a compile time name -> value mapping, with some introspection:

#!r6rs
(library (experimental static-map)
(export static-map)
(import (rnrs) (sweet-macros))

(def-syntax (static-map (name value) ...)
  #'(syntax-match (<names> name ...)
      (sub (ctx <names>) #''(name ...))
      (sub (ctx name) #'value)
      ...))
)

This is a kind of second order macro, since it expands to a macro transformer; its usage is obvious in implementations with implicit phasing:

$ cat use-static-map.ss

(import (rnrs) (sweet-macros) (for (experimental static-map) expand))
;; the for syntax is ignored in implementations with implicit phasing

(def-syntax color (static-map (red #\R) (green #\G) (yellow #\Y)))

(display "Available colors: ")
(display (color <names>))
(display (list (color red) (color green) (color yellow)))
(newline)

color is a macro which replaces a symbolic name in the set red, green, yellow with its character representation (#\R, #\G, #\Y) at expand-time (notice that in Scheme characters are different from strings, i.e. the character \#R is different from the string of length 1 "R").

If you run this script in Ikarus or Ypsilon or Mosh you will get the following unsurprising result:

$ ikarus --r6rs-script use-static-map.ikarus.ss
Available colors: (red green yellow)(R G Y)

However, in PLT and Larceny, the above will fail. The PLT error message is particularly cryptic:

$ plt-r6rs use-static-map.ss
/home/micheles/.plt-scheme/4.0/collects/experimental/static-map.sls:8:25:
compile: bad syntax; reference to top-level identifier is not allowed,
because no #%top syntax transformer is bound in: quote

I was baffled by this error, so I asked for help in the PLT mailing list, and I discovered that there is nothing wrong with the client script and that there is no way to fix the problem by editing it: the problem is in the library code!

The problem is hidden, since you can compile the library without issues and you see it only when you use it. Also, the fix is pure dark magic: you need to rewrite the import code in (experimental static-map) by replacing

(import (rnrs))

with

(import (rnrs) (for (rnrs) (meta -1))

i.e. the static-map macro must import the (rnrs) environment at meta-level -1! Why it is so? and how should I interpret meta-level -1?

Negative meta-levels

Matthew Flatt explained to me how meta-levels work. The concept of meta-level is only relevant in macro programming. When you define a macro, the right hand side of the definition can only refer to names which are one meta-level up, i.e. typically at meta-level 1 (expand time). On the other hand, inside a template one goes back one meta-level, and therefore usually a template expands at meta-level 0 (run-time).

However, in the case of the static-map macro, the template is itself a syntax-match form, and since the templates of this inner syntax-match expand one level down, we reach meta-level -1. This is why the macro needs to import the (rnrs) bindings at meta-level -1 and why the error message says that quote is unknown. The comments below should make clear how meta-levels mix:

(def-syntax static-map                          ;; meta-level 0
 (begin
   <there could be code here ...>               ;; meta-level 1
 (syntax-match ()
  (sub (static-map (name value) ...)
       #'(begin
           <there could be code here ...>       ;;  meta-level 0
           (syntax-match (<names> name ...)
             (sub (ctx <names>)
                #''(name ...))                  ;; meta-level -1
             (sub (ctx name)
                #'value)                        ;; meta-level -1
             ...))))

Actually quote is the only needed binding, so it would be enough to import it with the syntax (import (for (only (rnrs) quote) (meta -1))). If we ignored the introspection feature, i.e. we commented out the line

(sub (ctx <names>) #''(name ...))

there would be no need to import quote at meta-level -1, and the macro would work without us even suspecting the existence of negative meta-levels.

Things are even trickier: if we keep the line (sub (ctx <names>) #''(name ...)) in the original macro, but we do not use it in client code, the original macro will apparently work, and will break at the first attempt of using the introspection feature, with an error message pointing to the problem in client code, but not in library code :-(

Meta-levels greater than one

It is clear that the meta-level tower is theoretically unbound in the negative direction, since you can nest macro transformers at any level of depth, and each level decreases the meta-level by one unity; on the other hand, the tower is theoretically unbound even in the positive direction, since a macro can have in its right hand side a macro definition which right hand side will requires bindings defined at an higher level, and so on. In general nested macro definitions increase the meta-level; nested macro templates decrease the meta-level.

Here is an example of a macro which requires importing names at meta-level 2:

$ cat meta2.ss

#!r6rs
(import (rnrs)
        (for (sweet-macros) (meta 0) (meta 1))
        (for (only (rnrs) begin lambda display) (meta 2)))

(def-syntax m
  (let ()
    (def-syntax m2
      (begin                                ;; begin, display and
        (display "at metalevel 2\n")        ;; lambda are used here
        (lambda (x) "expanded-m\n")))       ;; at meta-level 2
    (define _ (display "at metalevel 1\n")) ;; meta-level 1
    (lambda (x) (m2))))                     ;; here

(display (m))

Notice that right hand side of a def-syntax form does not need to be syntax-match form; the only requirement for it is to be a transformer, i.e. a one-argument procedure. In this example the inner macro m2 has a transformer returning the string "m-expanded" whereas the outer macro m has a transformer returning the expansion of (m2) i.e. again the string "m-expanded". Running the script will print the following:

$ ikarus --r6rs-script meta2.ss
at meta-level 2
at meta-level 1
expanded-m

You will get the same in Larceny and in sufficiently recent versions of PLT Scheme (> 4.1.3). Currently Ypsilon raises an exception but this is just a bug (already fixed in the trunk).

Discussion

The concept of meta-level is tricky. On one hand, there only two physical meta-levels, i.e. the run-time (when the code is executed) and the compile time (when the code is compiled). On the other hand, conceptually there is an arbitrary number of positive meta-levels ("before compile time") and negative meta-levels ("after run-time") which have to be taken in account to compile/execute a program correctly: everytime the compiler look at a nested macro, it has to consider the innermost level first, and the outermost level last.

The power (and the complication) of phase specification is that the language used at a given phase can be different from the language used in the other phases. Suppose for instance you are a teacher, and you want to force your students to write their macros using only a functional subset of Scheme. You can do so by importing at compile time all R6RS procedures except the nonfunctional ones (like set!) while importing at run-time the whole of R6RS. You could even perform the opposite, and remove set! from the run-time, but allowing it at compile time.

However, personally I do not feel a need to distinguish the languages at different phases and I like Scheme to be a Lisp-1 language with a single namespace for all variables. I am also not happy with having to keep manually track of the meta-levels, which is difficult and error prone when writing higher order macros. Moreover, in PLT and Larceny writing a macro which expands to a nested macro with N levels is difficult, since one has to write by hand all the required meta imports.

Aziz destroys the Tower of Meta-levels

All this trouble is missing in Ypsilon and in the implementations based on psyntax. In such systems importing a module imports its public variables for all meta-levels. In other words all meta-levels share the same language: the tower of meta-levels is effectively destroyed (one could argue that the tower is still there, implicitly, but the point is that the programmer does not need to think about it explicitly). The model of implicit phasing was proposed by Kent Dybvig and Abdul Aziz Ghuloum, who wrote his Ph. D. thesis on the subject.