## `match` -- pattern matching

#### Introduction

`match(`expression, pattern`)` checks whether the syntactical structure of `expression` matches `pattern`, and if so, returns a set of replacement equations transforming `pattern` into `expression`.

#### Call(s)

`match(expression, pattern <, option1, option2, ...>)`

#### Parameters

`expression` | - | a MuPAD expression
`pattern` | - | the pattern: a MuPAD expression
`option1, option2, ...` | - | optional arguments (see below)

#### Options

`Ass = {f1, f2, ...}` | - | assume that the identifiers `f1, f2, ...` represent associative operators
`Comm = {g1, g2, ...}` | - | assume that the identifiers `g1, g2, ...` represent commutative operators
`Cond = {p1, p2, ...}` | - | conditional matching: consider only matches for which the conditions specified by the procedures `p1, p2, ...` are satisfied
`Const = {c1, c2, ...}` | - | assume that the identifiers `c1, c2, ...` represent constants
`Null = {h1 = e1, h2 = e2, ...}` | - | assume that the identifiers `e1, e2, ...` represent the neutral elements with respect to the operators `h1, h2, ...`, respectively

#### Returns

a set of replacement equations or `FAIL`.

#### Related Functions

`matchlib::analyze`, `simplify`, `subs`, `subsex`, `subsop`

#### Details

- `match` computes a set of replacement equations `S` for the identifiers occurring in `pattern`, such that `subs(pattern, S)` and `expression` coincide up to associativity, commutativity, and neutral elements.

- Most of the functionality of `match` is available via additional options. However, `match` is still in an experimental state, and some features may not work properly, yet.

- Without additional options, a purely syntactical matching is performed; associativity, commutativity, or neutral elements are not taken into account. In this case, `subs(pattern, S) = expression` holds for the set `S` of replacement equations returned by `match` if the matching was successful. Cf. example 1. You can declare these properties for operators via the options Ass, Comm, and Null (see below). Then `subs(pattern, S)` and `expression` need no longer be equal in MuPAD, but they can be transformed into each other by application of the rules implied by the options.

- Both `expression` and `pattern` may be arbitrary MuPAD expressions, i.e., both atomic expressions such as numbers, Boolean constants, and identifiers, and composite expressions.

- Each identifier without a value that occurs in `pattern`, including the 0th operands, is regarded as a pattern variable, in the sense that it may be replaced by some expression in order to transform `pattern` into `expression`. Use the option Const (see below) to declare identifiers as non-replaceable.

- With the exception of some automatic simplifications performed by the MuPAD kernel, distributivity is not taken into account. Cf. example 5.

- `match` evaluates its arguments, as usual. This evaluation usually encompasses a certain amount of simplification, which may change the syntactical structure of both `expression` and `pattern` in an unexpected way. Cf. example 6.

- Even if there are several possible matches, `match` returns at most one of them. Cf. example 7.

- If the structure of `expression` does not match `pattern`, `match` returns `FAIL`.

- If `expression` and `pattern` are equal, the empty set is returned.

- Otherwise, if a match is found and `expression` and `pattern` are different, then a set `S` of replacement equations is returned. For each pattern variable `x` occurring in `pattern` that is not declared constant via the option Const, `S` contains exactly one replacement equation of the form `x = y`, and `y` is the expression to be substituted for `x` in order to transform `pattern` into `expression`.

#### Option: Ass = {f1, f2, ...}

- It is assumed that operators `f1, f2, ...` are associative and may take an arbitrary number of arguments, i.e., expressions such as `f1(f1(a, b), c)`, `f1(a, f1(b, c))`, and `f1(a, b, c)` are considered equal.

- No special rules for associative operators with less than two arguments apply. In particular, `f1(a)` and `a` are not considered equal.

#### Option: Comm = {g1, g2, ...}

- The operators `g1, g2, ...` are assumed to be commutative, i.e., expressions such as `g1(a, b)` and `g1(b, a)` are considered equal.

#### Option: Cond = {p1, p2, ...}

- Only matches satisfying the conditions specified by the procedures `p1, p2, ...` are considered. Each procedure must take exactly one argument and represents a condition on exactly one pattern variable. The name of the procedure's formal argument must be equal to the name of a pattern variable occurring in `pattern` that is not declared constant via the option Const. Each condition procedure must return an expression that the function `bool` can evaluate to one of the Boolean values `TRUE` or `FALSE`.

  Anonymous procedures created via `->` can be used to express simple conditions. Cf. example 8.

- If a possible match is found, given by a set of replacement equations `S`, then `match` checks whether all specified conditions are satisfied by calling `bool(p1(y1) and p2(y2) and ...)`, where `y1` is the expression to be substituted for the pattern variable `x1` that agrees with the formal argument of the procedure `p1`, etc. If the return value of the call is `TRUE`, then `match` returns `S`. Otherwise, the next possible match is tried.

  For example, if `p1` is a procedure with formal argument `x1`, where `x1` is a pattern variable occurring in `pattern`, then a match `S = {..., x1 = y1, ...}` is considered valid only if `bool(p1(y1))` returns `TRUE`.

- There can be at most one condition procedure for each pattern variable. If necessary, use the logical operators `and` and `or` as well as the control structures `if` and `case` to combine several conditions for the same pattern variable in one condition procedure. Cf. example 8.

#### Option: Const = {c1, c2, ...}

- The identifiers `c1, c2, ...` are regarded as constants, i.e., they must match literally and must not be replaced in order to transform `pattern` into `expression`.

#### Option: Null = {h1 = e1, h2 = e2, ...}

- It is assumed that `e1, e2, ...` are the neutral elements with respect to the associative operations `h1, h2, ...` i.e., expressions such as `h1(a, e1)`, `h1(e1, a)`, and `h1(a)` are considered equal.

- This declaration affects only operators that are declared associative via the option Ass. Moreover, the neutral elements are not implicitly assumed to be constants.

#### Example 1

All identifiers of the following pattern are pattern variables:

    >> match(f(a, b), f(X, Y))

                               {X = a, Y = b, f = f}

The function `f` is declared non-replaceable:

    >> match(f(a, b), f(X, Y), Const = {f})

                                  {X = a, Y = b}

#### Example 2

The following call contains a condition for the pattern variable `X`:

    >> match(f(a, b), f(X, Y), Const = {f}, Cond = {X -> not has(X, a)})

                                       FAIL

If the function `f` is declared commutative, the expression matches the given pattern--in contrast to the preceding example:

    >> match(f(a, b), f(X, Y), Const = {f}, Comm = {f},
                               Cond = {X -> not has(X, a)})

                                  {X = b, Y = a}

#### Example 3

The following expression cannot be matched since the number of arguments of the expression and the pattern are different:

    >> match(f(a, b, c), f(X, Y), Const = {f})

                                       FAIL

We declare the function `f` associative with the option Ass. In this case the pattern matches the given expression:

    >> match(f(a, b, c), f(X, Y), Const = {f}, Ass = {f})

                               {X = a, Y = f(b, c)}

#### Example 4

If, however, the function call in the pattern has more arguments than the corresponding function call in the expression, no match is found:

    >> match(f(a, b), f(X, Y, Z), Const = {f}, Ass = {f})

                                       FAIL

If the neutral element with respect to the operator `f` is known, additional matches are possible by substituting it for some of the pattern variables:

    >> match(f(a, b), f(X, Y, Z), Const = {f}, Ass = {f}, Null = {f = 0})

                               {X = a, Z = b, Y = 0}

#### Example 5

Distributivity is not taken into account in general:

    >> match(a*x + a*y, a*(X + Y), Const = {a})

                                       FAIL

The next call finds a match, but not the expected one:

    >> match(a*(x + y), X + Y)

                              {Y = a (x + y), X = 0}

The following declarations and conditions do not lead to the expected result, either:

    >> match(a*(x + y), a*X + a*Y, Const = {a},
                                   Cond = {X -> X <> 0, Y -> Y <> 0})

                                       FAIL

#### Example 6

Automatic simplifications can ``destroy'' the structure of the given expression or pattern:

    >> match(sin(-2), sin(X))

                                       FAIL

The result is `FAIL`, because the first argument `sin(-2)` is evaluated:

    >> sin(-2)

                                      -sin(2)

You can circumvent this problem by using `hold`:

    >> match(hold(sin(-2)), sin(X))

                                     {X = -2}

#### Example 7

`match` returns only one possible match:

    >> match(a + b + c + 1, X + Y)

                              {X = a, Y = b + c + 1}

To obtain other solutions, use conditions to exclude the solutions that you already have:

    >> match(a + b + c + 1, X + Y, Cond = {X -> X <> a})

                              {X = b, Y = a + c + 1}

    >> match(a + b + c + 1, X + Y,
             Cond = {X -> X <> a and X <> b})

                              {X = c, Y = a + b + 1}

    >> match(a + b + c + 1, X + Y,
             Cond = {X -> not X in {a, b, c}})

                              {Y = a + b + c, X = 1}

#### Example 8

Every pattern variable can have at most one condition procedure. Simple conditions can be given by anonymous procedures (`->`):

    >> match(a + b, X + Y, Cond = {X -> X <> a, Y -> Y <> b})

                                  {X = b, Y = a}

Several conditions on a pattern variable can be combined in one procedure:

    >> Xcond := proc(X) begin
         if domtype(X) = DOM_IDENT then
           X <> a and X <> b
         else
           X <> 0
         end_if
       end_proc:

    >> match(sin(a*b), sin(X*Y), Cond = {Xcond})

                                 {Y = a b, X = 1}

    >> match(sin(a*c), sin(X*Y), Cond = {Xcond})

                                  {Y = a, X = c}

    >> delete Xcond:

#### Changes

- new function

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000