EditHint: Could be merged/recombined with
PartialOrder,
ConstraintLogicProgramming,
BooleanLattice,
DirectedAcyclicGraph (all
CategoryMath I guess)
EditHint 2: An appropriate place for most stuff could be
LatticeStructure.
Meet and join are two fundamental operations on types; which come from
CategoryTheory. A
meet of two types
T1 and
T2 is a type
Tm with the following properties:
- Tm is a (not necessarily proper) subtype of both T1 and T2. (Tm <= T1; Tm <= T2).
- There is no type Tx such that Tx <= T1, Tx <= T2, and Tm < Tx. (If there is, then Tx and not Tm might be a meet of T1 and T2
Note that if
T1 <
T2, then
Tm =
T1. Similarly, if
T2 <
T1, then
Tm =
T2, and if
T1 =
T2, then
Tm =
T1 =
T2.
Likewise, a
join is the opposite function; it has the following properties:
- Tj is a (not necessarily proper) supertype of both T1 and T2. (Tj >= T1; Tm >= T2).
- There is no type Tx such that Tx >= T1, Tx >= T2, and Tj > Tx. (If there is, then Tx and not Tj might be a join of T1 and T2
Note that if
T1 <
T2, then
Tj =
T2. Similarly, if
T2 <
T1, then
Tj =
T1, and if
T1 =
T2, then
Tj =
T1 =
T2.
In a type system with single inheritance, and neither
T1 nor
T2 is a subtype of the other, then their meet doesn't exist (alternatively, it could be said to be the
BottomType, and no instances of that exist). In a single-inheritance system, two types may have either one join or none; in singly-rooted systems without MI, any two types will have exactly one join (which may be
TopType).
In a type system with
MultipleInheritance, a class which inherits from
T1 and
T2 is a meet of the two types, unless it has a supertype which is a meet of
T1 and
T2. Likewise, multiple joins are possible in such a system. (The Java type system runs into difficulties with this; as the type of the ternary (? :) operator is - or ought to be - defined as the join of the types of the two choices. Since Java interfaces allow multiple joins to exist, the language takes the easy way out and uses Object instead, rather than selecting any particular join).
A
meet can also be called an
intersection, and a
join can be called a
sum or
union (preferably not
union, since unions in
CeeLanguage are not joins).
However, a
CeeLanguage union can certainly be used to represent a meet:
union {
struct foo *pFoo;
struct bar *pBar;
} foobar_u;
There have been many times I've wished for a way to have a
JavaLanguage (or occasionally
CeeSharpLanguage) reference have a meet-of-interfaces type. (Actually defining this meet as a new interface doesn't work -- because
JavaLanguage uses
NominativeTyping instead of
StructuralTyping, classes that implement all necessary interfaces would have to have the new interface explicitly added to their supertype list.) In
CeeSharpLanguage the concept sometimes falls apart because the same method may have multiple different implementations dispatched on the type of the reference.
See also
ConstraintLogicProgramming,
BooleanLattice,
DirectedAcyclicGraph