Re: Lisp pattern matching libraries & difference between unification and pattern matching

On Jan 26, 7:44 pm, Slobodan Blazeski <slobodan.blaze...@xxxxxxxxx>
wrote:
On Jan 26, 5:23 pm, Marco Antoniotti <marc...@xxxxxxxxx> wrote:



On Jan 25, 10:02 pm, Slobodan Blazeski <slobodan.blaze...@xxxxxxxxx>
wrote:

I want to make small embedded prolog with modular design so I'm
shopping for an existing  pattern matching library. If anybody has
some experience using them I would appreciate if you share it.
I started first with cl-unification, because of it's high quality
documentation, that would be even better if Marco gave some examples
of using match  &  matching macros,  and especially what's the idiom
of writing something like below in home made libraries:
(match '(p a b c a) '(p ?x ?y c ?x))

UNIFY:MATCH is a macro that builds an OCaml-like statement.  It does
pattern matching and not full blown unification (although UNIFY:UNIFY
is used under the hood).  Here is a small example.

cl-prompt> (unify:match ('(p ?x 2 ?z) '(p 1 2 3)) (+ ?x ?z))
4

MATCH unifies a pattern with an object and creates the appropriate
variable bindings for you.  In the example above you must quote the
pattern and object because they are evaluated (I decided that a non
evaluating MATCH, let's say a MATCHQ to honor tradition, would be easy
to add; maybe I will).  Note that the following will also work

cl-prompt> (unify:match ('(p ?x 2 ?z) '(p 1 2 3)) (+ x z))
4

The other matching macros (MATCH-CASE and MATCHING) are all built on
top of MATCH.

If you need to just match a pattern and an object and manipulate the
resulting bindings, you just use UNIFY

(let ((s (unify:unify '(p ?x 2 ?z) '(p 1 2 3))))
   (+ (unify:find-variable-value '?x e)
      (unify:find-variable-value '?z e)))
==> 4

I am open to suggestions for shorter names or better macros.  UNIFY is
pretty low level in CL-UNIFICATION as FIND-VARIABLE-VALUE is.

What's the difference between unification & pattern matching?
Especially with examples  what could be done with unification that
can't be done with pattern matching or vice versa?

Unification is a generalization of pattern-matching (and assignment).
The following will work

(unify:unify '(foo ?x 2 ?z) '(foo 1 ?y 3))

?x will bind to 1, ?y to 2 and ?z to 3.

In pattern matching you can have variables only on one side.

I suggest you sign to the cl-unification mailing lists to discuss
these things.

Cheers
--
Marco

Many thanks to everybody for their replies. Marco I subscribed to the
mailing list but just one more quick question. What's the right way to
collect all the unified variables :
(unify-collect '(?x 1 3 a) '(2 ?y ?z a))
((?x . 2) (?y . 1) (?z .3))


If you are using CL-UNIFICATION the result of UNIFY is exactly what
you need. Look at the file substitutions.lisp to see the structure.
Incidentally it *is* derived from SICP. So you can almost immediately
write the SICP Prolog interpreter with them.

Cheers
--
Marco
.

Relevant Pages