Previous Up Next

Chapter 12  Match cases and patterns

12.1  Match cases

MatchCase
::= { MatchRule (, MatchRule)* }
MatchRule
::= Patterns (when Expression)opt => Expression
Match cases are used to define function bodies (see Sections 7.5.2 and 11.11.1), exception handlers (see Section 11.3), and event wrappers (see Section 11.11.7). A match case consists of a sequence of one, or more, match rules. Each match rule consists of a pattern or pattern tuple, an optional guard expression, and an action expression. When matched agains a value, the pattern may bind variables to sub-terms of the value. The scope of these variables is the guard expression (if present) and the action expression.

A match case is evaluated against a value by testing each rule against the value until a match is found.1 The order of the rules matters. A match rule is tested against a value by first checking to see if the value matches the pattern and, if so, then testing to see if the guard expression evaluates to true. When a matching rule is found, the corresponding action expression is evaluated and its result is returned as the result of the match case. If no match is found, the standard Match exception is raised. Note that the compiler is expected to issue a warning on nonexhaustive match cases (except when used for exception handlers) and to issue an error on redundant match cases.

The typing judgements for match rules are
  G |- pat |> (t,VE)    G+VE |- exp |> t'  
  G |- pat => exp |> t®t'  
  G |- pat |> (t,VE)    G+VE |- exp1 |> Bool    G+VE |- exp2 |> t'  
  G |- pat when exp1 => exp2 |> t®t'  

12.2  Patterns

Patterns
::= PatternTuple
| Pattern
PatternTuple
::= ( Pattern (, Pattern)+ )

12.2.1  Constrained patterns

Pattern
::= IsPattern : Type
| IsPattern
The type checking rule for constrained patterns uses contravariant subtyping.
  G |- pat |> (t',VE)    G |- ty |> t    G |- t <: t'  
  G |- pat : ty |> (t,VE)  

12.2.2  Is patterns

IsPattern
::= ValueId is OrPattern
| ValueId isnot OrPattern
| _ isnot OrPattern
| OrPattern
The is pattern operator allow one to bind a variable to the term that matches the right-hand-side pattern. The isnot pattern operator is like the is pattern operator, except that the pattern successfully matches a term only when the term does not match the right-hand-side pattern. We require that the right-hand-side pattern of an isnot operator be variable free.

12.2.3  Or patterns

OrPattern
::= OrPattern (| ConsPattern)+
| ConsPattern
The infix ``|'' operator forms the or of two patterns. We require that the variables bound in the two sub-patterns of an or pattern be the same and that each bound variable has the same type in each sub-pattern. An or pattern matches a value when either the left pattern matches the value or the left pattern does not match and the right pattern matched the value. In other words, the pattern is tested from left to right. While this does not affect success or failure of the match, it does affect the binding of variables. For example, in the pattern 
a::_ | _::a_::_
the right pattern is covered by the left, so that a will always be bound to the head of the list on a successful match. In such a case, we say that the right pattern is redundant and the compiler should issue an error.

The typing rule for or patterns is
  G |- pat1 |> (t1,VE1)    G |- pat2 |> (t2,VE2)    G |- t1 = t2    G |- VE1 = VE2  
  G |- pat1 | pat2 |> (t1,VE1)  

12.2.4  Cons patterns

ConsPattern
::= ApplyPattern :: ConsPattern
| ApplyPattern
The infix ``::'' operator is the list cons constructor.

12.2.5  Application patterns

ApplyPattern
::= Pathopt DataCon PatternTuple
| Pathopt DataCon AtomicPattern
| AtomicPattern
The typing rule for constructor application allows for contravariant subtyping
  G(con) = t'®t    G |- pat |> (t'',VE)    G |- t' <: t''  
  G |- con(pat) |> (t,VE)  

12.2.6  Atomic patterns

AtomicPattern
::= ( Pattern )
| _
| ValueId
| DataConstructor
| Literal
| - NumericLiteral
Parenthesis can be used to override the natural associativity and precedence of patterns. For example, the pattern ``(a :: b) :: c'' matches a list of lists. Record patterns are described in the next section. The pattern ``_'' is called a wildcard and matches any value without binding any variables. A ValueId pattern matches any value and binds the variable to the value. A nullary data constructor pattern matches itself. A literal pattern matches the corresponding value.

12.2.7  Record patterns

RecordPat
::= {| LabeledPat (, LabeledPat)* |}
LabeledPat
::= Label
| Label = Pattern
| Label is Pattern
| Label isnot Pattern

12.3  Pattern matching semantics


  
  v |- x =Þ {x|®v}  

  
  v |- _ =Þ {}  

  v = ValueOf(lit)  
  v |- lit =Þ {}  

  v ¹ ValueOf(lit)  
  v |- lit =Þ FAIL  

  v |- p1 =Þ S  
  v |- p1 | p2 =Þ S  

  v |- p1 =Þ FAIL    v |- p2 =Þ S  
  v |- p1 | p2 =Þ S  

  v |- p1 =Þ FAIL    v |- p2 =Þ FAIL  
  v |- p1 | p2 =Þ FAIL  

  v |- p =Þ S  
  v |- x is p =Þ S±{x |® v}  

  v |- p =Þ FAIL  
  v |- x is p =Þ FAIL  

  v |- p =Þ {}  
  v |- x isnot p =Þ FAIL  

  v |- p =Þ FAIL  
  v |- x isnot p =Þ {x|®v}  

  v1 |- p1 =Þ S1    ···    vn |- pn =Þ Sn  
  (v1,...,vn) |- (p1,...,pn) =Þ S1 È ··· È Sn  

12.4  Pattern expressions

The definition of constants requires a syntactically restricted class of patterns called pattern expressions.2 A pattern expression is a pattern that does not contain or patterns, is or isnot patterns, or wild cards.

1
Obviously, more efficient implementation strategies are possible.
2
We use this terminology because the syntax is essentially the intersection of patterns and expressions [AR92].
Previous Up Next