[Python-3000] my take on "typeclasses"

[Talin]

Marcin 'Qrczak' Kowalczyk wrote:
> Talin <talin at acm.org> writes:
> 
> 
>>   # Use as a function argument constraint
>>   @generic
>>   def flatten( x:concepts.iterable ):
>>      ...
>>
>>   # Another overload
>>   @generic
>>   def flatten( x:concepts.associative ):
> 

> How are concepts defined?

Each concept is essentially a class, written in either Python or C, that 
defines a set of tests, and a set of introspection methods.

As to how the tests are defined, that really depends on the test.

> How is it determined which specialization takes preference when
> a function is specialized on several matching concepts?
> 
> (With generic functions based on types this is determined by
> explicitly declared subtyping.)

Probably by using a generalization of what happens with types. In many 
rule-based systems, the strategy for resolving conflicts is "most 
specific wins". If you think about it, this is exactly what happens when 
you use subtyping - a specific type wins over a more generalized type.

In order to extend this to concepts, you would need a way to compare 
predicates by specificity (which is a handy feature to have regardless.)

For any two predicates A & B, comparing them will produce one of four 
possible outcomes:

    1) A is a superset of B. In other words, any object that meets the 
criteria for B also meets the criteria for A.
    2) B is a superset of A.
    3) Neither A nor B overlap. So an object that meets the criteria for 
A can never meet the criteria for B and vice versa.
    4) There may or may not be some overlap between A and B.

Case 4 is simply means that cases 1, 2 and 3 cannot be proven. It might 
mean that A and B overlap, or it might mean that there's no overlap and 
we just don't know it.

When a dispatcher needs to decide which method to call, they can compare 
the predicates using the above outcomes. Assume that an object X matches 
both criteria A and B:

    1) A includes B: Choose B.
    2) B includes A: Choose A.
    3) A distinct from B: Can't ever happpen.
    4) A overlaps B (maybe).
       -- strict method: raise AmbiguousDispatch exception
       -- lenient method: Use a heuristic to determine which predicate
          accepts the smaller number of possible inputs.

Note that much of this decision making can be computed in advance (at 
the time that the decorators are run). The decorator could construct a 
decision tree at startup.

One question that this brings up is what about comparisons between types 
and concepts? I think the answer here is that the concepts will need to 
be smart enough to be able to look at a type and determine whether or 
not there is a potential overlap. For example, we know that an integer 
can never be an iterable and vice versa, so the iterable concept, when 
presented with an "int", can return "no overlap" when attempting to 
compare them.

>>Testing for signatures, how about something like this:
>>
>>   def function( f:concepts.function( concepts.iterable, int ) )
>>
>>Which describes a function that takes an argument which is
>>a function that takes an iterable and an int.
> 
> 
> When such concept is called to test the claim against an object,
> how does it determine whether the object is a function which takes
> an iterable and an int?

By looking at the function's signature information.

(By the way, I did mention that this was a "sketch", which means that it 
doesn't have all the details worked out yet.)

-- Talin