4 Compound Shapes

This section introduces compound shapes, including list shapes and ellipsis shapes. It discusses several implementation strategies for macros consuming ellipsis shapes.

4.1 List Shapes

The main kind of compound shape is the list shape, describing list terms of fixed or varying length. Actually, we have already been using list shapes to describe a macro’s arguments: a macro transformer function in fact receives exactly one argument, corresponding to the whole macro-use term. Typically, that is a list term with the macro identifier first and the arguments making up the rest of the list.

We can add additional levels of grouping to the arguments. For example, here’s a variant of my-and-let that groups the identifier with the expression that provides its value:

; (my-and-let2 [x:Id Expr] Expr{x}) : Expr

(define-syntax my-and-let2

(syntax-parser

[(_ [x:id e1:expr] e2:expr)

#'(let ([x e1])

(if x e2 #f))]))

By itself, though, this change isn’t very interesting. The real utility of list shapes (and patterns, and templates) is in their interaction with enumeration shapes and ellipses. We’ll discuss ellipses now as a special case and discuss enumeration shapes later.

4.2 Ellipses with Simple Shapes

Ellipses mean zero or more repetitions of the preceding shape, pattern, or template. They are like the star (*) operator in regular expressions. For example, here is the shape of Racket’s and macro:

;; (and Expr ...) : Expr

4.2.1 Recursive Macros

(This isn’t quite like Racket’s and, which returns the value of the last expression if all previous expressions were true, and it evaluates the last expression in tail position. But it’s close enough to illustrate ellipses and recursive macros.)

⇒ (if (odd? 1) (my-and (even? 2) (odd? 3)) #f)

Where once there were three, now there are only two expressions in the remaining call to my-and. Subsequent steps rewrite that to one, and then none, and then my-and’s base case matches and it disappears entirely:

⇒ (if (odd? 1) (if (even? 2) (my-and (odd? 3)) #f) #f)

⇒ (if (odd? 1) (if (even? 2) (if (odd? 3) (my-and) #f) #f) #f)

⇒ (if (odd? 1) (if (even? 2) (if (odd? 3) #t #f) #f) #f)

4.2.2 Recursive Run-time Helper Function

Another implementation strategy is to expand into another variable-arity form or function. For example, here is another definition of my-and that relies on Racket’s andmap function, “thunking” to delay evaluation, and the variable-arity list function:

; (my-and Expr ...) : Expr

(define-syntax my-and

(syntax-parser

[(_ e:expr ...)

#'(andmap (lambda (thunk) (thunk))

(list (lambda () e) ...))]))

For a frequently-used, simple macro like and, this might not be a good implementation because of run-time overhead, but for other macros this kind of implementation might be reasonable.

Lesson: Many macros can be decomposed into two parts: a compile-time part that adds lambda wrappers to handle scoping and delayed evaluation, and a run-time part that implements the computation and behavior of the macro.

4.2.3 Recursive Compile-time Helper Function

The final strategy is to use a compile-time helper function, which handles the recursion either directly or indirectly. Here is another implementation of my-and, where the macro itself is not recursive but the transformer uses a recursive compile-time helper function:

(begin-for-syntax

; my-and-helper : (Listof Syntax[Expr]) -> Syntax[Expr]

(define (my-and-helper exprs)

(if (pair? exprs)

#`(if #,(car exprs)

#,(my-and-helper (cdr exprs))

#f)

#'#t)))

; (my-and Expr ...) : Expr

(define-syntax my-and

(syntax-parser

[(_ e:expr ...)

(my-and-helper (syntax->list #'(e ...)))]))

The compile-time my-and-helper function takes a list of syntax objects representing expressions and combines them into a single syntax object representing an expression. Whenever possible, annotate the Syntax type with the shape of the term that the syntax object represents: for example, Syntax[Expr], Syntax[(Expr ...)], etc. The function uses quasisyntax (which has the reader abbreviation #`) to create syntax from a template that allows unsyntax escapes (#,) to compute sub-terms. The macro calls the helper with a list of syntax objects. First it uses ellipses to form the syntax list containing all of the argument expressions: #'(e ...). This value has the type Syntax[(Expr ...)]. Then it calls syntax->list, which unwraps the syntax list into a list of syntax — in this case, specifically, a (Listof Syntax[Expr]).

Because it is defined in the transformer environment (or “at phase 1”), you cannot directly call my-and-helper at the REPL to explore its behavior. But you can call it using phase1-eval special form. Keep in mind that the whole argument to phase1-eval is a compile-time expression, so you cannot refer to any run-time variables. Also, phase1-eval must be told how to convert the phase-1 (compile-time) answer into an expression to produce a phase-0 (run-time) value. When the result type is syntax, use quote-syntax if you want to preserve the syntax-nature of the result; otherwise, use quote. For example:

> (phase1-eval (my-and-helper (list #'(odd? 1) #'(even? 2)))                #:quote quote-syntax)

#<syntax:eval:11:0 (if (odd? 1) (if (even? 2) #t #f) #f)>

> (phase1-eval (my-and-helper (list #'(odd? 1) #'(even? 2)))                #:quote quote)

'(if (odd? 1) (if (even? 2) #t #f) #f)

4.3 Ellipses with Compound Shapes

Ellipses can also be used with compound shapes. For example, here is the shape of a simplified version of cond (it doesn’t support => and else clauses):

;; (my-cond [Expr Expr] ...) : Expr

Here’s a recursive implementation:

; (my-cond [Expr Expr] ...) : Expr

(define-syntax my-cond

(syntax-parser

[(_)

#'(void)]

[(_ [condition1:expr result1:expr] more ...)

#'(if condition1

result1

(my-cond more ...))]))

Here is an implementation using a recursive helper macro — Racket’s variadic or macro. It also relies on fact that and and or treat any value other than #f as true, and return that specific true value as their result when appropriate.

; (my-cond [Expr Expr] ...) : Expr

(define-syntax my-cond

(syntax-parser

[(_ [condition:expr result:expr] ...)

#'((or (and condition (lambda () result))

...

void))]))

Exercise 7: Implement my-cond using a compile-time helper function that takes a list of condition expressions and a list of result expressions:

;; my-cond-helper : (Listof Syntax[Expr]) (Listof Syntax[Expr]) -> Syntax[Expr]

;; PRE: the two lists of expressions have the same length

Hint: Racket’s foldr function is variadic.

Exercise 8: Generalize my-and-let so that it takes a list of identifier-and-expression clauses. That is, it should have the following shape:

;; (my-and-let ([Id Expr] ...) Expr) : Expr

The scope of each identifier includes all subsequent clauses and the final expression. Implement the macro either as a recursive macro or by using a compile-time helper function.

Exercise 9: Design a macro my-evcase1 with the following shape:

;; (my-evcase1 Expr [Expr Expr] ...) : Expr

The macro evaluates its first argument to get the value to match. Then it tries each clause until one is selected. A clause is selected if its first expression produces a value equal to the value to match; that clause’s second expression is the result of the macro. If no clause matches, the result is (void).

(my-evcase1 (begin (printf "got a coin!\n") (* 5 5))

[5 "nickel"] [10 "dime"] [25 "quarter"] [(/ 0) "infinite money!"])

; expect print once, result = "quarter"