Writing ‘syntax-case’ Macros

Disclaimer: This is not really a tutorial on macros, it's more of a quick introduction to using Racket's syntax-case-based macros for people who are familiar with symbolic macros and miss their “simplicity”. It's also not comprehensive or thorough or complete, it's just intended to provide a rough quick overview of how to write macros. It was originally posted on comp.lang.scheme in a thread called “Idiot's guide to Scheme macros”, but I avoided that title here, since it's not a general purpose guide. (Also, it's yet another attempt to dispel the irrational “macrophobia” some people have when it gets to hygienic macros, leading them back to using defmacro with all its problems.)

The main idea with Racket's macro system (and with other syntax-case systems) is that macros are syntax to syntax functions, just like the case of defmacro, except that instead of raw s-expressions you're dealing with syntax objects. This becomes very noticeable when identifiers are handled: instead of dealing with plain symbols, you're dealing with these syntax values (called “identifiers” in this case) that are essentially a symbol and some opaque information that represents the lexical scope for its source. In several syntax-case systems this is the only difference from defmacro macros, but in the Racket case this applies to everything — identifiers, numbers, other immediate constants, and even function applications, etc — they are all the same s-expression values that you're used to, except wrapped with additional information. Another thing that is unique to Racket is the extra information: in addition to the opaque lexical context, there is also source information and arbitrary properties (there are also certificates, but that's ignorable for this text).

With this in mind, explaining the rest is not too difficult:

• (syntax-source stx), (syntax-position stx), (syntax-line stx), (syntax-column stx) — retrieve parts of the source location information.
• (syntax-e stx) — takes a syntax value and returns the value it “wraps”. For example, if stx is an identifier you'd get a symbol, and if it's a number you'd get the number. If it's a simple parenthesized form, you'd get a list of syntax values for the subforms. Note that the list can be improper, with the last element being a syntax object that contains a proper list. (But the list will actually be improper if the original syntax was a dotted list.)
• (syntax->datum stx) — takes a syntax value and returns the plain s-expression that it holds. This is done by recursive uses of syntax-e. (It would be a simple definition that does what you'd think it should do.)
• (syntax->list stx) — sometimes you want to pull out the list of syntax values from a given parenthesized syntax, but syntax-e does too little (can still return an improper list) and syntax->datum does too much (gives you back raw s-expressions). syntax->list is a utility function that uses syntax-e as many times as needed to get back a proper list of syntax values. If that's not possible (if the input syntax was not a proper list), it returns #f, so it serves as a predicate too.
• (syntax-property stx prop) — returns the given property value from stx, if any, and #f if none. For example, try

  (syntax-property #'[foo] 'paren-shape)

  (The #' is similar to a quote, but for syntax values — I'll get to that later on.)
• Note that there is no accessor for the opaque lexical scope, and as you'll see next, you don't need one.
• To create a piece of syntax you use datum->syntax, and you give it an s-expression which will be the “contents” of the resulting syntax object. (The input can contain syntax values, which are left as is.) But when you do that you need to give it the other bits — including the lexical context thing, which you have no access to. The way that's done is:

  (datum->syntax context-stx input-sexpr)

  This returns a syntax value that wraps the input-sexpr value, using the lexical scope from context-stx. A common way to “break hygiene” and create a binding that is visible to the macro user's code is:

  (datum->syntax stx 'foo)

  where stx is some syntax value that you get from the user input to the macro. It returns a foo identifier that has the same lexical context information as stx, so it's as if it came from there.
  Note that there is actually another optional argument that specifies the source (either using another syntax object, or as an explicit list), and another for copying the properties from — so an alternative to the above would be:

  (datum->syntax stx 'foo stx stx)

  which also makes the source information and the properties be the same as those of stx (for example, this can matter in case of syntax errors ).
• There is also (quote-syntax blah) which creates a quoted syntax, with its lexical source from the place it appears.
• Finally, define-syntax does the magic of tying a name with a transformer function.

And that's almost everything that you need in order to write hygienic (and non-hygienic) macros. Very inconveniently.

For example, here's a simple while macro (use this in a file that starts with “#lang racket”):

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   stx
   `(let loop ()
      (when ,(cadr subs)
        ,@(cddr subs)
        (loop)))
   stx))

which breaks like this:

(define x 2)
(let ([let 5])
  (while (< x 10)
    (printf "x = ~s\n" x)
    (set! x (add1 x))))

The problem is that all of those quoted names are getting the context of the user input, which is not the right thing (it's close to a defmacro). To fix this, you need to quote-syntax all of these identifiers, so they'll have the macro source instead of the input source:

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   stx
   `(,(quote-syntax let) ,(quote-syntax loop) ()
     (,(quote-syntax when) ,(cadr subs)
      ,@(cddr subs)
      (,(quote-syntax loop))))
   stx))

But that's clearly insane... More than being tedious, it's still incorrect since all of those function application parens will have the user's lexical context (Racket has a special implicit #%app macro that gets used in all function applications, and in this case the context of this application will make it unhygienic). Instead of doing this, a better approach would be to create the resulting syntax with the lexical context of the macro source by changing just that argument:

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   (quote-syntax here)
   `(let loop ()
      (when ,(cadr subs)
        ,@(cddr subs)
        (loop)))
   stx))

And that's simple again, and works fine now.

The problem is that it's tedious wrt to deconstructing the input (which happens to be trivial in this case), and wrt slapping together an output value — and that's where syntax-case comes in. It addresses the both by using pattern matching, where identifiers in patterns are bound as “syntax patterns”. A new form is added — syntax — which is similar to a quote, except that (a) it actually quotes things similarly to quote-syntax, with the lexical context of the syntax form; and (b) pattern variables are substituted with what they matched. With this, the above macro becomes much easier:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax (let loop ()
               (when test
                 body ...
                 (loop))))]))

The first line specifies that you want to match the stx input syntax, and that you have no “keywords” (in the same sense as in syntax-rules). The second line is the pattern that is matched against this input — with two pattern variables that match the second subexpression and the sequence of expressions from the third and on. (The first subexpression is matched against _ which is a wild-card that matches anything without binding a pattern variable — the head part is often not needed, since it's just the macro name.) The last line is the output, specified using syntax, which means that it's very similar to the previous version where everything is given the lexical context of the macro and the two pattern variables are replaced with the two matches (so body gets spliced into the resulting syntax).

Now, say that you want an unhygienic user-visible piece of syntax. For example, bind the always entertaining it thing to the test result. This:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax (let loop ()
               (let ([it test])
                 (when it
                   body ...
                   (loop)))))]))

won't work because it has the macro source — it's hygienic and therefore not visible. Instead, you need to use datum->syntax with the user syntax:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (let ([it (datum->syntax stx 'it)])
       (syntax (let loop ()
                 (let ([it test])
                   (when it
                     body ...
                     (loop))))))]))

But this doesn't really work since it needs to be bound as a pattern variable rather than a plain binding. syntax-case can be used here again: (syntax-case <name> () [foo <body>]) will match foo against the <name> syntax, and if it's a name then it will be bound as a pattern variable in the <body>.

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax-case (datum->syntax stx 'it) ()
       [it (syntax (let loop ()
                     (let ([it test])
                       (when it
                         body ...
                         (loop)))))])]))

Note that since it is a pattern variable, it doesn't need to be unquoted — syntax will do that.

Finally, there are some more conveniences. First, with-syntax is a macro that binds pattern variables (by a similar translation to syntax-case):

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (with-syntax ([it (datum->syntax stx 'it)])
       (syntax (let loop ()
                 (let ([it test])
                   (when it
                     body ...
                     (loop))))))]))

and there's the #' reader macro for syntax:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (with-syntax ([it (datum->syntax stx 'it)])
       #'(let loop ()
           (let ([it test])
             (when it
               body ...
               (loop)))))]))

and there are also #` and #, and #,@ which are implemented by translating them to uses of with-syntax.

Note that the last example uses the lexical context of the whole form for the new identifier, but that's not only the option. You could use any other part of the macro input — for example, you could use the macro keyword:

(define-syntax (while stx)
  (syntax-case stx ()
    [(hd test body ...) ; need the head now
     (with-syntax ([it (datum->syntax #'hd 'it)])
       ... same ...)]))

or the test expression (use #'test). Each of these choices has subtle differences that are especially important when you're composing macros (for example, using a second macro that expands to a while, where the test expression comes from that macro rather than the user code). Demonstrating these things is a popular way to pass the time in some circles, but I'll avoid it here. In fact, a great way to avoid this whole thing altogether is not create unhygienic bindings in the first place. It sounds like doing so excludes cases where you really want to have a new binding visible in user code, but racket provides “syntax parameters” that can be used more conveniently (and less confusingly) — see an earlier post for a description of that. As a side note, these options are a good hint that a hygienic macro system is more expressive than a symbolic defmacro system, where no such choices exist. Creating such macros using defmacro can appear easier simply because of this lack of choice — in the same way that CPP-style string-based macros are “simpler” than defmacro since they're less expressive (just appending lexical tokens, no structural information).

There are other important aspects of the Racket macro system that are not covered here. The most obvious of them is worth mentioning here: Racket separates the “runtime phase” from the “syntax phase”. For example, if you want to try these examples with “#lang racket/base”, you'll need to add (require (for-syntax racket/base)) since the racket/base language doesn't have a full language in its syntax phase.

Roughly speaking, this makes sure that source code is deterministically compilable by having each level live in its own world, limiting macros to deal only with the input syntax only and not runtime values. (For example, a CLOS implementation in this system cannot check the value of an identifier bound to a class to determine how some macro should expand.) This results in reliable compilations that do not depend on how things were loaded, or whatever happened on the REPL.

The important bottom line here is that you get to write macros with the full language available — and phase separation means that Racket is explicitly designed to make running code at the macro level and using it by the compiler as robust as possible, so you don't have to worry about using any complex system as part of your macro. You just need to keep in mind that the macro world is completely separate from the runtime, and the direct benefit of not worrying about weird interactions with compilation and file loading orders.

Languages as Libraries, PLDI 2011

We've just finished up the final version of our PLDI 2011 paper on language extension in Racket. The paper describes how the module system and the syntax system work together to support new languages with new static semantics, such as Typed Racket. Here's the abstract:

Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage experimentation with domain-specific languages. The Scheme programming language improves on Lisp with macros that respect lexical scope.

The design of Racket—a descendant of Scheme—goes even further with the introduction of a full-fledged interface to the static semantics of the language. A Racket extension programmer can thus add constructs that are indistinguishable from “native” notation, large and complex embedded domain-specific languages, and even optimizing transformations for the compiler backend. This power to experiment with language design has been used to create a series of sub-languages for programming with first-class classes and modules, numerous languages for implementing the Racket system, and the creation of a complete and fully integrated typed sister language to Racket's untyped base language.

This paper explains Racket's language extension API via an implementation of a small typed sister language. The new language provides a rich type system that accommodates the idioms of untyped Racket. Furthermore, modules in this typed language can safely exchange values with untyped modules. Last but not least, the implementation includes a type-based optimizer that achieves promising speedups. Although these extensions are complex, their Racket implementation is just a library, like any other library, requiring no changes to the Racket implementation.

To learn how to implement your own new language in Racket, start with this documentation.

Extending Typed Racket, Part 1

The Typed Racket team is pleased to announce a number of new additions to our system. We'll be writing a few blog posts about them, all of which you can read here.
This post begins with the core of the Typed Racket type system. The fundamental idea at the heart of Typed Racket is called occurrence typing. This is the technique that allows us to typecheck existing Racket programs without requiring rewrites. Here's a simple example:

(if (number? x) (add1 x) 0)

The typechecker can figure out from the use of number? that the second occurrence of x is always going to be a number. This simple form of occurrence typing is enough to take Typed Racket a long way. But because we want to be able to handle all the sophisticated reasoning that programmers are already using to write their Racket programs, we have been working on extending the system further.
The new design of our system is described in a paper, Logical Types for Untyped Languages, in the upcoming International Conference on Functional Programming. The introduction provides an overview that's acessible to any Racket programmer, but here's the key example:

(cond
  [(and (number? x) (string? y)) — 1 —]
  [(number? x)                   — 2 —]
  [else                          — 3 —])

In expression 1, we know that x is a number and y is a string. In 2, we know that x is a number and y is not a string, by the logical properties of and and cond. This form of logical reasoning is enabled by the new foundation of the system, and makes the entire system significantly more expressive.
All of these improvements are available in the current version of Racket.

Serializable Closures in PLT Scheme

PLT Scheme supports an extensible serialization system for structures. A structure is serializable if it has a prop:serializable property. There are many properties in PLT Scheme for other extensions, such as applicable structures and custom equality predicates.

The PLT Web application development framework uses these features to provide serializable continuations through a number of source transformations and a serializable closure structure.

Warning: This remainder post refers to features only available in the latest SVN revision of PLT Scheme.

I've recently made these closures more accessible to non-Web programs through web-server/lang/serial-lambda. Here's a demo:

#lang scheme
(require web-server/lang/serial-lambda
         scheme/serialize)

(define f
  (let ([z 5])
    (serial-lambda
     (x y)
     (+ x y z))))

(define (test-it)
  (printf "~S~n" (f 1 2))
  (let ([fs (serialize f)])
    (printf "~S~n" fs)
    (let ([df (deserialize fs)])
      (printf "~S~n" df)
      (printf "~S~n" (df 1 2)))))

> (test-it)
8
((2) 1 ((#"/Users/jay/Dev/svn/plt/collects/web-server/exp/test-serial.ss" . "lifted.6")) 0 () () (0 5))
#(struct:7a410aca70b31e88b4c2f0fe77fa7ffe:0 #)
8

Now, let's see how it is implemented. web-server/lang/serial-lambda is thin wrapper around web-server/lang/closure, which has two syntax transformer functions: define-closure! which defines the closure structure and make-closure which instantiates the closure. (The two tasks are separated to easily provide a user top-level definition syntax for named closures with different free identifires, rather than simply anonymous lambdas with fixed free identifiers.)

make-closure does the following:

1. Expands the procedure syntax using local-expand, so it can use free-vars to compute the free identifires.
2. Uses define-closure! to define the structure and get the name for the constructor.
3. Instantiates the closure with the current values of the free identifiers.

The more interesting work is done by define-closure!. At a high-level, it needs to do the following:

1. Create a deserialization function.
2. Create a serialization function that references the deserializer.
3. Define the closure structure type that references the serializer.
4. Provide the deserializer from the current module so that arbitrary code can deserialize instances of this closure type.

These tasks are complicated in a few ways:

1. The deserializer needs the closure structure type definition to create instances and the serializer needs the closure structure type to access their fields.
2. The serializer needs the syntactic identifier of the deserializer so that scheme/serialize can dynamic-require it during deserialization.
3. The deserializer must be defined at the top-level, so it may be provided.
4. All this may occur in a syntactic expression context.

Thankfully, the PLT Scheme macro system is powerful to support all this.

• syntax-local-lift-expression allows a syntax transformer to lift an expression to the top-level of a module and returns the identifier it is bound to.
• syntax-local-lift-values-expression (added in 4.2.0.3) provides the same for expressions that return multiple values, such as make-struct-type, which is used to define structures.
• syntax-local-lift-provide (added in 4.2.0.4) allows a syntax transformer to lift a provide to the top-level.

The only complicated piece is allowing the deserializer and serializer to refer to the closure structure constructor and accessors. This is easily accomplished by first defining lifting boxes that will hold these values and initializing them when the structure type is defined. This is safe because all accesses to the boxes are under lambdas that are guaranteed not to be run before the structure type is defined.

An aside on the closure representation. The closure is represented as a structure with one field: the environment. The environment is represented as a thunk that returns n values, one for each of the free identifiers. This ensures that references that were under lambdas in the original syntax, remain under lambdas in the closure construction, so the serializable closures work correctly inside letrec. This thunk is applied by the serializer and the free values are stored in a vector. The closure also uses the prop:procedure structure property to provide an application function that simply invokes the environment thunk and binds its names, then applys the original procedure syntax to the arguments.

An aside on the serializer. The deserializer is bound to lifted identifier which is represented in PLT Scheme as an unreadable symbol. Version 4.2.0.5 added support for (de)serializing these.

Explicit Renaming Macros; Implicitly

It's been one too many times that I hear respectable Schemers talk about how they like explicit renaming macros — not because they're more powerful, but because using them is close to using simple defmacros. In this post I'll show how you can easily write ER-like macros in PLT, just so I won't need to explain the same thing once again. Disclaimers:

• If you're not interested in ER-macros, then you shouldn't read this.
• I'm not claiming that ER macros are not respectable, I'm just surprised at the knee jerk reaction to syntax-case.
• This is not an attempt at providing some portable library or even a PLT library. The intention is to show that syntax-case-style macros are "as convenient" as ER macros, if you really want to get down to that level.
• This is also not an attempt at any kind of formal claim of equivalence in any direction, only a demonstration that you can get the same kind of convenience.
• The bottom line here should be just the convenience point, addressed at people who like ER macros for that, and who think that syntax-case macros are somehow magical or that you lose the ability to play with S-expressions.

The important fact here is that while PLT's syntax-case macro system does not give you raw S-expressions, what you get is a simple wrapper holding them. A macro is a syntax transformer: a function that consumes a syntax value and returns one. For example:

  (define-syntax (foo stx)
    #'123)

is a macro that always expands to 123 (with #'123 being the usual shorthand for (syntax 123)). A syntax object in PLT Scheme (the input to macro functions) is an S-expression, with some lexical information added — this includes the lexical context (in an opaque form), source location, and a few more things. To be more precise, a syntax value is a nested structure of wrappers holding lists and pairs, holding more wrappers, with identifiers at the leaves, where an identifier is a wrapper holding a symbol. It's easy to strip off all wrappers using syntax->datum if you like to work with S-expressions, but you don't want to strip it off of identifiers, since that will lose the important gravy. (In fact, the defmacro library works by stripping off all information, even from identifiers, then reconstructing it by trying to match names in the output form with the original input.) Instead of throwing away all information, what we want to do is preserve identifiers. We can use syntax->list for this: this is a function that takes a syntax value that contains a list, and strips off the top-level extra information leaving you with a list of syntaxes for the sub-expressions (returning #f if the input syntax does not hold a list). Once we have such a list, we can do the usual kind of processing with it, and when we're done turn the result back into a syntax using datum->syntax (which "borrows" the original input expression's information). For example,

  (define-syntax (add1 stx)
    (let ([+ #'+])
      (datum->syntax stx `(,+ 1 ,@(cdr (syntax->list stx))) stx)))

That's a very simple example though; if you try something a little more complicated, you quickly find out that all this unwrapping is inconvenient:

  (define-syntax (mylet stx)
    (let ([*lambda #'lambda])
      (datum->syntax
       stx
       `((,*lambda ,(map (lambda (x) (car (syntax->list x)))
                         (syntax->list (cadr (syntax->list stx))))
                   ,@(cddr (syntax->list stx)))
         ,@(map (lambda (x) (cadr (syntax->list x)))
                (syntax->list (cadr (syntax->list stx)))))
       stx)))

(Note also the *lambda that is used to avoid the lambda expressions used in the meta-code.) What can help here is some helper function that receive a syntax value as its input, and turn all wrapped lists into real lists recursively, but will leave identifiers intact:

  (begin-for-syntax
    (define (strip stx)
      (let ([maybe-list (syntax->list stx)])
        ;; syntax->list returns #f if the syntax is not a list
        (if maybe-list (map strip maybe-list) stx))))

But as long as we're writing a syntax utility, we can make it do a litte more work: feed the resulting tree to your transformer, grab its result, and do the necessary datum->syntax voodoo on it:

  (begin-for-syntax
    (define (er-like-transformer transformer)
      (define (strip stx)
        (let ([maybe-list (syntax->list stx)])
          ;; syntax->list returns #f if the syntax is not a list
          (if maybe-list (map strip maybe-list) stx)))
      (lambda (stx)
        (datum->syntax stx (transformer (strip stx)) stx))))

With this utility defined, the above macro becomes much easier to deal with:

  (define-syntax mylet
    (er-like-transformer
     (lambda (exp)
       (let ((vars  (map car (cadr exp)))
             (inits (map cadr (cadr exp)))
             (body  (cddr exp)))
         `((,(syntax lambda) ,vars ,@body)
           ,@inits)))))

...and this is almost identical to the explicit renaming version of the macro; for example, compare it with the sample code in the MIT-Scheme manual. The only change is that (rename 'lambda) is replaced with (syntax lambda). Obviously, this is very close, but doesn't show intentional captures. So I just grabbed the loop example from the same page, and did the same change — only this time I used #'foo instead of (syntax foo) (and I also changed the one-sided if to a when). The resulting macro works fine:

  (define-syntax loop
    (er-like-transformer
     (lambda (x)
       (let ((body (cdr x)))
         `(,#'call-with-current-continuation
           (,#'lambda (exit)
            (,#'let ,#'f () ,@body (,#'f))))))))
  
  (define-syntax while
    (syntax-rules ()
      ((while test body ...)
       (loop (when (not test) (exit #f))
             body ...))))
  
  (let ((x 10))
    (while (> x 0)
      (printf "~s\n" x)
      (set! x (- x 1))))

This is pretty close to a library, and indeed, as I was writing this text I found a post by Andre van Tonder on the Larceny mailing list that uses a very similar approach and does make a library out of it. This is done by adding two arguments to the expected ER-transformation function — one is a rename function (since the above method uses syntax it is limited to immediate identifiers), and the other is always passed as free-identifier=?. Such a compatibility library is, however, not the purpose of this post. Finally, there is still a minor issue with this — PLT has an implicit #%app which is used wherever there are parentheses that stand for a function application — and in this code they are used unhygienically. This is usually not a noticeable problem, and if it is, you can add explicit #%apps. It might also be possible to find a more proper solution (e.g., use a hash table to keep track of lists that were disassembled by the client transformer), but at this point it might be better to just use the more natural syntax-case anyway.

The Two State Solution: Native and Serializable Continuations in the PLT Web Server

One of the annoyance of the stateless Web application language that comes with the PLT Web Server is that you can't call third-party higher-order library procedures with arguments that try to capture serializable continuations. (I know, you try to do that all the time.) For example:

(build-list
 3
 (lambda (i)
   (call-with-serializable-current-continuation
    (lambda (k) (serialize k)))))

The problem is that the stateless language performs a transformation on your program to extract the continuations into a serializable representation. If you really need to do this, we've developed a compromise called "The Two State Solution": one state on the client and the other on the server. Only the third-party parts of the continuation (in this case, the code inside build-list) are stored on the server; everything else is shipped to the client. You just need to annotate your code slightly to indicate where the transition is:

(serial->native
 (build-list
  3
  (lambda (i)
    (native->serial
     (call-with-serializable-current-continuation
      (lambda (k) (serialize k)))))))

serial->native signals the transition to the third-party and native->serial signals the transition back.

It is still a little annoying to find when you've called these third-party higher-order library procedures with arguments that try to capture serializable continuations, so there's a simple macro that provides a transitioning wrapper for you:

(define-native (build-list/native _ ho) build-list)

expands to:

(define (build-list/native fst snd)
  (serial->native
   (build-list
    fst
    (lambda args
      (native->serial
       (apply snd args))))))

This new feature is documented in the online manual, of course.

Dirty Looking Hygiene

With the recent release of Arc, there has been some discussion over hygienic macros. Yes, hygienic macros are usually very convenient, but they can become messy in some ‘corner’ cases. People who learn about macros in Scheme usually start with syntax-rules, and being the limited tool that it is, they often get the impression that for advanced uses (like a macro that captures an identifier) you need to use syntax-case which is this “really obscure thing”. For example, say that we want to implement an if form that is similar to Arc's if. This is pretty easy using syntax-rules:

  (define-syntax if*
    (syntax-rules ()
      [(if*) (void)]
      [(if* X) X]
      [(if* C X more ...) (if C X (if* more ...))]))

But more important than being easy to write: it is also easy to read. In fact, the nice thing about syntax-rules is that you write more or less the specification of your transformation. Compare this to the specification of Arc's if, which appears in a comment before the definition of ac-if in “ac.scm”:

  ; (if) -> nil
  ; (if x) -> x
  ; (if t a ...) -> a
  ; (if nil a b) -> b
  ; (if nil a b c) -> (if b c)

(Except that the comment mixes up the syntactic specification and the semantic evaluation.) As a side note, now that we have this definition, it is easy to construct a new language that is just like MzScheme, except for its if that behaves like the above:

  (module arc-like mzscheme
    (define-syntax if* ...the above definition...)
    (provide (all-from-except mzscheme if)
             (rename if* if)))

You can now write code that uses "arc-like.scm" as its language, using the new if. There is no problem in accommodating two languages with two different if's: the new form is compiled to the old one, and there is no confusion in which version you use in any module. Back to the macro issue: as I said above, you run into problems if you want to capture names, right? For example, if you want to implement Arc's aif. The usual syntax-case solution is to construct an identifier that has the lexical context of the input syntax. It's easy to abstract over all this — I posted a message on the Arc forum showing how to define a defmac macro that has the simplicity of syntax-rules with the added convenience of specifying keywords and captured names. This works for some cases, but there are still some subtle corner cases. But there's a better solution in PLT Scheme, one that follows Paul Graham's intuition when he says:

“captured symbols are kind of freaky”

The basic idea is a change of perspective: instead of (unhygienically) binding individual occurrences of it whenever aif is used, you define it once as a thing in its own right — a special context-dependant piece of syntax. Outside of an aif form, it has no meaning: we simply make it throw a syntax error. Uses of aif provide a meaning for it by locally changing its meaning (its expansion) to something useful: the binding that holds the result of evaluating the condition expression. (“Locally” means within a piece of syntax, so the new meaning is valid in a lexical-scope.) In PLT Scheme, the “special context-dependant piece of syntax” are syntax parameters, and you change them locally with syntax-parameterize. To continue the above example, here's how we make our if* anaphoric:

• require the (lib "stxparam.ss" "mzlib") library,
• define it as a syntax using define-syntax-parameter, and have it raise an error by default,
• bind a temporary variable to the result of evaluating the condition,
• wrap the positive branch with syntax-parameterize, using make-rename-transformer, which is a convenient way to make a macro that behaves like the new variable.

The implementation looks like this:

  (require (lib "stxparam.ss" "mzlib"))
  (define-syntax-parameter it
    (lambda (stx)
      (raise-syntax-error #f "can only be used inside `if'" stx)))
  (define-syntax if*
    (syntax-rules ()
      [(if*) (void)]
      [(if* X) X]
      [(if* C X more ...)
       (let ([b C])
         (if b
           (syntax-parameterize ([it (make-rename-transformer #'b)]) X)
           (if* more ...)))]))

The resulting macro does not break hygiene. For example, (let ([it 3]) (if #t it)) evaluates to 3, because it shadows the global it that if changes. This is a change from a real unhygienic macro — but that's the whole point: we (the macro author) do not interfere with scopes in the user code. Note that (if 1 (if 2 it)) still evaluates to 2, because the outer if does not really bind it — it is not captured, just changed locally — so the inner if changes it again. Also, (if #f it it) raises the usual context error, since our macro changes it only in the positive branch.

PLT Modules and Separate Compilation

For my summer job this year, I'm programming in Common Lisp; this is the first time I've used the language for anything more than toy examples. The experience has given me new appreciation for the PLT module system and how it enables separate compilation.

Lisp has a package system, of course, but it's not the same thing. It's primarily a tool to make sure that the symbols in one part of the program don't collide with the symbols in another part (unless you ask them to). Packages aren't about abstraction: while you can specify which symbols are exported from the package and which aren't, that's just a suggestion that's not enforced by the language.

(You'll notice, by the way, that I used the word "symbol" and not "identifier," which is the more common term in the study of programming languages, in the previous paragraph. That's deliberate: the Lisp package system works on symbols, not identifiers, so it also affects quoted, literal symbols. In my experience, this is sometimes helpful, sometimes a real pain, and usually completely unexpected. But that's a topic for another post.)

Also, there's no real relationship between Lisp packages and files. One package can be spread across multiple files, and one file can contain code in several different packages.

All this means that separate compilation in Lisp is a real problem. There is a system, ASDF, that attempts to address this need. (For more details, consult the closest thing to a homepage that I could find for ASDF.) I'm no expert on ASDF, but essentially the programmer specifies the dependencies between source files, in a set of files that exist parallel to the Lisp source. (ASDF does support grouping source files into larger chunks and specifying dependencies between those chunks, but as far as I can tell that's largely a convenience thing.)

The key thing for separate compilation, of course, is the dependencies. With ASDF, the programmer specifies those manually, and then ASDF basically does a topological sort such that if file a depends on file b, then ASDF ensures that a is compiled and loaded before b is compiled, and again before B is loaded. (This should start sounding a little familiar to folks who've worked in the area where PLT's modules and macros intersect.)

So far, so good. Unfortunately, there are a couple of problems with this setup. First, the dependencies between files are specified outside the language. This means that, if you happen to forget one, the results are not well-defined. If ASDF happens to choose an order that's consistent with the dependency you left out, everything will just work, and you won't have any indication that there's a problem. If, however, it doesn't, then you'll get random "undefined function" and "undefined symbol" errors---if you're lucky (at least in SBCL, the implementation of Common Lisp that I use at my job). In PLT, by contrast, inter-module dependencies are part of the language, so the compiler will always give you an undefined-identifier error when it tries to compile a module in which you've forgotten a require form. Big win, in my opinion (although we could argue about whether this should be an error or a warning, and whether the compiler should report lots of errors or just one before giving up completely).

Second, because ASDF lives outside the compiler, it can't be very smart about how macros affect separate compilation. I don't fully understand this, perhaps because the folks who've been mentoring me at my job haven't thought it worth the time to explain it to me fully. But it appears that, if you change a macro that's used in other files, or change a function that's called by a macro at expansion time, you have to do the effect of a make clean in a distressingly large number of cases. This is a real problem when you've got a large source base (~200K LOC, I think) and you're trying to speed up builds, as we are, and it's especially problematic if you're trying to run unrelated parts of the build in parallel.

I've certainly griped about the complexity of the interaction between PLT's modules and macros in the past. But after this summer, I have to say it's awfully nice to have a module system that Just Works for separate compilation. Nicely done, Matthew.

(I've pointed the folks at work at Matthew's ICFP 02 paper, but as that technique requires a lot of support from the compiler, and we don't have the resources to add the necessary support to SBCL ourselves, I don't know that it'll be more than a "wouldn't it be nice if we could do that?")

(Answer to rhetorical question in preceding paragraph: Yes. Yes it would.)

macros and hygiene, resumed

The Friday entry demonstrates how to break hygiene for a macro that defines a generator. Ryan Culpepper, the local macrologist, reminded me that expanding into this macro goes wrong in the syntax-case world:

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

Run this in Pretty Big [DrScheme] and you get a strange note concerning MrEd's yield or run it in MzScheme [Textual] and you get an error message about 'yield' being unbound. What gives? The 'stx' of datum->syntax-object is the syntactic context of the new macro but it doesn't bind yield; it just uses it. So the definition of yield in define/y must be a different one according to the hygiene standards. Ergo yield is free at the top-leve [MzScheme] or bound to the yield import from MrEd [Pretty Big]. ;; --- How can we try to fix this? The explanation suggests we use a different macro definition for define/y, one that uses a context that is guaranteed from the body of an instance of define/y:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body0 body ...)
     (with-syntax 
         ((yield-name 
           (datum->syntax-object (syntax body0) 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body0 body ...))))]))

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

;; --- try it out ---

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

(list (bar) (bar) (bar) (bar))

Run it. You will find that it works as expected. Tomorrow, time permitting, I will tell you what's wrong with it and how you can fix it.

control and macros

After reading the posts on control operators, Vlado Zlatanov decided to look into prompt, control, fcontrol and the rest of the goodies in control.ss. So based on the example from the blog post I did this python-like snippet:

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

He decided to look into turning it into a macro, such that the above ends up being correct code. When he got stuck, he asked on our mailing list and the resulting dialog was so informative that I decided to blog it. My first replay was this suggestion:

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define exit-with #f)
       (define (switch-control-context th)
         (call/cc 
          (lambda (k)
            (set! exit-with k)
            (th))))
       (define (yield-name x)
         (call/cc 
          (lambda (resume-here)
            (set! name 
               (lambda () 
                 (switch-control-context 
                  (lambda () 
                     (resume-here 'dummy)))))
            (exit-with x))))
       (switch-control-context (lambda () body ...)))]))

I sent this out with two suggestions. First, use control.ss to simplify the code. Second, use syntax-case to eliminate the need for the programmer-user of define/y to specify the name of yield. So, here is the prompt-based code:

(require (lib "control.ss"))

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define (yield-name x)
         (control resume-here
            (set! name
                  (lambda ()
                    (prompt (resume-here 'dummy))))
            x))
       (prompt body ...))]))

(define/y yield (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

This time I include a test case that assures the proper return behavior of yield. The definition of define/y shows how to mark the return point with prompt and how to switch to this point with control so that your generator can resume the traversal at the place where it was interrupted. For the second challenge, I wrote this definition:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body ...)
     (with-syntax 
         ((yield-name (datum->syntax-object stx 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body ...))))]))

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

If you compare the two macro definitions, you notice very little difference. Indeed, what really differs is the "interface" (the API), that is, the way you can use the macro: see the test case. What also differs is that the definition uses syntax-case and with-syntax to inject yield into the body of define/y. In response, Vlado wrote "but isn't this non-hygienic." Here is my response:

Hygiene is a uniformity default imposed on the expander with a provision for programmers to choose the non-default. I chose this word carefully when I coined the phrase. So what you have *is* a hygienic solution.

In other words, injecting an identifier into a macro is not a violation of hygiene at all. It's just means using the full power of the macro system.

XML Transformation in Scheme

Selenium is a tool for testing web applications, the core of which is a Javascript library that controls a web browser. With the Selenium IDE you can convert your actions in a web browser into tests, and with the Selenium Remote Control you can control a web browser from code. I've recently been working on adding Selenium Remote Control bindings to PLT Scheme, which has resulted in a nice and hopefully instructional demonstration of XML transformation in PLT Scheme

The Selenium Remote Control is controlled by sending simple messages over HTTP. The format of the messages isn't important. What is, is that there are a lot of them, and the API is specified in a file called iedoc.xml that comes with Selenium. The Java/Python/Ruby bindings are generated using XSL. If I was to use XSL I'd have a processing pipeline that uses three languages (XSL, Java, Scheme) which is two more than I'd like. Hence I turned to WebIt!, an XML transformation DSL written in Scheme, to create an all Scheme pipeline. The rest of this post wshows the steps I used to transform the Selenium API into Scheme code using WebIt! I think this is interesting in its own right, but also serves as a nice demonstration of the power of macros, which WebIt! makes extensive use of.

My first step is to get an idea of the structure of the XML. The bits I'm interested in look like this:

<function name="click">
  <param name="locator">an element locator</param>
  <comment>Clicks on a link, button, checkbox or radio button.
  If the click action causes a new page to load (like a link usually
  does), call waitForPageToLoad.</comment>
</function>

Let's read in the XML file and extract all the function elements. For this I'll use SSAX and SXPath:

(require
 (planet "ssax.ss" ("lizorkin" "ssax.plt" 1))
 (only (planet "sxml.ss" ("lizorkin" "sxml.plt" 1)) sxpath))

(define api
  (with-input-from-file "iedoc.xml"
    (lambda () (ssax:xml->sxml (current-input-port) '()))))

(define functions
  ((sxpath '(// function)) api))

Ok, so we have all the functions. Now let's parse them into a more useful datastructure. Here's my first attempt:

(require (planet "xml.ss" ("jim" "webit.plt" 1 5)))

;; struct function : string (listof string)
(define-struct function (name params))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))
     (make-function name (list param-name ...))]))

(map parse-function functions)

The xml-match macro is a pattern matcher for SXML. You specify the “shape” of the SXML, and if the input matches the pattern the following expressions are evaluated:

(xml-match value
  [(pattern expression ...)]...)

The simplified form of a pattern is:

• (element ...) matches an element with the given name.
• name: value matches an attribute with the given name and value.
• ,binding binds the value of binding to the given name in the scope of the following expressions.
• ... matches zero or more of the preceeding patterns.

In our example the pattern is:

     (function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))

So we're looking for an element called function with an attribute called name the value of which is bound to name. Then follows zero or more param elements, with attribute name, the value of which is bound to param-name. Finally we expect a comment element which can contain any amount of data. The use of _ as the binding name is a common convention to indicate data we don't care about but must still match to make our pattern complete.

I run the code in DrScheme and see the result:

xml-match: no matching clause found

Oops. So our pattern isn't complete. We've also seen one flaw of WebIt!: it doesn't give very good error messages. However we can easily fix this by adding a catch all pattern that raises an error telling us what we failed to match. The code follows. Notice that I've also added pretty printing to make the unmatched SXML easier to read.

(require (lib "pretty.ss"))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))
     (make-function name (list param-name ...))]
    [,err (let ([op (open-output-string)])
            (pretty-print err op)
            (error (format "Didn't match ~n~a~n" (get-output-string op))))]))

Run this code and you'll see the error occurs as we don't allow the description to contain more than one element. This is easily fixed by extending the pattern to ,desc .... The next error is more interesting. The function element contains a return element. The WebIt! pattern language doesn't allows us to express optional patterns, so we have to duplicate our pattern and include the case of return. This also requires we extend the defintion of the function structure.

;; struct function : string string (listof string)
(define-struct function (name return params))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc ...) ...
               (comment ,_ ...))
     (make-function name "void" (list param-name ...))]
    [(function name: ,name
               (return type: ,type ,return-desc ...)
               (param name: ,param-name ,desc ...) ...
               (comment ,_ ...))
     (make-function name type (list param-name ...))]
    [,err (let ([op (open-output-string)])
            (pretty-print err op)
            (error (format "Didn't match ~n~a~n" (get-output-string op))))]))

This works! This is as far as I want to go in this article. We've seen how we can use SSAX. SXPath, and WebIt! to create XML transforms in pure Scheme. There is a lot more to all of these packages but what we've used is sufficient for many uses. The rest of the code to create Scheme from the API is quite straightforward and specific to Selenium. If you're curious read the source of the Selenium PLaneT package, which will be released soon.

This post also appears on Untyping

Macros Matter

Thank you Jens for setting up this Blog.

PLT Scheme is a 12-year old project now and it is definitely time to open it up to the world. The language and the project has contributed numerous ideas and products to the world. This covers programming languages (units, mixins, an implementation of cml-style concurrency, etc); programming tools (drscheme, check-syntax, transparent repls, module browsers, etc), programming pedagogy (htdp, htdc); program engineering (we resurrected the "expression" problem, web programming and continuations); and some more.

Time and again, people have asked me what I consider the one 'feature' that distinguishes us from the rest of the hordes of programming languages. I always respond with a single word:

                                            macros.

We have pushed macros hard, and we have accomplished a lot with them. I conjecture that without macros, we would never have achieved the level of productivity that this group displays.

Of course, everyone else in academia works on types. ML's module type system of the third kind and Haskell's system-complete type system are serious challenges to anyone. It is probably true that you shouldn't consider yourself a programmer if you can't read and write some of those type-laden programs, and I seriously believe that they are the next generation of influential languages.

For the generation-after-the-next then, I see "macros" as one of the big topics (next to concurrency). A real programmer will have to know how Lisp and Scheme-style macros can reduce labor by orders of magnitude, how macros provide the tools for creating the "ultimate abstraction" in the form of domain-specific and embedded languages (Hudak's words). And there is no better place to start with than PLT Scheme's macro system.

So I would like to dedicate this blog to all things macros and everything else that matters in (and to) PLT Scheme.