---

• Notions
• Examples
• Example 1. Non-Linear Patterns
• Example 2. Or-Patterns
• Example 3. And-Patterns
• Example 4. Not-Patterns
• Example 5. Application of Pattern Function Inside Pattern
• Pattern-Matching with Infinite Results

---

Notions

We introduce several notations to explain Egison pattern-matching mechanism.
Here is a really brief explanation of each notation.
We will deepen the understanding of these notions, examining the examples in the following sections.

Matching State

Egison's pattern-matching is reduction of a collection of matching states.
Each matching-state has a stack of matching-trees and data to proceed pattern-matching.

Matching Tree

A matching-tree has two kinds of forms, a matching-atom and a matching-node.

Matching Atom

A matching atom is a tuple of a pattern, a target, and a matcher.

Matching Node

A matching-node has a stack of matching-trees as a matching-state.
The structure of matching-node is similar with a matching state.

---

Examples

Example 1. Non-Linear Patterns

Let us examine what will happen when Egison evaluates following pattern-matching expressions.

(match-all {2 8 2} (multiset integer) [<cons $m <cons ,m _>> m]) ;=>{2 2}

At first, the initial matching-state is generated. It is as follow.
The data constructor MState takes three arguments, a stack of matching-trees, an environment, and a result in the middle of the pattern-matching.
The env is the environment when the evaluation process enters the match-all expression.
The stack of matching-tree contains a single matching-atom whose pattern, target and matcher are same with the arguments of match-all.

MState {[<cons $m <cons ,m _>> {2 8 2} (multiset integer)]} env {}

The stack of the matching-tree contains only one matching-atom.
This matching atom is reduced with the matcher (multiset integer) as specified in the matching-atom.
The matching-states increases to 3 with this reduction as follow.

MState {[$m 2 integer] [<cons ,m _> {8 2} (multiset integer)]} env {} MState {[$m 8 integer] [<cons ,m _> {2 2} (multiset integer)]} env {} MState {[$m 2 integer] [<cons ,m _> {2 8} (multiset integer)]} env {}

We focus on the first matching state, for now.
It is the following one.

MState {[$m 2 integer] [<cons ,m _> {8 2} (multiset integer)]} env {}

This matching-state is reduced as follow in the next reduction step.
The matcher of the matching-atom of the top of the stack is changed to something from integer.
something is the built-in matcher of Egison.
It can match with a wildcard or a pattern variable.

MState {[$m 2 something] [<cons ,m _> {8 2} (multiset integer)]} env {}

This matching-state is reduced as follow in the next reduction step.
The matching atom of the top of the stack is popped out, and a new binding [m 2] is appended to the result of the middle of pattern-matching.
something can only append a new binding to the result of pattern-matching.

MState {[<cons ,m _> {8 2} (multiset integer)]} env {[m 2]}

This matching-state is reduced as follow in the next reduction step.
The matching-states increases to 2 with this reduction.

MState {[,m 2 integer] [_ {8} (multiset integer)]} env {[m 2]} MState {[,m 8 integer] [_ {2} (multiset integer)]} env {[m 2]}

In the above matching-states, ,m is pattern-matched with 8 and 2 respectively as integer.
When we do pattern-matching with the value pattern, the result of the middle of pattern-matching is used to evaluate it.
Therefore, in this case, m is evaluated to 2.
The first matching-state fails to pattern-match.
The second matching-state succeeds in pattern-matching and be reduced as follow in the next reduction step.

MState {[_ {8} (multiset integer)]} env {[m 2]}

This matching-state is reduced as follow in the next reduction step.
The pattern is a wildcard and matches with any object.
No new binding is appended to the result of pattern-matching.

MState {} env {[m 2]}

When the matching-tree stack is empty, the reduction finish.
This result of pattern-matching {[m 2]} is added to the final result.

Example 2. Or-Patterns

Let us examine what will happen when our system evaluates the following pattern-matching expression.

(match-all {1 1 2} (list integer) [<cons $m (| <nil> <cons ,m _>)> m]) ;=>{1}

Our system reaches the following matching-state.

MState {[(| <nil> <cons ,m _>) {1 2} (list integer)]} env {[m 1]}

This matching-state is reduced as follow in the next reduction step.

MState {[<nil> {1 2} (list integer)]} env {[m 1]} MState {[<cons ,m _> {1 2} (list integer)]} env {[m 1]}

Example 3. And-Patterns

Let us examine what will happen when our system evaluates the following pattern-matching expression.

(match-all {1 2 3} (list integer) [<cons $n (& <cons _ _> $rs)> [n rs]]) ;=>{[1 {2 3}]}

Our system reaches the following matching-state.

MState {[(& <cons _ _> $rs) {2 3} (list integer)]} env {[n 1]}

This matching-state is reduced as follow in the next reduction step.

MState {[<cons _ _> {2 3} (list integer)] [$rs {2 3} (list integer)]} env {[n 1]}

Example 4. Not-Patterns

Let us examine what will happen when our system evaluates the following pattern-matching expression.

(match-all {2 8 2} (multiset integer) [<cons $m (& ^<cons ,m _> $rs)> [m rs]]) ;=>{[8 {2 2}]}

Our system reaches the following matching-state.

MState {[^<cons ,m _> {2 2} (multiset integer)] [$rs {2 2} (multiset integer)]} env {[m 8]}

When our system reaches the matching-state whose top matching-atom is a not-pattern, our system generates a new matching-state which contains only the matching-atom with the not-pattern as follow. All information of the matching-state and the matching-nodes except about the rest of matching-tree stack are retained.

MState {[<cons ,m _> {2 2} (multiset integer)]} env {[m 8]}

Our system proceeds the pattern-matching on the new generated matching-state, and if it fails pattern-matching our system pops out the matching-atom of the not-pattern from the original matching-state as follow and proceeds the pattern-matching. Otherwise our system fails the pattern-matching.

In this case, the above matching-state succeeds pattern-matching. Therefore, the matching-state with the not-pattern is reduced as follow.

MState {[$rs {2 2} (multiset integer)]} env {[m 8]}

Example 5. Application of Pattern Function Inside Pattern

We explain how our system deals with modularization of patterns with this example.
Let us examine what will happen when our system evaluates the following pattern-matching expression.

(define $twin (pattern-function [$pat1 $pat2] <cons (& $pat pat1) <cons ,pat pat2>>)) (match-all {1 2 1 3} (multiset integer) [<cons $m (twin $n _)> [m n]]) ;=>{[2 1] [3 1] [2 1] [3 1]}

Our system reaches the following matching-state.

MState {[(twin $n _) {1 1 3} (multiset integer)]} env {[m 2]}

This matching-state is reduced as follow in the next reduction step. A matching-node has extra information, a pattern-environment. In this case, the pattern-environment is {[pat1 $n] [pat2 _]}.

MState {(MNode {[<cons (& $pat pat1) <cons ,pat pat2>> {1 1 3} (multiset integer)]} env1 {} {[pat1 $n] [pat2 _]})} env {[m 2]}

Our system reaches the following matching-state. When the top of the matching-tree stack of the matching-state is a matching-node, our system pops the matching-atom of the top of the matching-tree stack of the matching-node. If the top of the matching-tree stack of the matching-node is a matching-node again, our system pops out the matching-atom from the top of the matching-tree stack of that matching-node.

MState {(MNode {[pat1 1 integer] [<cons ,pat pat2> {1 3} (multiset integer)]} env1 {[pat 1]} {[pat1 $n] [pat2 _]})} env {[m 2]}

This matching-state is reduced as follow in the next reduction step.
pat1 is called a variable-pattern.
It can appear only in the body of pattern-functions.
When the matching-atom whose pattern is a variable-pattern is popped out, our system gets what pattern is bound to the variable-pattern from the pattern-environment, and push a new matching-atom to the matching-tree stack of the one level upper matching-node or matching-state.

MState {[$n 1 integer] (MNode {[<cons ,pat pat2> {1 3} (multiset integer)]} env1 {[pat 1]} {[pat1 $n] [pat2 _]})} env {[m 2]}

The arguments of a pattern-function are handled in special way as above. This is the reason why the pattern-function can take only patterns. A pattern must be bound to a variable-pattern.

I'll stop the explanation of pattern-matching step here, for now.
I've explained most of the essential points, already.

Pattern-Matching with Infinite Results

We explain how our system executes pattern-matching which has infinite results. Let us examine what will happen when our system evaluate the following pattern-matching expression.

(take 10 (match-all nat (set integer) [<cons $m <cons $n _>> [m n]])) ;=>{[1 1] [1 2] [2 1] [1 3] [2 2] [3 1] [1 4] [2 3] [3 2] [4 1]}

The following picture is the reduction tree of matching-states when we execute the pattern-matching above. Rectangles stand for matching-states. The rectangle at the upper left is the initial matching-state. Circles stand for final matching-states that succeed pattern-matching.

The width of a reduction tree of matching-states can be infinite because there are cases that a matching-state is reduced to infinite matching-states. The depth of a reduction tree also can be infinite if we use a recursive pattern-function in a pattern. We need to think on the order of reduction to examine all nodes of a reduction tree. The numbers on rectangles and circles denote the order of reduction. If we see a reduction tree obliquely, it can be regarded as a binary tree. Therefore, we can trace all nodes of reduction trees if we do breadth-first search on the tree, though it will use a lot of memory.