Re: looking for a predicate hierarchy

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
.

Relevant Pages
Loading