2A Quick Tour of Egison

This chapter introduces Egison's features for pattern-match-oriented programming. Once you understand this chapter, you should have a nearly complete understanding of Egison's pattern matching specification.

The first half of this chapter (Sections 2.1, 2.2, 2.3, 2.4, and 2.5) introduces the syntax for pattern matching. Egison's pattern matching is designed to efficiently handle non-linear patterns (patterns that reference values bound to pattern variables within the same pattern) with multiple match results, in order to realize pattern matching on non-free data types. The first half of this chapter explains how this functionality is expressed as syntax.

The second half of this chapter (Sections 2.6, 2.7, 2.8, 2.9, and 2.10) introduces various built-in patterns. Among these, the loop patterns and sequential patterns introduced in the latter sections are patterns not yet implemented in any programming language other than Egison. These built-in patterns may seem specialized and ad hoc at first. It is not a problem if you do not fully understand the meaning of these built-in patterns on first encounter. Please come back to this chapter when practical examples of these patterns are introduced later in the book.

2.1Pattern Matching with matchAll Expressions

Egison provides several syntactic constructs for describing pattern matching. The most fundamental of these is the matchAll expression.

matchAll [1,2,3] as list something with
| $x :: $ts -> (x, ts)
-- [(1,[2,3])]

A matchAll expression consists of a target (in the above case, [1,2,3]), a matcher (in the above case, list something), and one or more match clauses (in the above case, $x :: $xs -> (x,xs)). A match clause consists of a pattern (in the above case, $x :: $xs) and a body (in the above case, (x,xs)). Like match expressions in existing programming languages, a matchAll expression attempts to pattern match the target against the pattern, and if it matches, evaluates the body of that match clause.

The distinguishing features of Egison's matchAll expression are (1) that it returns a list as the result, and (2) that it takes an additional argument called a matcher. Feature (1) is designed to support pattern matching with multiple results. A matchAll expression evaluates the body for all pattern matching results and collects them into a list. The :: used in the pattern of the above example is a pattern constructor called the cons pattern, which decomposes a list into its head element and the remaining list. Therefore, in the above example, since there is only one pattern matching result, it returns a list of length \(1\). Feature (2) enables extensibility and polymorphism of pattern matching algorithms. A matcher is a unique object not found in languages other than Egison, designed to hold pattern matching algorithms. Polymorphism of patterns through matchers is covered in Section 2.4. Lines beginning with -- are comments. In this book, comments immediately following a program indicate the execution result of that program.

Let us explain the grammar of matchAll expressions in a bit more detail. The matcher is enclosed by the keywords as and with. A matchAll expression can take multiple match clauses.matchAll \(t\) as \(m\) with \(c_1\) \(c_2\) \(...\)is equivalent to (matchAll \(t\) as \(m\) with \(c_1\)) ++ (matchAll \(t\) as \(m\) with \(c_2\)) ++ \(...\) Each match clause is preceded by |.When there are multiple match clauses, the | before the first match clause is also required. The | improves program readability when match clauses span multiple lines. The pattern and body within a match clause are separated by ->.

matchAll target as matcher with
| pattern1 -> body1
| pattern2 -> body2
...

When there is only one match clause, the | before the match clause can be omitted as follows.

matchAll target as matcher with pattern -> body

Let us introduce an example of pattern matching with multiple results. The ++ used in the pattern of the matchAll expression below is a pattern constructor called the join pattern, which decomposes a list into a prefix list and the remaining list. The matchAll expression evaluates the body expression for all decompositions produced by the join pattern.

matchAll [1,2,3] as list something with
| $hs ++ $ts -> (hs, ts)
-- [([], [1, 2, 3]), ([1], [2, 3]), ([1, 2], [3]), ([1, 2, 3], [])]

2.2Non-Linear Patterns via Value Patterns and Predicate Patterns

The matchAll expression reveals its true power when combined with non-linear patterns. For example, the following non-linear pattern succeeds in matching when the target collection contains a pair of equivalent elements.

matchAll [1,2,3,2,4,3] as list integer with
| _ ++ $x :: _ ++ #x :: _ -> x
-- [2,3]

The value pattern plays an important role in expressing non-linear patterns. A value pattern checks whether its content is equal to the target. A value pattern is prefixed with #. Any expression can follow the #. The expression following # is evaluated while referencing values bound to pattern variables that appear to the left of that value pattern. To realize this behavior, Egison's patterns are defined to be processed in order from left to right. As a result, a pattern like $x :: #x :: _ is valid, but #x :: $x :: _ does not work correctly. (If you really need to reference the value of a pattern variable appearing to the right, you can use sequential patterns, introduced in Section 2.8.)

As another example of non-linear patterns, we introduce pattern matching for twin primes. Twin primes are pairs of primes whose difference is 2. The infinite sequence of primes is bound to primes.primes is defined in Egison's built-in library. This matchAll expression extracts all twin primes from the infinite sequence of primes in order. Egison has a static type system, but type annotations can be omitted thanks to type inference. When needed, types can be explicitly specified as in def twinPrimes : [(Integer, Integer)] := ....

def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

take 8 twinPrimes
-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]

Sometimes we want to use conditions more general than equality in pattern matching. The predicate pattern is a built-in pattern provided for this purpose. A predicate pattern succeeds in matching when the result of applying its predicate to the target is True. A predicate pattern begins with ?, followed by a single-argument predicate.

def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: ?(\q -> q = p + 2) :: _ -> (p, p + 2)

2.3Efficient Non-Linear Pattern Matching via Backtracking

The pattern matching algorithm inside Egison uses backtracking to efficiently process non-linear patterns.

matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ -> x
-- `\color{P@GrayComment}{Returns}` [] `\color{P@GrayComment}{in O(n\^{}2)}`
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x
-- `\color{P@GrayComment}{Returns}` [] `\color{P@GrayComment}{in O(n\^{}2)}`

The two match expressions above extract pairs and triples, respectively, of identical elements from a list of integers from \(1\) to \(n\). Since neither pairs nor triples of identical elements exist in the target list, both matchAll expressions return the empty list. When the second matchAll expression is evaluated, the Egison interpreter never reaches the second #x pattern. This is because the match fails at the first #x. (As stated in Section 2.2, Egison's pattern matching processes patterns from left to right in order.) Therefore, the time complexity of both matchAll expressions is the same. The pattern matching algorithm inside Egison is explained in detail in Chapter 5.

2.4Extensibility and Polymorphism of Patterns via Matchers

In addition to pattern extensibility, another benefit that matchers provide is ad hoc polymorphism of patterns. Ad hoc polymorphism of patterns is the property that pattern constructors such as :: and ++ can be used with the same name across multiple matchers such as lists and multisets. Ad hoc polymorphism of patterns is extremely important in Egison, which allows pattern matching on various non-free data types. This is because a single piece of data is often pattern matched as different non-free data types at different points in a program. For example, a list may be pattern matched as a multiset or a set. Polymorphism of patterns can significantly reduce the number of pattern constructor names.

The matchAll expressions below pattern match the collection [1,2,3] as a target, using different matchers with the same cons pattern. We use the term collection here, but this refers to what we have been calling lists. A collection may be pattern matched as a list, a multiset, or a set. Therefore, we henceforth use the term collection to refer collectively to data that may be treated as a list, multiset, set, and so on. When the matcher is a list, the cons pattern decomposes the collection into the head element and the remaining collection. When the matcher is a multiset, the cons pattern decomposes the collection into some element and the remaining collection. When the matcher is a set, the cons pattern decomposes the collection into some element and the target collection itself. This behavior for sets can be considered natural if we think of a set as a collection containing infinitely many copies of every element. (Think of it as \(\infty - 1 = \infty\).)

matchAll [1,2,3] as list something with $x :: $xs -> (x,xs)
-- [(1,[2,3])]
matchAll [1,2,3] as multiset something with $x :: $xs -> (x,xs)
-- [(1,[2,3]),(2,[1,3]),(3,[1,2])]
matchAll [1,2,3] as set something with $x :: $xs -> (x,xs)
-- [(1,[1,2,3]),(2,[1,2,3]),(3,[1,2,3])]

Polymorphism of patterns is especially useful when expressing value patterns. Like constructor patterns such as the cons pattern, the behavior of value patterns also varies depending on the matcher. For example, the equality of collections such as [1,2,3] == [2,1,3] depends on whether the collection is regarded as a list or a multiset. However, in Egison, thanks to ad hoc polymorphism of patterns, both equalities can be checked using the same pattern. Polymorphism of value patterns significantly improves the readability of programs that deal with non-free data types.

matchAll [1,2,3] as list integer with #[2,1,3] -> "Matched" -- []
matchAll [1,2,3] as multiset integer with #[2,1,3] -> "Matched" -- ["Matched"]

2.5Controlling the Order of Pattern Matching Results with matchAllDFS

The internal pattern matching algorithm of the matchAll expression is designed to enumerate all countably infinite results, but the order of enumeration is determined by the interpreter. In some cases, this order matters.

Let us introduce a typical example. The following matchAll expression enumerates all pairs of natural numbers. The take function is used to extract the first \(8\) pairs. matchAll performs a breadth-first search to traverse all nodes of the pattern matching search tree.The details of this breadth-first search are explained in Section 5.2 of the paper on Egison pattern matching design [1]. As a result, the order of pattern matching results is as follows.

take 8 (matchAll [1..] as set something with
        | $x :: $y :: _ -> (x,y))
-- [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(2,3),(3,2)]

The above order is suitable for traversing a search tree that may be infinitely large. However, there are situations where this order is not desirable. matchAllDFS, which performs a depth-first search of the pattern matching search tree, is provided for such situations.

take 8 (matchAllDFS [1..] as set something with
        | $x :: $y :: _ -> (x,y))
-- [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8)]

For example, when defining the concat function via pattern matching as shown below, using a matchAllDFS expression allows the result collection to be generated in the correct order.

def concat xss := matchAllDFS xss as list (list something) with
  | _ ++ (_ ++ $x :: _) :: _ -> x

If matchAll were used instead of matchAllDFS, the elements of the argument's list of lists would be enumerated in an interleaved fashion as follows.

take 10 (matchAll [[1..], map neg [1..]] as list (list something) with
         | _ ++ (_ ++ $x :: _) :: _ -> x)
--  [1,2,-1,3,-2,4,-3,5,-4,6]

2.6And-Patterns, Or-Patterns, and Not-Patterns

Logical patterns such as and-patterns, or-patterns, and not-patterns play an important role in expanding the expressiveness of patterns. An and-pattern takes two patterns and succeeds in matching when both patterns match. An or-pattern takes two patterns and succeeds in matching when either one of the patterns matches. A not-pattern takes one pattern and succeeds in matching when that pattern fails to match.

As an example of and-patterns and or-patterns, we introduce pattern matching for extracting prime triples. A prime triple is a triple of primes of the form \((p,p+2,p+6)\) or \((p,p+4,p+6)\). The or-pattern (#(p + 2) | #(p + 4)) is used to match both \(p+2\) and \(p+4\). The and-pattern ((#(p + 2) | #(p + 4)) & $m) is used to bind the matched value (either \(p+2\) or \(p+4\)) to $m. This use of the and-pattern is similar to the use of as-patterns provided in Haskell.

def primeTriples := matchAll primes as list integer with
  | _ ++ $p :: ((#(p + 2) | #(p + 4)) & $m) :: #(p + 6) :: _
  -> (p, m, p + 6)

take 6 primeTriples -- [(5,7,11),(7,11,13),(11,13,17),(13,17,19),(17,19,23),(37,41,43)]

A not-pattern, as its name suggests, succeeds in matching when the target does not match the pattern. A not-pattern is prefixed with !, followed by an arbitrary pattern. The following matchAll enumerates pairs of adjacent primes that are not twin primes. The not-pattern !#(p + 2) represents a pattern that matches any value other than \(p+2\).

take 10 (matchAll primes as list integer with
         | _ ++ $p :: (!#(p + 2) & $q) :: _ -> (p, q))
-- [(2,3),(7,11),(13,17),(19,23),(23,29),(31,37),(37,41),(43,47),(47,53),(53,59)]

2.7Loop Patterns

The loop pattern is a built-in pattern for expressing multiple repetitions of a pattern. Loop patterns are an extension of the Kleene star operator (*) in regular expressions.

Let us begin by considering a pattern match that enumerates all 2-element combinations from a target collection. This can be written with the following matchAll expression.

def comb2 xs := matchAll xs as list something with
  | _ ++ $x_1 :: _ ++ $x_2 :: _ -> [x_1, x_2]

comb2 [1,2,3,4] -- [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]]

Egison allows subscripts to be appended to pattern variables, as in $x_1 and $x_2 in this example.Because of this, snake_case variable naming cannot be used in Egison. These are called indexed variables and correspond to mathematical expressions like \(x_1\) and \(x_2\). The expression following _ is called a subscript and must evaluate to an integer. An arbitrary number of subscripts can be appended to a variable, as in x_i_j_k. When a value is bound to an indexed variable $x_i, if no value has yet been bound to the variable x, the Egison interpreter creates an associative array and binds it to x. The key of this associative array is the integer i, and the corresponding value is the value matched by the indexed variable $x_i. If an associative array is already bound to the variable x, a new key-value pair is added to this associative array.

Let us generalize the \(2\) in the above comb2 to \(n\). Here, we can use a loop pattern.

def comb n xs := matchAll xs as list something with
             | loop $i                 -- `\color{P@GrayComment}{index variable}`
                    (1, n)             -- `\color{P@GrayComment}{index range}`
                    (_ ++ $x_i :: ...) -- `\color{P@GrayComment}{repeat pattern}`
                    _                  -- `\color{P@GrayComment}{terminal pattern}`
             -> map (\i -> x_i) [1..n]

comb 2 [1,2,3,4] -- [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]]
comb 3 [1,2,3,4] -- [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

A loop pattern takes an index variable, an index range, a repeat pattern, and a terminal pattern as arguments. The index variable (in the above case, $i) is a variable that holds the current iteration count. The index range (in the above case, (1, n)) is used to specify the range over which the index variable varies. The index range is a pair of a start value and an end value. The repeat pattern (in the above case, (_ ++ $x_i :: ...)) is the pattern that is repeated while the index variable is within the index range. The terminal pattern (in the above case, _) is the pattern that is expanded when the index variable moves outside the index range. Within the repeat pattern, the ellipsis pattern ... can be used. The repeat pattern or terminal pattern is expanded at the position of the ellipsis pattern. When the repeat pattern is expanded at an ellipsis pattern, the value of the index variable is incremented. For example, when \(n=3\), the above loop pattern is expanded as follows.

(loop $i (1, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: (loop $i (2, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: (loop $i (3, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: _ ++ $x_3 :: (loop $i (4, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: _ ++ $x_3 :: _

In the above loop pattern, the number of repetitions was a constant. However, by making the end value of the index range a pattern instead of an integer value, the number of repetitions of the loop pattern can vary depending on the target. When the end value of the index range is a pattern, the ellipsis pattern is expanded into both the repeat pattern and the terminal pattern. The number of repetitions when the ellipsis pattern is expanded into the terminal pattern is matched against the end value pattern of the index range. The following loop pattern enumerates the prefixes of the target collection.

matchAll [1,2,3,4] as list something with
| loop $i (1, $n) ($x_i :: ...) _ -> map (\i -> x_i) [1..n]
-- [[],[1],[1,2],[1,2,3],[1,2,3,4]]

We have introduced two types of index range specification above, but these are expanded into the following more general form of index range specification. (1, n) corresponds to the third case below, and (1, $n) corresponds to the fourth case below.

(`start`)                  <=> (`start`, [`start`..], _)
(`start`, `end-list`)      <=> (`start`, `end-list` _)
(`start`, `end`)           <=> (`start`, [`end`] _)
(`start`, `terminal-pat`)  <=> (`start`, [`start`..], `terminal-pat`)

In general, an index range consists of three components: a start value, a list of end values, and a terminal pattern. The start value cannot be omitted. When the list of end values is omitted, an infinite list starting from the start value is used as the list of end values. When the list of end values is not a list but a single integer value, it is converted to a list containing only that integer value. When the terminal pattern is omitted, a wildcard is filled in. For example, (1, n) is expanded to (1, [n], _), and (1, $n) is expanded to (1, [1..], $n), respectively.

Loop patterns are used especially often when pattern matching on trees and graphs. Examples of this are introduced in Section 3.4 of Chapter 3. The formal syntax and semantics of loop patterns are described in the paper on loop patterns [2].

2.8Sequential Patterns

The Egison interpreter processes patterns from left to right in order. However, there are cases where one wants to change this processing order, such as when wanting to reference the value of a pattern variable bound on the right side of the pattern. The sequential pattern is a built-in pattern provided for this purpose.

A sequential pattern allows the user to change the order in which pattern matching is processed. A sequential pattern is represented as a list of patterns. Pattern matching is executed in order from the head of the list. The following sequential pattern matches the target list in the order of the third element, the first element, and the second element.

matchAll [2,3,1,4,5] as list integer with
| {     @    ::     @    :: $x :: _,
   (#(x + 1),       @    ),
                 #(x + 2)}
-> "Matched" -- ["Matched"]

The @ appearing in a sequential pattern is called a later pattern variable. The target bound to a later pattern variable is pattern matched by the pattern in the next element of the sequential pattern. When multiple later pattern variables appear, the next sequence matches them collectively as a tuple.

This feature of sequential patterns makes it possible to apply a not-pattern collectively to multiple separate parts of a pattern. For example, the following sequential pattern succeeds in matching when the pair of target collections contains exactly one common element. The sequential pattern enables checking that the respective collections share a common element, and then checking that the remaining collections have no further common elements. The combination of sequential patterns and not-patterns appears when describing mathematical algorithms. For example, it also appears in Section 4.1 of Chapter 4.

def singleCommonElem xs ys := match (xs, ys) as (multiset eq, multiset eq) with
| {($x :: @, #x :: @),
   !($y :: _, #y :: _)} -> True
| _ -> False

Some readers may have wondered whether the same thing as a sequential pattern can be expressed by nesting matchAll expressions. In fact, this is impossible for at least two reasons. The first reason stems from the fact that nested matchAll expressions break Egison's internal breadth-first search. The second result of the outer matchAll expression is computed only after all results of the inner matchAll expression for the first result of the outer expression have been evaluated. The second reason is that later pattern variables preserve not only the target but also the matcher information. The matcher argument of matchAll may be a parameter originating from a function argument. Therefore, the matcher that should be used in the inner matchAll expression may not be syntactically derivable.

2.9Modularizing Patterns with Pattern Functions

Pattern constructors such as the cons pattern and the join pattern are defined in matchers, as explained in Chapter 6. These pattern constructors can be combined to create new pattern constructors. To do this, one uses a pattern function, which takes patterns as arguments and returns a pattern.

A pattern function is defined with the def pattern statement. After the name come type parameters ({a}), parameters with type annotations, and, after :, the type targeted by the pattern that the application produces. The pattern function twin defined below modularizes a doubly nested cons pattern that matches when the first elements are equal. The formal parameters of a pattern function are called variable patterns. In this example, the variable patterns are pat1 and pat2. The parameter annotation (pat1: a) says that pat1 is a pattern that matches values of type a. When referencing the content of a variable pattern in the body of a pattern function, ~ is prefixed to the variable pattern. This is to distinguish variable patterns from pattern constructors.

def pattern twin {a} (pat1: a) (pat2: [a]) : [a] :=
  (~pat1 & $x) :: #x :: ~pat2

This twin pattern function behaves as follows.

match [1, 1, 2, 3] as list integer with
| twin $n $ns -> (n, ns)
-- (1, [2, 3])

Type checking of pattern functions is explained in Section 6.12 of Chapter 6.

2.10Generating New Matchers via Matcher Composition

Except for something, which is Egison's only built-in matcher, all matchers that have appeared so far can be defined by users. The basic way to define a matcher is to use the matcher expression explained in Chapter 6, but new matchers can also be created by combining existing matchers. Using this method, for example, one can define a matcher for tuples of multisets or a matcher for multisets of multisets.

A matcher for tuples is represented by a tuple of matchers. A tuple pattern is used for pattern matching with such matchers. For example, the following is the definition of the intersect function, which also appeared in Section 1.2 of Chapter 1. It uses a matcher for a tuple of two sets to extract common elements of collections via pattern matching.

def intersect xs ys := matchAll (xs,ys) as (set eq, set eq) with
  | ($x :: _, #x :: _) -> x

The eq matcher used above is a user-defined matcher that can be used for pattern matching on data types with defined equality.The type of the eq matcher is {Eq a} => Matcher a; it is usable at any type with an Eq instance (Section 6.8 of Chapter 6). When a value pattern is used with the eq matcher, pattern matching is performed by checking equality.

Furthermore, by combining tuple matchers with functions that take matchers as arguments and return matchers, one can define matchers for various non-free data types. For example, when representing each node of a graph as an integer and each edge as a pair of two nodes, a matcher representing a directed graph can be defined as a multiset of edges as follows.

def graph := multiset (integer, integer)

A matcher for a graph represented by an adjacency list can also be defined. A graph represented by an adjacency list is defined as a multiset of tuples, each consisting of an integer and a multiset of integers. Here again, node IDs are represented by integers.

def adjacencyGraph := multiset (integer, multiset integer)

Matchers for algebraic data types can also be defined using the matcher expression, but Egison provides a special syntax algebraicDataMatcher that allows matchers for algebraic data types to be defined with a concise description. The algebraicDataMatcher expression is syntactic sugar that desugars into a matcher expression. Using algebraicDataMatcher, for example, a matcher for binary trees can be defined as follows.

def binaryTree a := algebraicDataMatcher
  | bLeaf a
  | bNode a (binaryTree a) (binaryTree a)

Matchers for algebraic data types and matchers for non-free data types can also be combined. For example, a matcher for a tree with an arbitrary number of children that ignores the order of children can be defined as follows. Pattern matching on this tree is introduced in Section 3.4 of Chapter 3.

def tree a := algebraicDataMatcher
  | leaf a
  | node a (multiset (tree a))