9 Embedded Languages
Goals |
— |
Let’s build an embedded language with macros.
Specifically, we translates the class pattern into a Racket-embedded language. The class pattern is commonly used in the non-pattern form in class-oriented programming languages, like Java and C++. As a pattern, however, it typically appears in languages like C or (original) JavaScript. The pattern is that a function (called a constructor) returns an object that collects a set of data together and defines methods over that set of data. These methods can implicitly refer to the data (and each other), as well as the object.
Rather than starting with the expanded code and deriving the macro implementation, like we did previously, let’s start with the ultimate code we want to allow programmers to write. Then, we will work through each of the components of the macro.
9.1 An Example Class
Our example class, posn, represents a point on the 2D plane. We will be able to determine its distance from another point, its distance from the origin, be able to slide it around in the X dimension, and adjust it in the Y dimension. Let’s first go over how users of posns will interact with them.
(posn #:x 0 #:y 0) (posn #:y 4 #:x 2) (posn #:x 3 #:y 5)
(define p (posn #:y 4 #:x 2)) (from-origin (p . slide . 1)) ; => 5
(classy posn ....more....)
These bindings, however, are illegal outside of the posn class. So, a user could not write (posn.x (posn #:x 3 #:y 5)) to get 3. Similarly, the forms field and method are illegal outside of the classy macro.
Like the field accessors, the this reference is illegal outside of the classy form.
9.2 This and That
The first problem to solve in the implementation of classy is exposing the various names (posn, this, posn.x, posn.y, and update) to the macro use.
Macro systems like Racket’s provide default scoping rules (called "hygiene") that are intended to make the scope of variables as predictable as possible. Consider the following macro:
(define-simple-macro (our-or left right) (let ([tmp left]) (if tmp tmp right)))
This macro defines the binding tmp and uses the bindings let & if. What do we expect should happen in the following use site?
(let ([let #f] [if #f]) (our-or 1 2))
If macros were purely textual, like in the C Pre-Processor or M4, then this use site would error because the bindings for let and if are not as expected. The hygiene rules protect the definition of our-or from uses in strange contexts like this. let and if in the definition will always refer to what they refered to when it was defined.
Now, let’s consider another use site:
(let ([tmp 7]) (our-or #f tmp))
In this case, the expansion appears to be
(let ([tmp 7]) (let ([tmp #f]) (if tmp tmp tmp)))
which would lead to the result #f, rather than the expected 7. However, Racket’s macro scope rules also protect use sites from strange macros that move code into contexts that use the same variable names as them. In other words, it is as if the expansion were
(let ([tmp-from-user 7]) (let ([tmp-from-macro #f]) (if tmp-from-macro tmp-from-macro tmp-from-user)))
(define-simple-macro (our-or left-name left right) (let ([left-name left]) (if left-name left-name right)))
(let ([tmp 7]) (our-or tmp #f tmp))
In our classy macro, this is like the posn binding that defines the class and the method bindings (distance-from, etc) that give access to the behavior. On the other hand, classy also needs to expose behavior through a lot of other names, like this, in defiance of the default scoping rules that Racket’s hygiene system provides.
9.3 Introducing Names
Let’s write a trivial macro that demonstrates the functionality we want classy to have with respect to this. This macro will simply take an expression and bind the variable it to that expression. For example,
(define-it 5) (+ it it) ; => 10
We will use the ability to introduce new pattern variables (using with-syntax and #:with) but rather than the right-hand side being another pattern template or generate-temporaries, we will use a new function, datum->syntax.
(define-simple-macro (define-it e) #:with the-new-name (datum->syntax #'e 'it) (define the-new-name e))
datum->syntax converts a piece of datum into a syntax object. A syntax object is simply piece of Racket data with additional scope information attached to it. Therefore, datum->syntax takes two arguments. The second is just the data; in this case new name you want to bind. The first is a syntax object that currently has the scope that you want the new name to be bound inside of; in this case, we want the new name to be bound in the same scope as the expression it is bound to, in this case #'e.
The explanation of datum->syntax above is not completely precise. Refer to the documentation if you want the real dope.
Occasionally, you will want to have the new name based on a piece of the macro input. For example, rather than defining it, we could define something that was like the variable given to the macro.
(define-like x 5) (+ x-like x-like) ; => 10
As the name suggests, datum->syntax has a cousin, syntax->datum, that removes the special syntax information from a piece of data. We could use that on the base name (x) and then manipulate the symbol as data to get something that was x-like.
(define-simple-macro (define-like base:id e) #:with new-name (datum->syntax #'base (string->symbol (string-append (symbol->string (syntax->datum #'base)) "-like"))) (define new-name e))
This code, however, is hideous and we will never contemplate writing it again. Instead, we’ll use format-id, which is like format, except that it produces identifiers and automatically performs all the appropriate coercions.
(define-simple-macro (define-like base:id e) #:with new-name (format-id #'base "~a-like" #'base) (define new-name e))
This new version does exactly the same thing at runtime as the syntax->datum version, but it much more pleasant to write.
9.4 Scoped New Names
define-it and define-like demonstrate that it is possible in Racket to introduce new names and manually break the default hygiene rules. However, it is considered poor taste to introduce new names like this, based solely on manufactured names.
The more beautiful way of doing this is to use syntax parameters. These are distinct names that are separate from the definition of the macro that binds them and the macro specifically takes over the value of the particular name. The macro can only take over the name within a specific region of the program, typically provided as an argument to the macro. (In other words, it can let the name, but it cannot define the name.)
An example use comparable to the last use is as follows:
(with-it 5 (+ it it)) ; => 10
However, if we consider a situation where the user attempts to reference it outside of a context where the macro bound it, the two macros will behave very differently.
; Establish a new scope, A (let () ; Establish another scope, B (let () ; Define it in scope B (define-it 5)) ; Reference it in scope A it ; => ERROR: `it` is unbound)
In this example, Racket itself errors with a reference to an unbound identifier it. In contrast, using syntax parameters, we will be responsible for the error, so we can get the following behavior:
; Establish a new scope, A (let () ; Establish another scope, B, that defines it (with-it 5 (void)) ; Reference it in scope A it ; => it: Illegal outside of with-it)
In this case, it is always bound, but it is bound to a special kind of macro that we write that errors when it is not inside of a with-it. Let’s see how it works.
First, we’ll define the it syntax parameter:
(define-syntax-parameter it (λ (stx) (raise-syntax-error #f "Illegal outside with-it" stx)))
define-syntax-parameter is just like define-syntax, except that it defines one of these special kinds of macros. Now, let’s define the with-it macro:
(define-simple-macro (with-it e body ...+) (let ([this-it e]) (syntax-parameterize ([it (λ (stx) #'this-it)]) body ...)))
This macro first uses let to define this-it, then it uses syntax-parameterize to override the definition of it inside of the new scope that surrounds the body expressions. This new definition is a macro that ignores its input and inserts a reference to the this-it variable.
Our rebinding of it is not very robust though, because it ignores the structure of its input. In other words, a use like this fails:
(with-it (λ (x) (add1 x)) (it 5)) ; => #<procedure>, not 6
It is possible to write this macro robustly, but Racket provides a simple way of producing a macro that simply provides a new name for another binding. These rename transformers are sensitive to the structure of the use, including complex structures like being embedded inside of a set!.
(define-simple-macro (with-it e body ...+) (let ([this-it e]) (syntax-parameterize ([it (make-rename-transformer #'this-it)]) body ...)))
This pattern is extremely common and we will use it for most of the names introduced by our macro. However, our macro makes use of a different kind of name as well: a literal identifier that serves as notation.
9.5 Literal Identifiers
In classy, field and method are identifiers that are not explicitly bound to anything, but rather serve as the notation that is used in the input to the macro. As another trivial example, let’s make a macro that ignores everything after a special marker.
In the with-ignored macro use, everything after the EOF token is ignored and not part of the expansion.
(with-ignored (define x 6) (+ x x) EOF x y z (/ 1 0)) ; => 12, no unbound identifier references or divide-by-zero exceptions
We will define EOF as a macro that raises an error if it is ever used::
(define-syntax EOF (λ (stx) (raise-syntax-error #f "Illegal outside with-ignored" stx)))
If we were to try to define with-ignored as
(define-simple-macro (with-ignored before ... EOF after ...) (let () before ...))
then it would fail, because in this case EOF is just another pattern variable in our input pattern. Instead, we must explicitly tell the pattern match that EOF should be matched literally:
(define-simple-macro (with-ignored before ... (~literal EOF) after ...) (let () before ...))
In this case, the with-ignored form expects to find an identifier that is equivalent to EOF. It may not actually be EOF, because the binding for EOF may have been prefixed when required through prefix-in or it may actually be an identifier produced with (make-rename-transformer #'EOF). If you try to use ~literal without defining the binding yourself, then the macro definition will fail to compile.
It is possible to insist that the macro contain the characters E, O, and F by using (~datum EOF) rather than (~literal EOF). But doing so is generally bad-form, because it is not sensitive to the sorts of renamings that ~literal supports. Datum literals like this are typically reserved for purely notational keywords that appear in well-known places in macro uses. A prime example is the else datum used by cond.
Sometimes, especially in a macro with many cases, you will find yourself writing (~literal x) in many different places in the input syntax. In situations like these, syntax-parse (and define-syntax-class) allow you to declare that a particular identifier is always a literal. We could have written with-ignored as:
(define-syntax (with-ignored stx) (syntax-parse stx #:literals (EOF) [(_ before ... EOF after ...) #'(let () before ...)]))
When you use literals with syntax-parse, you should almost always pass the additional keyword #:track-literals, as in:
(define-syntax (with-ignored stx) (syntax-parse stx #:literals (EOF) #:track-literals [(_ before ... EOF after ...) #'(let () before ...)]))
This keyword, which define-simple-macro adds automatically, adds special meta-information to the result of expansion that Racket IDEs like DrRacket can use to indicate that the binding of EOF was inspected, even though it does not actually appear in the expansion of the macro. This is called a "disappeared use".
9.6 The definition of classy
We will now step through the implementation of the classy macro.
First, we need to define our syntax parameters for this and update, which will be overridden with syntax-parameterize, and define our bindings for field and method, which always fail:
(define-syntax-parameter this (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax-parameter update (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax field (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax method (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx)))
Next, we will define a syntax class (remember those from this morning?) that matches the body of classy. This class is going to provide a uniform interface to everything we need to know about the body of a classy. We need to know what the names of the fields are, the names of the methods, the arguments to each of those methods, and the bodies of each of the methods. We annotate these attribute names with the number of ...s that appear to their right. Each pattern of needs to provide all of these four attributes. The patterns will treat field and method as literals.
(begin-for-syntax (define-syntax-class classy-clauses #:attributes ([fields 1] [methods 1] [methods-args 2] [methods-body 2]) #:literals (field method) ....pattern1.... ....pattern2.... ....pattern3....))
The first pattern is simple, it is used when the body of the classy is empty and just binds the attributes to empty lists.
pattern1 := (pattern () #:with (fields ...) #'() #:with (((methods methods-args ...) methods-body ...) ...) #'())
The second pattern recognizes fields and then more clauses. It passes through the method information from the rest of the body, but prepends information about the given field:
pattern2 := (pattern ((field f:id) . more:classy-clauses) #:with (fields ...) #'(f more.fields ...) #:with (((methods methods-args ...) methods-body ...) ...) #'(((more.methods more.methods-args ...) more.methods-body ...) ...))
Lastly, the third pattern recognizes methods and more clauses. It is dual to the field pattern:
pattern3 := (pattern ((method (m:id ma:id ...) mb:expr ...+) . more:classy-clauses) #:with (fields ...) #'(more.fields ...) #:with (((methods methods-args ...) methods-body ...) ...) #'(((m ma ...) mb ...) ((more.methods more.methods-args ...) more.methods-body ...) ...))
We can now use the syntax class to match the input to the macro:
(define-simple-macro (classy name:id . c:classy-clauses) ....classy1....)
The syntax class allows us to use c.fields to refer to all of the fields and c.methods to refer to the methods.
Next, we need to actually write out the expansion. We’re going to make it so that every class becomes a Racket struct behind the scenes to hold the fields:
classy1 := ....classy0.... (begin (struct name-rep (c.fields ...)) (define (name field-arg ... ...) (name-rep c.fields ...)) ....classy2....)
But this is going to complicate a few things, because struct is itself non-hygeinic. It is going to define names like name-rep?, name-rep-field1, and name-rep-field2. But, we don’t want those names to be available to any code except the definition of this class. struct documents that the names it introduces are given the same scope as the name of the struct, i.e. name-rep. Thus, we will manufacture that name so that it is not bound in the same scope as name, and thus will be invisible! We will also need to create bindings to all the names created by struct, plus the syntax we will put in the formals position of the constructor (field-arg)
classy0 := ; #f is a fresh scope that does not overlap with any other #:with name-rep (datum->syntax #f 'name-rep) ; name-rep? refers to a predicate created by struct #:with name-rep? (format-id #f "~a?" #'name-rep) ; We iterate through each field and construct related names #:with ([name-rep-field name-dot-field field-kw (field-arg ...)] ...) (for/list ([f (in-list (syntax->list #'(c.fields ...)))]) (define kw (string->keyword (symbol->string (syntax->datum f)))) (list ; These names are bound in the #f scope, which matches name-rep, so they are invisible (format-id #f "~a-~a" #'name-rep f) ; These names are bound in the #'name scope, so they are visible (format-id #'name "~a.~a" #'name f) kw (list kw f)))
Next, we will define syntax parameters for each of the field accessors of this object. These are syntax parameters because we want them to be mentionable by classy user code but illegal outside of method bodies:
classy2 := (define-syntax-parameter name-dot-field (λ (stx) (raise-syntax-error #f (format "Illegal outside ~a methods" 'name) stx))) ... ....classy3....
This is an example of a macro-defining macro, because our macro classy defines a group of other macros that are related to it. If we were writing a robust library for public consumption, we would make a special kind of transformer (like make-rename-transformer) for these kinds of macros to reduce the amount of code generated.
Now that we have method schemas let’s define the methods. Each method will take an additional argument in the first position beyond those that were specified in the input. We will check that the provided object has the correct representation and error otherwise. We’ll call the argument this-this and later arrange for it to be referenceable via this.
classy3 := (define (c.methods this-this c.methods-args ...) (unless (name-rep? this-this) (error 'c.methods "Expects an ~a object, given ~e" 'name this-this)) ....classy4....) ...
Next, we will provide access to the this object and the struct accessors (posn.x and posn.y) by using syntax-parameterize. In the first case, we rename this to this-this. In the second, we rename name-dot-field (posn.x), a public name, to name-rep-field (posn-rep-x), a private name.
classy4 := (syntax-parameterize ([this (make-rename-transformer #'this-this)] [name-dot-field (make-rename-transformer #'name-rep-field)] ...) ....classy5....)
We can now bind the values of the fields of the this object by using these parameters. In our example, this binds x to the result of (posn.x this), which is renamed into (posn-rep-x this-this).
classy5 := (define c.fields (name-dot-field this)) ... ....classy6....
There’s just one more feature to implement: update. update is a special form inside of method bodies that returns an updated representation of the object where one field is different. It is kind of like a call to the construtor where one field is different. We can make it expand into exactly that by providing a unique update macro for every method body where the input pattern recognizes one field and refers to the other fields by their binding established in classy5.
classy6 := (syntax-parameterize ([update (λ (stx) (syntax-parse stx [(_ field-kw c.fields) #'(name-rep c.fields ...)] ...))]) ....classy7....)
This is an extreme example of a mind-bending macro-generating macro. In classy, every method gets its own definition of the update macro, which is bound to a syntax parameter, taking over its definition. The custom update has a variable number of patterns, based on the number of fields of the class. The right-hand side of the pattern embeds a call to the representation constructor where all but one of the arguments come from the surrounding context and the last argument comes from the update pattern.
The classy macro ends with a whimper as we simply embed the method body:
classy7 := c.methods-body ...
Let’s put it all together and see the entire thing all at once:
(define-syntax-parameter this (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax-parameter update (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax field (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (define-syntax method (λ (stx) (raise-syntax-error #f "Illegal outside classy" stx))) (begin-for-syntax (define-syntax-class classy-clauses #:attributes ([fields 1] [methods 1] [methods-args 2] [methods-body 2]) #:literals (field method) (pattern () #:with (fields ...) #'() #:with (((methods methods-args ...) methods-body ...) ...) #'()) (pattern ((field f:id) . more:classy-clauses) #:with (fields ...) #'(f more.fields ...) #:with (((methods methods-args ...) methods-body ...) ...) #'(((more.methods more.methods-args ...) more.methods-body ...) ...)) (pattern ((method (m:id ma:id ...) mb:expr ...+) . more:classy-clauses) #:with (fields ...) #'(more.fields ...) #:with (((methods methods-args ...) methods-body ...) ...) #'(((m ma ...) mb ...) ((more.methods more.methods-args ...) more.methods-body ...) ...)))) (define-simple-macro (classy name:id . c:classy-clauses) #:with name-rep (datum->syntax #f 'name-rep) #:with name-rep? (format-id #f "~a?" #'name-rep) #:with ([name-rep-field name-dot-field field-kw (field-arg ...)] ...) (for/list ([f (in-list (syntax->list #'(c.fields ...)))]) (define kw (string->keyword (symbol->string (syntax->datum f)))) (list (format-id #f "~a-~a" #'name-rep f) (format-id #'name "~a.~a" #'name f) kw (list kw f))) (begin (struct name-rep (c.fields ...)) (define (name field-arg ... ...) (name-rep c.fields ...)) (define-syntax-parameter name-dot-field (λ (stx) (raise-syntax-error #f (format "Illegal outside ~a methods" 'name) stx))) ... (define (c.methods this-this c.methods-args ...) (unless (name-rep? this-this) (error 'c.methods "Expects an ~a object, given ~e" 'name this-this)) (syntax-parameterize ([this (make-rename-transformer #'this-this)] [name-dot-field (make-rename-transformer #'name-rep-field)] ...) (define c.fields (name-dot-field this)) ... (syntax-parameterize ([update (λ (stx) (syntax-parse stx [(_ field-kw c.fields) #'(name-rep c.fields ...)] ...))]) c.methods-body ...))) ...))
A mere 67 lines!
Finally, let’s see the expansion of a simple use of classy:
(classy posn (field x) (field y) (method (add-xs p2) (update #:x (+ x (posn.x p2)))))
This expands to:
(begin (struct posn-rep (x y)) (define (posn #:x x #:y y) (posn-rep x y)) (define-syntax-parameter posn.x (λ (stx) (raise-syntax-error #f (format "Illegal outside ~a methods" 'posn) stx))) (define-syntax-parameter posn.y (λ (stx) (raise-syntax-error #f (format "Illegal outside ~a methods" 'posn) stx))) (define (add-xs this-this p2) (unless (posn-rep? this-this) (error 'add-xs "Expects an ~a object, given ~e" 'posn this-this)) (syntax-parameterize ([this (make-rename-transformer #'this-this)] [posn.x (make-rename-transformer #'posn-rep-x)] [posn.y (make-rename-transformer #'posn-rep-y)]) (define x (posn.x this)) (define y (posn.y this)) (syntax-parameterize ([update (λ (stx) (syntax-parse stx [(_ #:x x) #'(posn-rep x y)] [(_ #:y y) #'(posn-rep x y)]))]) (update #:x (+ x (posn.x p2)))))))
If we look add the definition of add-xs, this further expands to:
(define (add-xs this-this p2) (unless (posn-rep? this-this) (error 'add-xs "Expects an ~a object, given ~e" 'posn this-this)) (define x (posn-rep-x this-this)) (define y (posn-rep-y this-this)) (posn-rep (+ x (posn.x p2)) y))
This is the kind of idiomatic code that we typically see in environments that do not provide support for class-oriented programming, or do not provide support for language-oriented programming, so that programmers can build their own class systems.
9.7 What we did not cover
Although this lecture used a macro for class-oriented programming as a motivating example, classy is not a great class macro. It is missing things like inheritance, super calls, and many many other useful features of class systems. If you were to look at the real implementation of racket/class, you’d see many of the techniques shown today, but they would be slightly obscured beneath the implementation of scores of other useful parts of a full-fledged class library.