Pattern Matching for Tuples
We’ll use tuples to illustrate the concepts of pattern matching in detail; other types of structures will be covered more concisely.
Pattern-based Variable Declaration
Recall from JH: Chapter XX, FIX REFERENCE that tuple elements can be accessed using explicit projection operations. Below is an example of a situation where we need to declare a val binding for each element of a tuple.
val t1: (Z, B, String) = (0, F, "") // immutable tuple (mutability automatically detected)
val z1 = t1._1 // using projection operations to access tuple elements
val b1 = t1._2
val s1 = t1._3
assert(z1 == 0 && b1 == F && s1 == "")
The same effect can be achieved much more compactly using pattern matching, as illustrated below.
// Pattern matching in declarations -- declaring multiple val/vars at once
val (z2,b2,s2) = t1 // using pattern matching to access tuple elements
// implicitly creates val declarations for z2, b2, s2
assert(z2 == 0 && b2 == F && s2 == "")
In addition to being more compact, the pattern matching style of accessing is often easier to comprehend at a glance because the structure of the accessing code (the pattern) matches the developer’s conceptualization of the structure of the data being decomposed.
In situations where names for certain elements are not needed or the structure of those elements is irrelevant (e.g., subsequent code doesn’t use those elements), the wildcard character _ can be used.
// Wildcards -- ignore certain elements
val (_,b3,_) = t1 // use underscore (wildcard) when elements don't need to be named
assert(b3 == F)
Patterns can be nested.
// Nested patterns
val t2 = (t1, ("a", F), 1) // nested tuples
assert(t2._1._2 == F) // using project operations to access nested tuple elements
val ((z3,_,_),(s4,b4),_) = t2 // using pattern matching to access nested tuple elements
assert(z3 == 0 && s4 == "a" && b4 == F)
Patterns can also be used in var declarations.
// Pattern matching in var declarations
var (_, _, z4) = t2 // pattern matching can also be used in var declarations (not just val)
assert(z4 == 1)
Pattern-matching Cases
Slang includes Scala’s case-based pattern matching control structure, illustrated below. The expression before the match keyword is evaluated and its value is compared against the patterns appearing in the case clauses. When a match occurs, identifiers in the matching pattern are bound to the corresponding elements in the structure, and the corresponding statement/expression/block following the => is evaluated (the result of the evaluation becomes the resulting value of the entire match construct).
// Match / case -- functional style
@pure def matchPair(p: (Z,Z)): Option[Z] = {
p match { // pattern match on pair p
case (0,pz2) => return Some(pz2) // case where first element has value 0
case (1,pz2) => return Some(pz2) // case where first element has value 1
case _ => return None() // wildcard (matches entire tuple) is used to express "else" case
}
}
This example shows the literals (e.g., 0 and 1) can be mixed in with identifiers and wildcards to form a pattern.
The code to evaluate upon a match can also be a single command or a block.
// Match / case -- imperative style
@pure def matchPairCMD(p: (Z,Z)): Option[Z] = {
var ans: Option[Z] = None()
p match { // pattern match on pair p
case (0,pz2) => { // case where first element has value 0
ans = Some(pz2) // ...block to execute upon match
}
case (1,pz2) => { // case where first element has value 1
ans = Some(pz2)
}
// case _ => ..default case is captured by initial value
}
return ans
}
With pattern matching, one should think about potential problems associated with both non-disjoint (i.e., overlapping) cases and non-exhaustive cases. Regarding non-disjointness, Slang (and Scala) allows there to be more than one pattern that matches (i.e., the patterns can be “overlapping”). Since the cases are evaluated in order, there is no non-determinism – the first pattern to match in the case sequence determines the evaluation. The possibility for overlapping is somewhat obvious when one considers that the wildcard always matches (so it would overlap with any other matching pattern).
// Pattern matching -- non-disjoint cases
@pure def matchPairOVERLAPPING1(p: (Z,Z)): Option[Z] = { // illustrating overlapping cases
p match { // pattern match on pair p
case (0,pz2) => return Some(pz2) // case where first element has value 0
case (pz1,pz2) => return Some(pz2) // ..overlaps.. covers all other cases
}
}
Non-disjoint cases may sometimes impact readability/understandability. When taking a purist approach, one might desire the cases to be read “mathematically” where there is a single result returned determined solely based on the case condition (i.e., as in a mathematical proof). When overlapping cases are used, this property is violated: multiple cases apply, and there appears to be more than one possible return value. However, the case conditions themselves are often less complex if one acquiesces to rely on the case ordering.
In extreme situations, non-disjoint cases can lead to dead code, as in the example below.
// Pattern matching -- non-disjoint cases with dead code
@pure def matchPairOVERLAPPING2(p: (Z,Z)): Option[Z] = { // illustrating overlapping cases - problematic
p match { // pattern match on pair p
case (0,pz2) => return Some(pz2) // case where first element has value 0
case (pz1,pz2) => return Some(pz2) // all other cases
case _ => None() // all other cases -- redundant (dead code)
// and potentially problematic for understandability...
// ...read mathematically/non-sequentially, the method returns
// two different values for the same input
}
}
Non-exhaustive cases are more problematic – the match expression can possibility be executed in situations where no case applies, and thus the intended behavior of the code is unclear. Therefore, almost all languages that support pattern matching generate a run-time exception when executing a match expression results in no applicable case. This is illustrated in the example below.
// match / case -- non-exhaustive cases and run-time exception
@pure def matchPairNONEXHAUSTIVE(p: (Z,Z)): Option[Z] = { // non-exhaustive pattern matching may lead to run-time exception
p match { // pattern match on pair p
case (0,pz2) => return Some(pz2) // case where first element has value 0
case (1,pz2) => return Some(pz2) // case where first element has value 1
} // ...if control reaches this point, exception is raised
}
// matchPairNONEXHAUSTIVE((2,1)) // ERROR: this call leads to a "MatchError" exception
The exception thrown for the call above looks something this::
Exception:: […] scala.MatchError: (2,1) (of class scala.Tuple2) at Main$$anon$1.matchPairBADSTYLE(chapter-06.sc:47) […]
Use of patterns in val/var declarations can have similar problems: if the pattern used in the declaration cannot be matched with the value of the given initializing expression, a MatchError exception is raised.
// Patterns in declarations -- no match and run-time exception
// recall: val t1: (Z, B, String) = (0, F, "")
val (0,b5,s5) = t1 // Literals can also be used in pattern-based
// val declarations, but this is bad style due to the
// possibility of a non-match and a run-time exception.
// For good style, pattern matching in val defs should always succeed.
// e.g., use variables and wildcards only.
// val (1,b6,s6) = t1 // ERROR: non-match on first element leads to run-time exception
Because there is a general desire to avoid unanticipated run-time exceptions, Logika generates a verification condition requiring “exhaustiveness” of the cases in matching contexts (i.e., it must be verified that there will always be a match).
Note
JH: To Robby, are other features of Scala pattern matching supported such as pattern guards and matching on types only?
Pattern Binders
Slang supports Scala’s pattern binders (see Scala reference manual). A pattern binder x @ p allows one to introduce a value identifier x that binds to the entire structure that matches a pattern p (not just elements of the matching structure).
// Pattern binders -- id @ pattern
@pure def matchPairPatternBinder(p: (Z,Z)): (Z,Z) = {
p match { // pattern match on pair or pairs p
case t1 @ (3,_) => return t1 // case where first element is 3
// t1 will name the entire pair
case t2 @ (_, 2) => return t2 // case where second element is 2
// t2 will name the entire pair
case _ => return (0,0) // wildcard (matches entire tuple) is used to express "else" case
}
}
assert(matchPairPatternBinder((9,2)) == (9,2))
The above example is not completely convincing in terms of motivation: in the match-case above, one could get the same effect by omitting the pattern binding and just returning p in both the first and second cases.
Using pattern binding nested inside of a larger pattern (as in the example below) better illustrates the utility of the concept.
// Pattern binders in nested patterns -- a better motivation
@pure def matchPairPatternBinder(p: ((Z,Z),(Z,Z))): (Z,Z) = {
p match { // pattern match on pair or pairs p
case (t1 @ (3,_), _) => return t1 // case where first element has a first element of 3
// t1 will name the entire first element
case (_, t2 @ (_, 2)) => return t2 // case where second element has a second element of 2
// t2 will name the entire second element
case _ => return (0,0) // wildcard (matches entire tuple) is used to express "else" case
}
}
assert(matchPairPatternBinder((7,9),(12,2)) == (12,2))
Pattern binders can also be used in variable declarations.
// Pattern binders in variable declarations
// recall val t1: (Z, B, String) = (0, F, "")
// val t2 = (t1, ("a", F), 1)
val (_,innerp @ (innerpe1,_), _) = t2 // using pattern binder declares innerp to name the inner pair
// as well as innerpe1 to name the first element of the pair
assert(innerp == ("a", F))
Pattern Guards
Slang supports Scala’s notion of pattern guard (see Tour of Scala and Scala reference manual). Pattern guards are boolean conditions that are added after the pattern to make the cases more specific. Though it is not illustrated in the example below, the expression in the condition can reference any variable in scope – not just the variables introduced in the pattern.
// Pattern guards
@pure def matchPairPatternGuard(p: (Z,Z)): Option[Z] = {
p match { // pattern match on pair p
case (m,n) if m > n => return Some(m) // pattern is guarded by extra condition m > n
case (m,n) if m < n => return Some(n) // pattern is guarded by extra condition m < n
case _ => return None() // "otherwise" case
}
}
assert(matchPairPatternGuard((9,7)) == Some(9))
assert(matchPairPatternGuard((6,8)) == Some(8))
assert(matchPairPatternGuard((5,5)) == None())
Pattern Alternatives
Slang supports Scala’s notion of pattern alternate, which allows one to specify more than one pattern in a single case (see Scala reference manual).
// Pattern alternatives
@pure def matchPairPatternAlternatives(p: (Z,Z)): Option[Z] = {
p match {
case (0,1) | (1,0) | (0,0) | (1,1) => return Some(0) // state alternatives using "|"
// case (2,n) | (m,2) => Some(2) // ERROR: cannot use pattern variables with alternative
case (m,n) if m == 2 || n == 2 => return Some(2) // ...so achieve the desired logic above using guards
case (3,_) | (_,3) => return Some(3) // wildcards are allowed in alternatives
case _ => return None()
}
}
assert(matchPairPatternAlternatives((0,0)) == Some(0))
assert(matchPairPatternAlternatives((0,1)) == Some(0))
assert(matchPairPatternAlternatives((2,4)) == Some(2))
assert(matchPairPatternAlternatives((3,9)) == Some(3))
assert(matchPairPatternAlternatives((7,1)) == None())
The example above illustrates that pattern alternatives may not bind variables other than wildcards (allowing variable binding would lead to a variable having an undefined value when the alternative does not match). Pattern alternatives are most often using when matching on literals of basic types (see Scala examples).
Pattern Matching on Mutable Structures
A key difference between Slang and Scala pattern matching is that, when matching mutable structures on patterns that bind variables, Slang makes an implicit copy to avoid aliasing (this follows the philosophy and examples in the discussion of assignment and mutable structures in Chapter XXX).
The following code illustrates this with two methods that appear to similar functionality but produces different effects on the parameter due to implicit copying when pattern matching.
In the first method matchPairMutable, the identifier binding in the pattern used to match the mutable element of the pair parameter induces an implicit copy – so the subsequent update to the mutable sequence bound to the variable produces no externally observable effect outside of the method (the update only applies to the implict copy of the mutable sequence – which does not flow outside of the method).
In the second method pairMutableSideEffect, instead of pattern matching, the projection operation ._2 is used to access/update the second element of the pair parameter. Since no new variable binding is involved, no implicit copy is necessary to avoid aliasing. Therefore, the update to the parameter is visible outside of the method.
// Pattern matching on mutable structures produces a copy
def matchPairMutable(p: (Z,MSZ[Z])): Unit = {
p match {
case (0,mszz) => mszz(0) = 2 // implicit copy of mut. seq. param due to pattern binding to mszz
case _ => // do nothing
}
} // method produces no externally visible side effects due to implicit copy of sequence
def pairMutableSideEffect(p: (Z,MSZ[Z])): Unit = {
p._2(0) = 2
} // method produces externally visible side effects on the mut. seq. in p
val p1 : (Z, MSZ[Z]) = (1, MSZ(1)) // mutable tuble (at least one mutable element)
matchPairMutable(p1)
assert(p1 == (1, MSZ(1))) // assert that method call HAS NOT updated value of parameter
// ...due to implicit copy in pattern matching
pairMutableSideEffect(p1)
assert(p1 == (1, MSZ(2))) // assert that method call HAS updated parameter
// ...due to direct manipulation/update of mutable structure
Scala Connection
Tuples are among the easiest structures to support in pattern matching. For this reason, and since Slang uses Scala tuples directly, Slang supports all of Scala’s features for tuple pattern matching.