1.15.1 Match Tutorial

In this course, we define all languages using s-expressions, and encode them using Racket lists and symbols. To pattern match on language forms, we use Racket’s match. We’ll primarily use quasiquote, unquote, ..., _ patterns, and the #:when clause to disambiguate.

Using lists and match has some advantages over creating new data types for each language. We can write program abstract syntax trees (ASTs) directly using quasiquote, without worrying about the constructors for each language’s data type. The syntax is also more flexible, since we do not have fixed constructors. We can easily print the output of compilers, and transparently use functions over lists as functions on programs.

It has a few disadvantages though. The primary disadvantage is that match cannot check that we’ve covered all cases of a non-terminal. This means we must be extra careful to follow the design recipe and disambiguate every match case, or we’ll get annoying run-time errors or mysterious failures for ambiguous cases in the language.

As a simple example of using match, the function below counts the nodes in a tree of integers. This uses all of the features you are expected to know when writing compilers over s-expressions.

See Pattern Matching for a more thorough tutorial on match.