Which statically typed languages support intersection types for function return values?

Question

Initial note:

This question got closed after several edits because I lacked the proper terminology to state accurately what I was looking for. Sam Tobin-Hochstadt then posted a comment which made me recognise exactly what that was: programming languages that support intersection types for function return values.

Now that the question has been re-opened, I've decided to improve it by rewriting it in a (hopefully) more precise manner. Therefore, some answers and comments below might no longer make sense because they refer to previous edits. (Please see the question's edit history in such cases.)

Are there any popular statically & strongly typed programming languages (such as Haskell, generic Java, C#, F#, etc.) that support intersection types for function return values? If so, which, and how?

(If I'm honest, I would really love to see someone demonstrate a way how to express intersection types in a mainstream language such as C# or Java.)

I'll give a quick example of what intersection types might look like, using some pseudocode similar to C#:

interface IX { … }
interface IY { … }
interface IB { … }

class A : IX, IY { … }
class B : IX, IY, IB { … }

T fn()  where T : IX, IY
{
    return … ? new A()  
             : new B();
}

That is, the function fn returns an instance of some type T, of which the caller knows only that it implements interfaces IX and IY. (That is, unlike with generics, the caller doesn't get to choose the concrete type of T — the function does. From this I would suppose that T is in fact not a universal type, but an existential type.)

P.S.: I'm aware that one could simply define a interface IXY : IX, IY and change the return type of fn to IXY. However, that is not really the same thing, because often you cannot bolt on an additional interface IXY to a previously defined type A which only implements IX and IY separately.

---

_{Footnote: Some resources about intersection types:}

_{Wikipedia article for "Type system" has a subsection about intersection types.}

_{Report by Benjamin C. Pierce (1991), "Programming With Intersection Types, Union Types, and Polymorphism"}

_{David P. Cunningham (2005), "Intersection types in practice", which contains a case study about the Forsythe language, which is mentioned in the Wikipedia article.}

_{A Stack Overflow question, "Union types and intersection types" which got several good answers, among them this one which gives a pseudocode example of intersection types similar to mine above.}

Answer 1

Scala has full intersection types built into the language:

trait IX {...}
trait IY {...}
trait IB {...}

class A() extends IX with IY {...}

class B() extends IX with IY with IB {...}

def fn(): IX with IY = if (...) new A() else new B()

Answer 2

In fact, the obvious answer is: Java

Whilst it may surprise you to learn that Java supports intersection types ... it does indeed through the "&" type bound operator. For example:

<T extends IX & IY> T f() { ... }

See this link on multiple type bounds in Java, and also this from the Java API.

Answer 3

Original question asked for "ambiguous type". For that the answer was:

Ambiguous type, obviously none. The caller needs to know what they'll get, so it's isn't possible. All any language can return is either base type, interface (possibly auto-generated as in intersection type) or dynamic type (and dynamic type is basically just type with by-name call, get and set methods).

Inferred interface:

So basically you want it to return an interface IXY that derives IX and IY though that interface was not declared in either A or B, possibly because wasn't declared when those types were defined. In that case:

• Any that is dynamically typed, obviously.
• I don't remember any statically typed mainstream language would be able to generate the interface (it is the union type of A and B or intersection type of IX and IY) itself.
• GO, because it's classes implement interface if they have the correct methods, without ever declaring them. So you just declare an interface that derives the two there and return it.
• Obviously any other language where type can be defined to implement interface outside of definition of that type, but I don't think I remember any other than GO.
• It's not possible in any type where implementing an interface has to be defined in the type definition itself. You can however work around in most of them by defining wrapper that implements the two interfaces and delegates all methods to a wrapped object.

P.S. A strongly typed language is one in which an object of given type can't be treated as object of another type, while weakly typed language is one that has a reinterpret cast. Thus all dynamically typed languages are strongly typed, while weakly typed languages are assembly, C and C++, all three being typed statically.

Answer 4

The Go Programming Language kind of has this, but only for interface types.

In Go any type for which the correct methods are defined automatically implements an interface, so the objection in your P.S. doesn't apply. In other words, just create an interface that has all the operations of the interface types to be combined (for which there's a simple syntax) and it all Just Works.

An example:

package intersection

type (
    // The first component type.
    A interface {
        foo() int
    }
    // The second component type.
    B interface {
        bar()
    }

    // The intersection type.
    Intersection interface {
        A
        B
    }
)

// Function accepting an intersection type
func frob(x Intersection) {
    // You can directly call methods defined by A or B on Intersection.
    x.foo()
    x.bar()

    // Conversions work too.
    var a A = x
    var b B = x
    a.foo()
    b.bar()
}

// Syntax for a function returning an intersection type:
// (using an inline type definition to be closer to your suggested syntax)
func frob2() interface { A; B } {
    // return something
}

Answer 5

You might be able to do what you want by using a bounded existential type, which can be encoded in any language with generics and bounded polymorphism, e.g. C#.

The return type will be something like (in psuedo code)

IAB = exists T. T where T : IA, IB

or in C#:

interface IAB<IA, IB>
{
    R Apply<R>(IABFunc<R, IA, IB> f);
}

interface IABFunc<R, IA, IB>
{
    R Apply<T>(T t) where T : IA, IB;
}

class DefaultIAB<T, IA, IB> : IAB<IA, IB> where T : IA, IB 
{
    readonly T t;

    ...

    public R Apply<R>(IABFunc<R, IA, IB> f) {
        return f.Apply<T>(t);
    }
}

Note: I haven't tested this.

The point is that IAB has to be able to apply an IABFunc for any return type R, and an IABFunc has to be able to work on any T which subtypes both IA and IB.

The intent of DefaultIAB is just to wrap an existing T which subtypes IA and IB. Note that this is different from your IAB : IA, IB in that DefaultIAB can always be added to an existing T later on.

References:

• Existential types in C#

Answer 6

Ceylon has full support for first-class union and intersection types.

You write a union type as X | Y and an intersection type as X & Y.

Even better, Ceylon features a lot of sophisticated reasoning about these types, including:

• principal instantiations: for example, Consumer<X>&Consumer<Y> is the same type as Consumer<X|Y> if Consumer is contravariant in X, and
• disjointness: for example, Object&Null is the same type as Nothing, the bottom type.

Answer 7

TypeScript is another typed language that supports intersection types T & U (along with union types T | U). Here's an example cited from their documentation page about advanced types:

function extend<T, U>(first: T, second: U): T & U {
    let result = <T & U>{};
    for (let id in first) {
        (<any>result)[id] = (<any>first)[id];
    }
    for (let id in second) {
        if (!result.hasOwnProperty(id)) {
            (<any>result)[id] = (<any>second)[id];
        }
    }
    return result;
}

Answer 8

While Rust does not have the traditional OOP notion of inheritance, it does have a notion of traits and trait objects. Object-safe traits perform roughly the same role as interfaces, and trait objects express most of the same affordances as interface-typed objects in OOP languages like C# and Java.

Rust lets you express a trait object for any object-safe trait, and a new trait can be defined that represents an arbitrary intersection of traits, then automatically implemented for all implementors of the constituent traits. This new trait will be object-safe if its supertraits are. This means that it is possible to return a trait object for an arbitrary intersection of object-safe traits, and you can bolt-on the new trait to an externally-defined type.

Unfortunately, this object of an intersection of traits can't be expressed simply as dyn X + Y*, and needs the explicit boilerplate of a subtrait and blanket implementation. See the RFC for Trait objects for multiple traits.

fn returns_intersection(which: bool) -> Box<dyn XY> {
    if (which) {
        Box::new(A{ … })
    } else {
        Box::new(B{ … })
    }
}

trait X { … }
trait Y { … }
trait Z { … }

trait XY: X + Y {}
impl<T: X + Y> XY for T {}

struct A { … };

impl X for A { … }
impl Y for A { … }

struct B { … };

impl X for B { … }
impl Y for B { … }
impl Z for B { … }

*except under limited circumstances

Answer 9

C++ functions all have a fixed return type, but if they return pointers the pointers can, with restrictions, point to different types.

Example:

class Base {};
class Derived1: public Base {};
class Derived2: public Base{};

Base * function(int derived_type)
{
    if (derived_type == 1)
        return new Derived1;
    else
        return new Derived2;
}

The behavior of the returned pointer will depend on what virtual functions are defined, and you can do a checked downcast with, say,

Base * foo = function(...);dynamic_cast<Derived1>(foo).

That's how polymorphism works in C++.

Answer 10

Python

It's very, very strongly typed.

But the type is not declared when a function is created, so the returned objects are "ambiguous".

In your specific question, a better term might be "Polymorphic". That's the common use case in Python is to return variant types which implement a common interface.

def some_function( selector, *args, **kw ):
    if selector == 'this':
        return This( *args, **kw )
    else:
        return That( *args, **kw )

Since Python is strongly typed, the resulting object will be an instance of This or That and cannot (easily) be coerced or cast to another type of object.