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

Awesome!

Thanks for the great work.
Tuba

David, this looks great!

sent from my mobile device

On Aug 9, 2011 7:58 AM, "Tuba Lambanog" <tuba.lamba...@gmail.com> wrote:

Thanks! This looks really good.

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

On Aug 9, 7:49 am, David Nolen <dnolen.li...@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

On 9 Aug 2011, at 06:49, David Nolen wrote:

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

That's a great explanation Baishampayan, thanks !

 Edmund

On 09/08/2011 10:43, Baishampayan Ghose wrote:

Hi Sam,

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

Hi BG,

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

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

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

Thanks,
Ambrose

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

Regards,
BG

--
Baishampayan Ghose
b.ghose at gmail.com

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

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

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

On Tue, Aug 9, 2011 at 6:34 AM, Ambrose Bonnaire-Sergeant <

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

Wow, that is cool!

Hi,

Am Dienstag, 9. August 2011 15:14:25 UTC+2 schrieb Ambrose
Bonnaire-Sergeant:

This reminds me of Scheme's syntax-rules.

Meikel

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

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

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

Hi James,

For the 0.1 release, that is correct.

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

Thanks,
Ambrose