4 Exhaustive Enumerations

Inspiration for this exercise comes from an example from Robby Findler’s talk Racket: a programming-language programming language.

A concept available in many programming languages is the notion of enumerations, a value with a known set of discrete possibilities. An enumeration might be used to represent the days of the week, a set of well-known colors, different blending modes, or all sorts of other things.

In Racket, ordinary Racket symbols are often used for this purpose. For example, one might represent a day of the week using the symbols 'sunday, 'monday, 'tuesday, etc. It’s possible to use Racket’s case form to branch on the value of a symbol, so we could use it to write a function that checks if a day of the week is a weekend or not:

(define (weekend? day)

(case day

[(saturday sunday) #t]

[(monday tuesday wednesday thursday friday) #f]))

For the purposes of this exercise, we’ll use a smaller, sillier example: an enumeration of animals, 'cat, 'dog, and 'cow. We could write a function that accepts an animal and produces a string corresponding to the sound it makes:

(define (animal-sound x)   (case x     [(cat) "meow"]     [(dog) "woof"]     [(cow) "moo"]))

> (animal-sound 'cat)

"meow"

> (animal-sound 'dog)

"woof"

However, what if we subsequently wanted to make our program support a new kind of animal, such as 'fish? Well, we could just add a new case to our animal-sound function, like this:

(define (animal-sound x)

(case x

[(cat) "meow"]

[(dog) "woof"]

[(cow) "moo"]

[(fish) "glub"]))

But there’s a problem. What if you use animals all over your program, and you forget to add the new 'fish case in just one of them? Oops. That’s probably a bug. Wouldn’t it be great if case knew which possible values can be in our enumeration, and it would warn us if we forgot to handle one of them?

To make this possible, we can write two macros, define-enum and enum-case, which will work together to ensure at compile-time all values are handled:

> (define-enum animal     [cat dog cow fish])

> (define (animal-sound x)     (enum-case animal x       [(cat) "meow"]       [(dog) "woof"]       [(cow) "moo"]))

enum-case: missing case for 'fish

> (define (animal-sound x)     (enum-case animal x       [(cat) "meow"]       [(dog) "woof"]       [(cow) "moo"]       [(fish) "glub"]))

> (animal-sound 'fish)

"glub"

Ensuring that call cases are handled is known as exhaustiveness checking.

4.1 Implementation strategy

How is it possible to implement define-enum and enum-case, given that they need to somehow communicate with each other at compile-time? And what does define-enum even define?

The key to solving is problem is a special function, syntax-local-value, which provides a mechanism for compile-time cooperation between macros. Specifically, it makes it possible for a macro to get at the value of a definition defined with define-syntax. Normally, we use define-syntax to define a macro by creating a syntax binding with a procedure of one argument as its value, but this isn’t actually necessary. We can use define-syntax to define anything at all:

> (define-syntax x 3)

What does this actually do? Well, on its own, not very much. We can’t use x as an expression, since it raises a compile-time error:

> x

eval:2:0: x: illegal use of syntax

in: x

However, we can use syntax-local-value to retrieve the value of x inside a macro.

> (define-syntax (quote-x stx)     #`(quote #,(syntax-local-value #'x)))

> (quote-x)

3

Of course, this alone isn’t very useful. It becomes interesting, however, when we use syntax-local-value on an identifier provided to the macro as a subform:

> (define-simple-macro (quote-local-value i:id)     #:with val (syntax-local-value #'i)     (quote val))

> (quote-local-value x)

3

This trick can be used to allow define-enum and enum-case to indirectly communicate. define-enum can expand into a use of define-syntax that binds the name of the enumeration to a set of valid symbols at compile-time, and enum-case can use syntax-local-value on the provided enumeration name to inspect which symbols should be covered.

4.2 Specification

The expected behavior of define-enum and enum-case is defined in terms of how they should work together. A definition of the shape (define-enum enum-id [case-id ...]) does not do anything at all on its own, but it should define enum-id in such a way that it can be used with enum-case.

The enum-case form should function equivalently to case, except that it should be provided the name of an enumeration, and it should perform exhaustiveness checking at compile-time based on the possible cases of the enumeration.

Here are two sample enumerations defined with define-enum:

(define-enum day-of-week

[sunday monday tuesday wednesday thursday friday saturday])

(define-enum animal

[cat dog cow fish])

Assuming the above enumeration definitions, both of the following definitions should be valid:

(define (weekend? day)

(enum-case day-of-week day

[(saturday sunday) #t]

[(monday tuesday wednesday thursday friday saturday) #f]))

(define (animal-sound x)

(enum-case animal x

[(cat) "meow"]

[(dog) "woof"]

[(cow) "moo"]

[(fish) "glub"]))

The above definitions should produce the following results when called:

> (weekend? 'wednesday)

#f

> (weekend? 'sunday)

#t

> (animal-sound 'dog)

"woof"

Both of the following definitions should be invalid, and they should fail to compile with error messages similar to the following:

> (define (weekend? day)     (enum-case day-of-week day       [(saturday sunday) #t]       [(monday friday) #f]))

enum-case: missing cases for 'tuesday, 'wednesday, and 'thursday

> (define (animal-sound x)    (enum-case animal x      [(cat kitten) "meow"]      [(dog puppy) "woof"]      [(cow) "moo"]      [(fish) "glub"]))

enum-case: 'kitten and 'puppy are not valid cases for animal

4.3 Grammar

syntax (define-enum enum-id   [case-id ...])

syntax (enum-case enum-id val-expr   [(case-id ...+) body-expr ...+] ...)