PLT Redex & SEwPR

The six key parts of PLT Redex are language, reduction-relation, define-metafunction, stepper, redex-check, and test-->. There are many other functions in the library that build on these (and provide variations and extensions), but these illustrate the key services that PLT Redex provides. The first,
(define-language name (non-terminal-name rhs-pattern ...) ...)
specifies a BNF grammar for a regular tree language. Each right-hand side is written in PLT Redex's pattern language (consisting of a mixture of concrete syntax elements and non-terminals, roughly speaking). With a language definition in place, the reduction-relation form is used to define the reduction relation:
(reduction-relation language-name (--> lhs-pattern consequence) ...)
Syntactically, it consists of three sub-expressions: a language to which the reduction applies, a source pattern specifying which terms the rule matches, and Racket code that, when evaluated, produces the resulting term as an S-expression. Metafunctions are defined like this:
(define-metafunction language-name name : pattern ... -> pattern [(name lhs-pattern ...) result] ...)
The define-metafunction form defines the metafunction name by cases. Unlike the reduction relation, the branches for a metafunction are ordered. As soon as one of the patterns matches, that branch is taken regardless of other matches that might happen. The functions
stepper : language reduction-relation term -> any traces : language reduction-relation term -> any
open GUI windows that let you explore the reduction graph of terms reachable from the initial term. The stepper behaves in a manner similar to DrRacket's stepper, and traces shows the reduction graph in a graph-viewing window. Redex can randomly generate example expressions to try to falsify conjectures about the rewriting system. For example, this expression
(redex-check language-name pattern predicate)
randomly generates expressions matching pattern (typically a non-terminal) from the language language-name and then evaluates predicate. If it ever returns false, redex-check reports the expression that falsified the predicate. Finally,
(test--> reduction-relation starting-term final-terms ...)
can be used to develop test suites for PLT Redex programs. It accepts a reduction relation and an example term and applies the reduction relation until it cannot reduce any further, at which point it checks to make sure that each the given final terms match.