SML# Document

Chapter 19. Patterns and Pattern Matching

Patterns pat describe structures of values, and are used to bind variables values through pattern matching mechanism, built-in val-bind declarations (valBind)22.1, function declarations (funDecl)22.2, case expressions, fn expression,and handle expressions.

When evaluated, pattern matching generates static type environment at compile time, and dynamic value environment at runtime. These environments are used to added to the evaluation environment for the expressions and declarations in the scope of the pattern.

Syntax of Patterns is given below.

  • top-level pattern

    pat ::= atpat
     | (op)? longVid atpat data structure
     | pat vid pat data structure (infix operator form)
     | pat : ty pattern with type constraint
     | vid (: ty)? as pat layered pattern
  • atomic patterns

    atpat ::= scon constant
     | _ anonymous pattern
     | vid variable and constructor
     | longVid constructor
     | {(patrow)? } record pattern
     | () unit type constant
     | (pat1,,patn) tuples (n2)
     | [pat1,,patn] list (n0)
     | (pat)
    patrow ::= ... anonymous field
     | lab = pat (, patrow)? record fields
     | vid(:ty)? (as pat)? (,patrow)? label and variable

The following subsections define for each pattern pat, its type ty, matching values, and the resulting type environment. The dynamic environment generated at runtime corresponds to the generated type environment and it binds identifiers to the matched values.

¶ Constant pattern:scon

They are the same the constant expressions defined in 18.2. They have the corresponding types, match the same constant values, and generate the empty type environment.

¶ Anonymous pattern:_

This has arbitrary type determined by the context, matches any value, and generates the empty type environment.

¶ identifier pattern:vid

If the identifier is defined as a constructor, then it has the type of the constructor, matches the constructor, and generate the empty type environment.

If the identifier is not defined or defined as a variable, then it has arbitrary type ty determined by the context, matches any value of type ty, and generate the type environment {vid:ty}.

The following shows simple examples.

SML# 3.4.0 for x86_64-pc-linux-gnu with LLVM 3.7.0
# val A = 1
val A = 1 : int
# fn A => 1;
val it = fn : ['a. 'a -> int]
# fn A => 1;
val it = fn : ['a. 'a -> int]
# datatype foo = A;
datatype foo = A
# fn A => 1;
val it = fn : foo -> int
# datatype foo = A of int;
datatype foo = x of int
# fn A => 1;
(interactive):12.3-12.3 Error:
   (type inference 039) data constructor A used without argument in pattern

¶ long identifier:longVid

If the long identifier is defined as a constructor, then it has the type of the constructor, matches the constructor, and generate the empty type environment. It is an error if the identifier is not defined as a constructor or defined as a constructor with an argument. The following shows simple examples.

# structure A = struct datatype foo = A | B of int val C = 1 end;
structure A =
  struct
    datatype foo = A | B of int
    val C = 1 : int
  end
# val f = fn A.A => 1;
val f = fn : A.foo -> int
# val g = fn A.B => 1;
(interactive):3.11-3.13 Error:
  (type inference 046) data constructor A.B used without argument in pattern
# val h = fn A.C => 1;
(interactive):4.11-4.13 Error: (name evaluation "020") unbound constructor: A.C

A.B is a constructor with an argument and A.C is a variable, function declarations g and h result in errors.

¶ record pattern:{(patrow)? }

The pattern {} without record fields has the unit type, matches the value (), and generate the empty type environment.

If it has of the form lab1:ty1,,lab1:ty1, with non-empty record fields, there are two cases according to the record field pattern patrow. Let Γ be the type environment generated by the set of patterns in the fields.

  1. Monomorphic record pattern, i.e. the case where the anonymous field ... is not contained. It has the (monomorphic) record type {lab1:ty1,, lab1:ty1}, matches any records containing all the fields that matches the record field patterns patrow, and generate Γ.

  2. Polymorphic record pattern, i.e. the case where the anonymous field ... is contained. It has the polymorphic record type 'a#{lab1:ty1,, lab1:ty1} with the record kind of the field types of patrow, matches any records containing all the fields that matches the record field patterns patrow, and generate Γ. The polymorphic type of this entire pattern can be instantiated with any record types having the kind.

¶ record field pattern:patrow

  • Anonymous field pattern : .... It indicates that matching records may contains more fields than the specified fields.

  • Field pattern : lab = pat (, patrow)?. Let the filed type and the generated type environment of (, patrow)? be lab1:ty1,,lab1:ty1, and Γ. Let the type and the generated type environment of the pattern pat be ty and Γ0. If the label lab is different than any labels lab1,,lab1, then the type and the generated type environment of the entire pattern are lab:ty,lab1:ty1,,lab1:ty1, and Γ0Γ. It is a type error if the label lab is one of lab1,,lab1.

  • variable as label pattern: vid(:ty)? (as pat)?  (, patrow)?

    This is converted to the following field pattern before evaluation.

    vid = vid(:ty)? (as pat)?  (, patrow)?

    The generated static environment and the matching dynamic value are the same as the transformed record pattern. The following shows simple examples.

# val f = fn {x:int as 1, y} => x + y;
(interactive):33.8-33.34 Warning: match nonexhaustive
  {x = x as 1, y = y} => ...
val f = fn : {x: int, y: int} -> int
# val g = fn {x = x:int as 1, y = y} => x + y;
(interactive):34.8-34.37 Warning: match nonexhaustive
  {x = x as 1, y = y} => ...
val g = fn : {x: int, y: int} -> int
# f {x = 1, y = 2};
val it = 3 : int
# g {x = 1, y = 2};
val it = 3 : int

¶ Tuple pattern:(pat1,,patn)

This is converted to the monomorphic record pattern {1=pat1,,n=patn}.

The generated static environment and the matching dynamic value are the same as the transformed record pattern. The following shows simple examples.

# val f = fn (x,y) => 2 * x + y;
val f = fn : int * int -> int
# val g = fn {1=x, 2=y} => 2 * x + y;
val g = fn : int * int -> int
# f 1=1, 2=2;
val it = 4 : int
# g (1,2);
val it = 4 : int

¶ List pattern:[pat1,,patn]

This is converted to the following nested list data structure pattern:

pat1 :: :: patn :: nil

The generated static environment and the matching dynamic value are the same as the transformed constructor application pattern. The following shows simple examples.

# val f = fn [x,y] => 2*x + y;
(interactive):24.8-24.26 Warning: match nonexhaustive
  :: (x, :: (y, nil )) => ...
val f = fn : int list -> int
# val g = fn (x::y::nil) => 2*x + y;
(interactive):25.8-25.32 Warning: match nonexhaustive
  :: (x, :: (y, nil )) => ...
val g = fn : int list -> int
# f (1::2::nil);
val it = 4 : int
# g [1,2];
val it = 4 : int

¶ Data structure pattern:(op)? longVid atpat

If longVid is bound to a constructor C of type of the form ty1 -> ty2,then it has type ty2 and generates a type constructor generated by atpat. This pattern matches a data structure of the form C(v) if the subterm v matches atpat.

Data structure patter in infix form pat1 vid pat2 is syntactically converted to op vid(pat1,pat2) before evaluation. The type and type environment being generated and the matching dynamic value are the same as those of converted pattern.

¶ Typed pattern: pat:ty

If pattern pat has type ty1 ad type environment Γ0, and ty1 and ty unifies under type substitution S, then this pattern has type S(ty) and type environment S(Γ0). This pattern matches a value of type S(ty) that matches pattern pat.

¶ Layered pattern: vid (: ty)? as pat

If the pattern pat:ty has type ty' and a type environment Γ then this pattern has type ty' and a type environment Γ{x:ty}. It matches a dynamic value that the pattern pat:ty matches.