[cl-unification-devel] Re: question about CL-UNIFICATION

[rpgoldman at real-time.com]

>>>>> "MA" == Marco Antoniotti <marcoxa at cs.nyu.edu> writes:

    MA> Hi
    MA> thanks for the comments.

    MA> On May 27, 2005, at 12:25 PM, Robert P. Goldman wrote:

    >> 
    >> I was following up on CL-UNIFICATION based on your email to the cells
    >> list, and read over the web site docs.  I was left with the question
    >> of how to unify together two structures or objects.  I see how one can
    >> unify a structure (or object) with a template, and how that might be
    >> used for ML-style pattern-matching.
    >> 
    >> But what if you really want to know if two structures themselves
    >> unify?  Presumably one might want to do something like the following:
    >> 
    >> (setf x #S(FOO A 42 S NIL D NIL))
    >> (setf y #S(FOO A 42 S NIL D NIL))
    >> 
    >> where x and y are EQUALP, but not EQ, and you'd like to do
    >> 
    >> (unify x y)
    >> 
    >> but this is impossible.

    MA> Ooops.  Not good.



    >> Is the following correct:
    >> 
    >> (unify x #T(FOO foo-a (foo-a y) foo-s (foo-s y) foo-d (foo-d y)))

    MA> Yes.  This would work.


    >> 
    >> and, if so, is there some less cumbersome way to make this happen?
    >> I.e., to have a unification method definition that would say "whenever
    >> I unify together a FOO and a FOO, I want to apply this template to the
    >> second argument?

    MA> You make a very good point.

    MA> Right now, the only defined methods for UNIFY with STRUCTURE-OBJECTs are

    MA> unify structure-object template
    MA> unify template structure-object

    MA> TRT would be to write a method for

    MA> unify structure-object structure-object

    MA> This would be a limited method in any case, just testing for equality 
    MA> with EQUALP.  E.g. given

    MA> (setf x #S(FOO A ?x))
    MA> (setf y #S(FOO A 42))

    MA> (unify x y)

    MA> would return an empty environment.  I.e. the unifier would not recur 
    MA> into the slots.
    MA> In alternative the unifier could generate two subtests

    MA> (unify x #T(FOO foo-a (foo-a y) foo-s (foo-s y) foo-d (foo-d y)))
    MA> (unify #T(FOO foo-a (foo-a x) foo-s (foo-s x) foo-d (foo-d x)) y)

    MA> This is needed to ensure cross unifications.

    MA> I know I could do away with all of this by invoking implementation 
    MA> dependent code  getting the structure slots.  But I am kind of against 
    MA> it.  As it is the unification code is completely portable.
    MA> Yet, given enough pressure, I will concede and add the the
    MA> extra code.

Actually, what I had intended was for the programmer to be able to
extend unify along the lines that you were talking about (the pair of
tests for FOO, above).  I agree that this can't be done generally, but
could be made to work in special purpose cases.

The next thing that one might do, it seems to me, would be to write a
metaclass for unifiable structures, wherein one might mark slots as
being intended for use in unification or not, as one chose.  Then if
one wished to make a unifiable class, one could make it of the
unifiable metaclass...

Best,
Robert

-- 
Robert P. Goldman
Senior Scientist
Smart Information Flow Technologies (d/b/a SIFT, LLC)

211 N. First St., Suite 300
Minneapolis, MN 55401

Voice:	(612) 384-3454
SIFT offices:  (612) 339-7438
Email:    rpgoldman at SIFT.info