looking for a predicate hierarchy
in [OOP]
|
From: Laurent Deniau on 19 Dec 2006 13:12 Dmitry A. Kazakov wrote: > 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? yes. >>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. Yes. But tuple dispatch is a restricted version of predicate dispatch where dispatch happens on a tuple of polymorphic objects plus some constraint expressed as a boolean expression on the values of the instances. As an example: person vote(p(a)person) when age >= 18 // register vote return p; means that this vote specialization will be called if the type of its first argument p is a person and if its age (a state variable of a person) is >= 18. in C++ it could be written as: person& vote(person &p) { if (p.age >= 18) { // register p } return p; } But this is a closed form (not extensible). You can have a look to: http://www.cs.ucla.edu/~todd/research/oopsla04.pdf for more examples and code equivalence. Internally, predicate dispatch is equivalent to evaluate the boolean expression and call the specialization (generated by the compiler): person vote(p(a)person, true(a)bool) // register vote return p; which is just a tuple dispatch. See the work of Chambers http://citeseer.ist.psu.edu/337093.html for an efficient algorithm which transforms predicate dispatch into tuple dispatch (as 1-uple dispatch) and implemented in Cecil and some extension of Dylan. > 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. I don't think so. Logical operations on types do not produce new types, but select other type. > 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. It is. Consider the following hierarchy Number <- Integer <- Floating <- Complex If a specialization for Number exists, NOT Integer means Floating OR Complex specialization. If you add a subclass to Number, then it is automatically added to the set NOT Integer. This is why I said that inheritance implement logical OR and specialization *may* implement complement. > 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) but it is not a valid token and it also means non-terminal, error, nil, false, etc... So usually, libraries adopted indeterminate or uncertain for this 'third' boolean state (i.e. tribool). and I am not talking about predicate logic, but class for predicate dispatch. The context is quite different since it maps a structured set of types to allowed behaviors instead of a general set of types to a structure. This is also why I think it is difficult to extrapolate the usage of a such hierarchy if we haven't minimum experience with its use. >>- 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 no, 3^2 > 2 = the depth of the type hierarchy > 3 = the number of parameters within the same hierarchy (2 arguments + the > result) the depth of the hierarchy has nothing to do here (except to reduce the number of specialization required to fill the table by using some properties you enumerate below). This is the number of argument to the multimethod which matters, that is 2. 2 parameters, 3 states -> 3^2 > 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: I provided the truth table in my post. > 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 *. Right and hopefully both specializations will not lead to the same algorithm (e.g. commutativity is not lost but is not there). BTW matrices are not set nor structure, but only a *representation* of linear mapping. The non-commutativity of * is a property of linear mapping. > 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 because C is not an extension of R (or I misunderstand what you mean by extension). R^* is an extension of R. Vector spaces are not extension of C either, but C is a vector space. By the way, it is not simple to map mathematical structures to type system. So this kind of example always generate loooonnng discussions (which I would like to avoid, I am just quering for experience, references or links.). Regards, ld.
From: V.J. Kumar on 19 Dec 2006 15:20 "Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> wrote in news:12cnousl5msxh.1anmyqm356hwb$.dlg(a)40tude.net: > > (in logic "uncertain" is usually denoted as _|_, flipped T) In what logic ? > >> - 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 Without implication, your three-valued logic is not fully specified.
From: V.J. Kumar on 19 Dec 2006 15:35 Laurent Deniau <laurent.deniau(a)cern.ch> wrote in news:em9a39$p4i$1(a)cernne03.cern.ch: > Number > <- Integer > <- Floating > <- Complex > It is a silly hierarchy mathematically speaking because what is 'Number' ? Usual attempts to tie up mathematical structures in a naive object hierarchy are doomed to failure. I guess it's due to lack of mathematical education, a phenomenon regrettably common amongst computer science types. > > I provided the truth table in my post. > You did not for implication, so your logic is underspecified. > BTW > matrices are not set nor structure, but only a *representation* of > linear mapping. The non-commutativity of * is a property of linear > mapping. BTW, matrices are a structure allright, it's called a ring. > By the way, it is not > simple to map mathematical structures to type system. Right.
From: Dmitry A. Kazakov on 20 Dec 2006 03:57 On Tue, 19 Dec 2006 21:20:53 +0100 (CET), V.J. Kumar wrote: > "Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> wrote in > news:12cnousl5msxh.1anmyqm356hwb$.dlg(a)40tude.net: > >> (in logic "uncertain" is usually denoted as _|_, flipped T) > > In what logic ? Ah, there are so many. Even for a tri-state logic one could take "contradictory" T instead of "uncertain" _|_ as the third element. > Without implication, your three-valued logic is not fully specified. Right. That depends on the definition of implication. (not x) V y is well defined in tri-state logic because not _|_ = _|_. But it would be a bad implication to take. A better one is ~xVy, where ~_|_=T. That is not closed in tri-state logic. It is in four-state Belnap logic: x y x=>y ------------------ 0 0 1 0 1 1 0 _|_ 1 1 0 0 1 1 1 1 _|_ _|_ _|_ 0 T _|_ 1 1 _|__|_ 1 -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Dmitry A. Kazakov on 20 Dec 2006 05:25
On Tue, 19 Dec 2006 19:12:50 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> 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? > > yes. But True is a value, while <: is defined on types. >>>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. > > Yes. But tuple dispatch is a restricted version of predicate dispatch > where dispatch happens on a tuple of polymorphic objects plus some > constraint expressed as a boolean expression on the values of the > instances. I beg to disagree. It is exactly same. Any constraint imposed on the values of polymorphic objects effectively defines a [sub]type of. With these new types you get back a clean dispatch on tuples. > As an example: > > person vote(p(a)person) when age >= 18 > // register vote > return p; > > means that this vote specialization will be called if the type of its > first argument p is a person and if its age (a state variable of a > person) is >= 18. > > in C++ it could be written as: > > person& vote(person &p) > { > if (p.age >= 18) { > // register p > } > > return p; > } C++ does not have constrained subtypes but if it had that would be equivalent to plain overloading. Consider (imaginary syntax): subtype Adult is Person (Age in 18..Age'Last); -- Constrained subtype procedure Vote (X : in out Adult); -- Done This is not a dispatch yet. It would be one if Vote where a method and Adult were a derived type. But bringing Vote up to type hierarchy to Person is undesirable. > But this is a closed form (not extensible). > > You can have a look to: > > http://www.cs.ucla.edu/~todd/research/oopsla04.pdf Thank you for the reference. I saw many articles on this subject. I am not impressed by the idea, rather the opposite... >> For example, AND dispatches on the tuple (1st >> argument, 2nd argument, result). >> >>>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. > > I don't think so. Logical operations on types do not produce new types, > but select other type. Um, is there any difference? >> 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. > > It is. Consider the following hierarchy > > Number > <- Integer > <- Floating > <- Complex > > If a specialization for Number exists, NOT Integer means Floating OR > Complex specialization. If you add a subclass to Number, then it is > automatically added to the set NOT Integer. This is why I said that > inheritance implement logical OR and specialization *may* implement > complement. I think that it were inconsistent. What you propose is the following. There is a class Number. This class contains types Number, Integer, Floating, Complex. Formally you propose to define NOT S as T'Class - S. Here T is some ancestor of S. In your example: T=Number, S=Integer, T'Class={Number, Integer, Floating, Complex}. Objections: 1. NOT S is not a type. T'Class - S is a set of. 2. NOT S is not even a class. T'Class - S is not a class, it is an arbitrary set of types. A class is a set of types derived from some common base, class root. You cannot name any root for T'Class - S. 3. NOT is not a proper predicate, because it does not contain T as an argument. Let Comparable be an ancestor of Number. Should then NOT Integer be a in class Comparable or class Number? 4. What happens with multiple ancestors? 5. What happens with equivalent types (self subtypes). Consider: UTF-8-String <--> UCS-2-String Will NOT UCS-2-String contain UCS-2-String? >> 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 *? > > ? OK, "&" would be a much better choice. (:-)) The point is that types are values + operations. The type algebra should describe what happens with the operations as well as with the values. Conventional type algebraic operations like inheritance, aggregation, reference type construction etc, do it well. If type-algebraic lattice operations it would be quite difficult to do. >>>- 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 > > no, 3^2 > >> 2 = the depth of the type hierarchy >> 3 = the number of parameters within the same hierarchy (2 arguments + the >> result) > > the depth of the hierarchy has nothing to do here (except to reduce the > number of specialization required to fill the table by using some > properties you enumerate below). This is the number of argument to the > multimethod which matters, that is 2. > > 2 parameters, 3 states -> 3^2 Aha, now what you are aiming at. No, that would be untyped. In my view we cannot talk about dispatch without types, even less about types algebra. OK, we could forget about types, but then it would be fundamentally flawed. There are so many objections that I cannot list them all. Just consider a case where enumerating all states were impossible or too expensive. >> 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: > > I provided the truth table in my post. If you wanted to enumerate the states, then your table was not complete. In the most general case the value True of Boolean is not necessary the value True of TirState. It becomes obvious when you consider complex zero, real zero, integer zero etc. In a properly typed system values of different types are always different. >> 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 > > because C is not an extension of R (or I misunderstand what you mean by > extension). Mine ad-hoc definition would be roughly - there exists an injection mapping + some operations (like sqrt) get closed. > R^* is an extension of R. It is just another extension. There are many of different properties. With any extension you gain something, but also loose something. > Vector spaces are not extension of > C either, but C is a vector space. By the way, it is not simple to map > mathematical structures to type system. Right, because type systems are fundamentally weaker, and nothing can be done about it. > So this kind of example always > generate loooonnng discussions (which I would like to avoid, I am just > quering for experience, references or links.). Experience is for something that has a well established theory. Don't expect too much... (:-)) -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |