[cl-unification-devel] Re: question about CL-UNIFICATION
Hi thanks for the comments. 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.
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)))
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?
You make a very good point. Right now, the only defined methods for UNIFY with STRUCTURE-OBJECTs are unify structure-object template unify template structure-object TRT would be to write a method for unify structure-object structure-object This would be a limited method in any case, just testing for equality with EQUALP. E.g. given (setf x #S(FOO A ?x)) (setf y #S(FOO A 42)) (unify x y) would return an empty environment. I.e. the unifier would not recur into the slots. In alternative the unifier could generate two subtests (unify x #T(FOO foo-a (foo-a y) foo-s (foo-s y) foo-d (foo-d y))) (unify #T(FOO foo-a (foo-a x) foo-s (foo-s x) foo-d (foo-d x)) y) This is needed to ensure cross unifications. I know I could do away with all of this by invoking implementation dependent code getting the structure slots. But I am kind of against it. As it is the unification code is completely portable. Yet, given enough pressure, I will concede and add the the extra code. Cheers Marco PS. Do subscribe to the mailing lists. They are very low volume, but most announcements and discussions go there. -- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
"MA" == Marco Antoniotti <marcoxa@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@SIFT.info
On May 27, 2005, at 2:51 PM, rpgoldman@real-time.com wrote:
"MA" == Marco Antoniotti <marcoxa@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.
Well, you can extend UNIFY. Just add methods to the generic function. I believe the basic behavior is documented, so you know where the 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...
Yes. I agree. But I am not sure you can specify a metaclass for structure classes. Cheers -- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
"MA" == Marco Antoniotti <marcoxa@cs.nyu.edu> writes:
MA> On May 27, 2005, at 2:51 PM, rpgoldman@real-time.com wrote: >>>>>>> "MA" == Marco Antoniotti <marcoxa@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
participants (2)
-
Marco Antoniotti -
rpgoldman＠real-time.com