Pattern matching¶

The libndtypes implementation of datashape is dynamically typed with strict type checking. Static type checking of datashape would be far more complex, since datashape allows dependent types [1], i.e. types depending on values.

Dynamic pattern matching is used for checking function arguments, return values, broadcasting and general array functions.

Again, we will be using the ndtypes module included in ndtypes to demonstrate datashape pattern matching. The rest of this document assumes that the ndtypes module has been imported:

from ndtypes import ndt

General notes¶

ndt instances have a match method for determining whether the argument type is compatible with the instance type. The match succeeds if and only if the set of types described by the right hand side is a subset of the set of types described by the left hand side.

Simple example¶

>>> p = ndt("Any")
>>> c = ndt("int32")
>>> p.match(c)
True

Non-commutativity¶

From the above definition it follows that pattern matching is not commutative:

>>> p = ndt("int32")
>>> c = ndt("Any")
>>> p.match(c)
False

Concrete matching¶

Much like members of the alphabet in regular expressions, concrete types match themselves:

>>> p = ndt("int32")
>>> c = ndt("int32")
>>> p.match(c)
True

>>> p = ndt("10 * float64")
>>> c = ndt("10 * float32")
>>> p.match(c)
False

Type kinds¶

Type kinds are named subsets of types.

Unlike dtype variables, matching type kinds does not require that a well defined substitution exists. Two instances of a type kind can match different types:

>>> p = ndt("(Any, Any)")
>>> c = ndt("(float64, int32)")
>>> p.match(c)
True

Any¶

The Any type kind is the most general and describes the set of all types.

Here’s how to match a dtype against the set of all types:

>>> p = ndt("Any")
>>> c = ndt("int32")
>>> p.match(c)
True

This matches an array type against the set of all types:

>>> p = ndt("Any")
>>> c = ndt("10 * 5 * { v: float64, t: float64 }")
>>> p.match(c)
True

Scalar¶

The Scalar type kind stands for the set of all scalars.

int32 is a member of the set of all scalars:

>>> p = ndt("Scalar")
>>> c = ndt("int32")
>>> p.match(c)
True

Unlike with type variables, different types match a type kind:

>>> p = ndt("(Scalar, Scalar)")
>>> c = ndt("(uint8, float64)")
>>> p.match(c)
True

FixedString¶

The set of all fixed string types.

>>> p = ndt("FixedString")
>>> c = ndt("fixed_string(100)")
>>> p.match(c)
True

>>> p = ndt("FixedString")
>>> c = ndt("fixed_string(100, 'utf16')")
>>> p.match(c)
True

>>> p = ndt("FixedString")
>>> c = ndt("string")
>>> p.match(c)
False

FixedBytes¶

The set of all fixed bytes types.

>>> p = ndt("FixedBytes")
>>> c = ndt("fixed_bytes(size=100)")
>>> p.match(c)
True

>>> p = ndt("FixedBytes")
>>> c = ndt("fixed_bytes(size=100, align=2)")
>>> p.match(c)
True

>>> p = ndt("FixedBytes")
>>> c = ndt("bytes(align=2)")
>>> p.match(c)
False

Dimension kinds¶

Dimension kinds stand for the set of all instances of the respective kind.

Fixed¶

The set of all instances of the fixed dimension kind.

>>> p = ndt("Fixed * 20 * bool")
>>> c = ndt("10 * 20 * bool")
>>> p.match(c)
True

>>> p = ndt("Fixed * Fixed * bool")
>>> c = ndt("var * var * bool")
>>> p.match(c)
False

Dtype variables¶

dtype variables are placeholders for dtypes. It is important to note that they are not general type variables. For example, they do not match array types, a concept which is used in general array functions [2], whose base cases may operate on a dtype.

This matches a record against a single dtype variable:

>>> p = ndt("T")
>>> c = ndt("{v: float64, t: float64}")
>>> p.match(c)
True

Match against several dtype variables in a tuple type:

>>> p = ndt("T")
>>> c = ndt("(int32, int32, bool)")
>>> p.match(c)
True

>>> p = ndt("(T, T, S)")
>>> c = ndt("(int32, int64, bool)")
>>> p.match(c)
False

Symbolic dimensions¶

Recall that array types include the dimension kind, which can be symbolic.

Simple symbolic match¶

This matches a concrete fixed size array against the set of all one-dimensional fixed size arrays:

>>> p = ndt("N * float64")
>>> c = ndt("100 * float64")
>>> p.match(c)
True

Symbolic+Dtypevar¶

Symbolic dimensions can be used in conjunction with dtype variables:

>>> p = ndt("N * T")
>>> c = ndt("10 * float32")
>>> p.match(c)
True

Ellipsis match¶

Finally, all dimension kinds (including multiple dimensions) match against ellipsis dimensions (named or unnamed):

>>> p = ndt("... * float64")
>>> c = ndt("10 * 2 * float64")
>>> p.match(c)
True

>>> p = ndt("Dim... * float64")
>>> c = ndt("10 * 20 * float64")
>>> p.match(c)
True

This is used in broadcasting [2].

[1]	An argument is often made that the term dependent types should be reserved for static type systems. We use it here while explicitly acknowledging that the datashape implementation is dynamically typed.

[2]	(1, 2) Additional section needed.