Algorithm for Type Disjointness Blocking Classes
Author Message 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

Tue, 22 May 2001 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages

Powered by phpBB® Forum Software