ANN: Optimized Pattern Matching Library for Clojure

[David Nolen]

Ambrose and I have been working on a high performance pattern matching library for Clojure. There's much left to do but it's already in a place where it's fun to play around with and we think some of you might even find it useful even in this early form.

Some highlights:

* Literal patterns

* Seq patterns with rest support

* Map patterns, can constrain keys with only

* Bindings can be introduced anywhere a wildcard might appear

* No type constraints on columns

* Lazy pattern matching semantics a la Haskell

This library implements Maranget's fascinating description for compiling pattern matching into good decision trees. Suffice to say, this library is pretty darn fast. 

We look forward to hearing your feedback. For code, more documentation, and where we are heading you can look here:

https://github.com/swannodette/match

David

[Tuba Lambanog]

Awesome!

Thanks for the great work.

Tuba

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[László Török]

David, this looks great!

sent from my mobile device

[Max Penet]

Thanks! This looks really good.

I hope this ends up in contrib at some point, also looking forward to
its extension (guards & co).

[Sam Aaron]

Exciting stuff!

Do you happen to have any simple descriptions/examples of where and how we might use this stuff in our daily programming repertoires? I for one am sure I'm not educated enough as to the value and utility of pattern matching - at the moment I just think "that looks cool" rather than "I'm definitely going to use that to do X and Y".

Sam

---
http://sam.aaron.name

[Baishampayan Ghose]

> Do you happen to have any simple descriptions/examples of where and how we might use this stuff in our daily programming repertoires? I for one am sure I'm not educated enough as to the value and utility of pattern matching - at the moment I just think "that looks cool" rather than "I'm definitely going to use that to do X and Y".

To me pattern matching is the bee's knees :) If you have a lot of
functions where you check the input for some certain type of value and
then perform some action depending on the value(s), then pattern
matching can be very useful. It's used extensively in Erlang and
Haskell among others.

For example, say you have a function `decide` -

(defn decide
"A very simple example using cond"
[x y]
(cond
(= x :foo) (do-foo y)
(= x :bar) (do-bar y)
:else (do-default y)))

I expect two arguments x & y and depending on the value of `x`, I
would like to call the functions `do-foo`, `do-bar` or `do-default`
with the value of `y`.

See how the code is riddled with the conditional checks and my
business logic (the part I care the most about). Using
pattern-matching, I can write the above code a bit more succinctly
like this -

(defn decide
"A very simple example using match"
[x y]
(match [x y]
[:foo arg] (do-foo arg)
[:bar arg] (do-bar arg)
[_ arg] (do-default arg)))

The above code is *much* clearer and conveys the exact logic that I am
trying to implement. Internally `match` will rewrite the above to an
optimised bit of code which uses `cond`.

If I am feeling adventurous, I can write a simple macro which will let
me define the same function in an even more succinct manner like this
-

(defm decide
"A very simple example"
([:foo arg]
(do-foo arg))
([:bar arg]
(do-bar arg))
([_ arg]
(do-default arg)))

A sample implementation of the `defm` macro used above could be
something like this (UNTESTED!) -

(defmacro defm
[name & fdecl]
(let [m (if (string? (first fdecl))
{:doc (first fdecl)}
{})
fdecl (if (string? (first fdecl))
(next fdecl)
fdecl)
argcount (count (ffirst fdecl))
args (vec (repeatedly argcount (partial gensym "arg__")))
body (apply concat
(for [decl fdecl]
(if (nnext decl)
(cons (first decl) (list (cons `do (next decl))))
decl)))]
`(defn ~name
~m
~args
(match ~args
~@body))))

It's even more awesome when you bring in complex maps, etc. into the picture.

I personally believe that David and Ambrose are doing some incredible
work with match & core.logic; these two projects will prove be
extremely useful in the future.

Regards,
BG

--
Baishampayan Ghose
b.ghose at gmail.com

[Edmund]

That's a great explanation Baishampayan, thanks !

Edmund

[Ambrose Bonnaire-Sergeant]

Hi Sam,

On Tue, Aug 9, 2011 at 3:50 PM, Sam Aaron <sama...@gmail.com> wrote:

Do you happen to have any simple descriptions/examples of where and how we might use this stuff in our daily programming repertoires?

Think of pattern matching sugar for nested conditionals.

For example

(match [x y]

       [1 0] 0

       [0 1] 1)

expands to:

(cond

  (= x 0) (cond

            (= y 1) 1

            :else (throw (java.lang.Exception. "Found FailNode")))

  (= x 1) (cond

            (= y 0) 0

            :else (throw (java.lang.Exception. "Found FailNode")))

  :else (throw (java.lang.Exception. "Found FailNode")))

Here's a handy macro to see what's going on under the covers:

match.core=> (defmacro expand-pattern [vars & clauses]

               `(-> (build-matrix ~vars ~@clauses)

                  compile

                  to-clj

                  source-pprint))

#'match.core/expand-pattern

match.core=> (expand-pattern [x y]

                               [1 0] 0

                               [0 1] 1)

(cond

  (= x 0) (cond

            (= y 1) 1

            :else (throw (java.lang.Exception. "Found FailNode")))

  (= x 1) (cond

            (= y 0) 0

            :else (throw (java.lang.Exception. "Found FailNode")))

  :else (throw (java.lang.Exception. "Found FailNode")))

nil

match.core=> 

Thanks,

Ambrose

[Ambrose Bonnaire-Sergeant]

Hi BG,

On Tue, Aug 9, 2011 at 5:43 PM, Baishampayan Ghose <b.g...@gmail.com> wrote:

A sample implementation of the `defm` macro used above could be

something like this (UNTESTED!) -

*snip*

`defm` is already at `match.core/defmatch`. Pretty neat :)

 

I personally believe that David and Ambrose are doing some incredible
work with match & core.logic; these two projects will prove be
extremely useful in the future.

David thinks up some amazing projects! Thanks for the encouragement, it's really way too much fun!

Thanks,

Ambrose

[Baishampayan Ghose]

> On Tue, Aug 9, 2011 at 5:43 PM, Baishampayan Ghose <b.g...@gmail.com>
> wrote:
>>
>> A sample implementation of the `defm` macro used above could be
>> something like this (UNTESTED!) -
>> *snip*
>
> `defm` is already at `match.core/defmatch`. Pretty neat :)

Lol! I realised that while looking into the match.core code _after_
sending out the email :fp

[Ambrose Bonnaire-Sergeant]

For those browsing the source, I'll give a quick run through of what's going on.

1. A "pattern matrix" is built using the given variables and pattern rows. A Pattern row is a pair of matches and a result.

Example:

match.core=> (build-matrix [x y]

                           [1 0] 0

                           [0 1] 1)

#match.core.PatternMatrix[[#match.core.PatternRow[[<LiteralPattern: 1> <LiteralPattern: 0>], 

                                                                            0, nil] ;; results in 0

                                       #match.core.PatternRow[[<LiteralPattern: 0> <LiteralPattern: 1>], 

                                                                           1, nil]], ;; results in 0

                                      [x y]]  ;; the variables to match

2. The pattern matrix is "compiled" into a decision tree, a DAG. Switch nodes can take multiple routes down the tree, depending on which ":case" matches the ":occurance". 

Example:

match.core=> (-> (build-matrix [x y]

                               [1 0] 0

                               [0 1] 1)

               compile)

#match.core.SwitchNode{:occurrence x, 

                                    :cases ([<LiteralPattern: 0> 

                                                #match.core.SwitchNode{:occurrence y, 

                                                                                    :cases ([<LiteralPattern: 1> 

                                                                                                #match.core.LeafNode{:value 1, :bindings nil}]), 

                                                                                    :default #match.core.FailNode{}}] 

                                               [<LiteralPattern: 1> 

                                                #match.core.SwitchNode{:occurrence y, 

                                                                                    :cases ([<LiteralPattern: 0> 

                                                                                               #match.core.LeafNode{:value 0, :bindings nil}]), 

                                                                                    :default #match.core.FailNode{}}]), 

                                   :default #match.core.FailNode{}}

3. The DAG is then converted to the equivalent Clojure code.

match.core=> (-> (build-matrix [x y]

                               [1 0] 0

                               [0 1] 1)

               compile

               to-clj source-pprint)

(cond

  (= x 0) (cond

            (= y 1) 1

            :else (throw (java.lang.Exception. "Found FailNode")))

  (= x 1) (cond

            (= y 0) 0

            :else (throw (java.lang.Exception. "Found FailNode")))

  :else (throw (java.lang.Exception. "Found FailNode")))

nil

Ambrose

[Sam Aaron]

Wonderful. Baishampayan and Ambrose thanks so much for your fantastically lucid examples.

I can totally see myself using this stuff. David and Ambrose, it's remarkable work - well done!

Sam

---
http://sam.aaron.name

[David Nolen]

On Tue, Aug 9, 2011 at 3:50 AM, Sam Aaron <sama...@gmail.com> wrote:

Exciting stuff!

Do you happen to have any simple descriptions/examples of where and how we might use this stuff in our daily programming repertoires? I for one am sure I'm not educated enough as to the value and utility of pattern matching - at the moment I just think "that looks cool" rather than "I'm definitely going to use that to do X and Y".

Sam

---
http://sam.aaron.name

Think about code for dealing with macros.

(defmacro foo [& forms]

  (match [forms]

     [(a [x] :else & rest)] ...

     [(a [x b] :else & rest)] ...))

Also we've reserved vector notation for data structures that support random access and slicing. For example say you're doing some network programming:

(match [byte-buffer]

    ([127 1  38 58 l & rest] ...)

    ([127 2  0  0  l & rest] ...)

    ([1   id 0  0  l & rest] ...))

This should of course expand out to highly optimized calls to pull apart the particular data structure. Because of lazy pattern matching it would be efficient without you would having to write such logic by hand (it will automatically check ahead on bytes that actually matter for determining which branch to take).

David

[David Nolen]

On Tue, Aug 9, 2011 at 6:34 AM, Ambrose Bonnaire-Sergeant <abonnair...@gmail.com> wrote:

For those browsing the source, I'll give a quick run through of what's going on.

This means that the machinery is already exposed.  There's a bit of code cleanup to do but the pattern matcher is meant to be *extensible*. So if you spend some time to understand how the library works you can extend the pattern matcher to deal with new kind of patterns. For example you may very well decide that you'd like to do the following:

(match [s]

   ([(#"foo" :as m)] ...)

   ([(#"bar.*" :as m)] ...)

We may or may not add regex support to match, but it doesn't mean that you shouldn't be able to. It will take some time to figure out what the precise protocol is for this, but we're thinking about it as we implement the current feature set.

David

[Ambrose Bonnaire-Sergeant]

On Tue, Aug 9, 2011 at 7:39 PM, David Nolen <dnolen...@gmail.com> wrote:

Think about code for dealing with macros.

(defmacro foo [& forms]

  (match [forms]

     [(a [x] :else & rest)] ...

     [(a [x b] :else & rest)] ...))

Wow, that is cool! 

[Meikel Brandmeyer (kotarak)]

Hi,

This reminds me of Scheme's syntax-rules.

Meikel
 

[David Nolen]

A quick heads up. We've switched to vectors for seq matching. This brings things in line with Clojure destructuring syntax, but more importantly it frees us to reserve lists for custom syntax. This will allow for things like this:

(match [x y]

  [({1 :b} :as m) _] ...)

We'll probably support optimized vector matching like so:

(match [x y]

  [([1 2 & r] :vector) _] ...)

David

[Peter Taoussanis]

This is great stuff: thank you! I can totally see this being the kind
of thing like destructuring, where once you've used it you won't want
to go back :)

--
Peter

[James Sofra]

Hi David,

Looks really neat!

Just to clarify, you can extend the matching to new types but the match is 'closed' in the sense that unlike mutimethods you can't add additional cases? Is that correct?

Hope that makes sense,

James Sofra

[Ambrose Bonnaire-Sergeant]

Hi James,

On Wed, Aug 10, 2011 at 5:43 PM, James Sofra <james...@gmail.com> wrote:

Just to clarify, you can extend the matching to new types but the match is 'closed' in the sense that unlike mutimethods you can't add additional cases? Is that correct?

For the 0.1 release, that is correct.

In future releases, we will explore 'open' matching, a la multimethods.

Thanks,

Ambrose