Patterns and Matching

A (text) pattern is a formalism for constructing a text from some fragments, possibly using some glue between these fragments. It typically comes with some constraints on the fragments used (or on the meanings the context gives to them). A text so constructed can then be given meaning in terms of the meanings of the fragments (and how the pattern uses them).

For instance, I can use mapping ( input ) as a pattern, in which mapping is constrained to be a denotation for some function, input is constrained to be a denotation for some value which the mapping accepts as an input and the ( and ) are glue. I can use this to give meaning to the whole text: eg as the output the function produces for the given input. Some context which includes this definition can give meaning to names f, as some function, and x, as some value which f accepts: f(x) then has its conventional meaning.

Of course, for a context to introduce any patterns, it needs to introduce some means for the reader to recognise part of its text as a pattern: and to distinguish the glue from the building-blocks. Fortunately, English is rich enough for the former: I can state that some portion of the text is a pattern. For the latter, I find it suffices to use italic tokens for building-blocks and bold tokens for glue, as in the example above. This will aid in recognising patterns.

Two Meta-Patterns: optional parts and repetition

A pattern can have optional parts in it: thus sign digits is a standard pattern for an integer, but the sign is only required when the integer is negative. One can cater to this by having constraints which allow sign to be the empty text (which is omni-present in every text), but when the optional component includes some glue this doesn't work. I'll enclose optional parts of patterns in [ italicised ] square brackets.

We're now in a position to do something quite powerful. First, use the pattern item, constrain item to be a denotation for (say) some value: describe the resulting text as a comma-separated list. Next, use item , separated as a pattern, require item again to be some value and separated to be a comma-separated list; describe the resulting text also as a comma-separated list. This gives the usual meaning to comma-separated list subject to some quibbles about whether the list of length one deserves that title, and whether we should also allow the empty list.

That definition is, however, somewhat fiddly: which rather distracts from the essentially simple thing being defined. It also forces me to name the variety of structure involved, so that I can do the self-referential part of the definition. So I stoop to a piece of syntactic sugar and define a denotational form for use in optional parts of patterns for this kind of repetition. This will render the comma-separated list, above, as item [... , item ] without needing to introduce a name for this structure.

If the opening [ of an optional fragment is followed by ... (to be distinguished carefully from ... which is bold so will, when present, be a piece of glue rather than a token to be replaced by a fragment of text) or the closing ] is preceded likewise, then the rest of the contents of the [ ] brackets may be omitted or arbitrarily repeated (as a whole). Note that

Matching Patterns

I have introduced patterns as a way of constructing a text with meaning from fragments with appropriate meanings - this is a synthetic description of the relationship between text and patterns. The reader, on the other hand, will be more concerned with identifying the patterns from which I have constructed a text and thus inferring a meaning for the whole from the meanings of the fragments so combined - calling for an analytic description.

I'll describe a choice of fragments satisfying a pattern's constraints as a match of the resulting text to the given pattern: I'll say that this text (as a whole) matches the pattern.

There may, in principle, be several matches of one text to some given pattern: or several patterns which a given text matches. A discourse which introduces meanings using this pattern mechanism must attend, in its definitions, to ways of handling or avoiding such ambiguities.

The bulk of how I deal with potential ambiguity in is in terms of nesting rules: the denotations I introduce which involve {, [, (, ), ] and } will do so in matched pairs. Any text in which no {, [, (, ), ], or } characters appear is properly nested; any text which matches one of the patterns

is properly nested provided each nested is a properly nested text. So long as I have only given meaning to properly nested texts, the application of a properly nested pattern (in which each non-glue fragment is bound to have been given meaning) can only yield a properly nested text: until there is a meaningful text which isn't properly nested, it's impossible to construct such a text. So all texts to which I shall give meaning are properly nested - which hugely simplifies the task of working out: which patterns a text might possibly match (since bracket-matching algorithms are easy to implement); and which decompositions of the text into fragments might possibly be matches to any given pattern.

Implicit Naming

Just as the text may explicitly introduce a name and associate it with a value, so also a denotational definition may provide for the introduction of names by which to refer to values. I call this implicit naming when the denotation allows that a name, to which context otherwise gives no meaning, may be used as one of the subtexts combined by the pattern and, when this option is exercised, the name is implicitly to be given meaning as some value which satisfies all relevant constraints. As ever, the denotation which introduces the name may export this naming to other contexts, so a denotational definition can allow for names introduced in some of its fragments to be recognised with the relevant meaning in its other fragments: which may, in turn, impose further constraints on the value associated with the name.

Written by Eddy.