Friday, September 20, 2013

On Confluence and Type Parameter Unification in C#

Awhile back I had written about a a type unification nuisance I had run into. In a nutshell, the problem occurs when a class with two type parameters tries to implement the same interface twice, once for each type parameter:

// compiler error:
// 'Foo<T0,T1>' cannot implement both 'IEnumerable<T0>' and
// 'IEnumerable&;lt;T1>' because they may unify for some type
// parameter substitutions
public class Foo<T0, T1> : IEnumerable<T0>, IEnumerable<T1>
{
}

As Doug McClean pointed out in the comments, the reason behind this error is because the two implementations of the interfaces may not be confluent, ie. behaviourally identical, in which case there's no legitimate way to choose between the two.

The application I had in mind at the time used marker interfaces, ie. interfaces with no methods or properties, so they were guaranteed to be confluent. I also had a sneaking suspicion that C# already permitted this structure elsewhere, but they just try to superficially enforce this rule like some other annoying aesthetic constraints.

This turns out to be exactly the case, and it is possible to implement the same interface twice for two type parameters. All you need to do is implement the interfaces at two separate classes in the same inheritance hierarchy, and C# lets this pass with nary a whimper. Here's the sample code:

public interface IFoo<T>
{
    void Bar(T value);
}
public abstract class FooBase<T0, T1> : IFoo<T1>
{
    public void Bar(T1 value)
    {
        Console.WriteLine("T1 Bar");
    }
}
public sealed class Foo<T0, T1> : FooBase<T0, T1>, IFoo<T0>
{
    public void Bar(T0 value)
    {
        Console.WriteLine("T0 Bar");
    }
}
public static class Example
{
    public static void Main(string[] args)
    {
        var core = new Foo<int, int>();
        var ifoo = core as IFoo<int>;
        var foob = core as FooBase<int, int>;
        var ifoo2 = foob as IFoo<int>;

        core.Bar(2);  // output: T0 Bar
        ifoo.Bar(2);  // output: T0 Bar
        foob.Bar(2);  // output: T1 Bar
        ifoo2.Bar(2); // output: T0 Bar
    }
}

So reduction is still confluent because all views of IFoo<T> go through the most recent implementation in the inheritance hierarchy. The only way to call the Bar method on FooBase is by explicitly casting to an instance of FooBase and invoking Bar.

This recently bit me since I was implementing an IObserver<T> that was observing two differently typed streams, but because the interfaces were declared at different levels of the inheritance hierarchy, the compiler never complained. Not very common I agree, but for consistency, I'd suggest that either this structure too be ruled out, or that type unification on type parameters be permitted via some convention just like it's allowed via inheritance. For instance, select the implementation for the first (or last) type parameter.

No comments: