Algorithm for Type Disjointness Blocking Classes

Previously:

Quote:

> 32. A class C is said to 'join' two types A and B in system S if S union

> {C} is a system, A and B are disjoint in S, and A and B are not disjoint

> in S union {C}.

Note that C does not join A and B in S if A and B are already non-disjoint

in S. Also note that C does not join A and B in S if S union {C} is not a

system (i.e. if C cannot be created without first creating other types).

...

Quote:

> 39. Algorithm to determine whether two given types A, B are disjoint in

> system S:

> If either (wlog A) is a singleton type: return not whether A's object is

> in B (36);

> if either (wlog A) is a union type: return whether both components of A

> are disjoint from B;

> if both are classes: return not whether there exists a class in S that is

> a subclass of both A and B;

> if both are limited types: see (33.d.v);

> if one (wlog A) is a class and the other (B) is a limited type:

> if B is null (33.d.vi): return yes;

> return whether A is disjoint from the base class of B in S.

40. Trivial slow algorithm to determine whether a class C joins two types

A and B in system S:

return A and B are disjoint in S (39), and A and B are not disjoint in (S

union {C}).

41. Better algorithm to determine whether a class C joins two types A and

B in system S: 'joins?(C :: <class>, A :: <type>, B :: <type>, S ::

<class-system>)'

If either type is a singleton type: return no;

if either type (wlog A) is a union type: return joins?(C, A.1, B, S) or

joins?(C, A.2, B, S);

if both are classes: return

whether there does not exist a class in S that is a subclass of both A

and B, and,

whether C is a subclass of both A and B;

if both are limited types: use (33.d.v) in a similar way to (40);

if one (wlog A) is a class and the other (B) is a limited type:

if B is null (33.d.vi): return no;

return joins?(C, A, B.base-class, S) (and see 'both are classes').

--

Ashley Yakeley, Seattle WA