Limited double dispatch for ADTs

[orthoxerox]

Right now the simulation of double dispatch is very cumbersome, you have to provide a visitor method for each derived class in the base class and so on. For example, this is what it takes to implement a virtual operator:

public abstract class Base
{
    public static string operator+ (Base lhs, Base rhs) => lhs.Add(rhs);

    internal virtual string Add(Base other) => other.AcceptAdd(this);

    internal string AcceptAdd(Base first)
    {
        throw new ApplicationException("unmatched visitor");
    }
    internal abstract string AcceptAdd(Foo first);
    internal abstract string AcceptAdd(Bar first);
}

public class Foo : Base
{
    internal override string Add(Base other) => other.AcceptAdd(this);

    internal override string AcceptAdd(Foo first) => "FooFoo";

    internal override string AcceptAdd(Bar first) => "BarFoo";
}

public class Bar : Base
{
    internal override string Add(Base other) => other.AcceptAdd(this);

    internal override string AcceptAdd(Foo first) => "FooBar";

    internal override string AcceptAdd(Bar first) => "BarBar";
}

But if C#7 is to have compiler-verified closed inheritance hierarchies (#188), why not automate that?

For example, you could write

public sealed abstract class Base
{
    public static string operator+ (Base lhs, Base rhs) => lhs.Add(rhs);

    [DoubleDispatch]
    internal abstract Base Add(Base other);
}

public class Foo : Base
{
    internal override Base Add(Foo other) => "FooFoo";

    internal override Base Add(Bar other) => "FooBar";
}

public class Foo : Base
{
    internal override Base Add(Foo other) => "BarFoo";

    internal override Base Add(Bar other) => "BarBar";
}

and C# would perform the following analysis:

1. Method M marked with DoubleDispatchAttribute must be declared in a sealed abstract class (BaseReceiver) and its first argument must be a sealed abstract class as well (BaseArgument) (BaseReceiver and BaseArgument can be the same class, as in the example above).
2. Methods with the same name M in derived classes of BaseReceiver can be covariant on their first argument.
3. Each combination of non-abstract child classes of BaseReceiver and BaseArgument must have an implementation. If BaseReceiver.M(BaseArgument, other_args...) is declared abstract, it is redefined to throw an exception (otherwise the program won't compile), but this redefinition doesn't count as an implementation for this step.
4. Each implementation of M is moved into the appropriate child of BaseArgument with a mangled name MMangled and swapped receiver and first argument.
5. Each class in the BaseReceiver inheritance tree receives an implementation of M(BaseArgument baseArgument, other_args...) with the same body return baseArgument.MMangled(this, other_args...);.

Some examples where this would be useful.

1. A parsing library, where Pattern + Pattern produces new Sequence(Pattern, Pattern), but LiteralPattern + LiteralPattern produces new LiteralPattern(lhs.Text + rhs.Text); Pattern | Pattern produces new Choice(Pattern, Pattern), but Pattern | Choice produces new Choice(Pattern, Choice) (a different constructor).
2. A state machine where each State produces IEnumerable<Decision> PossibleDecisions() and has a State Proceed(Decision decision) method. Proceed could use explicit pattern matching to enumerate all allowed decisions, but since each decision-taking method is relatively lengthy, they have to be split into separate methods anyway and choosing between them is a housekeeping task best delegated to the compiler.

[gafter]

Multimethods require CLR support.

[orthoxerox]

Not really, casting to dynamic enables unsafe multimethods, but my proposal is not about multiple dispatch in general, it's about a very limited, but useful subset.

[gafter]

I don't see anything special about double dispatch from a language point of view, compared to a more general multi dispatch. Since you can express double dispatch directly using visitors (and few people actually need to in commonly written code), it doesn't seem a prime candidate for language support.