Add Intersection Types

[0x53A]

Add Intersection Types

I propose we add Intersection Types to the language.

What are they?

Intersection types are conceptually similar to union types.

Whereas a union type may be either one of multiple sub-types, an intersection types is all of its sub-types combined.

Because of this, and because in .Net classes may only inherit from a single parent, intersection types are only really usefull with interfaces.

Example:

type IA =
  abstract member DoA : unit -> unit
type IB =
  abstract member DoB : unit -> unit

type TUnion = A of IA | B of IB
type TIntersect = IA & IB

// instances

let unionA = TUnion.A({new IA with member DoA() = ()})
let unionB = TUnion.B({new IB with member DoB() = ()})

let intersected = TIntersect ({new IA with member x.DoA() = ()
                               interface IB with member x.DoB() = ()})

// usages:

// with a union, I need to match, and can then use the value it actually is
match unionA with
| TUnion.A a -> a.DoA()
| TUnion.B b -> B.DoB()

// in contrast. the intersection type is both sub-types:
intersected.DoA()
intersected.DoB()

The existing way of approaching this problem in F# is ...

Most often, unsafe type casts are used at runtime. They can also be approximated as a tuple:

let aAndB =
    {new IA with member x.DoA() = ()
     interface IB with member x.DoB() = ()}
let tpl : IA * IB = (aAndB :> IA, aAndB :?> IB)

// usage
(fst tpl).DoA()
(snd tpl).DoB()

Real-World Problems that motivated this

Representing an Actor that handles multiple messages

I am using Akka.Net in F#.
Akka.Net itself is objectly typed, but I have written a small typed wrapper on top of it similar to Akkling.

In Akka, an actor may handle multiple unrelated message types.

To correctly encode this in the type system, I would like to be able to say

let t : (IActorRef<A> & IActorRef<B>) = ...

where A and B are the two message types it can handle.

Note that this could also be encoded with true union types (unlike the explicit unions F# uses):

let t : IActorRef<(A|B)> = ...

Workaround:

Currently I explicitly unwrap and rewrap the ActorRef with the different types, which is basically an unsafe runtime cast.

Exposing only certain parts of a class

I have an ObservableCollection<'T>.

I want to expose this instance as readonly, but also want to expose its CollectionChanged-event so that clients can re-query the data if it changes.

My wish:

type MyT() =
  let collection = ObservableCollection(int)
  member x.Data : IEnumerable<string> & INotifyCollectionChanged = collection

With intersection types, I could expose only the enumerable (so that the consumer can read the data) and the event (so he gets notified), but he would not be able to change the data.

Current workarounds:

I can either expose the underlying ObservableCollection directly, and hope no-one changes it, or I need to expose two properties.

Re-Engineered System.IO.Stream

Currently Stream is an abstract base class which provides all possible methods. You need to do feature-checks at runtime (CanSeek),otherwise you get an exception.

Imagine we could re-implement Stream with intersection types:

You would have ISeekable, IReadable, IWritable, ...

You need a stream where you need to seek and read? Easy, ISeekable & IReadable.

Workaround:

You could create all permutations as interfaces, e.g. IReadableAndSeekable : IReadable, ISeekable,but this has two issues:

• the possible combinations explode
• you can't use an object that implements both IReadable and ISeekable,but not the combined marker-interface IReadableAndSeekable

Pros and Cons

The advantages of making this adjustment to F# are ...

Intersection Types are an established part of type theory and implemented in, for example, scala.
They enable further type-safety and replace runtime casts.

The disadvantages of making this adjustment to F# are ...

I don't know of a way to encode it in the CLR metadata, so it would be a F# only feature. Depending on the implementation, it would probably be erased and visible as object + Attributes.

Extra information

The scala documentation of Compound Types: http://docs.scala-lang.org/tour/compound-types.html

The typescript documentation of Intersection Types: https://www.typescriptlang.org/docs/handbook/advanced-types.html (it is the first one described)

A similar C# proposal: dotnet/roslyn#4586

Estimated cost (XS, S, M, L, XL, XXL): XL

Related suggestions: (put links to related suggestions here)

Affidavit (please submit!)

Please tick this by placing a cross in the box:

• This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• I have searched both open and closed suggestions on this site and believe this is not a duplicate
• This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

• This is not a breaking change to the F# language design
• I or my company would be willing to help implement and/or test this

[cartermp]

Also in Ceylon: https://ceylon-lang.org/documentation/1.3/tour/types/#intersection_types

I think this would be a great addition.

[Rickasaurus]

I'm a bit confused by this.

where A and B are the two message types it can handle.

How do you tell which one it is? What happens if you invoke a member that isn't available because it was on the other interface?

Even if the members were exactly the same except for the generic you'd also need to add a way to support a multi-typed scope, maybe by code gen over the two branches and some kind of dispatch? Seems very complicated.

[0x53A]

@Rickasaurus I'm not sure I follow. Could you expand a bit?

Here is a more complete example:

type MessageA = { X : string }

type MessageB =
| Other
| Different
| Things

// this actor can handle MessageA, MessageB and int
type MyActor() =
    inherit ReceiveActor()
    do
        base.Receive<MessageA>( ... )
        base.Receive<MessageB>( ... )
        base.Receive<int>( ... )

let myActorRef : ( IActorRef<MessageA> & IActorRef<MessageB> & IActorRef<int> ) = ...
myActorRef.Tell({ MessageA.X = "Y" }) // ok
myActorRef.Tell(MessageB.Things) // ok
myActorRef.Tell(1) // ok
myActorRef.Tell(MessageC.X) // does not compile
myActorRef.Tell("z") // does not compile

This example assumes that all members are implicitly available. Depending on the spec and implementation you may also need a cast:

let myActorRef : ( IActorRef<MessageA> & IActorRef<MessageB> ) = ...

// note the "safe" cast - it would fail at compile time, NOT runtime
(myActorRef :> IActorRef<MessageB>).Tell(MessageB.Things)

My preference would be that all members, which are not ambiguous, are directly available on the intersected type. For the others you would need a safe type cast.

Example:

type IA =
  abstract member DoA : unit -> unit
  abstract member Do : unit -> unit
type IB =
  abstract member DoB : unit -> unit
  abstract member Do : unit -> unit

let x : IA & IB = ...
x.DoA() // ok
x.DoB() // ok
x.Do() // error: ambiguous
(x :> IA).Do() // ok and type-safe

[Rickasaurus]

@0x53A I can see how might work nicely with (non-recursive?) union types.

For the interface example, they still require a cast, but I guess it still gives you a little bit of extra type safety on the caller side. I guess you could do something similar but more verbosely with method overloads for reach type that simply wrap an obj method.

Both IA and IB expose the same method with the same type. In the top example they both have a different generic though. I'm not sure how that would work out.

[0x53A]

@Rickasaurus I'm still not completely sure what you mean. This has nothing to do with union types, that was just an example for an actor message type. The first examples may have not been the best way to describe what I want.

Maybe scala describes it better than I do: http://docs.scala-lang.org/tour/compound-types.html

[isaacabraham]

Hmmm. Would this also apply to e.g. records? So to combine records A and B into a new Record C?

[0x53A]

No. That would also be an interesting proposal, but is not related to this. The reason is that this basically just combines multiple, opaque types. And one object can't be both Record A and Record B because each record is its own, sealed class.

That is also why this only works with interfaces and up to one concrete class. At the end, you need an object instance that satisfies all sub-types of the intersection type.

[Rickasaurus]

@0x53A Sorry if I sound like and idiot but I'm still trying to understand how they might work. It's not completely clear to me from the examples. The Scala one seems to be based on traits which have independent implementations. If you combined interfaces where do the implementations come from? If it must implement all of the Interfaces then couldn't you do this with generic interface constraints?

<'a when 'a :> IReadable and 'a :> ISeekable>

[0x53A]

If you combined interfaces where do the implementations come from? If it must implement all of the Interfaces then couldn't you do this with generic interface constraints?

Second one, one single object instance must implement all types.

Yes, in some cases you can approximate this with generic constraints. In general, you CAN do it, if you pass it into a method, but CAN'T do it, if it is the return value.

Let's adapt the second example:

open System.Collections.Generic
open System.Collections.Specialized
open System.Collections.ObjectModel

type MyT() =
  member x.SetData<'T when 'T :> IEnumerable<string> and 'T :> INotifyCollectionChanged > (t : 'T) =
        // now I can use both interfaces inside the method        
        ()


// usage:

let collection = ObservableCollection<string>()
let myT = MyT()

// this works (and the explicit generic parameter can be omitted - it will be inferred):
myT.SetData<ObservableCollection<string>>(collection)

This works because the caller controls the generic parameter and also passes in the concrete instance.

But how do we return something?:

open System.Collections.Generic
open System.Collections.Specialized
open System.Collections.ObjectModel

type MyT() =
  let collection = ObservableCollection<string>()
  member x.GetData<'T when 'T :> IEnumerable<string> and 'T :> INotifyCollectionChanged > () : 'T = collection


// usage:

let myT = MyT()

let collection = myT.GetData<???>()

The caller would need to set the generic parameter. But what does he set? The callee actually returns the OC, but doesn't want to expose the whole object, just the two interfaces.

This is where intersection types come in. You say the return value is IEnumerable<string> & INotifyCollectionChanged, which is NOT a generic type, but a concrete type (well, almost).

[0x53A]

Another scenario where this would help:

dotnet/fsharp#3999 (Implement IReadOnlyDictionary for dict)

Even with this implemented, you need to know that dict implements IReadOnlyDictionary and do an unsafe cast at runtime.

With intersection types you could instead type dict as seq<'key * 'val> -> (IDictionary<'key, 'val> & IReadOnlyDictionary<'key, 'val>).

Then the compiler knows that the object implements both and you can do a safe cast.

[vasily-kirichenko]

jus use safe cast (d :> IROD)

[0x53A]

how?

[vasily-kirichenko]

Does dict implements IROD?

[cartermp]

Nope (or not yet).

[0x53A]

Not yet, but it will in the future. But as far as I know there is no way to express that in the signature.

Currently dict is typed as seq<'key * 'val> -> IDictionary<'key, 'val>.

Changing this to seq<'key * 'val> -> IReadOnlyDictionary<'key, 'val> would present the same problem, just switched around.

IDictionary and IReadOnlyDictionary are not related in the type hierarchy.

With IT you could express that it returns both.

[NullVoxPopuli]

I wonder if intersection types would be a solution to this problem: #564 (comment)

[MarkNicholls]

In a sense you can already implement intersection types by implementing a type with both the constituent parts. You can also specifiy that a type is a member of an intersection using parametric parameters

when 'a :> IFoo and 'a :> IBar

so this can be boiled down into...can we make the anonymous expression

{ new IFoo with ... interface IBar with ... }

visibly (to the compiler, be of type IBoo and IBar?

(I have no problem with the rest of the proposal, but in the interests of cutting it down to the bare basics, and thus hopefully getting it sooner rather than later).

I suspect that's just an f# compiler thing (I am no expert in the framework itself)..but for me as long as the compiler understands these types soundly, I am happy, the rest I can work my way around, the bit I object to is having to explicitly create nominal types).

[ShalokShalom]

Intersection types are in Scala 3 as well now. They appear in all the talks and on the homepage of Dotty itself as the top mentioned feature: http://dotty.epfl.ch/docs/reference/new-types/intersection-types.html

[MarkNicholls]

I've returned to this (because irritatingly I wanted to do the same thing again and couldn't).

My only issue with this proposal is its name, we don't actually need intersection types i.e. a syntax in the type system, like "IA & IB", we can emulate that with parametric types i.e. "'requires 'a :> IA and 'a :> IB"

What we need are "anonymous object expressions", basically we need anonymous records be allowed to implement interfaces.

This IS discussed in

https://github.com/fsharp/fslang-design/blob/master/FSharp-4.6/FS-1030-anonymous-records.md

and accepted in theory, just not included in the scope of that enhancement.

I think it would also nicely unify the idea of object expressions and anonymous records and make the language simpler (though you'd probably preserve record syntax as a shorthand).

[lambdakris]

Would it be possible to accomplish something like what typescript has?

https://www.typescriptlang.org/docs/handbook/2/objects.html#intersection-types

I'm imagining that in F# it would look something like this:

// define your types
type Person = { GivenName: string; FamilyName: string }
type Phone = { CountryCode: string; SubscriberNumber: string }
type Contact = Person & Phone
type Lead = { Campaign: string } & Contact

// utilize your types
let person = { 
    GivenName = "John"
    FamilyName = "Doe" }
let phone = { 
    CountryCode = "+1"
    SubscriberNumber = "555-555-5555" }
let contact = { 
    GivenName = "Jane"
    FamilyName = "Doe"
    CountryCode = "+1"
    SubscriberNumber = "555-555-5555" }
let lead = { 
    Campaign = "Google"
    GivenName = "Timmy"
    FamilyName = "Doe"
    CountryCode = "+1"
    SubscriberNumber = "555-555-5555" }

This seems like a really useful (and more robust) alternative to inheritance, where all you inherit is essentially structure. Allowing one to efficiently build up type definitions from common parts and avoiding any dangers of inheriting or overriding behavior.

[Happypig375]

What about composition and containing the components?

[yatli]

This repo is full of gems :)

A few questions:

1. Does it apply to abstract classes? Of course there must be at most one.
2. Is the type erased after typecheck? Erased = can be used across assembly boundaries, maybe not as type anymore but as type constraint where applicable, but remains a generic 'a otherwise. Not erased = have explicit type definition and cannot cast from one A&B to another.
3. ... which brings the 3rd question -- the proposal refers to anonymous unions as "true unions" -- do we have "true intersections" here? Named vs. Anonymous equivalence?

See also: https://github.com/fsharp/fslang-design/blob/main/FSharp-4.6/FS-1030-anonymous-records.md#design-principle-by-default-works-across-assembly-boundaries

[lambdakris]

Hmm, those are some good questions. Not really sure about composition and containment. I can at least say that I don't think an intersection type feature should concern itself with composing values of the part types, though if down the line this turns out to be desirable then I suppose it could be tacked on. Thinking about it more, I'm also not sure whether intersection makes sense for anything other than record types. Maybe a way to look at it is as a type combination mechanism, such that: 1) Object types combine through inheritance, Record types combine through intersection, and Union types and Function types don't combine, just compose? In terms of type erasure, I almost lean to not erased because I really like the idea of this as a type combination mechanism, and I would like the combined type to be a proper type, but perhaps there are good reasons not to do so?

[jl0pd]

There is related C# feature called "roles" dotnet/csharplang#5497, which will be implemented eventually and will bring runtime support for this

[ShalokShalom]

I like to leave this here:

https://ceylon-lang.org/blog/2015/10/27/why/#union_and_intersection_types

Ceylon was the first modern language to introduce a full implementation of union and intersection types, and the first language to realize that union and intersection types make flow-typing and type inference, especially generic type inference, very much simpler, more predictable, and more elegant.

[dsyme]

I'm closing this as while it's a sound feature it's not likely to make it into the F# language design, as it's a major addition to the type inference system

[Happypig375]

@dsyme Would someone in the community still be able to implement this if wanted?

[dsyme]

@dsyme Would someone in the community still be able to implement this if wanted?

@Happypig375 Perhaps - the technical details for type inference are however really non-trivial. It would need lots of care.

I've left a related note in #1262 which seems to point towards intersection types.

I could be convinced to reopen this if #1262 is first implemented.

[SchlenkR]

I could be convinced to reopen this if #1262 is first implemented.

@dsyme Re-open, since the requirements are met now?

[cartermp]

I'll re-open given the comments in there, and the fact that the & syntax is now added to types with the implementation