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))
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?
thanks
Slobodan
On Jan 25, 3:02 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> What's the difference between unification & pattern matching?
Abstractly,
Unification pays attention to variables on both sides, and will
produce binding for "right-hand side" variables too. Pattern matching
only pays attention to "left-hand side" variables and bindings.
so
(unify '(p ?x b) '(p a ?y)) will get you results with ?x bound to 'a
and ?y bound to 'b.
and
(unify '(p a ?x c) '(p ?y ?y ?y)) will fail.
Kevin
From: Don Geddis
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <877ihx9vaw.fsf@geddis.org>
Slobodan Blazeski <·················@gmail.com> wrote on Fri, 25 Jan 2008:
> What's the difference between unification & pattern matching?
Well, they're two different algorithms.
To a first approximation, unification is a generalization of pattern
matching. Pattern matching is usually a one-way mapping, from a more
general expression, to a specific instance. So, for example, the pattern
aba(b*)a
might match the concrete string
ababbbbba
Unification allows variables in both expressions, and assignments on either
side. So the expression
(?x ?y (f ?z))
can unify with the expression
(A (g ?w) ?v)
with the mapping
?x->A, ?y->(g ?w), ?v->(f ?z)
Pattern matching is used in things like regular expressions and text
processing. Unification is used in logic programming/inference/theorem
proving.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Under capitalism, man exploits man. Under communism, it's just the opposite.
-- John Kenneth Galbraith
On Jan 26, 3:26 am, Don Geddis <····@geddis.org> wrote:
> Slobodan Blazeski <·················@gmail.com> wrote on Fri, 25 Jan 2008:
>
> > What's the difference between unification & pattern matching?
>
> Well, they're two different algorithms.
>
> To a first approximation, unification is a generalization of pattern
> matching. Pattern matching is usually a one-way mapping, from a more
> general expression, to a specific instance. So, for example, the pattern
> aba(b*)a
> might match the concrete string
> ababbbbba
>
> Unification allows variables in both expressions, and assignments on either
> side. So the expression
> (?x ?y (f ?z))
> can unify with the expression
> (A (g ?w) ?v)
> with the mapping
> ?x->A, ?y->(g ?w), ?v->(f ?z)
>
> Pattern matching is used in things like regular expressions and text
> processing. Unification is used in logic programming/inference/theorem
> proving.
>
> -- Don
> ___________________________________________________________________________ ____
> Don Geddis http://don.geddis.org/ ····@geddis.org
> Under capitalism, man exploits man. Under communism, it's just the opposite.
> -- John Kenneth Galbraith
On Jan 26, 3:26 am, Don Geddis <····@geddis.org> wrote:
> Slobodan Blazeski <·················@gmail.com> wrote on Fri, 25 Jan 2008:
>
> > What's the difference between unification & pattern matching?
>
> Well, they're two different algorithms.
>
> To a first approximation, unification is a generalization of pattern
> matching. Pattern matching is usually a one-way mapping, from a more
> general expression, to a specific instance. So, for example, the pattern
> aba(b*)a
> might match the concrete string
> ababbbbba
>
> Unification allows variables in both expressions, and assignments on either
> side. So the expression
> (?x ?y (f ?z))
> can unify with the expression
> (A (g ?w) ?v)
> with the mapping
> ?x->A, ?y->(g ?w), ?v->(f ?z)
>
> Pattern matching is used in things like regular expressions and text
> processing. Unification is used in logic programming/inference/theorem
> proving.
>
Actually one must differentiate between two forms of "pattern
matching". The term as used in conjunction with regular expressions
denotes a slightly different version than the one used in "structure
matching". This last one is also used heavily in the ML-style
languages.
Cheers
--
Marco
From: Don Geddis
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <87zluq7umi.fsf@geddis.org>
Marco Antoniotti <·······@gmail.com> wrote on Sat, 26 Jan 2008:
>> To a first approximation, unification is a generalization of pattern
>> matching.
>
> Actually one must differentiate between two forms of "pattern matching".
> The term as used in conjunction with regular expressions denotes a slightly
> different version than the one used in "structure matching". This last one
> is also used heavily in the ML-style languages.
OK, but it's still the case that unification is a generalization of that form
of pattern matching also.
ML-style pattern matching is more restrictive than unification, but that
allows for implementation algorithms that have tighter complexity classes
than the algorithms required for unification.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Psychiatrist: "You have kleptomania." Patient: "Can I take something for it?"
-- "Rhymes with Orange", 9/14/2007
On Jan 27, 11:48 pm, Don Geddis <····@geddis.org> wrote:
> Marco Antoniotti <·······@gmail.com> wrote on Sat, 26 Jan 2008:
>
> >> To a first approximation, unification is a generalization of pattern
> >> matching.
>
> > Actually one must differentiate between two forms of "pattern matching".
> > The term as used in conjunction with regular expressions denotes a slightly
> > different version than the one used in "structure matching". This last one
> > is also used heavily in the ML-style languages.
>
> OK, but it's still the case that unification is a generalization of that form
> of pattern matching also.
>
> ML-style pattern matching is more restrictive than unification, but that
> allows for implementation algorithms that have tighter complexity classes
> than the algorithms required for unification.
Well, yes if you use CL-UNIFICATION simple minded algorithm. There is
a linear time unification algorithm around (cfr.
http://common-lisp.net/project/cl-unification/unify-function.html).
In that case you are just dealing with different constants.
Apart from that, I think there is still a different flavor between
"pattern-matching-as-regular-language-recognition" and "pattern-
matching-as-DESTRUCTURING-BIND". I did toy with the idea of
integrating regular-language-recognition in CL-UNIFICATION, but then I
decided that CL-PPCRE is already filling that need.
Cheers
--
Marco
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pr4ofngpp5764@corp.supernews.com>
Don Geddis wrote:
> Marco Antoniotti <·······@gmail.com> wrote on Sat, 26 Jan 2008:
>>> To a first approximation, unification is a generalization of pattern
>>> matching.
>>
>> Actually one must differentiate between two forms of "pattern matching".
>> The term as used in conjunction with regular expressions denotes a
>> slightly
>> different version than the one used in "structure matching". This last
>> one is also used heavily in the ML-style languages.
>
> OK, but it's still the case that unification is a generalization of that
> form of pattern matching also.
In a practical sense, ML style pattern matching is designed to integrate
into the type system in a way that unification cannot.
Consider translating the following trivial OCaml pattern into
cl-unification, for example:
# let f (`A x | `B x) = x;;
val f : [< `A of 'a | `B of 'a ] -> 'a = <fun>
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
> Don Geddis wrote:
> > Marco Antoniotti <·······@gmail.com> wrote on Sat, 26 Jan 2008:
> >>> To a first approximation, unification is a generalization of pattern
> >>> matching.
>
> >> Actually one must differentiate between two forms of "pattern matching".
> >> The term as used in conjunction with regular expressions denotes a
> >> slightly
> >> different version than the one used in "structure matching". This last
> >> one is also used heavily in the ML-style languages.
>
> > OK, but it's still the case that unification is a generalization of that
> > form of pattern matching also.
>
> In a practical sense, ML style pattern matching is designed to integrate
> into the type system in a way that unification cannot.
>
> Consider translating the following trivial OCaml pattern into
> cl-unification, for example:
>
> # let f (`A x | `B x) = x;;
> val f : [< `A of 'a | `B of 'a ] -> 'a = <fun>
This is completely off as you are confusing levels of interpretation.
Deep down in OCaml there is a unification algorithm (unless some magic
has happened since Hindley and Milner). CL-UNIFICATION works at that
level. Your example is at the language level and CL-UNIFICATION will
take care of that, provided that the appropriate semantic rules are in
place in a mostly S-expr syntax that may, or may not, be a
representation of CL.
Your example is at the level of saying that you cannot write
invertible predicates in Ocaml while trying to set up a Prolog system.
While CL-UNIFICATION gives you bits and pieces that resemble ML-like
languages, that is done mostly for convenience and showing off :) It
is a constituent, though not a replacement (although one could
conceive one) for a full blown type-inference machinery based on HM
ideas.
Cheers
--
Marco
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pssc1dsosti2e@corp.supernews.com>
Marco Antoniotti wrote:
>> # let f (`A x | `B x) = x;;
>> val f : [< `A of 'a | `B of 'a ] -> 'a = <fun>
>
> This is completely off as you are confusing levels of interpretation.
> Deep down in OCaml there is a unification algorithm (unless some magic
> has happened since Hindley and Milner).
I'm not talking about type inference. I'm talking about the above pattern
match.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 29, 1:15 am, Jon Harrop <······@jdh30.plus.com> wrote:
> Marco Antoniotti wrote:
> >> # let f (`A x | `B x) = x;;
> >> val f : [< `A of 'a | `B of 'a ] -> 'a = <fun>
>
> > This is completely off as you are confusing levels of interpretation.
> > Deep down in OCaml there is a unification algorithm (unless some magic
> > has happened since Hindley and Milner).
>
> I'm not talking about type inference. I'm talking about the above pattern
> match.
>
The above pattern is a polymorphic variant in OCaml. To match it
properly you need to implement the "let's build on the fly the 1-arity
constructors using the special backquote operator and return the
restricable type [<...]". This is language level semantic which is
built on top of a unification algorithm. On top of that, you are not
really doing pattern matching there. You are defining a function.
You do pattern matching when you call 'f'
# f (`A 42);;
- : int = 42
If you just want pattern matching for CL-UNIFICATION this would be
(unify:match (#T(union (A ?x) (B ?x)) '(A 42)) x)
From a pure syntactic point of view this is exactly what OCaml does
(including the "since having to define types beforehand is cumbersome
in many situations, let's introduce the polymorphic variants" :)
idea). There no claim in CL-UNIFICATION that the semantic is the same
as the full blown type checking of OCaml.
Cheers
--
Marco
PS. The 'union' (or 'or') template is not (yet) in CL-UNIFICATION. It
is left an an easy exercise to the reader :)
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13ptru1qs20nm5a@corp.supernews.com>
Marco Antoniotti wrote:
> (including the "since having to define types beforehand is cumbersome
> in many situations, let's introduce the polymorphic variants" :)
In all but the most trivial cases, using polymorphic variants because you
can't be bothered to make your types explicit is a bad idea. Polymorphic
variants are more often used because they provide open sum types.
> PS. The 'union' (or 'or') template is not (yet) in CL-UNIFICATION. It
> is left an an easy exercise to the reader :)
What does a complete implementation look like?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 29, 10:14 am, Jon Harrop <······@jdh30.plus.com> wrote:
> Marco Antoniotti wrote:
>
> > PS. The 'union' (or 'or') template is not (yet) in CL-UNIFICATION. It
> > is left an an easy exercise to the reader :)
>
> What does a complete implementation look like?
Depends on your style. A toy version I was playing around with is the
following. It ain't perfect but it does the unification of the
example.
============
(defclass union-template (expression-template) ())
(defmethod make-template ((kind (eql 'or)) (spec cons))
(make-instance 'union-template :spec spec))
(defun compound-template-compounds (x)
(declare (type compound-template x))
(rest (template-spec x)))
(defmethod unify ((ut union-template) (o t)
&optional (env (make-empty-environment)))
(let ((ts (compound-template-compounds ut)))
(if ts
(loop for tc in ts
for subst = (ignore-errors (unify tc o env))
when subst return subst
finally
(error 'unification-failure
:format-control "Cannot unify ~S with the
disjunction template ~S ."
:format-arguments (list o ut)))
(error 'unification-failure
:format-control "Cannot unify ~S with the empty
disjunction template."
:format-arguments (list o)))))
============
Note that the semantics of the above may or may not be correct. It
depends on what you want to achieve and how you want to fit this in
the language.
Cheers
--
Marco
On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
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
On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
> On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> 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))
cheers
Slobodan
On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
>
>
> > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > 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
On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
> On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
>
>
> > On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > > 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
I've looked through cl-unification code and now i'm sure that it won't
work for me without heavy rewrites. Goals for cl-unification are
different than my needs, I need simple (atom & cons only) but
efficient library that does most of it's work at compile time. Also
something better than naive kernel implementation would be nice to
have like Martelli Montanari or Alin Suciu.
cheers
Slobodan
On Jan 27, 11:57 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
> > wrote:
>
> > > On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > > > 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
>
> I've looked through cl-unification code and now i'm sure that it won't
> work for me without heavy rewrites. Goals for cl-unification are
> different than my needs, I need simple (atom & cons only) but
> efficient library that does most of it's work at compile time. Also
> something better than naive kernel implementation would be nice to
> have like Martelli Montanari or Alin Suciu.
I would second your goal. I would just suggest that you take into
account CL-UNIFICATION top-level syntax. After all that is not tied
to a particular unification algorithm.
Cheers
--
Marco
PS. thanks for the Suciu reference.
On Jan 28, 12:58 pm, Marco Antoniotti <·······@gmail.com> wrote:
> On Jan 27, 11:57 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
>
>
> > On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
> > > wrote:
>
> > > > On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > > > > 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
>
> > I've looked through cl-unification code and now i'm sure that it won't
> > work for me without heavy rewrites. Goals for cl-unification are
> > different than my needs, I need simple (atom & cons only) but
> > efficient library that does most of it's work at compile time. Also
> > something better than naive kernel implementation would be nice to
> > have like Martelli Montanari or Alin Suciu.
>
> I would second your goal.
Thank you .
> I would just suggest that you take into
> account CL-UNIFICATION top-level syntax.
I have problem with cl-unification syntax because it doesn't collect
the bidings instead it forces me to pick them one by one with find-
variable-value.
Also it uses common lisp condition system to signal unification
failure. I want something like On Lisp solution: (values established-
bindings succeded( t or nil))
Finally I would prefer to make a unification compiler instead of
interpreter.
Please correct me if I misunderstood sometething about cl-unification
implementation.
> After all that is not tied
> to a particular unification algorithm.
I'll start now to work on the implementation of Suciu algorithm, it
would be great if you find it useful.
>
> Cheers
> --
> Marco
>
> PS. thanks for the Suciu reference.
You're wellcomed . I've contacted him (his email is in the paper) re
implementation in c mentioned, so mail me if you need it or contact
Suciu if you need further informations.
cheers
Slobodan
On Jan 28, 1:33 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 28, 12:58 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > On Jan 27, 11:57 pm, Slobodan Blazeski <·················@gmail.com>
> > wrote:
>
> > > On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
> > > > wrote:
>
> > > > > On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > > > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > > > > > 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
>
> > > I've looked through cl-unification code and now i'm sure that it won't
> > > work for me without heavy rewrites. Goals for cl-unification are
> > > different than my needs, I need simple (atom & cons only) but
> > > efficient library that does most of it's work at compile time. Also
> > > something better than naive kernel implementation would be nice to
> > > have like Martelli Montanari or Alin Suciu.
>
> > I would second your goal.
> Thank you .
> > I would just suggest that you take into
> > account CL-UNIFICATION top-level syntax.
>
> I have problem with cl-unification syntax because it doesn't collect
> the bidings instead it forces me to pick them one by one with find-
> variable-value.
I don't understand this. The result of a unification is a
substitution. It does not matter how you represent it. Eventually
you need to select the variables one at the time. Even MATCH works
like that. What do you have in mind?
> Also it uses common lisp condition system to signal unification
> failure. I want something like On Lisp solution: (values established-
> bindings succeded( t or nil))
(defun unify* (p1 p2 &optional subst) (ignore-errors (unify p1 p2))) ;
Some tweaking required.
> Finally I would prefer to make a unification compiler instead of
> interpreter.
I think this is a worthy goal. But I invite you to provide one based
on the CL-UNIFICATION base. I would welcome such an addition. The
idea would be to write a macro that unfolded the UNIFY computation and
substituted MATCH. It isn't that difficult.
> Please correct me if I misunderstood sometething about cl-unification
> implementation.
I don't know what you know. I just want to push the idea of the
template matching language. Then I do not understand the point you
made before.
>
> > After all that is not tied
> > to a particular unification algorithm.
>
> I'll start now to work on the implementation of Suciu algorithm, it
> would be great if you find it useful.
I have not a good grasp of Suciu's algorithm. I stashed it away in
the never-shrinking pile of things to read (a problem compounded by
Valerio Evangelisti and Ian Rankin, which always make it in and out
the pile way too quickly :) ). I just have a feeling - by skimming it
- that it could be implemented a little more clearly without the
explicit stacks. However, I have not tried anything yet. Do let us
know.
Cheers
Marco
>
>
>
> > Cheers
> > --
> > Marco
>
> > PS. thanks for the Suciu reference.
>
> You're wellcomed . I've contacted him (his email is in the paper) re
> implementation in c mentioned, so mail me if you need it or contact
> Suciu if you need further informations.
>
Will do.
Marco
On Jan 28, 9:18 pm, Marco Antoniotti <·······@gmail.com> wrote:
> On Jan 28, 1:33 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
>
>
> > On Jan 28, 12:58 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > On Jan 27, 11:57 pm, Slobodan Blazeski <·················@gmail.com>
> > > wrote:
>
> > > > On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > > On Jan 26, 7:44 pm, Slobodan Blazeski <·················@gmail.com>
> > > > > wrote:
>
> > > > > > On Jan 26, 5:23 pm, Marco Antoniotti <·······@gmail.com> wrote:
>
> > > > > > > On Jan 25, 10:02 pm, Slobodan Blazeski <·················@gmail.com>
> > > > > > > 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
>
> > > > I've looked through cl-unification code and now i'm sure that it won't
> > > > work for me without heavy rewrites. Goals for cl-unification are
> > > > different than my needs, I need simple (atom & cons only) but
> > > > efficient library that does most of it's work at compile time. Also
> > > > something better than naive kernel implementation would be nice to
> > > > have like Martelli Montanari or Alin Suciu.
>
> > > I would second your goal.
> > Thank you .
> > > I would just suggest that you take into
> > > account CL-UNIFICATION top-level syntax.
>
> > I have problem with cl-unification syntax because it doesn't collect
> > the bidings instead it forces me to pick them one by one with find-
> > variable-value.
>
> I don't understand this. The result of a unification is a
> substitution. It does not matter how you represent it. Eventually
> you need to select the variables one at the time. Even MATCH works
> like that. What do you have in mind?
I want list of bindings as a result instead of unification envoroment
like this:
(unify '(a ?x) '(?y b))
((?x a) (?y b))
Currently unify returns unification enviroment, so I have to do add
some function that will collect all the variables ?'s for a given
input and than use something like
(defun collect (variables enviroment)
(mapcar #'(lambda (x) (find-variable-value x enviroment))
variables))
>
> > Also it uses common lisp condition system to signal unification
> > failure. I want something like On Lisp solution: (values established-
> > bindings succeded( t or nil))
>
> (defun unify* (p1 p2 &optional subst) (ignore-errors (unify p1 p2))) ;
> Some tweaking required.
>
> > Finally I would prefer to make a unification compiler instead of
> > interpreter.
>
> I think this is a worthy goal. But I invite you to provide one based
> on the CL-UNIFICATION base. I would welcome such an addition. The
> idea would be to write a macro that unfolded the UNIFY computation and
> substituted MATCH. It isn't that difficult.
I'll see how much time I have left, I'm waiting for some library
release so I can't code right now.
>
> > Please correct me if I misunderstood sometething about cl-unification
> > implementation.
>
> I don't know what you know. I just want to push the idea of the
> template matching language.
The idea of matching arbitrary structures is good but I just don't
have time to work on that.
> Then I do not understand the point you
> made before.
>
>
>
> > > After all that is not tied
> > > to a particular unification algorithm.
>
> > I'll start now to work on the implementation of Suciu algorithm, it
> > would be great if you find it useful.
>
> I have not a good grasp of Suciu's algorithm. I stashed it away in
> the never-shrinking pile of things to read (a problem compounded by
> Valerio Evangelisti and Ian Rankin, which always make it in and out
> the pile way too quickly :) ). I just have a feeling - by skimming it
> - that it could be implemented a little more clearly without the
> explicit stacks. However, I have not tried anything yet. Do let us
> know.
I started implementing and got stack in the parser, I have no
experience in parsing, afterwards algo seems easy. After I finish we
shall see how fast it is. And does it worth it to implement it as
compiler.
>
> Cheers
>
> Marco
>
>
>
> > > Cheers
> > > --
> > > Marco
>
> > > PS. thanks for the Suciu reference.
>
> > You're wellcomed . I've contacted him (his email is in the paper) re
> > implementation in c mentioned, so mail me if you need it or contact
> > Suciu if you need further informations.
>
> Will do.
>
> Marco
BTW In case you have some time to spare here's the problem of building
unification table page 2 of Suciu paper
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/740c43414b5b66b2#12548486d187db67
I'll continue to work on it but any tip is wellcome.
cheers
Slobodan
On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
> Incidentally it *is* derived from SICP. So you can almost immediately
> write the SICP Prolog interpreter with them.
>
> Cheers
> --
> Marco
I have a love-hate relationship with SICP. I love to watch SICP
videos, and feel the ideas and magic flowing from A&S lectures. But on
the other side it really makes me sick whe A&S don't try the
functions they wrote in the REPL. I want to see their function fed
with arguments and return the results. Thats a tradition that I
value in the common lisp books and makes me feel like home.
cheers
Slobodan
From: George Neuner
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <onnup3da5g6es5csm7u7r1c8n0ki1re20p@4ax.com>
On Sun, 27 Jan 2008 15:05:22 -0800 (PST), Slobodan Blazeski
<·················@gmail.com> wrote:
>On Jan 26, 8:46 pm, Marco Antoniotti <·······@gmail.com> wrote:
>> Incidentally it *is* derived from SICP. So you can almost immediately
>> write the SICP Prolog interpreter with them.
>>
>> Cheers
>> --
>> Marco
>I have a love-hate relationship with SICP. I love to watch SICP
>videos, and feel the ideas and magic flowing from A&S lectures. But on
>the other side it really makes me sick whe A&S don't try the
>functions they wrote in the REPL. I want to see their function fed
>with arguments and return the results. Thats a tradition that I
>value in the common lisp books and makes me feel like home.
>
>cheers
>Slobodan
Stupid question ... you do know that SICP is Scheme, not Lisp? It's
been many years since I went through it, but I don't recall having
much trouble with the examples.
George
--
for email reply remove "/" from address
On Jan 29, 6:18 pm, George Neuner <·········@/comcast.net> wrote:
> Stupid question ... you do know that SICP is Scheme, not Lisp?
I May Be Stupid But I'm Not Crazy
cheers
Slobodan
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13ppejidq5vmtb5@corp.supernews.com>
Slobodan Blazeski 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.
Marco's cl-unification library is by far the best I found for Common Lisp.
Nothing like as mature or efficient as the pattern matchers in language
implementations like OCaml though.
> What's the difference between unification & pattern matching?
In the context of Lisp, unification is more general but, consequently, less
predictable than pattern matching. In general, pattern matching is much
more widely used (e.g. in SML, OCaml, Haskell, Mathematica, F#) because it
is predictable, efficient and ties in with static type systems and type
inference very elegantly so it can offer far more static checking.
> Especially with examples what could be done with unification that
> can't be done with pattern matching or vice versa?
You can do anything with either, of course, given enough effort. You might
like to look at the unification-based Hindley-Milner type inference
algorithm implemented in ML using pattern matching. That implements one
form of unification in terms of pattern matching. Neel posted one on
comp.lang.functional recently.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 27, 6:02 pm, Jon Harrop <······@jdh30.plus.com> wrote:
> Slobodan Blazeski 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.
>
> Marco's cl-unification library is by far the best I found for Common Lisp.
What else have you tried?
> Nothing like as mature or efficient as the pattern matchers in language
> implementations like OCaml though.
I want full unification not only pattern matching.
CL-unification seems to using the naive kernel (*) I plan to try this
to optimize unification process a little http://arxiv.org/PS_cache/cs/pdf/0603/0603080v1.pdf
and see how it copes.
>
> > What's the difference between unification & pattern matching?
>
> In the context of Lisp, unification is more general but, consequently, less
> predictable than pattern matching. In general, pattern matching is much
> more widely used (e.g. in SML, OCaml, Haskell, Mathematica, F#) because it
> is predictable, efficient and ties in with static type systems and type
> inference very elegantly so it can offer far more static checking.
Static typing is price I don't want to pay. I want to optimize only
when I feel like optimizing.
I tried some whirlwind tour to haskell just to see how does pattern
matching works in other languges beside prolog, and all the time I
worked without specifying the types in Haskell functions. That's just
me.
>
> > Especially with examples what could be done with unification that
> > can't be done with pattern matching or vice versa?
>
> You can do anything with either, of course, given enough effort. You might
> like to look at the unification-based Hindley-Milner type inference
> algorithm implemented in ML using pattern matching. That implements one
> form of unification in terms of pattern matching. Neel posted one on
> comp.lang.functional recently.
Thanks for the tip , I will look at it.
cheers
Slobodan
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/products/?u
(*)
,
"The unification algorithm implemented is very flexible and provides
many hooks for customization. However, it is not necessarily
asymptotically efficient (it has a worst case exponential time
complexity.)
It would be interesting to reimplement the kernel of the system using
a linear unification algorithm like the one described in
[MM82] A. Martelli and U. Montanari, An Efficient Unification
Algorithm, ACM Transactions on Programming Languages and Systems, Vol.
4, No. 2, April 1982, Pages 258--282."
http://common-lisp.net/project/cl-unification/unify-function.html
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pr4n7fs5omn63@corp.supernews.com>
Slobodan Blazeski wrote:
> On Jan 27, 6:02 pm, Jon Harrop <······@jdh30.plus.com> wrote:
>> Slobodan Blazeski 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.
>>
>> Marco's cl-unification library is by far the best I found for Common
>> Lisp.
> What else have you tried?
I also tried fare-matcher but it is really awful and a couple of others but
I can't remember their names now. I discussed it on this list a few years
ago.
>> Nothing like as mature or efficient as the pattern matchers in language
>> implementations like OCaml though.
> I want full unification not only pattern matching.
> CL-unification seems to using the naive kernel (*) I plan to try this
> to optimize unification process a little
> http://arxiv.org/PS_cache/cs/pdf/0603/0603080v1.pdf and see how it copes.
If you want to optimize anything then I strongly recommend restricting
yourself to linear pattern matching. Otherwise you are not likely to be
able to predict the asymptotic complexity of your implementation and,
consequently, cannot optimize it.
>> > What's the difference between unification & pattern matching?
>>
>> In the context of Lisp, unification is more general but, consequently,
>> less predictable than pattern matching. In general, pattern matching is
>> much more widely used (e.g. in SML, OCaml, Haskell, Mathematica, F#)
>> because it is predictable, efficient and ties in with static type systems
>> and type inference very elegantly so it can offer far more static
>> checking.
>
> Static typing is price I don't want to pay. I want to optimize only
> when I feel like optimizing.
There is also the question of maturity: ML is more popular than the whole of
Common Lisp now so any given pattern matching or unification library for CL
will certainly be much less mature.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
> Slobodan Blazeski wrote:
> > On Jan 27, 6:02 pm, Jon Harrop <······@jdh30.plus.com> wrote:
> >> Slobodan Blazeski 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.
>
> >> Marco's cl-unification library is by far the best I found for Common
> >> Lisp.
> > What else have you tried?
>
> I also tried fare-matcher but it is really awful and a couple of others but
> I can't remember their names now. I discussed it on this list a few years
> ago.
>
> >> Nothing like as mature or efficient as the pattern matchers in language
> >> implementations like OCaml though.
> > I want full unification not only pattern matching.
> > CL-unification seems to using the naive kernel (*) I plan to try this
> > to optimize unification process a little
> >http://arxiv.org/PS_cache/cs/pdf/0603/0603080v1.pdfand see how it copes.
>
> If you want to optimize anything then I strongly recommend restricting
> yourself to linear pattern matching. Otherwise you are not likely to be
> able to predict the asymptotic complexity of your implementation and,
> consequently, cannot optimize it.
I don't plan to spend so much time on it , just want to see how it
compares with streightforward implementation. Unification is
interesthing but far from an important weapon in my arsenal.
>
> >> > What's the difference between unification & pattern matching?
>
> >> In the context of Lisp, unification is more general but, consequently,
> >> less predictable than pattern matching. In general, pattern matching is
> >> much more widely used (e.g. in SML, OCaml, Haskell, Mathematica, F#)
> >> because it is predictable, efficient and ties in with static type systems
> >> and type inference very elegantly so it can offer far more static
> >> checking.
>
> > Static typing is price I don't want to pay. I want to optimize only
> > when I feel like optimizing.
>
> There is also the question of maturity: ML is more popular than the whole of
> Common Lisp now so any given pattern matching or unification library for CL
> will certainly be much less mature.
Beside the more popular part which I would take as your personal
opinion, please restrain yourself from starting another trollish
posts, I agree that ML pattern matching is more mature especially
OCaml one, but the reason is more than practical. Lispers have very
little interest in unification. It's useful now and then but far from
relying on it. Actually if it wasn't question of prolog I'd never seen
much need for it. Let's say that my brain is wired differently, and I
don't feel like changing. You're all wellcomed to contribute to this
group, post as much alternative coding solutions in OCaml/F# as you
want, it's good to see how different languages solve different
problems but cut out the "convert you infidels bulshit".
cheers
Slobodan
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/products/?u
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pst8kbp7dl932@corp.supernews.com>
Slobodan Blazeski wrote:
> On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
>> Slobodan Blazeski wrote:
>> There is also the question of maturity: ML is more popular than the whole
>> of Common Lisp now so any given pattern matching or unification library
>> for CL will certainly be much less mature.
>
> Beside the more popular part which I would take as your personal
> opinion...
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox%2Cerlang-base%2Cghc6%2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
From: Sohail Somani
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <vPunj.21998$vp3.4556@edtnps90>
On Tue, 29 Jan 2008 00:31:10 +0000, Jon Harrop wrote:
> Slobodan Blazeski wrote:
>> On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
>>> Slobodan Blazeski wrote:
>>> There is also the question of maturity: ML is more popular than the
>>> whole of Common Lisp now so any given pattern matching or unification
>>> library for CL will certainly be much less mature.
>>
>> Beside the more popular part which I would take as your personal
>> opinion...
>
> http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-
nox%2Cerlang-base%2Cghc6%
2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=
%25Y-%25m&beenhere=1
I like this one better: http://people.debian.org/~igloo/popcon-graphs/
index.php?packages=sbcl%2Cocaml-nox%2Cghc6%
2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=
%25Y-%25m&beenhere=1
(shows two of the more popular ones instead of only one)
Also, I haven't used a Lisp from a Linux distribution since about 2
months after I started using it. Including Emacs Lisp. Don't know how
common that is.
--
Sohail Somani
http://uint32t.blogspot.com
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pts15o1vgnf5c@corp.supernews.com>
Sohail Somani wrote:
> (shows two of the more popular ones instead of only one)
The total figures will be somewhere between the maximum and the total, both
of which are still smaller than the current OCaml user base and are growing
more slowly as well.
The Ubuntu results are similar.
> Also, I haven't used a Lisp from a Linux distribution since about 2
> months after I started using it. Including Emacs Lisp. Don't know how
> common that is.
Yes: I have both CLisp and SBCL installed but never use either. I doubt the
error in either direction is bigger than in the other.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
On Jan 29, 1:31 am, Jon Harrop <······@jdh30.plus.com> wrote:
> Slobodan Blazeski wrote:
> > On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
> >> Slobodan Blazeski wrote:
> >> There is also the question of maturity: ML is more popular than the whole
> >> of Common Lisp now so any given pattern matching or unification library
> >> for CL will certainly be much less mature.
>
> > Beside the more popular part which I would take as your personal
> > opinion...
>
> http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocam...
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/products/?u
The frog remains a frog, Ocaml has one implementation lisp has sbcl,
allegro, lw, cmucl, ecl, openmcl, gcl & scieneer beside clisp. The
last time I've used or had installed clisp was ~3 years ago.
Slobodan
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13q0f6l259uona3@corp.supernews.com>
Slobodan Blazeski wrote:
> Ocaml has one implementation lisp has sbcl, allegro, lw, cmucl, ecl,
> openmcl, gcl & scieneer beside clisp.
Even if you add all of the open source Common Lisp implementations up (i.e.
assuming users of each do not use any of the others), the total is still
lower than OCaml:
http://flyingfrogblog.blogspot.com/2007/11/most-popular-functional-languages-on.html
Moreover, the OCaml userbase continues to grow much faster and Ubuntu shows
the same trends.
> The last time I've used or had installed clisp was ~3 years ago.
I have three Common Lisp implementations installed but work only with OCaml.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
In article <···············@corp.supernews.com>,
Jon Harrop <······@jdh30.plus.com> wrote:
> Slobodan Blazeski wrote:
> > On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
> >> Slobodan Blazeski wrote:
> >> There is also the question of maturity: ML is more popular than the whole
> >> of Common Lisp now so any given pattern matching or unification library
> >> for CL will certainly be much less mature.
> >
> > Beside the more popular part which I would take as your personal
> > opinion...
>
> http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox%2Cerlang-base%2Cghc6%2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
As you can see here
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox&show_old=on&show_recent=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
OCAML gets installed but not used.
In article <····························@news-europe.giganews.com>,
Rainer Joswig <······@lisp.de> wrote:
> In article <···············@corp.supernews.com>,
> Jon Harrop <······@jdh30.plus.com> wrote:
>
> > Slobodan Blazeski wrote:
> > > On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
> > >> Slobodan Blazeski wrote:
> > >> There is also the question of maturity: ML is more popular than the whole
> > >> of Common Lisp now so any given pattern matching or unification library
> > >> for CL will certainly be much less mature.
> > >
> > > Beside the more popular part which I would take as your personal
> > > opinion...
> >
> > http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox%2Cerlang-base%2Cghc6%2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
>
> As you can see here
>
> http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox&show_old=on&show_recent=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
>
> OCAML gets installed but not used.
Actually, see the regular usage peeks? I guess that are students at universities. Course starts and uses OCAML, everybody tries OCAML. -> Peak.
Nobody does anything then. Drops. End of course gets near. Sudden rush. -> Peak. Then dropping again.
From: Jon Harrop
Subject: Re: Lisp pattern matching libraries & difference between unification and pattern matching
Date:
Message-ID: <13pvahlpocg9m41@corp.supernews.com>
Rainer Joswig wrote:
> In article <···············@corp.supernews.com>,
> Jon Harrop <······@jdh30.plus.com> wrote:
>> Slobodan Blazeski wrote:
>> > On Jan 28, 9:26 am, Jon Harrop <······@jdh30.plus.com> wrote:
>> >> Slobodan Blazeski wrote:
>> >> There is also the question of maturity: ML is more popular than the
>> >> whole of Common Lisp now so any given pattern matching or unification
>> >> library for CL will certainly be much less mature.
>> >
>> > Beside the more popular part which I would take as your personal
>> > opinion...
>>
>>
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox%2Cerlang-base%2Cghc6%2Cclisp&show_installed=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
>
> As you can see here
>
>
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox&show_old=on&show_recent=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
>
> OCAML gets installed but not used.
So does many other language implementations, like GCC:
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=gcc&show_old=on&show_recent=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
SBCL and CLisp both show similar trends and much lower usage than OCaml:
http://people.debian.org/~igloo/popcon-graphs/index.php?packages=ocaml-nox%2Cclisp%2Csbcl&show_recent=on&want_legend=on&from_date=2004-01-01&to_date=2007-11-01&hlght_date=&date_fmt=%25Y-%25m&beenhere=1
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u