In Egison, every pattern matching algorithm is defined by matchers. list, multiset and set are matchers too, which are defined in standard libraries.
This chapter explains how users can define their original matchers.

---

• matcher
• algebraic-data-matcher

---

matcher Expression

  (matcher {[pppattern matcher {[pdpattern formula] ...}] ...})
  pppattern (primitive pattern pattern) ::= _ | $ | ,$value | <identifier pppattern ...> | [pppattern ... ]
  pdpattern (primitive data pattern) ::= _ | $identifier | <Identifier pdpattern ...> | [pdpattern ... ] | constants

Let's think about defining a matcher unordered-integer-pair, which matches with a tuple of 2 integers but ignores the order.

(match-all [1 2] unordered-integer-pair {[<pair $a $b> [a b]]}) ;=>{[1 2] [2 1]}

This unordered-integer-pair matcher can be defined as follows.

(define $unordered-integer-pair (matcher {[<pair $ $> [integer integer] {[[$x $y] {[x y] [y x]}]}] [$ something {[$tgt {tgt}]}]}))

Line 3 and 4 corresponds with the case where we want to decompose the tuple, and line 5 and 6 is for the case where we don't want to.
The expression <pair $ $> in line 3 defines a pattern constructor named pair, which enables the pattern expression like <pair $a $b>. The following [integer integer] indicates that the both of matched 2 terms should be recursively pattern-matched by using integer matcher.
The expression [[$x $y] {[x y] [y x]}] in line 4 defines the correspondense between the syntastic representation of the target data and pattern matching results.
In the example above, the target data [1 2] is syntastically matched with [$x $y], making the variable x bound to 1 and y to 2. As a result, the pattern matching result (specified with {[x y] [y x]}) will be {[1 2] [2 1]}. Then, variable a and b in the pattern expression <pair $a $b> are bound to one of the pattern matching result. Since it is a match-all expression, this binding enumrates for the entire results, meaning that first a is bound to 1 and b to 2, and secondly a to 2 and b to 1.

In addition, we can make a "polymorphic" matcher by making it a function that takes matchers and returns a matcher. For example, unordered-pair for an arbitrary matcher can be defined as follows:

(define $unordered-pair (lambda [$m] (matcher {[<pair $ $> [m m] {[[$x $y] {[x y] [y x]}]}] [$ something {[$tgt {tgt}]}]}))) ; Example (match [{1 2} {3 4}] (unordered-pair (multiset integer)) {[<pair <cons ,4 _> _> #t]}) ;=>#t

algebraic-data-matcher Expression

  (algebraic-data-matcher {<identifier matcher ...> ...})

algebraic-data-matcher is a convenient syntax sugar for defining normal matchers, which decompose data accordingly to their data structure.
For example, the following code defines a matcher for terms in untyped lambda calculus.

(define $term (algebraic-data-matcher {<var string> ; variable <abs string term> ; abstraction <app term term> ; application }))

The above definition is desugared into the following one:

(define $term (matcher {[<var $> [string] {[<Var $x> {x}] [_ {}]}] [<abs $ $> [string term] {[<Abs $x $t> {[x t]}] [_ {}]}] [<app $ $> [term term] {[<App $s $t> {[s t]}] [_ {}]}] [$ [something] {[$tgt {tgt}]}]}))

---

If you are interested in how our pattern matching works, please check out the chapter Pattern Matching Mechanism.

What to do next...

Next Chapter: Basics of IO Top of Manual Back to Home