[WIP] Internals of trait implementations and generic constraints

[WhiteBlackGoose]

Problem

The CLR currently does not support implementing interfaces for unowned types (see roles and extensions).

The basic idea is to use attributes instead of core IL features like interface implementation and generic constraints.

Generic constraints

Here I consider only constraints to traits.

type TraitConstraint inherits Attribute
    new : (toConstrain: string,  traitName: string, traitTypeArgs: string[])

For example, assume we want to write a function which adds two generic types. For that, I implement trait CanAdd<T, T, T>, which has operator + defined. Now I want to create function add whose type argument is constrained to this trait:

add<T>: (a, b) : T x T -> T
where T : CanAdd<T, T, T>
= a + b

Then internally (or from C#) it looks like:

[TraitConstraint(toConstrain: "T", traitName: "CanAdd", traitTypeArgs: new [] {"T", "T", "T"})]
static T Add<T>(T a, T b) => /* ... */

Implementing traits for types we don't own

The attribute:

type TraitImplementation inherits Attribute
    new : (target: Type, implementation: Type)

Assume we are defining a trait. Then, we want to implement it for types we do not have control over. Then, each our trait should have a list associated with it. Each element of this list is pair - (type, implementation of the trait for this type).

Assume we have a trait, its implementation, and use:

trait CanQuack<T>
{
    Quack : T -> ()
}

impl CanQuack<T> for Foo
{
    Quack a = ()
}

quack<T> (a : T) =
where T : CanQuack<T>
=
a.Quack()

quack ( new Foo() )

Then in .NET it will look like

[FreshTrait]
[TraitImplementation(target: typeof(Foo), implementation: typeof(CanQuack_Foo_Generated<T>))]
interface CanQuack<T>
{
    public void Quack();
}

[CompilerGeneratedType]
public static class CanQuack_Foo_Generated<T>
{
    public static void Quack(Foo foo) { }
}

static void quack<T>(T a)
{
    if a has no method Quack, throw
    if it does, make sure that this type exists in CanQuack's list of implemented types
    OR the list of implemented traits contains the needed one
}

new Foo().Quack() // inlined when used within Fresh

Implementing traits we don't own for types we own

The attribute:

type TypeImplementation inherits Attribute
    new : (targetTrait: Type, typeArgs: string[])

Assume this time that we own Person, but not CanQuack<T>:

type Person = {
    name: string;
    age: int;
}

impl CanQuack<string> for Person {
    Quack(s : string) => print(s + name);
}

So in .NET it looks like

[TypeImplementation(targetTrait: typeof(CanQuack<>), typeArgs: new [] { "string" })]
record Person(string name, int age)
{
    Quack(string s) => WriteLine(s + name);
}

Interop

So far my current thought is that within Fresh we inline methods, where we use complicated generic constraints (similar to F#'s SRTP with inline).

However, we cannot force compilers of other .NET langs do the same. So when a Fresh-written method with trait constraints is invoked from, say, C#, it will somehow need to execute correctly without inlining.

To do it, from the .NET perspective these methods will have looser constraints, so that any type argument which passes in Fresh, would pass when invoking this method in C#.

Then, we will need to use reflection to determine the right method to execute (by storing a table of traits/types correspondance, though we have to refine these details later). If there's no such method (or, if there is, but the provided type does not implement the trait), then we throw an exception in runtime.

In the long run we can implement static analyzers for C# and F# which could prevent some cases of providing a bad type to a Fresh-written method.

[LPeter1997]

Additional responsibility: Associated types or static members will also be part of metadata, in case we support those in traits. For example, a trait could require that it defines a type:

trait Foo {
    type Bar;
}

This means that the implementation will have to define or alias a type named Bar.

[333fred]

I think you need more details on how you'll emit calls here. From what you've shown so far, you'll require reflection to call the implementation of Quack.

[WhiteBlackGoose]

My current thought is that we do it like in F#'s SRTP: inline methods with .NET-unsupported constraints. So reflection will be invoked only on interop. Will make it clearer it in the post

[333fred]

Even with the edit, I don't understand what the body of that static quack method will look like. It looks to me like you need reflection.

[WhiteBlackGoose]

Assume we have a method, which constraints T to implement CanQuack<T>, and then just invokes it on the instance:

quack<T> (a : T) where T : CanQuack<T>
{
    a.Quack()
}

Within Fresh (be that the same assembly or different one), we invoke this function:

blabla
quack(new Foo())
blabla

Then function quack will be inlined by the compiler. As we remember, method quack has just one line:

a.Quack()

where a is the only parameter of the function. So we supply it with new Foo() and inline:

blabla
new Foo().Quack()
blabla

That's it. We inline it before emitting IL.

Example of how it's accomplished by F#:

type Foo() =
    member _.Quack() = System.Console.WriteLine("Hello, world")

let inline quack< ^a when ^a : (member Quack : unit -> unit)> (c : ^a) =
    (^a : (member Quack : unit -> unit) c)

let someOther () =
    quack (Foo ())

If we look at someOther, where this function with complicated constraints is invoked, here's what we see:

public static void someOther()
{
    Foo foo = new Foo();
    Console.WriteLine("Hello, world");
}

So, no invokation of quack.

Yes its IL body will be reflection, but reflection will only be invoked when interop. When it's not interop, we should restore the initial code (from metadata? or somewhere else?) and inline it.

[333fred]

I'm somewhat concerned by the need to inline. That means that you'll either need to emit the implementation into the ref assembly (bloating the assembly, and potentially causing the need for other things in the ref assembly) or not have ref assemblies at all.

How does F# deal with inline methods that access private type data? Ie private fields.

[WhiteBlackGoose]

Yeah, F#ers don't use SRTP as often as we would use traits. Agree, that's some question yet to solve. Maybe we should balance between inlining and reflection? Not sure.

How does F# deal with inline methods that access private type data? Ie private fields.

From what I know, it does not allow (example).

[333fred]

The private data is going to be an issue, since presumably fresh won't disallow this?

[WhiteBlackGoose]

Yeah, it absolutely is, if we use the inlining strategy.

Now I'm thinking more about finding some balance between inlining and reflection. For instance, we could reveal otherwise private members by reflection.

Though it doesn't sound good in a sense, that we get an incentive to prefer public members to private (because public members unexpectedly can give a better perf).

Hmmmm....

[WhiteBlackGoose]

Another idea, based on basically using the internals of lambdas for external implementations.

E. g. we have type List<T>. In Fresh it's gonna externally implement interface

trait IIndex<TIndex, T> {
     [TIndex]: T
}

Now assume we have

func getIthElement<T, TElement>(i: int, indexable: T: IIndex<int, TElement>): TElement
    = indexable[i]

now in Fresh we have

val list = List<string>();
return getIthElement(0, list);

which gets compiled into

var list = new List<string>();
return getIthElement(0, new IIndexForList<string>(list));
...
[CompilerGenerated]
public struct IIndexForList<T> : IIndex<int, T>
{
    private List<T> field;

    public IIndexForList(List<T> arg) => field = arg;

    public T Item(int index) => field[index];
}