Previous Table of Contents Next


6.3.2.3. Matching Procedures

The obvious approach to extending the built-in repertoire of matching expressions is to write matching procedures—procedures that obey the matching protocol.

Showing how move(i) and tab(i) can be written as procedures illustrates the principles. This is one way to write a procedure tab(i):

    procedure tab(i)
       local saved_position

       saved_position := &pos

       if &pos := i then {
          suspend &subject[saved_position : &pos]
          &pos := saved_position
          }

       fail

    end

The local identifier saved_position is used to save the position. If the assignment of i to &pos succeeds (that is, if i is in range), tab() suspends with the matched substring of the subject. If tab() is resumed, it restores the saved position and fails.

This procedure is an instance of a more general model for matching procedures:

    procedure tab(i)
       local saved_position

       saved_position := &pos

       every &pos := new_pos do {
          suspend &subject[saved_position : &pos]
          &pos := saved_position
          }

       fail

    end

where new_pos indicates an expression that generates values for the position. An example of the use of this model is

    procedure gap()
       local saved_position

       saved_position := &pos

       every &pos := saved_position to *&subject + 1 do {
          suspend &subject[saved_position : &pos]
          &pos := saved_position
          }

       fail

    end

This procedure matches strings of length 0, 1, and so on through the end of the subject.

As mentioned earlier, a pattern abstractly characterizes a set of strings without any particular order among them. A procedure like gap() may match several different strings, but, of course, there is an order. The preceding procedure is “pessimistic” and tries the shortest possible string first, matching longer strings only if it is forced to do so by resumption resulting from the failure of subsequent matching expressions. An optimistic version of this matching procedure is

    procedure gap()
       local saved_position

       saved_position := &pos
       every &pos := *&subject + 1 to saved_position by –1 do {
          suspend &subject[saved_position : &pos]
          &pos := saved_position
          }

       fail

    end

6.3.2.4. Matching Procedures as Arguments to Matching Procedures

One of the potentially most powerful aspects of pattern matching is to use matching procedures as first-class values—passing matching procedures as arguments to other matching procedures.

Consider a matching procedure, p(), and the common situation in which a match is wanted for p() or the empty string. This can be written as

    p() | “”

However, matching something or the empty string is a concept that can be encapsulated in a way that is independent of any particular matching procedure—in another procedure, say orempty(p). The idea is that orempty(p) applies p in the desired context:

    procedure orempty(p)

       suspend (p() | “”)

    end

To understand orempty(), follow through the evaluation. The call p() is evaluated first. If it fails, the empty string is evaluated next, orempty() suspends with the empty string, and what happens next is clear. If p() succeeds, orempty() suspends with the value it matched; that is, it does just what p() alone would have done. If orempty() is resumed, p() is resumed because it suspended (as required of matching expressions).

Sometimes a particular construction in a string—a pattern—occurs several times in a row; perhaps zero or more. Suppose p() matches this pattern. What is needed is a matching procedure arbno(p) that matches what p() matches, zero or more times in a row:

    “” | p() | (p() || p()) | (p() || p() || p()) | …

Of course, there must be some context that causes the alternatives to be evaluated.

Such an open-ended construction suggests a closed form, using recursion:

    procedure arbno(p)

       suspend “” | (p() || arbno(p))

    end

arbno(p) first matches the empty string (zero occurrences of p(p). If it is resumed, it matches p() followed by arbno())—which matches the empty string first, so this amounts to one match of p(), and so on.

Note that arbno() is a recursive generator.


Previous Table of Contents Next