Discussion thread for RFC FS-1043 (Extension methods can solve trait constraints)

[dsyme]

Discussion thread for F# RFC FS-1043 - Extension members should be available to solve operator trait constraints

[dsyme]

Something I noticed during testing... First, that this allows extension operators on arrays like this:

    type ``[]``<'T> with 
        static member inline (+)(a, b) = Array.map2 (+) a b

Second, F# only currently supports extension instance methods on tuple types, and those only via C#-extensions. So this is not allowed:

    type System.ValueTuple<'T,'U> with 
        static member inline (+)(struct(a,b), struct(c,d)) = struct(a + c, b + d)
    type System.Tuple<'T,'U> with 
        static member inline (+)((a,b), (c,d)) = (a + c, b + d)

    let v1 = (1,2) + (3,4) 
    let v2 = (struct (1,2)) + (struct (3,4) )

Third, for the array example - and for any other similar generic extension operator - the (constrained) generic type parameter of the operator must not be the same as the enclosing, (which is unconstrained as with all F# extension members). So this:

    type ``[]``<'T> with 
        static member inline (+)(a:'T1[], b: 'T2[]) = Array.map2 (+) a b

and not this

    type ``[]``<'T> with 
        static member inline (+)(a:'T[], b: 'U[]) = Array.map2 (+) a b

[gusty]

Third, for the array example - and for any other similar generic extension operator - the (constrained) generic type parameter of the operator must not be the same as the enclosing, (which is unconstrained as with all F# extension members). So this:

That's currently a restriction for normal static methods as well.
In F#+ tend to use a lowercase for the type parameter in the type and the same identifier but uppercase in the static methods. Otherwise it tries to add constraint to the type.

[abelbraaksma]

First, that this allows extension operators on arrays like this:

I think that's a good thing? Or do you suggest this should not be allowed? Unless it causes issues with existing code, this looks like a good extra 'nice to have' :)

[Swoorup]

type int with 
    member x.Show() = printfn "%A" x

Will RFC FS-1043 also allow solving constraints for non-static methods like the above?

[abelbraaksma]

It would be nice if this proposal could also take constants into account. The use case is simple, suppose you need to write numeric code that depends on something like Int32.MaxValue (and any other numeric type that has this constant field), currently you won't be able to do so, and after this change it would require writing an extension method (or property) for each type.

Another use case is where you want your code to depend on a constant field like DefaultValue.
The advantage of allowing this is that constants are differently compiled than normal fields and can result in better performance, even more so if the only alternative is writing an extension method just for getting the constant.

Allowing resolution of constant fields seems a relatively easy addition, considering that normal fields can already be resolved. But I may be wrong.

Apologies if this is out of scope.

[dsyme]

I'm examining some consequences of the part of this RFC "Weak Resolution no longer forces overload resolution...". In general this seems a great improvement. However, I have found one case where, for the complicated SRTP code such as found in FSharpPlus, existing code no longer compiles.

Example

Here is a standalone repro reduced substantially, and where many types are made more explicit:

module Lib

let inline CallApplyMethod (input1: ^I1, input2: ^I2, mthd : ^M) : ^R =
    ((^M or ^I1 or ^I2 or ^R) : (static member ApplyMethod : ^I1 * ^I2 * ^M -> ^R) input1, input2, mthd)

let inline CallMapMethod (mapping: ^F, source: ^I, _output: ^R, mthd: ^M) =
    ((^M or ^I or ^R) : (static member MapMethod : (^I * ^F) * ^M  -> ^R) (source, mapping), mthd)

type Apply =
    static member inline ApplyMethod (f: ^AF, x: ^AX, _mthd:Apply) : ^AOut = ((^AF or ^AX) : (static member Apply : ^AF * ^AX -> ^AOut) f, x)

type Map =
    static member inline MapMethod ((x: ^FT, f: 'T->'U), _mthd: Map) : ^R = (^FT : (static member Map : ^FT * ('T -> 'U) ->  ^R) x, f)

let inline InvokeApply (f: ^AF) (x: ^AX) : ^AOut = CallApplyMethod(f, x, Unchecked.defaultof<Apply>)

let inline InvokeMap (mapping: 'T->'U) (source: ^FT) : ^FU =  CallMapMethod (mapping, source, Unchecked.defaultof< ^FU >, Unchecked.defaultof<Map>)

[<Sealed>]
type ZipList<'s>() =

    static member Map (_xs: ZipList<'a>, _f: 'a->'b) : ZipList<'b> = failwith ""

    static member Apply (_fs: ZipList<'a->'b>, _xs: ZipList<'a>) : ZipList<'b>  = failwith ""

The following code fails to compile with this RFC activated:

let inline AddZipLists (x: ZipList<'a>, y: ZipList<'a>) : ZipList<'a> =
    InvokeApply (InvokeMap (+) x) y

Explanation

The characteristics are

1. The problem involves the use of chained method constraints (InvokeApply --> ApplyMethod --> Apply and InvokeMap --> MapMethod --> Map).

2. There is no overloading directly, but this code is generic and there is the potential for further overloading by adding further extension methods.

3. The definition of the nested member constraints relies on all argument and return types, e.g. (^M or ^I or ^R) for the MapMethod constraint and (^M or ^I1 or ^I2 or ^R). Because of this, the return type of InvokeMap (+) x is not known to be a ZipList until weak resolution is applied to the constraints. The nested member constraints are thus "over-flexible" i.e. under-constrained for use in writing generic code.

4. The resolution of the nested member constraints will eventually imply that the type variable 'a support the addition opreator.

5. After this RFC, the generic function AddZipLists now gets generalized before all member constraints are fully solved. The process of generalizing the function makes the type variable 'a rigid (generalized). The member constraints are then solved via weak resolution in the final phase of inference, and the return type of InvokeMap is determined to be a ZipList, and the 'a variable requires an addition operator. Because the code has already been generalized the checking fails.

Workarounds

There are numerous workarounds:

1. sequentialize the constraint problem rather than combining the resolution of the Apply and Map methods, e.g.

let inline (+) (x: ZipList<'a>, y: ZipList<'a>) : ZipList<'a> =
    let f = InvokeMap (+) x
    InvokeApply f y

This works because using let f = InvokeMap (+) x forces weak resolution of the constraints involved in this construct (whereas passing InvokeMap (+) x directly as an argument to InvokeApply f y leaves the resolution delayed).

2. Another approach is to annotate, e.g.

let inline (+) (x: ZipList<'a>, y: ZipList<'a>) : ZipList<'a> =
    InvokeApply (InvokeMap ((+): 'a -> 'a -> 'a) x) y

This works because the type annotation means the op_Addition constraint is immediately assocaited with the type variable 'a that is part of the function signature.

3. Another approach (and likely the best) is to no longer use return types as resolvers in this kind of generic code. (My understanding is that the use of return types as resolvers in such cases FSharpPlus was basically "only" to delay weak resolution anyway). This means using this definition:

let inline CallMapMethod (mapping: ^F, source: ^I, _output: ^R, mthd: ^M) =
    ((^M or ^I) : (static member MapMethod : (^I * ^F) * ^M  -> ^R) (source, mapping), mthd)

instead of

let inline CallMapMethod (mapping: ^F, source: ^I, _output: ^R, mthd: ^M) =
    ((^M or ^I or ^R) : (static member MapMethod : (^I * ^F) * ^M  -> ^R) (source, mapping), mthd)

With this change the code compiles.

This is the only example I've found of this in FSharpPlus. However I guess there may be client code of FSharpPlus that hits this problems. In general I suppose it may result whenever we have

     let inline SomeGenericFunction (...) =
        ...some composition of FSharpPlus operations that use return types to resolve member constrinats....

I could certainly see this happening in client code of FSharpPlus code. I don't think there is any simple adjustment to the RFC to avoid this problem, though I suspect the RFC allows the systematic removal of the use of return types as resolvers

Recommendation

1. Keep the change in the RFC

2. Adjust FSharpPlus to no longer use return types as resolvers unless absolutely necessary

3. Apply workarounds for client code by adding further type annotations

4. As part of this RFC I think we should also deliver a guide on writing SRTP code that documents cases like this and gives guidelines about their use. (Aside: This is skipping ahead as the guidelines have not been written, but I have to say that on the whole much of FSharpPlus would fall outside these guidelines and would thus not be recommended for use according to those guidelines: the library just relies on too much overloading and produces exceptionally obscure error messages when resolution fails. However we may be able to work with @gusty and the other authors to progressively adjust FSharpPlus and at least precisely document the variations on SRTP being used, and perhaps converge.)

Slightly Simpler Example

For completeness here's a vastly simpler example

let inline InvokeMap (mapping: ^F) (source: ^I) : ^R =  
    ((^I or ^R) : (static member Map : ^I * ^F ->  ^R) source, mapping)

 // A similated collection
type Coll<'T>() =

    // A similated 'Map' witness
    static member Map (source: Coll<'a>, mapping: 'a->'b) : Coll<'b> = new Coll<'b>()

Now consider this generic inlince code:

let inline MapTwice (x: Coll<'a>) (v: 'a) : Coll<'a> =
    InvokeMap ((+) v) (InvokeMap ((+) v) x)

Here the trait call for InvokeMap depends on return type and can only be strongly resolved once the return type is known (because of the use of (^I or ^R)). Changing this ^I resolves the problem.

[dsyme]

From Slack with @gusty:

@gusty says

"Hmmm. But for some functions the return type is key"

@dsyme says:

The thing about, say, Map is that if the input collection type is known (e.g. C<'T>) then the user will expect all resolutions to proceed immediately and code to generalize normally. If you're delaying on the return type then resolutions may be delayed until much later. Its normal for things like empty to need a type annotation in F# code and the user won't be too surprised. However it's not normal for object oriented things like xs.Map(f) to need annotations of return type to resolve overloading to determine what you're mapping to.

Basically FSharpPlus SRTP relies on F# OO programming/resolution, so needs to follow some of the rules of OO design. For the cases where an F# API allows return type overloading (or you decide to allow it through the use of the new AllowOverloadOnReturnType attribute) then it's ok, and in some cases like zero it's ok to simulate it. But don't rely on it for cases where it would not be reasonable to overload on return type otherwise.

And then this side comment from @dsyme:

Here's an idea: In general I think it would be really nice if FSharpPlus were somehow written so it was always possible to progressively concretize code that uses the operators through a simple regular process requiring no thought. I think it's kind of close but you need more.

For example it should be possible that each operator like map can be systematically replaced by Map.Map overload call. This would remove the reliance on SRTP.

And then there should be a specific regular name for each target overload available. So if you want to remove the reliance on method overloading then you can do Map.MapZipList And then you're down to code that has no overloading, no operators, no SRTP. Something really systematic and regular.

The use of SRTP and overloading results in brutal error messages and compilation times and a systematic way of eliminating it would be great.

As an aside I dislike how abstractions like Arrows and Bifunctors and Dimaps creep into basic coding. If you can hide that stuff away in namespaces so none of it is activated unless you do open FSharpPlus.Control.Arrows that would be great. It should be pay as you go, not a massive hit of complexity added to your error messages up front. I think some of these could also just be removed or put into "FSharpPlus.Advanced". I get the value of a library providing a super-generic "map" and a few of the other operators, but some are just too obscure.

[dsyme]

I added the notes about this issue in the compatibility sectiuon of the RFC

[dsyme]

I also added testing to the implementation PR

[NinoFloris]

However it's not normal for object oriented things like xs.Map(f) to need annotations of return type to resolve overloading to determine what you're mapping to.

Basically FSharpPlus SRTP relies on F# OO programming/resolution, so needs to follow some of the rules of OO design.

Is F#+ even a proponent of instance member overloads? i.e. isn't this somewhat of a strawman? In any case I hope we can all agree that OO style method chaining shouldn't need return type annotations, I would for instance not mind it one bit if AllowOverloadOnReturnType could not be used on instance members. However when static members are used (as they mostly are in F#+) we're not far of from functions like empty, zero, etc. which sometimes need annotations. @dsyme Could you elaborate a bit on this, was it w.r.t. F#+ or generally speaking?

[dsyme]

Is F#+ even a proponent of instance member overloads?

Yes some F#+ operators like zero rely on return types on static members for resolution. It's ok to use ^R supports for this, preferably in conjunction with the AllowOverloadOnReturnType attribute proposed in this RFC to avoid the need for the dummy ^R typed arguments

Yes it's not about instance members specifically - though AFAIK there is no technical difference between static and instance here

[NinoFloris]

though AFAIK there is no technical difference between static and instance here

Technically no, I can't think of any differences myself either, but as you stated yourself xs.Map(f) is much less amenable to return type overloading than piping static members or functions. This is why I asked what instance members (as opposed to static members) had to do with F#+.

[gusty]

@dsyme Notice that the workarounds you wrote above for the AddZipLists, don't respect the original name of the function, instead you call the function (+) which redefines the original operator and that's a different effect.

Now, if I use the AddZipLists name (or another arbitrary one) for your proposed workarounds, they still fail to compile.