Content deleted Content added
No edit summary |
m →External links: HTTP to HTTPS for Cornell University |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 21:
[[Computer algebra system]]s generally support pattern matching on algebraic expressions.<ref>Joel Moses, "Symbolic Integration", MIT Project MAC MAC-TR-47, December 1967</ref>
==Terminology==
Pattern matching involves specialized terminology.
; Matching
: The act of comparing a ''discriminant'' to a ''pattern'' (or collection of patterns), possibly selecting a ''continuation'', extracting ''bindings'', performing a ''substitution'', or any combination of these. Also known as '''destructuring'''.
; Pattern
: Syntax describing expected structure in the ''discriminant'', plus specification of portions of the discriminant to extract (''bindings'') or ignore (''wildcards''). Pattern languages can be rich; see below for terminology denoting specific kinds of pattern.
; Discriminant
: The value to be examined and matched against a pattern. In most cases, this will be a data structure of some kind, with type [[Duality (mathematics)|dual to]] the pattern being applied. Also known as the '''subject value''' or '''scrutinee'''.
; Continuation
: In some languages, when multiple alternative patterns are applied to a discriminant, when one alternative matches, an associated code fragment is executed in an environment extended with the matching pattern's ''bindings''. This code fragment is the ''continuation'' associated with the pattern.
; Substitution
: Replacement of a portion of a discriminant data structure with some computed value. The computation may depend on the replaced portion of the discriminant as well as on other bindings extracted from the discriminant.
===Terminology of patterns===
While some concepts are relatively common to many pattern languages, other pattern languages include unique or unusual extensions.
; [[Name binding|Binding]]
: A way of associating a ''name'' with a portion of the discriminant, so that the name is [[Name binding|bound to]] that portion when the continuation executes. For example, in Rust, {{code|2=rust|1=match v { (a, b) => ... } }} expects <code>v</code> to be a pair, and <code>a</code> and <code>b</code> are bindings bringing variables of the same name into scope in the continuation ("<code>...</code>").
; Wildcard
: Often written as a single underscore, <code>_</code>, the wildcard pattern accepts all values without examining them further, ignoring their structure. Also known as '''discard''', the '''wild pattern''', the '''catch-all pattern''', or as a '''hole'''.
; [[Guard (computer science)|Guard]]
: A ''guard'' is an expression that must succeed (or yield boolean true) as a final step before considering a pattern to have successfully matched. In some languages (e.g. [[Erlang (programming language)|Erlang]]), guards are written using a restricted subset of the full language; in others (e.g. [[Haskell]]), guards may use the full language.
; Predicate
: Some pattern languages allow user-defined ''predicate'' functions to be embedded in a pattern. The predicate is applied to the portion of the discriminant corresponding to the position of the predicate in the pattern; if the predicate responds with boolean false, the pattern is considered to have failed. For example, in Racket, the pattern {{code|(list (? even?) ...)|rkt}} first expects a list, and then applies the predicate <code>even?</code> to each element; the overall pattern thus succeeds only when the discriminant is a list of even numbers.
; View pattern
: Languages like Haskell<ref>{{cite web|url=https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/view_patterns.html|title=View Patterns - Glasgow Haskell Compiler User's Guide}}</ref> and Racket<ref>{{cite web|url=https://docs.racket-lang.org/reference/match.html#(idx._(gentag._255._(lib._scribblings/reference/reference..scrbl)))|title=Pattern Matching: app}}</ref> include ''view patterns'', where a user-defined function transforms the portion of the discriminant corresponding to the position of the view pattern before continuing the match. View patterns generalize predicate patterns, allowing further matching on the result of the function rather than simply expecting a boolean value.
; Constraint
: Some pattern languages allow direct comparison of portions of the discriminant with previously-computed (or constant) data structures. For example, the pattern {{code|1=(== expr)|2=rkt}} in Racket compares the value against the result of evaluating <code>expr</code>. In Erlang, mention of any variable already in scope in a pattern causes it to act as a constraint in this way (instead of as a binding).
; Literal pattern; atomic pattern
: Patterns that match simple atomic data such as <code>123</code> or <code>"hello"</code> are called ''literal patterns''.
; Compound pattern
: Patterns that destructure compound values such as lists, hash tables, tuples, structures or records, with sub-patterns for each of the values making up the compound data structure, are called ''compound patterns''.
; Alternative (<code>or</code>-pattern)
: Many languages allow multiple alternatives at the top-level of a pattern matching construct, each associated with a ''continuation''; some languages allow alternatives ''within'' a pattern. In most cases, such alternatives have additional constraints placed on them: for example, every alternative may be required to produce the same set of ''bindings'' (at the same types).
; Macros
: Some languages allow macros in pattern context to allow abstraction over patterns. For example, in Racket, ''match expanders'' perform this role.<ref>{{cite web|url=https://docs.racket-lang.org/reference/match.html#%28form._%28%28lib._racket%2Fmatch..rkt%29._define-match-expander%29%29|title=Pattern Matching: define-match-expander}}</ref>
==Types==
Line 261 ⟶ 314:
*[https://archive.today/19990225161739/http://www.haskell.org/development/views.html Views: An Extension to Haskell Pattern Matching]
* Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper. [https://web.archive.org/web/20060304053330/http://wwwhome.cs.utwente.nl/~tina/apm/applPatts.pdf Application patterns]. A presentation at Trends in Functional Programming, 2005
*[
*[https://archive.today/20130630081135/http://www.showtrend.com/ ShowTrend]: Online pattern matching for stock prices
*[https://web.archive.org/web/20060211020429/http://cm.bell-labs.com/cm/cs/who/dmr/qed.html An incomplete history of the QED Text Editor] by [[Dennis Ritchie]] - provides the history of regular expressions in computer programs
| |||