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

[rpgoldman at real-time.com]

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

    MA> On May 27, 2005, at 2:51 PM, rpgoldman at real-time.com wrote:

    >>>>>>> "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.

    MA> Well, you can extend UNIFY.  Just add methods to the generic function.  
    MA> I believe the basic behavior is documented, so you know where the 
    MA> limits are.

    >> 
    >> 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...

    MA> Yes.  I agree.  But I am not sure you can specify a metaclass for 
    MA> structure classes.

Ah.  A good point.  Perhaps then an extended DEFSTRUCT macros.  I
don't think my earlier email was particularly clear.  What I had in
mind was the ability for the user to easily specify a default template
that could be used in the process of comparing two objects of the same
type.  For structure objects DEFSTRUCT-UNIFIABLE would be one way to
do this, and for CLOS objects a metaclass might be better (accepting
caveats about the portability of the MOP...)

Best,
R