pattern-matching.md

Pattern Matching

Switches on many numbers are compiled to sequences of simple switch expressions:

  # These two are equivalent
  switch n {
    0: A
    1: B
    2: C
    _: (D n-3)
  }

  switch n {
    0: A
    _: switch n-1 = n-1 {
      0: B
      _: switch n-2 = n-1-1 {
        0: C
        _: use n-3 = n-2-1; (D n-3)
      }
    }
  }

Matches on ADT constructors are compiled to different expressions depending on the chosen encoding:

type Maybe = (Some val) | None

UnwrapOrZero x = match x {
  Maybe/Some: x.val
  Maybe/None: 0
}

# If the current encoding is 'adt-num-scott' it becomes:
Maybe/Some = λval λx (x 0 val)
Maybe/None = λx (x 1)
UnwrapOrZero x = (x λtag switch tag {
  0: λx.val x.val
  _: λ* 0
})

# Otherwise, if the current encoding is 'adt-scott' it becomes:
Maybe/Some = λval λMaybe/Some λMaybe/None (Maybe/Some val)
Maybe/None = λMaybe/Some λMaybe/None Maybe/None
UnwrapOrZero x = (x λx.val x.val 0)

Pattern Matching functions

Besides matchand switch terms, Bend also supports equational-style pattern matching functions.

And Bool/True  b = b
And Bool/False * = Bool/False

There are advantages and disadvantages to using this syntax. They offer more advanced pattern matching capabilities and also take care linearizing variables to make sure that recursive definitions work correctly in strict evaluation mode, but take away your control of how the pattern matching is implemented and can be a bit more resource intensive in some cases.

Pattern matching equations are transformed into a tree of match and switch terms from left to right.

# These two are equivalent
(Foo 0 Bool/False (List/Cons h1 (List/Cons h2 t))) = (Bar h1 h2 t)
(Foo 0 * *) = Baz
(Foo n Bool/False *) = n
(Foo n Bool/True *) = 0

Foo = λarg1 λarg2 λarg3 (switch arg1 {
  0: λarg2 λarg3 match arg2 {
    Bool/True: λarg3 Baz
    Bool/False: λarg3 match arg3 {
      List/Cons: (match arg3.tail {
        List/Cons: λarg3.head (Bar arg3.head arg3.tail.head arg3.tail.tail)
        List/Nil: λarg3.head Baz
      } arg3.head)
      List/Nil: Baz
    }
  }
  _: λarg2 λarg3 (match arg2 {
    Bool/True: λarg1 0
    Bool/False: λarg1 arg1
  } arg1)
} arg2 arg3)

Besides the compilation of complex pattern matching into simple match and switch expressions, this example also shows how some arguments are pushed inside the match. When compiling for strict evaluation, by default any variables that are used inside a match get linearized by adding a lambda in each arm and an application passing its value inwards. To ensure that recursive pattern matching functions don't loop in strict mode, it's necessary to make the match arms combinators, so that they can be converted into separate functions and a lazy reference is used in the match arm.

# This is what the Foo function actually compiles to.
# With -Olinearize-matches and -Ofloat-combinators (default on strict mode)
# Main function
(Foo) = λa λb λc (switch a { 0: Foo__C8; _: Foo__C9; } b c)

# Case 0 branch
(Foo__C8) = λa λb (a Foo__C5 b)                       # Foo.case_0
(Foo__C5) = λa switch a { 0: λ* Baz; _: Foo__C4; }    # Foo.case_0.case_true
(Foo__C4) = λ* λa (a Foo__C3)                         # Foo.case_0.case_false
(Foo__C3) = λa switch a { 0: Baz; _: Foo__C2; }       # Foo.case_0.case_false_cons
(Foo__C2) = λ* λa λb (b Foo__C1 a)                    # Foo.case_0.case_false_cons_cons
(Foo__C1) = λa switch a { 0: λ* Baz; _: Foo__C0; }    # Foo.case_0.case_false_cons_nil
(Foo__C0) = λ* λa λb λc (Bar c a b)                   # Foo.case_0.case_false_nil

# Case non-zero branch
(Foo__C9) = λa λb λc (b Foo__C7 c a)                  # Foo.case_+
(Foo__C7) = λa switch a { 0: λ* λ* 0; _: Foo__C6; }   # Foo.case_+.case_false
(Foo__C6) = λ* λ* λa (+ a 1)                          # Foo.case_+.case_true

# As an user, you can't write a function with __ on its name, that sequence is reserved for things generated by the compiler.

Pattern matching equations also support matching on non-consecutive numbers:

Parse '(' = Token.LParenthesis
Parse ')' = Token.RParenthesis
Parse 'λ' = Token.Lambda
Parse  n  = (Token.Name n)

The compiler transforms this into an optimized cascade of switch expressions. Each switch computes the distance from the smallest character to efficiently test each case:

Parse = λarg0 switch matched = (- arg0 '(') {
  0: Token.LParenthesis
  # ')' + 1 - '(' is resolved during compile time
  _: switch matched = (- matched-1 ( ')'-1-'(' ) {
    0: Token.RParenthesis
    _: switch matched = (- matched-1 ( 'λ'-1-')' ) {
      0: Token.Lambda
      _: use n = (+ 1 matched-1); (Token.Name n)
    }
  }
}

Unlike with switch, with pattern matching equations you can't access the value of the predecessor of the matched value directly, but instead you can match on a variable. Instead, variables (like n above) are bound to computed expressions based on the matched value. Notice how in the example above, n is bound to (+ 1 matched-1).

Notice that this definition is valid, since * will cover both p and 0 cases when the first argument is False.This example shows how patterns are considered from top to bottom, with wildcards covering multiple specific cases:

pred_if Bool/False * if_false = if_false
pred_if Bool/True  p *        = (- p 1)
pred_if Bool/True  0 *        = 0

Pattern matching on strings and lists desugars to a list of matches on Cons and Nil

Hi "hi" = 1
Hi _ = 0

Foo [] = 0
Foo [x] = x
Foo _ = 3

# Becomes:
Hi (String/Cons 'h' (String/Cons 'i' String/Nil)) = 2
Hi _ = 0

Foo List/Nil = 0
Foo (List/Cons x List/Nil) = x
Foo _ = 3