Leandro Facchinetti

Playing the Game with PLT Redex

A language defines patterns for terms and gives them names. In programming languages, a language determines which terms are programs and which are not. A language might also include extra machinery, for example, binding and type environments, stores, machine states, and so forth. This extra machinery is invisible to programmers, but is used by an interpreter or a type checker, for example. In general, if terms are data, then languages are the definitions of data structures. They provide names for the patterns we explored in the previous section.

A language for Peg Solitaire must specify the patterns for terms that represent pegs, boards, and so forth. In the previous section, we defined a placeholder language called peg-solitaire, using the define-language form. The specification was empty, because we just wanted enough to allow us to explore pattern matching, so we revisit that language definition now to add names for patterns:


#lang racket
(require redex "terms.rkt")

(define-language peg-solitaire
  [board    ::= (row ...)]
  [row      ::= [position ...]]
  [position ::= peg space padding]
  [peg      ::= ]
  [space    ::= ]
  [padding  ::= ·])

Each line [<name> ::= <pattern> ...] assigns a <name> to a <pattern>, and occurrences of other <name>s in <pattern> are interpreted accordingly, for example, the name row appears in the pattern for board. The following is each line of the definition above in more detail:

We can use the pattern names when matching terms, for example:

(test-equal (redex-match? peg-solitaire peg
                          (term         ))
(test-equal (redex-match? peg-solitaire position
                          (term         ))
(test-equal (redex-match? peg-solitaire (peg  )
                          (term         (    )))
(test-equal (redex-match? peg-solitaire (position  )
                          (term         (         )))
(test-equal (redex-match? peg-solitaire (position position )
                          (term         (                )))

Multiple occurrences of a name must match the same term, so the following does not match because position cannot be and at the same time:

(test-equal (redex-match? peg-solitaire (position position position)
                          ;                                ≠
                          (term         (                )))

We can suffix the names to allow them to match to different terms:

(test-equal (redex-match? peg-solitaire (position_1 position_2 position_3)
                          (term         (                    )))

We can use the peg-solitaire language to match the board examples:

(test-equal (redex-match? peg-solitaire board (term example-board-1))
(test-equal (redex-match? peg-solitaire board (term example-board-2))
(test-equal (redex-match? peg-solitaire board (term initial-board))
(test-equal (redex-match? peg-solitaire board (term example-winning-board))

Our language is too permissive, allowing board to match terms we consider ill-formed boards, for example:

(test-equal (redex-match? peg-solitaire board (term ([ ]

The term above does not represent a Peg Solitaire board: it is too small and the rows have different sizes. Yet, the board pattern in the peg-solitaire language matches it. We could refine the language definition so that it would match exactly the terms that represent Peg Solitaire elements, but that would be more complicated and would fail to communicate our intent to our readers. The named patterns we introduced in peg-solitaire will serve well for the definitions in the following sections, so this simpler language specification suffices. We will proceed assuming all boards are well-formed, and in a few cases we will even use ill-formed boards on purpose to simplify tests.

We will use the peg-solitaire language in later sections, so we provide it here:

(provide peg-solitaire)

Now that we have a language, we can operate on terms. On the next section, we cover the most familiar operation, the metafunction.