Type and library issues

Work in progress

Comprises and Excludes: Should exhaustive lists also be mutually exclusive?

background

Fortress's type system supports library writing, in a way that allows much of the language to be implemented in the library itself. One problem that we've had recently is definition of generators and reducers. Iteration generators are written with multiple overloadings on the reductions found with in a loop body, so that the iteration and reduction orders are both correct and efficient. For example, associative-commutative reducers that have identities (for example, integer "+") allow the greatest freedom in reduction ordering; non-associative, non-commutative reducers allow no freedom in their reduction ordering. (A binary-associative-with-id operation is a monoid).

Here's a portion of the extends-graph for reducers.

                              BinaryReducer
                                /       \
               AssociativeReducer        ReducerWithId
               /                \        /           \
NonMonoidAssociativeReducer    MonoidReducer    NonMonoidReducerWithId

The definition of this graph requires both "comprises" and "excludes" constraints on inheritance. It should not be possible for someone to define a type that is yet-another kind of AssociativeReducer, nor should it be possible for someone to define a type that is both MonoidReducer and NonMonoidAssociativeReducer. We can forbid the introduction of new direct subtypes by declaring

  trait AssociativeReducer extends BinaryReducer
      comprises {NonMonoidAssociativeReducer, MonoidReducer}
  trait ReducerWithIdentity extends BinaryReducer
      comprises {NonMonoidReducerWithIdentity, MonoidReducer}

and we can forbid the nonsensical pairs of extensions by declaring

  trait NonMonoidAssociativeReducer extends AssociativeReducer
      excludes {MonoidReducer, NonMonoidReducerWithIdentity}
  trait MonoidReducer extends {AssociativeReducer, ReducerWithIdentity}
      excludes {NonMonoidReducerWithIdentity}
  trait NonMonoidReducerWithIdentity extends ReducerWithIdentity
      (* exclusion is reflexive *)

The question, or the problem, comes with larger and larger numbers of similar-but-different operators. For N disjoint operator varieties, (N²-N)/2 exclusions are required, and this will be onerous and difficult to maintain. If we decided that "X comprises {Y, Z}" also declared that "Y excludes Z", then the quadratic blow-up in exclusions would go away.

However, doing this would take away the ability to declare an exhaustive set of non-exclusive direct subtypes. We haven't thought of a useful example yet, but that doesn't mean there isn't one. (Is it necessary and/or useful for BinaryReducer to list all of its direct subtypes? If so, that would be an example, because we see here that Monoid extends both AssociativeReducer and ReducerWithIdentity.)