Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 38 ยท Projects and Practice

Project: A Pattern Matcher

Learn Racket's match form, then build your own pattern matcher with variables, wildcards, list patterns and ellipsis rules, and use it to write a symbolic differentiator.

Pattern matching is one of the most useful ideas in functional programming: instead of testing the shape of data with chains of if, car and cdr, you write the shape you expect and name the pieces. Racket's match form does this, and it is built with macros (syntax-rules macros and later lessons). In this project you first use match, then build a small matcher yourself, and finish with a classic application: symbolic differentiation.

Racket is read-only here. The runnable code is a JavaScript stand-in matcher that works on nested arrays. It is a simplified model of match, not the real implementation.

Racket's match

RACKET
#lang racket

(define (describe v)
  (match v
    [0                  "zero"]
    [(? number? n)      (format "the number ~a" n)]
    ["hi"               "a greeting"]
    [(list 'point x y)  (format "point at ~a,~a" x y)]
    [(list a b ...)     (format "list starting with ~a, ~a more" a (length b))]
    [(struct person (name age)) (format "~a is ~a" name age)]
    [_                  "something else"]))

(describe '(point 3 4))      ; => "point at 3,4"
(describe '(1 2 3 4))        ; => "list starting with 1, 3 more"

Patterns include literals (0, "hi"), variables (x, which bind), _ (a wildcard that matches anything), (? pred var) (a predicate test), (list ...) patterns, ellipses (b ... collects the rest into a list), and struct patterns. Clauses are tried top to bottom and the first match wins, so put specific patterns before general ones. If no clause matches, match raises an error, which is a good thing: your function does not silently ignore a shape you forgot.

Design of our matcher

We represent patterns as data:

  • A string starting with ? (like "?x") is a variable that binds the value.
  • "_" is a wildcard.
  • An array is a list pattern matching an array of the same length, element by element.
  • A final element like "?rest..." matches the remaining elements into an array.
  • Anything else (numbers, plain strings) is a literal that must be equal.

match(pattern, value, bindings) returns the bindings object on success or null on failure. A repeated variable must match equal values both times, which also gives you simple equality tests.

JS Stand-in: a pattern matcher

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice ["pair", 7, 8]: the repeated-variable pattern fails because 7 is not 8, and matching continues to the next clause. That backtracking-to-the-next-clause is exactly how match behaves.

Application: symbolic differentiation

A calculus program is a perfect fit. Expressions are nested lists ["+", a, b], ["*", a, b], ["^", base, n], numbers and variable names. The derivative rules read like the math textbook:

RACKET
(define (deriv e x)
  (match e
    [(? number?) 0]
    [(? symbol? v) (if (eq? v x) 1 0)]
    [`(+ ,a ,b) `(+ ,(deriv a x) ,(deriv b x))]
    [`(* ,a ,b) `(+ (* ,(deriv a x) ,b) (* ,a ,(deriv b x)))]
    [`(^ ,u ,n) `(* (* ,n (^ ,u ,(- n 1))) ,(deriv u x))]))

With a simplifier from the quote lesson the output becomes readable. Here is the JavaScript version using our matcher:

JS Stand-in: differentiation with pattern matching

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The structure of deriv mirrors the math: one case per rule. Adding sin, cos or exp means adding a case, not restructuring the function. That openness is why pattern matching is so loved for compilers and interpreters (the interpreter project could use it for its special forms).

Extensions

  • Add a ?x:number style predicate pattern, like (? number? n).
  • Support nested ellipses, which gives match its full power over lists of lists.
  • Add a guard (#:when) so a clause can include an extra test.
  • Return all matches for a pattern in a tree (searching, not just matching at the root).
  • Implement unification, where both sides may contain variables, the engine behind logic programming.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Racket's match, what does _ do?

    The wildcard accepts any value and does not create a binding.
  2. 2. What happens when no match clause fits the value?

    match raises an error when nothing matches, so forgotten shapes show up instead of being ignored.
  3. 3. What does a repeated variable such as (pair ?a ?a) require?

    The second occurrence must be equal to the value already bound by the first.
  4. 4. Why are pattern-matching programs easy to extend?

    New data shapes or rules are added as clauses beside the existing ones.

Summary

  • match destructures data by shape: literals, variables, wildcards, predicates, lists, ellipses and structs.
  • Clauses are tried in order; the first match wins; no match is an error.
  • A matcher is a small recursive function from pattern, value and bindings to new bindings or failure.
  • Symbolic differentiation shows how rule-per-clause code mirrors the math.
  • Pattern matching, with macros and recursion, is a core tool for compilers and interpreters.

Next: Practice: Recursion Problems