Egison Blog

The Ruby Gem for Ultra Super Pattern Matching

June 16, 2014

I've implemented a Ruby Gem that provides the ultra super pattern-matching to Ruby. We can directly express non-linear pattern-matching against lists, multisets, and sets using this gem. Today, I'd like introduce the power of this gem.

This is open source software. You can access the source code on GitHub.



Installation

$ gem install egison

or

$ gem install bundler (if you need)
$ echo "gem 'egison'" > Gemfile
$ bundle install

Basic Usage

The library provides Kernel#match_all and Kernel#match.

A object, the argument of the match-all or match expression is pattern-matched with a pattern, the argument of with.

If a pattern matches, a block passed to with is called and returns its result.

In our pattern-matching system, there are cases that pattern-matching has multiple results. match_all calls the block passed to with for each pattern-matching result and returns all results as an array. match_all takes one single match-clause.

On the other hand, match takes multiple match-clauses. It pattern-matches from the first match-clause. If a pattern matches, it calls the block passed to the matched match-clause and returns a result for the first pattern-matching result.

Let's Try Pattern Matching!

Element patterns and subcollection patterns

An element pattern matches the element of the target array.

A subcollection pattern matches the subcollection of the target array. A subcollection pattern has * ahead.

A literal that contain _ ahead is a pattern-variable. We can refer the result of pattern-matching through them.

Three matchers: List, Multiset, Set

We can write pattern-matching against lists, multisets, and sets. When we regard an array as a multiset, the order of elements is ignored. When we regard an array as a set, both of the duplicates and order of elements are ignored.

_ is a wildcard. It matches with any object. Note that __ and ___ are also interpreted as a wildcard. This is because _ and __ are system variables and sometimes have its own meaning in IRB.

Note that _[] is provided as syntactic sugar for List.().

Non-linear patterns

Non-linear pattern is the most important feature of our pattern-matching system. Our pattern-matching system allows users multiple occurrences of same variables in a pattern. A Pattern whose form is __("...") is a value pattern. In the place of ..., we can write any ruby expression we like. It matches the target when the target is equal with the value that ... evaluated to.

When, the expression in the place of ... is a single variable, we can omit (" and ") as follow.

Pattern Matching against Stream (Infinite List)

We can do pattern-matching against streams with the match_stream expression. This feature is implemented by antimon2.

Demonstrations

Combinations

We can enumerates all combinations of the elements of a collection with pattern-matching.

Poker Hands

We can write patterns for all poker-hands in one single pattern. It is as follow. Isn't it exciting?

Twin Primes

The following code enumerates all twin primes with pattern-matching! I believe it is also a really exciting demonstration.

Background

The system that realizes pattern-matching above is based on the theory of the Egison programming language. Egison is the pattern-matching-oriented, pure functional programming language. Actually, the expressive power of the original pattern-matching of Egison is more powerful. For example, we can do following things in the original Egison.

  • We can define new pattern-constructors.
  • We can modularize useful patterns.

There is a new programming world! Please try it, too!


This website in other langauge: English, 日本語