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  
 
 [ 1 post ] 

 Relevant Pages 

1. Limited Collection Type Disjointness

2. Q: Is Block a first class object/type ?

3. Corrupt block/unknown block type freed bug

4. blocks and lambdas, or blocks as first-class entities

5. algorithm for type checking recursive types

6. type classes and type constraints

7. New User Question: extension types and python 2.2/class/type

8. Conflict Between Class-as-Module and Class-as-Type (long)

9. Extension Classes, Python Extension Types Become Classes

10. Block Scheduling Algorithm

11. std blocks vs blocks+cache ( was: block behavior)

12. Guaranteeing Disjointness

 

 
Powered by phpBB® Forum Software