4 Reduction Relations

All of the exports in this section are provided both by redex/reduction-semantics (which includes all non-GUI portions of Redex) and also exported by redex (which includes all of Redex).

Following the pattern and term can be the name of the reduction rule, declarations of some fresh variables, and/or some side-conditions.

The rule’s name (used in typesetting, the stepper, traces, and apply-reduction-relation/tag-with-names) can be given as a literal (an identifier or a string) or as an expression that computes a name using the values of the bound pattern variables (much like the rule’s right-hand side). Some operations require literal names, so a rule definition may provide both a literal name and a computed name. In particular, only rules that include a literal name may be replaced using extend-reduction-relation, used as breakpoints in the stepper, and selected using render-reduction-relation-rules. The output of apply-reduction-relation/tag-with-names, traces, and the stepper prefers the computed name, if it exists. Typesetting a rule with a computed name shows the expression that computes the name only when the rule has no literal name or when it would not typeset in pink due to with-unquote-rewriters in the context; otherwise, the literal name (or nothing) is shown.

The fresh variables clause generates variables that do not occur in the term being matched. If the fresh-clause is a variable, that variable is used both as a binding in the rhs-exp and as the prefix for the freshly generated variable. (The variable does not have to be a non-terminal in the language of the reduction relation.)

The second case of a fresh-clause is used when you want to generate a sequence of variables. In that case, the ellipses are literal ellipses; that is, you must actually write ellipses in your rule. The variable var1 is like the variable in first case of a fresh-clause, namely it is used to determine the prefix of the generated variables and it is bound in the right-hand side of the reduction rule, but unlike the single-variable fresh clause, it is bound to a sequence of variables. The variable var2 is used to determine the number of variables generated and var2 must be bound by the left-hand side of the rule.

The expressions within side-condition clauses and side-condition/hidden clauses are collected with and and used as guards on the case being matched. The argument to each side-condition should be a Racket expression, and the pattern variables in the pattern are bound in that expression. A side-condition/hidden clause is the same as a side-condition clause, except that the condition is not rendered when typesetting via redex/pict.

Each where clause acts as a side condition requiring a successful pattern match, and it can bind pattern variables in the side-conditions (and where clauses) that follow and in the metafunction result. The bindings are the same as bindings in a term-let expression. A where/hidden clause is the same as a where clause, but the clause is not rendered when typesetting via redex/pict.

As an example, this

(reduction-relation

lc-lang

(--> (in-hole c_1 ((lambda (variable_i ...) e_body) v_i ...))

(in-hole c_1 ,(foldl lc-subst

(term e_body)

(term (v_i ...))

(term (variable_i ...))))

beta-v))

defines a reduction relation for the lambda-calculus above.

Each of the clauses after the with define new relations in terms of other definitions after the with clause or in terms of the main --> relation.

A fresh variable is always fresh with respect to the entire term, not just with respect to the part that matches the right-hand-side of the newly defined arrow.

As an example, this

(reduction-relation

lc-num-lang

(==> ((lambda (variable_i ...) e_body) v_i ...)

,(foldl lc-subst

(term e_body)

(term (v_i ...))

(term (variable_i ...))))

(==> (+ number_1 ...)

,(apply + (term (number_1 ...))))

with

[(--> (in-hole c_1 a) (in-hole c_1 b))

(==> a b)])

defines reductions for the lambda calculus with numbers, where the ==> relation is defined by reducing in the context c.

If the original reduction-relation has a rule with the same name as one of the rules specified in the extension, the old rule is removed.

Examples:

> (define-language empty-lang)

> (define R       (reduction-relation        empty-lang        (--> 0 1)        (--> 0 2)        (--> 2 3)        (--> 3 3)))

> (apply-reduction-relation R 0)

'(2 1)

> (apply-reduction-relation* R 0)

'(1)