The aim of this document is to explain the concept of Egison as quickly as possible.
We use pseudocode of Haskell to make it easy to understand for those who don't used to parenthesized syntax.

## Introduction

Pattern-matching is an important feature of programming languages.
Pattern-matching enables us to express data decomposition and conditional branches in a simple pattern-matching expression.

However, the existing pattern-matching expressions have a problem that they are only capable against the limited range of data types.
For example, they are good at pattern-matching against lists, but not good at pattern-matching against multisets and sets that ignore the order of the elements.
Therefore, there still exist data operations that we cannot express directly.

Egison is a programming language designed to solve this problem.

In the following sample code, we are enumerating the elements that appear multiple times in a collection.
If we write it in the existing languages in a naive way without using library functions, we need to write nested loops and a conditional branch.
If we write it in Egison, we can write it in a single pattern-matching expression.

Ruby version
Egison version

In the following sections, we will explain what is the novelty of Egison with specific examples.

## Syntax of Pattern-Matching

Let us introduce the syntax of the match-all expression.
We can explain the concept of Egison with only this expression.

Egison version

The characteristic of our match-all expression is it takes a matcher. Our interpreter matches the target with the pattern in the way specified with the matcher.
A matcher specifies the way of pattern-matching.

If we wrote the same meaning code in Haskell, it will be as follow. (The following code does not run because Haskell does not support such kind of syntax for now.)

## Modularization of the Way of Pattern-Matching

We can define the way of pattern-matching for each data type.
In the following example, we do pattern-matching against a collection as a list, multiset and set respectively.
The pattern constructor cons divides a collection into an element and the rest.
The meaning of cons varies for each matcher and is defined in Egison libraries for each matcher.

Egison version

Please note that we are handling pattern-matching with multiple results.
This feature is necessary to pattern-matching against data types whose data have no standard form such as multisets and sets.
This is because they have multiple ways of destruction.

We can extract two elements from a collection with the nested cons pattern.

Egison version

We have the join pattern constructor, which divides a collection into two collections.
The meaning of join also varies for each matcher and is defined in Egison libraries for each matcher.

Egison version

Let us emphasize that we can define matchers such as list, multiset and set and pattern-constructors such as cons and join by ourselves.

## Non-Linear Patterns

We can handle multiple occurrence of same variables in a pattern.
Patterns that have , ahead are called value-patterns.
In many cases, it is natural to check equality by a value-pattern.
We can define how to handle value-patterns for each data type in the matcher.

Egison version

Egison is purely functional programming language. We can directly handle pattern-matching against infinite collections as Haskell.
Please also note that, we can write an any expression in a value pattern.

Egison version

Non-linear patterns extend the expressive power of pattern-matching so much.
It eliminates deeply nested loops and conditional branches.
Please check our Poker Hands Demonstration.

We can do pattern-matching also against nested data types such as lists of sets and sets and sets. The following code enumerates common elements among collections inside a collection that contains three collections.

Egison version

## Lexical Scoping of Patterns

We can modularize useful patterns with pattern-functions, functions that receive patterns and return a pattern.
Since a pattern-function has lexical scoping, useful patterns can be reused in many places in a program without worry of name clash.

Egison version

This feature enables us to write complex patterns very simply.

## Conclusion

The combination of all of the following features realizes intuitive powerful pattern-matching.

Modularization of the way of pattern-matching
We can define the way of pattern-matching for each data types.
For example, we can define how to pattern-match against lists, multiset, and sets respectively.
Multiple pattern-matching results
We can handle pattern-matching that has multiple results with backtracking.
This feature is necessary to pattern-matching against data types whose data have no standard form.
Non-linear patterns
We can handle multiple occurrence of same variables in a pattern.
Lexical scoping of patterns
We can modularize useful patterns with pattern-functions, functions that receive patterns and return a pattern.
Since a pattern-function has lexical scoping, bindings for pattern-variables in the argument patterns and the body of pattern-functions don't conflict.
Useful patterns can be reused in many places in a program without worry of name clash.