cl-pattern

CL-PATTERN
==========

CL-PATTERN is a very fast ML-like pattern-matching library for Common
Lisp.

API
---

### Macro: `match`

    match value &body clauses

`match` macro tries to match `value` with `clauses` and raise an error
if no clauses matched. A clause have to be a form of `(pattern
form*)`, where `pattern` is a pattern (see "Patterns").

#### Examples

    (match '(1 2)
      ((x y) (+ x y)))
    ;;=> 3

    (match '(x 1)
      (('x x) x))
    ;;=> 1

    (match '(1 2)
      ((1 &optional a) a))
    ;;=> 2

### Macro: `lambda-match`

    lambda-match &body clauses

`lambda-match` is a shorthand of `lambda` and `match`. For example,

    (lambda-match
      (('foo a) a))

will be expaneded to

    (lambda (arg)
      (match arg
        (('foo a) a)))

### Patterns

A pattern must be one of a symbol, a cons, and an atom. If the pattern
is symbol, the pattern is called a variable pattern, which can be
matched with any value. A body of a clause will be evaluated with
using a binding of the variable and the valueThe variable can be used
in a body of a. If the variable is `_`, any binding will not be
made. Here is an example:

    (match 1
      (x x))
    ;;=> 1

If the pattern is a cons, there is three cases you have to know. If a
`car` of the cons is `quote`, the pattern is called a constant
pattern, which can be matched with a same value of a `cadr` of the
cons. Here is an example:

    (match 'x
      ('x 1))
    ;;=> 1

Second case, if the `car` of the cons is `&optional`, the pattern is
called a optional variable pattern, which can be matched with any
value as same as usual variable patterns, but it can be not
matched. If not matched, we say the pattern is unbound, meaning an
undefined value (`nil` will bound to the pattern.

    (match '(1)
      ((1 &optional x) x))
    ;;=> NIL
    
    (match '(1 2)
      ((1 &optional x) x))
    ;;=> 2

Othewise, the pattern is called a structure pattern, which can be
matched if a `car` of the pattern and a `cdr` of the pattern are
matched with a value. Here is an example:

    (match '(1 . 2)
      ((x . y) (+ x y)))
    ;;=> 1

As you may guess, the `car` of the pattern and the `cdr` of the
pattern are also patterns. So you can nest patterns infinitely.

If the pattern is an atom, the pattern is called a constant pattern
too. As we said, the pattern can be matched with a same value of the
pattern. Here is an example:

    (match 1
      (1 'matched))
    ;;=> MATCHED

Micro Benchmark
---------------

Here is a micro benchmark comparing

    (match triple
      ((a &optional b c) (+ a b c)))

and

    (destructuring-bind (a &optional b c)
        triple
      (+ a b c))

* 10000000 times
* with `(declare (optimized (speed 3)))`
* on Core 2 Duo 1.6GHz

### Allegro CL v8.2 (Express Edition)

On Allegro CL, `destructuring-bind` seems to be tuned properly.

    MATCH
    ; cpu time (non-gc) 0.190000 sec user, 0.000000 sec system
    ; cpu time (gc)     0.000000 sec user, 0.000000 sec system
    ; cpu time (total)  0.190000 sec user, 0.000000 sec system
    ; real time  0.188305 sec
    ; space allocation:
    ;  0 cons cells, 0 other bytes, 0 static bytes
    DESTRUCTURING-BIND
    ; cpu time (non-gc) 0.040000 sec user, 0.000000 sec system
    ; cpu time (gc)     0.000000 sec user, 0.000000 sec system
    ; cpu time (total)  0.040000 sec user, 0.000000 sec system
    ; real time  0.040888 sec
    ; space allocation:
    ;  0 cons cells, 0 other bytes, 0 static bytes

### SBCL v1.0.47

On SBCL, even in such the simple case, `destructuring-bind` seems to
be a very high cost operation.

    MATCH
    Evaluation took:
      0.007 seconds of real time
      0.010000 seconds of total run time (0.010000 user, 0.000000 system)
      142.86% CPU
      10,040,848 processor cycles
      0 bytes consed
      
    DESTRUCTURING-BIND
    Evaluation took:
      0.983 seconds of real time
      0.980000 seconds of total run time (0.970000 user, 0.010000 system)
      99.69% CPU
      1,568,842,248 processor cycles
      0 bytes consed

### ECL v11.1.1

On ECL, `match` and `destructuring-bind` are almost same cost in this
simple case.

    MATCH
    real time : 0.883 secs
    run time  : 0.890 secs
    gc count  : 2 times
    consed    : 66339433 bytes
    DESTRUCTURING-BIND
    real time : 0.970 secs
    run time  : 0.960 secs
    gc count  : 1 times
    consed    : 66346216 bytes

Supported Implementations
-------------------------

* Allegro CL v8.2
* SBCL v1.0.47
* CMU CL v20b
* Clozure CL v1.6
* ECL v11.1.1
* GNU CLISP v2.48

----

Copyright (C) 2011  Tomohiro Matsuyama <<tomo@cx4a.org>>.


cl-pattern

Upstream URL

Author

License

cl-pattern

Version:

License:

Authors:

Dependencies:

cl-pattern-benchmark

Dependencies:

Dependencies (3)

Dependents (3)