looking for a predicate hierarchy
in [OOP]
|
From: Laurent Deniau on 18 Dec 2006 07:54 I am looking for a library (of an OO language) which uses a hierarchy of classes for predicate (type) dispatch in the context of multimethod. Ce concept is already well know and developed in the literature, but languages which support multimethods and metaclasses are not so common. Therefore, I have some difficulty to find such 'standard' use of class as predicates. The papers usually use hierarchies inspired from specific taxonomy (e.g. animals) which are not general enough to be useful. For the moment in my lib I have (<- means 'inherits from'): Predicate (root class) <- Nil <- TrueFalse <- True <- False <- Ordered <- Lesser <- Equal <- Greater But there is a lot of other possible predicates (not all useful): Next, Previous Forward, Backward Open, Close Front, Rear Bottom, Top Before, After Up, Down Even, Odd Left, Right North, South, Est, West etc... and selecting the predicates general enough (aliases and user defined predicates are always possible as extension) is somehow a problem of experience. BTW, the hierarchy stigmatize the possible logical combinations of the predicates (not, and, or) and strengthens the importance of its design (e.g. TrueFalse != Boolean). Has somebody already seen such hierarchy? Links and references would be really appreciated. Thanks. a+, ld.
From: Dmitry A. Kazakov on 18 Dec 2006 14:42 On Mon, 18 Dec 2006 13:54:40 +0100, Laurent Deniau wrote: > I am looking for a library (of an OO language) which uses a hierarchy of > classes for predicate (type) dispatch in the context of multimethod. Ce > concept is already well know and developed in the literature, but > languages which support multimethods and metaclasses are not so common. > Therefore, I have some difficulty to find such 'standard' use of class > as predicates. The papers usually use hierarchies inspired from specific > taxonomy (e.g. animals) which are not general enough to be useful. > > For the moment in my lib I have (<- means 'inherits from'): > > Predicate (root class) > <- Nil > <- TrueFalse > <- True > <- False > <- Ordered > <- Lesser > <- Equal > <- Greater > > But there is a lot of other possible predicates (not all useful): > > Next, Previous > Forward, Backward > Open, Close > Front, Rear > Bottom, Top > Before, After > Up, Down > Even, Odd > Left, Right > North, South, Est, West > > etc... > > and selecting the predicates general enough (aliases and user defined > predicates are always possible as extension) is somehow a problem of > experience. BTW, the hierarchy stigmatize the possible logical > combinations of the predicates (not, and, or) and strengthens the > importance of its design (e.g. TrueFalse != Boolean). > > Has somebody already seen such hierarchy? Links and references would be > really appreciated. Thanks. It is group theory which describes such relations, like symmetry groups in geometry, for example. However, you will never be able to create such a hierarchy. The list you proved is full of apples and oranges. True and False are elements of a lattice. I presume you meant identity relation? Lesser, Equal, Greater are binary relations. Ordered sets are not necessary lattices, even less predicates. Vector spaces (where the relations like up and down could be defined) aren't either. The set of all possible binary relations defined on such structures cannot be ordered or arranged in a tree. Because already the structures like 3D space (R^3) would be too rich for that. Even more the set of all possible binary relations over it should be. Which is the set of all possible sets of ordered pairs (x, y), i.e. 2^(R^6). -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: aloha.kakuikanu on 18 Dec 2006 14:57 Laurent Deniau wrote: > I am looking for a library (of an OO language) which uses a hierarchy of > classes for predicate (type) dispatch in the context of multimethod. Ce > concept is already well know and developed in the literature, but > languages which support multimethods and metaclasses are not so common. > Therefore, I have some difficulty to find such 'standard' use of class > as predicates. The papers usually use hierarchies inspired from specific > taxonomy (e.g. animals) which are not general enough to be useful. > > For the moment in my lib I have (<- means 'inherits from'): > > Predicate (root class) > <- Nil > <- TrueFalse > <- True > <- False > <- Ordered > <- Lesser > <- Equal > <- Greater > > But there is a lot of other possible predicates (not all useful): > > Next, Previous > Forward, Backward > Open, Close > Front, Rear > Bottom, Top > Before, After > Up, Down > Even, Odd > Left, Right > North, South, Est, West > > etc... > > and selecting the predicates general enough (aliases and user defined > predicates are always possible as extension) is somehow a problem of > experience. BTW, the hierarchy stigmatize the possible logical > combinations of the predicates (not, and, or) and strengthens the > importance of its design (e.g. TrueFalse != Boolean). > > Has somebody already seen such hierarchy? Links and references would be > really appreciated. Thanks. What do you mean by "predicate"? Is it logical concept? Then we can talk about relations in the database theory sence, both finite and infinite. Relations do form a lattice, so you work out tthis idea into extracting a "hierarchy" out of the lattice. But is this really what you want to do?
From: Laurent Deniau on 19 Dec 2006 08:49 aloha.kakuikanu wrote: > Laurent Deniau wrote: > >>I am looking for a library (of an OO language) which uses a hierarchy of >>classes for predicate (type) dispatch in the context of multimethod. Ce >>concept is already well know and developed in the literature, but >>languages which support multimethods and metaclasses are not so common. >>Therefore, I have some difficulty to find such 'standard' use of class >>as predicates. The papers usually use hierarchies inspired from specific >>taxonomy (e.g. animals) which are not general enough to be useful. >> >>For the moment in my lib I have (<- means 'inherits from'): >> >>Predicate (root class) >> <- Nil >> <- TrueFalse >> <- True >> <- False >> <- Ordered >> <- Lesser >> <- Equal >> <- Greater >> >>But there is a lot of other possible predicates (not all useful): >> >>Next, Previous >>Forward, Backward >>Open, Close >>Front, Rear >>Bottom, Top >>Before, After >>Up, Down >>Even, Odd >>Left, Right >>North, South, Est, West >> >>etc... >> >>and selecting the predicates general enough (aliases and user defined >>predicates are always possible as extension) is somehow a problem of >>experience. BTW, the hierarchy stigmatize the possible logical >>combinations of the predicates (not, and, or) and strengthens the >>importance of its design (e.g. TrueFalse != Boolean). >> >>Has somebody already seen such hierarchy? Links and references would be >>really appreciated. Thanks. > > > What do you mean by "predicate"? Is it logical concept? I am talking about class/type predicate in the context of mutlimethod dispatch. For example, a binary method with True as its type specialisation for its second formal argument answer positively if the second argument on the caller side *is of class* True (or a subclass of True). class predicate dispatch is a subset of predicate dispatch which does not include dispatch on boolean expression. > Then we can > talk about relations in the database theory sence, both finite and > infinite. Relations do form a lattice, so you work out tthis idea into > extracting a "hierarchy" out of the lattice. But is this really what > you want to do? Maybe ;-) In fact multimethod implement natively the logical AND while inheritance implement natively the logical OR between types/classes. State exclusion is represented by different branches in the hierarchy. Considering the first case (TrueFalse): - TrueFalse is the indeterminate/uncertain state (also called the third state in tribool and noted '?') - True and False are (exclusive) specialization of TrueFalse by inheritance. - Specialisation can be used to perform state complement (logical NOT) because most specific specialisation are selected first. With these observations, it is easy to build logical tables with the 3 states by writing 4 specialisations (instead of 9). For example, AND is (sample of my code): /* AND | F | T | ? ----+---+---+--- F | F | F | F T | F | T | ? ? | F | ? | ? */ defmethod(OBJ, And, (False,TrueFalse)) retmethod(False); endmethod defmethod(OBJ, And, (TrueFalse,False)) retmethod(False); endmethod defmethod(OBJ, And, (TrueFalse,TrueFalse)) retmethod(TrueFalse); endmethod defmethod(OBJ, And, (True,True)) retmethod(True); endmethod Note that because of inheritance and specialization, this hierarchy is still valid if you restrict the allowed states only to True and False. The same can be done for Ordered, which could also be understood as Unordered depending on the existing specialisations. The advantage is that the hierarchy above can represent the relation: no order: specialisation on Ordered (as 'Unordered') only total order: specialisation on Lesser, Equal and Greater only partial order: idem total order plus specialisation on Ordered So the same hierarchy can be applied to many cases where the defined multimethods (the hierarchy is fixed) caracterise the allowed relation. a+, ld.
From: Dmitry A. Kazakov on 19 Dec 2006 11:10
On Tue, 19 Dec 2006 14:49:07 +0100, Laurent Deniau wrote: > aloha.kakuikanu wrote: >> What do you mean by "predicate"? Is it logical concept? > > I am talking about class/type predicate in the context of mutlimethod > dispatch. For example, a binary method with True as its type > specialisation for its second formal argument answer positively if the > second argument on the caller side *is of class* True (or a subclass of > True). Do you mean <: relation here? > class predicate dispatch is a subset of predicate dispatch which does > not include dispatch on boolean expression. What does "dispatch on Boolean expression mean?" Dispatch happens on a tuple of polymorphic objects. For example, AND dispatches on the tuple (1st argument, 2nd argument, result). >> Then we can >> talk about relations in the database theory sence, both finite and >> infinite. Relations do form a lattice, so you work out tthis idea into >> extracting a "hierarchy" out of the lattice. But is this really what >> you want to do? > > Maybe ;-) > > In fact multimethod implement natively the logical AND while inheritance > implement natively the logical OR between types/classes. It is difficult to understand why. Anyway, logical operations on types as sets of values produce new types. If we'd considered the domain sets of types as a lattice, we could consider AND, OR, NOT operations there. I don't think that might get us anywhere far, because the type systems of programming language are not enough strong to be able to describe all elements of such lattice. Consider NOT Integer. This would be a quite non-constructive thing. What are non-integers? What are the operations of? The second question is even more tricky. Let I do String OR Customer. What happens with *? > State exclusion > is represented by different branches in the hierarchy. > > Considering the first case (TrueFalse): > > - TrueFalse is the indeterminate/uncertain state (also called the third > state in tribool and noted '?') (in logic "uncertain" is usually denoted as _|_, flipped T) > - True and False are (exclusive) specialization of TrueFalse by inheritance. > - Specialisation can be used to perform state complement (logical NOT) > because most specific specialisation are selected first. > > With these observations, it is easy to build logical tables with the 3 > states by writing 4 specialisations (instead of 9). Hmm, it should be 8. = 2^3 2 = the depth of the type hierarchy 3 = the number of parameters within the same hierarchy (2 arguments + the result) When Boolean and TriState are related types and both arguments and the result of AND are covariant then the dispatching table of AND will have 8 slots: AND : Boolean x Boolean -> Boolean AND : Boolean x Boolean -> TriState AND : Boolean x TriState -> Boolean AND : Boolean x TriState -> TriState AND : TriState x Boolean -> Boolean AND : TriState x Boolean -> TriState AND : TriState x TriState -> Boolean AND : TriState x TriState -> TriState Taking into account commutativity of AND, the number of distinct signatures can be reduced to 6: AND : Boolean x Boolean -> Boolean AND : Boolean x Boolean -> TriState AND : Boolean x TriState -> Boolean == AND : TriState x Boolean -> Boolean AND : Boolean x TriState -> TriState == AND : TriState x Boolean -> TriState AND : TriState x TriState -> Boolean AND : TriState x TriState -> TriState Because TriState is a generalization of Boolean (or equivalently Boolean is a specialization of TriState) AND : Boolean x Boolean -> Boolean <= AND : Boolean x Boolean -> TriState AND : Boolean x TriState -> Boolean == AND : TriState x Boolean -> Boolean AND : Boolean x TriState -> TriState == AND : TriState x Boolean -> TriState AND : TriState x TriState -> TriState => AND : TriState x TriState -> Boolean > For example, AND is > (sample of my code): > > /* > > AND | F | T | ? > ----+---+---+--- > F | F | F | F > T | F | T | ? > ? | F | ? | ? > > */ > defmethod(OBJ, And, (False,TrueFalse)) > retmethod(False); > endmethod > > defmethod(OBJ, And, (TrueFalse,False)) > retmethod(False); > endmethod > > defmethod(OBJ, And, (TrueFalse,TrueFalse)) > retmethod(TrueFalse); > endmethod > > defmethod(OBJ, And, (True,True)) > retmethod(True); > endmethod > > Note that because of inheritance and specialization, this hierarchy is > still valid if you restrict the allowed states only to True and False. > > The same can be done for Ordered, which could also be understood as > Unordered depending on the existing specialisations. The advantage is > that the hierarchy above can represent the relation: > > no order: specialisation on Ordered (as 'Unordered') only > total order: specialisation on Lesser, Equal and Greater only > partial order: idem total order plus specialisation on Ordered > > So the same hierarchy can be applied to many cases where the defined > multimethods (the hierarchy is fixed) caracterise the allowed relation. The algebraic properties of the dispatching table you observed for AND are determined by: 1. Dispatching parameters = the arguments and results in which the method is polymorphic = covariant of the involved parameters. 2. Symmetries along the parameters. Like commutativity (of +,*, AND etc), group inverses (of - to +, / to *), De Morgan rules etc etc. For example, relations as < possess symmetries like a<b <=> not b>=a. This also can reduce the number of signatures. However, note that symmetries often get violated upon inheritance. For example, should you extend R to a set of square matrices over R, you would loose commutativity of *. 3. Properties of the domain sets of the involved types. Like existence of injective mappings between the values (generalization). This is as crucial as 2. When you extend R to C you loose order. When you extend R to intervals, the order stays, but gets crippled. The result of < becomes tri-state. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |