3 Language Extensions via Macros

This morning we introduced the big ideas of the course through a quick series of examples and then brought you up to speed on a mental model of Racket that includes its macro expansion phase. This afternoon, we will slow things down and focus on the details.

3.1 When and Why

_f: addq %r7, %r7     cmpq %r7, $32     jle _f     retq   _g: movq %r7, $8     callq _f     movq %r8, %r7     callq _f     addq %r8, %r7     retq

int f (int x) {  while ( (x += x) <= 32 ) {}  return x; }   int g () {  int t = f(8);  return t + f(t); }

Figure 2: The Procedure Pattern

Language extensions add abstractions to a programming language that it does not already have. For example, in most assembly languages, there is the abstraction of the stack and the program counter, but there is not an abstraction of a procedure. In C, we add the language extension of procedure calls by integrating the many features of pushing arguments on the stack, jumping while pushing a return address, and extending the stack to allocate local variables. Although these features exist in assembly, their use does not constitute an abstraction, because assembly does not allow us to enforce the integrity of the procedure. For example, in C, it is not possible to goto a label in another procedure, while this is permissible inside of procedure-style assembly. Enforcing these abstractions is valuable because it allows us to implement the abstraction in ways that cannot be scalably done at the level of the pattern. For example, in C, we can perform exotic optimizations on our program because we know that the stack will always have the same structure at the start of every label, which is not the case in assembly. A fundamental aspect of language-oriented programming is identifying these intended abstractions and the invariants that enforce their integrity, then exploiting those invariants to produce a better program than you would have done without the abstraction.

button.onclick =  function () {   channel    .send("Where's my money?",     function (ans) {      box.text = ans; }); }

button.onclick =  async function () {   var ans = await channel    .send("Where's my money?");     box.text = ans; }

Figure 3: The Async Callback Pattern

It is typically the case that prior to the creation of a language extension, programmers that wish to use the concept employ a programming pattern, as mentioned above. For example, in JavaScript prior to ES7, it was typical for asynchronous functions to accept an explicit callback argument and extensive libraries and patterns built up to consume and produce these callbacks. In 2016, however, ES7 introduced the async and await keywords that automatically produce these callbacks from callback-less functions. Identifying an appropriate opportunity for language extension typically involves identifying a pattern like this in many programs.

(+ (+ 4 4) (+ 5 5))

(define (double x) (+ x x)) (+ (double 4) (double 5))

Figure 4: Function Abstraction

We could have told the same story about the discovery of particular functions: when the same pattern of computation occurs in a program, then we can abstract it into a function that encapsulates the repetition. Abstractions added via language extensions are distinct from these function abstractions because they cannot be implemented at the function level. Consider the asyncronous callback pattern, await is not a function that is definable inside of JavaScript. It is not a function that is definable inside of Racket either, because it consumes a syntactic block that contains a function call, rather than a value. It is, however, definable as a syntactix extension in Racket.

In this lecture, we will focus on the machinery to build abstractions that cannot be built without language extensions. In future lectures, we will discuss how use these abstractions to enforce and exploit additional invariants about the abstraction’s use. We’ll refer to these basic forms of language extensions as "macros".

3.2 How: Initialization Incantation

Racket programs that define macros should start by require-ing the syntax/parse module for-syntax and the syntax/parse/define module, as follows:

(require (for-syntax syntax/parse)

syntax/parse/define)

If you write your program in

#lang racket/base

then you also need to require racket/base for-syntax, as follows:

(require (for-syntax racket/base))

This means that your program will start as

or

3.3 Basic Macros

A simple re-occuring pattern in programs in the timer pattern. In this pattern, you want to know how long an expression took to evaluate, so you capture the time before, and the time after, then display the difference. For example:

(let* ([before (current-inexact-milliseconds)]

[answer (factorial (fibonacci 10))]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer)

This code sequence is awkward, especially when the expression to be timed is embedded inside of a larger context, such as

(printf "The factorial of the tenth fibonacci is: ~a\n"

(factorial (fibonacci 10)))

because the surrounding context is not already suited to define the local variables to capture the time and the answer.

If you attempt to abstract this pattern into a function, as

(define (try-to-time-it computation)

(let* ([before (current-inexact-milliseconds)]

[answer computation]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer))

(printf "The factorial of the tenth fibonacci is: ~a\n"

(try-to-time-it (factorial (fibonacci 10))))

then you will find that your computer suddenly got a lot faster. This is because try-to-time-it is not executed until after the computation is finished evaluating. This means that to make an abstraction out of this timer, you must employ the thunk pattern:

(define (thunk-time-it do-computation)

(let* ([before (current-inexact-milliseconds)]

[answer (do-computation)]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer))

(printf "The factorial of the tenth fibonacci is: ~a\n"

(thunk-time-it (λ () (factorial (fibonacci 10)))))

This implementation of thunk-time-it fails to be a satisfying abstraction, because it exposes to the user that it is a function and that the user cannot simply "time the evaluation of expression", but must also explicitly cooperate with thunk-time-it and delay the evaluation of the computation.

A basic form of syntactic extension is with the define-simple-macro form. define-simple-macro allows a simple single case of pattern-based templating of language extension.

The syntax of define-simple-macro is (define-simple-macro (macro-name input_pattern_) output_template_). Whenever the Racket expander sees a code fragment that looks like (macro-name input_pattern_), it will replace it with output_template_, substituting variables that occur in the output with what they match with in the input.

For example,

(define-simple-macro (time-it computation)

(thunk-time-it (λ () computation)))

(printf "The factorial of the tenth fibonacci is: ~a\n"

(time-it (factorial (fibonacci 10))))

will expand to

(printf "The factorial of the tenth fibonacci is: ~a\n"

(thunk-time-it (λ () (factorial (fibonacci 10)))))

because (time-it (factorial (fibonacci 10))) matches the pattern (time-it computation) with the variable computation matching (factorial (fibonacci 10)).

With this tool, the author of the time-it macro needs to know about the need to delay, but the user of time-it does not.

You may wonder if an acceptable implementation of time-it does without the thunk-time-it helper function, as follows

(define-simple-macro (bad-time-it computation)

(let* ([before (current-inexact-milliseconds)]

[answer computation]

[after (current-inexact-milliseconds)])

(printf "It took ~a ms to compute.\n" (- after before))

answer))

This is not acceptable, because each application of bad-time-it will duplicate the code segment that implements the timing logic, ballooning the size of the program, whereas the good implementation of time-it does not.

3.4 Macro Style

Another commonly occuring pattern is the iteration-producing-a-list pattern. In this pattern, you iterate through a sequence and perform the same computation on every element, collecting the values into a list. For example:

(define (burn-them-all l)

(cond [(empty? l)

empty]

[else

(cons (string-append "Burnt " (first l))

(burn-them-all (rest l)))]))

(burn-them-all (list "Rickard" "Brandon"))

This pattern is so common that many languages come with a standard library that provides function abstraction of it:

(map (λ (s) (string-append "Burnt" s)) (list "Rickard" "Brandon"))

Although as functional programmers we are extremely used to this pattern, it is important to understand that it is a pattern that cries out for a syntactic abstraction. define-simple-macro is adequate for this task.

(define-simple-macro (simple-for/list0 ([elem-name seq]) computation)

(map (λ (elem-name) computation) seq))

(simple-for/list0 ([s (list "Rickard" "Brandon")])

(string-append "Burnt" s))

Racket, of course, comes with an awesome macro for this pattern, for/list.

This macro has an interesting aspect that our earlier example did not have. It introduces parentheses around the elem-name and seq to suggest a connection between these pieces of the syntax and draw a parallel with let. We could have defined the macro as

(define-simple-macro (simple-for/list-1 elem-name seq computation)

(map (λ (elem-name) computation) seq))

(simple-for/list-1 s (list "Rickard" "Brandon")

(string-append "Burnt" s))

But this would not be acceptable, because we are not following the Racket syntactic style of associating binders with their bindings inside of parentheses (specifically, brackets). Many observers of languages like Racket describe them as "lacking syntax" because everything is indicated with parentheses. This is not true. Rules like this are the syntax of Racket. If Racket lacks something, it is that it is uncommon to introduce notational keywords. It is possible, of course. For example, we could have defined our macro as

(define-simple-macro (simple-for/list-verbose #:with elem-name #:from seq #:in computation)

(map (λ (elem-name) computation) seq))

(simple-for/list-verbose #:with s #:from (list "Rickard" "Brandon") #:in

(string-append "Burnt" s))

This sort of notational logorrhea is possible, but uncommon in Racket syntactic extensions.

3.5 Repetitious Macros

Once we have created simple-for/list0 it is natural to play with the abstraction and discover ways to make the abstraction more than just a simple wrapper around map. A macro often starts as a simple short-hand for some programming pattern, but as we understand it as an abstraction on its own, we discover uses that are not obviously applications of the pattern at the programming level. For example, suppose we want to iterate over two sequences at the same time:

(simple-for/list1 ([s (list "Rickard" "Brandon")]

[i (list 1 2)])

(string-append (number->string i) ". Burnt" s))

One option to implement this extension is to write another macro that allows two sequences at the same time. Another option is to have a single macro that allows an arbitrary number of sequences. Clearly this second option is the best.

The Racket macro systems support a special syntax in patterns and templates for indicating that a pattern may occur any number of times: ...

We can use this to define our new macro:

(define-simple-macro (simple-for/list1 ([elem-name seq] ...) computation)

(map (λ (elem-name ...) computation) seq ...))

The ... in the input signifies that [elem-name seq] can occur any number of times. The ... in the output signifies that elem-name should be repeated once for each time the pattern repeated in the input. This means that the use expands to

(map (λ (s i) (string-append (number->string i) ". Burnt" s))

(list "Rickard" "Brandon")

(list 1 2))

Use of ... typically requires us to make a new function abstraction, because our original version may not deal with arbitrary input. In this case, map does support iterating through multiple lists, but let’s suppose that it did not. We could have written our macro as

(define-simple-macro (simple-for/list1* ([elem-name seq] ...) computation)

(map (λ (elems)

(define-values (elem-name ...) (split elems))

computation)

(transpose (list seq ...))))

where tranpose is a function that takes a list of N lists each with M elements and produces a list of M lists each with N elements and split is a function that takes a list of N elements and returns them as N values.

Instead, if map did not support multiple concurrent lists, our macro so expand to a more elaborate program. For example,

(define-simple-macro (simple-for/list2 ([elem-name seq] ...) computation)

(letrec ([iterate

(λ (elem-name ...)

(cond

[(or (empty? elem-name) ...)

empty]

[else

(cons

(let ([elem-name (first elem-name)] ...)

computation)

(iterate (rest elem-name) ...))]))])

(iterate seq ...)))

This more elaborate use of ... arranges for each list to be bound to name elem-name inside the iterate function, then each first element to be bound to the same name before evaluating the computation.

Our use would expand to

(letrec ([iterate

(λ (s i)

(cond

[(or (empty? s) (empty? i))

empty]

[else

(cons

(let ([s (first s)] [i (first i)])

(string-append (number->string i) ". Burnt" s))

(iterate (rest s) (rest i)))]))])

(iterate (list "Rickard" "Brandon")

(list 1 2)))

This version actually enables a slightly different semantics from map as well. If map is called with multiple lists, then each must have the same length. If our macro is iterating through multiple lists, then the iteration will occur as many times as the shorter list. In otherwords, this use as the same output as the first:

(simple-for/list2 ([s (list "Rickard" "Brandon")]

[i (list 1 2 3)])

(string-append (number->string i) ". Burnt" s))

3.6 Basic Macros, Unveiled!

Up to this point, all of the macros we’ve written used the define-simple-macro form. This form has a suspicious adjective, "simple", in its name. We are about to graduate from these simple macros to more complex ones, so we need to translate away from this short hand and use the full version of defining a macro.

define-simple-macro is actually a macro itself. (Although, it isn’t written with define-simple-macro, of course!) When you write

(define-simple-macro (macro-name input-pattern)

output-template)

It is expanded into

(define-syntax macro-name

(λ (the-syntax-of-the-application)

(syntax-parse the-syntax-of-the-application

[(macro-name input-pattern)

#'output-template])))

The first line defines macro-name as a syntactic extension. The second line binds it to a function that takes one argument, which is the concrete syntax object for the call that the Racket expander discovered. The third begins to parse that application. The fourth matches the application against the input pattern. The fifth returns the output template and performs the pattern substitution described previously. The fifth line could have been written as (syntax output-template), but it is against Racket style to not use the #' short-hand.

As we progress beyond simple macros, you should start using this pattern as your incantation to define a macro, with a few tiny tweaks. First, it is simpler to use the function definition form rather than explicitly using λ. Second, it is typical to not mention the name of the macro in the input pattern. So if we were to define our most recent version of the iteration macro in this way, we would write:

(define-syntax (simple-for/list3 stx)

(syntax-parse stx

; 1. We will have more input pattern cases.

[(_ ([elem-name seq] ...) computation)

; 2. We will do more than just return the output template.

#'(letrec ([iterate

(λ (elem-name ...)

(cond

[(or (empty? elem-name) ...)

empty]

[else

(cons

(let ([elem-name (first elem-name)] ...)

computation)

(iterate (rest elem-name) ...))]))])

(iterate seq ...))]))

Although, we’ll actually do them in the opposite order.

3.7 More Than Just Templates

Our iteration macro is needlessly complicated with its re-use of the element name to bind the lists themselves. It only does this because we need to have an equal number of arguments to the iteration function as there are lists and we know that the number of element names is the same as the number of lists.

By wrapping the output pattern in a new form, with-syntax, we can introduce new names into the expansion. We can generate these temporary names with the function generate-temporaries. This function takes a syntax list and returns a number of new names equal to the length of the list. The resulting macro looks like this:

(define-syntax (simple-for/list3 stx)

(syntax-parse stx

[(_ ([elem-name seq] ...) computation)

(with-syntax ([(list-name ...) (generate-temporaries #'(elem-name ...))])

#'(letrec ([iterate

(λ (list-name ...)

(cond

[(or (empty? list-name) ...)

empty]

[else

(cons

(let ([elem-name (first list-name)] ...)

computation)

(iterate (rest list-name) ...))]))])

(iterate seq ...)))]))

This small change requires a large discussion of some subtle points.

First, we are now fully utilizing the ability of Racket to perform arbitrary computations during macro expansion, because we are calling the function generate-temporaries during the expansion of this macro and using the result. In future examples, we are going to be doing a lot more of this.

Second, we are constructing syntax objects with syntax/#' that do not get returned from the macro, in the argument position of generate-temporaries. Although this is a trivial use, it will turn out to be extremely common to construct syntax objects, store them inside of data structures or return them from helper functions, and then finally include them in the output of a macro. Syntax objects are valid objects in Racket programs just like numbers, lists, and strings.

Third, we are using with-syntax to introduce new names into the set of pattern variables that syntax/#' uses when it is transcribing the output pattern. This form can even use ... to bind sequences of pattern variables.

Finally, we should ask if it is possible to use these new names, list-name, in the computation? The answer is no, and it is not because they are actually obscured as identifiers like temporary_list-name1924_abcd. Instead, it is because Racket systematically tracks the definition of variables and ensures that variables bound in different scopes do not shadow or capture variables defined in other scopes.

We will return to each one of these points in the future.

3.8 A Short Hand for New Names and Compile-Time Computation

Occasionally, we will find it convenient to introduce a new pattern variable for a single small piece of syntax. For example, suppose we wanted our iteration macro to print out how many lists we being iterated through. We could write the following:

(define-syntax (simple-for/list4 stx)

(syntax-parse stx

[(_ ([elem-name seq] ...) computation)

(with-syntax ([(list-name ...) (generate-temporaries #'(elem-name ...))]

[how-many (length (syntax->list #'(elem-name ...)))])

#'(letrec ([iterate

(λ (list-name ...)

(cond

[(or (empty? list-name) ...)

empty]

[else

(cons

(let ([elem-name (first list-name)] ...)

computation)

(iterate (rest list-name) ...))]))])

(printf "There are ~a lists.\n" how-many)

(iterate seq ...)))]))

We define a new pattern variable, how-many, and bind it to the results of length, then reference it in the body of the letrec. On our example, this will expand to

(letrec ([iterate (λ (s-list i-list) ....)])

(printf "There are ~a lists.\n" 2)

(iterate ....))

That is, the number 2 is embedded in the program, not the syntax for the length computation that produces 2. This sort of compile-time computation is very powerful and we will exploit it more in the future.

This macro, however, is non-idiomatic because it is tedious to have to name every new piece of information that we want to include in the output. Naturally, Racket supports a way to inline the compile-time computation into the syntax/#' form. We do this by switching to quasisyntax/#`, which are similar to quasiquote/`, except that the produce syntax. Like quasiquote, quasisyntax supports escaping back to Racket, except that rather than using unquote/,, we use unsyntax/#,. We can rewrite the macro as

(define-syntax (simple-for/list5 stx)

(syntax-parse stx

[(_ ([elem-name seq] ...) computation)

(with-syntax ([(list-name ...) (generate-temporaries #'(elem-name ...))])

#`(letrec ([iterate

(λ (list-name ...)

(cond

[(or (empty? list-name) ...)

empty]

[else

(cons

(let ([elem-name (first list-name)] ...)

computation)

(iterate (rest list-name) ...))]))])

(printf "There are ~a lists.\n" #,(length (syntax->list #'(elem-name ...))))

(iterate seq ...)))]))

At this stage, this new quasisyntax quotation is contrived, but it will turn out to be very useful when we store syntax objects in data structures and when we define helper functions at the syntax level to produce syntax fragments.

3.9 Macros with Cases

Our iteration syntax extension’s expansion uses a common programming pattern: doing one thing with an null value, another thing with a cons cell and looking at the pieces in the body, and maybe a different thing for an atomic value like a number. A use of this pattern might be:

(define (sum-tree tree-var)

(cond

[(null? tree-var)

0]

[(cons? tree-var)

(let ([elem (car tree-var)]

[more (cdr tree-var)])

(+ (sum-tree elem) (sum-tree more)))]

[(number? tree-var)

tree-var]

[else

(error "Tree contains non-numeric value: ~e" tree-var)]))

This pattern is tedious to get right. We often forget to include the error case and do not thoroughly name all of the sub-pieces of the cons, so we may find ourselves writing (car x) a lot.

We can abstract this into a simple macro:

(define-simple-macro

(tree-match tree-var

[(#:null) null-case]

[(#:cons car-name cdr-name) cons-case]

[(#:number) num-case])

(cond

[(null? tree-var)

null-case]

[(cons? tree-var)

(let ([car-name (car tree-var)]

[cdr-name (cdr tree-var)])

cons-case)]

[(number? tree-var)

num-case]

[else

(error "Tree contains non-numeric value: ~e" tree-var)]))

(define (sum-tree tree-var)

(tree-match tree-var

[(#:null) 0]

[(#:cons elem more)

(+ (sum-tree elem) (sum-tree more))]

[(#:number) tree-var]))

However, this macro is extremely ugly, because it is too precisely tied to this exact task. It would be better to make a more general macro that accepts a sequence of clauses and does not force every use to have each. We could use it like

; Sum trees where numbers can occur anywhere

(define (sum-tree tree-var)

(simple-match tree-var

[(#:null) 0]

[(#:cons left right)

(+ (sum-tree left) (sum-tree right))]

[(#:number) tree-var]))

; Sum lists where numbers only occur to the left of a cons pair

(define (sum-list tree-var)

(simple-match tree-var

[(#:null) 0]

[(#:cons elem more)

(+ elem (sum-list more))]))

; Sum trees where leaves are always numbers

(define (sum-leaves tree-var)

(simple-match tree-var

[(#:cons left right)

(+ (sum-leaves left) (sum-leaves right))]

[(#:number) tree-var]))

Racket, of course, comes with an awesome macro for this pattern, match.

The standard way to implement this is with a macro that has one case for each different kind of clause and expands to itself recursively.

(define-syntax (simple-match stx)

(syntax-parse stx

[(_ var) #'(error "Input was not matched ~e" var)]

[(_ var [(#:null) null-case] more ...)

#'(if (null? var) null-case

(simple-match var more ...))]

[(_ var [(#:number) num-case] more ...)

#'(if (number? var) num-case

(simple-match var more ...))]

[(_ var [(#:cons car-name cdr-name) cons-case] more ...)

#'(if (cons? var) (let ([car-name (car var)]

[cdr-name (cdr var)])

cons-case)

(simple-match var more ...))]))

Our sum-tree example will expand in the following way:

; Input

(define (sum-tree tree-var)

(simple-match tree-var

[(#:null) 0]

[(#:cons left right)

(+ (sum-tree left) (sum-tree right))]

[(#:number) tree-var]))

; One Expansion

(define (sum-tree tree-var)

(if (null? tree-var) 0

(simple-match tree-var

[(#:cons left right)

(+ (sum-tree left) (sum-tree right))]

[(#:number) tree-var])))

; Two Expansions

(define (sum-tree tree-var)

(if (null? tree-var) 0

(if (cons? tree-var)

(let ([left (car tree-var)]

[right (cdr tree-var)])

(+ (sum-tree left) (sum-tree right)))

(simple-match tree-var

[(#:number) tree-var]))))

; Three Expansions

(define (sum-tree tree-var)

(if (null? tree-var) 0

(if (cons? tree-var)

(let ([left (car tree-var)]

[right (cdr tree-var)])

(+ (sum-tree left) (sum-tree right)))

(if (number? tree-var) tree-var

(simple-match tree-var)))))

; Four Expansions

(define (sum-tree tree-var)

(if (null? tree-var) 0

(if (cons? tree-var)

(let ([left (car tree-var)]

[right (cdr tree-var)])

(+ (sum-tree left) (sum-tree right)))

(if (number? tree-var) tree-var

(error "Input was not matched ~e" tree-var)))))

Macros like this are extremely powerful, because we can consume complex, non-homogenous, non-linear recursive input, and we can produce arbitrarily shaped output.

This lecture has simply introduced the mechanisms that we will employ in future days wherein we’ll explore the creative combination of these tools in much greater detail.

3.10 What we did not cover

The syntax-parse macro pattern language is extremely powerful. It supports optional components of syntax (~optional), sequences that are not nested inside of lists (~seq), ensuring that components match multiple patterns (~and), as well as exposing its back-tracking search algorithm to the user to control the exact behavior (~!). It is beyond the scope of this introduction to go into those details; just remember that the ceiling is very high on macros.