Theoretical issues with intersection and structural subtyping

[rotemdan]

I've spent what seems like an excessive amount of time thinking about intersections. I'm trying to figure why on earth would people assume they are natural or desirable, also considering there are much simpler and even more powerful alternatives with much less "strings" attached. I speculate a pattern of reasoning is that many people assume that if unions are useful and reasonable (which seems to be the case), then naturally, intersections must be as well (after all, aren't they two sides of the "same coin"?).

However, there is a fundamental (and disturbing) difference between the two:

Defining a union type C = A | B is just like saying that type C includes all the possible values of A as well as all the possible values of B (Val(A) U Val(B)). It seems to be generally accepted that any two types can be "unioned" this way. This would mean that the universal set or "superset" here is the set of all possible values (or set of all values possibly generated by all possible types). Seeing it like that seems, at least on the surface, reasonable and doesn't seem to have obvious negative implications (at least from the limited perspective of a non-mathematician like myself, but I will leave the possibility that a more knowledgeable person might find issues I'm not capable of).

This is not the same case for intersection!

For type I = A & B and assuming A and B are [edit: non-strict] interfaces (this includes both object or function types), in order for A & B to have any meaning, Val(A) and Val(B) must belong to the same superset! How would you intersect two infinite sets (due to non-strictness) without having a well-defined notion of what values they include?

Now consider A is an object type and B is a function type. In order for that to be possible, they would have to be seen as parts of the same superset. Say you "stretch" the math and define the superset as the union of the set of all possible functions and objects [edit: and their hybrids]. Doing that would have some serious implications about assignability:

interface ObjType {
    prop: string;
}

interface FuncType {
    (arg: number): boolean
}

interface HybridType {
    prop: string;
    (arg: number): boolean
}

In order for ObjType & FuncType to have any meaning, the two must belong of the same superset. However, this would imply HybridType must be considered to be a structural subtype of both ObjType and FuncType (remember, all object and function types are currently non-strict in TypeScript). This would be forced by the math:

let obj: ObjType;
let func: FuncType;
let hybrid: HybridType;

obj = hybrid; // This *must* work because it is dictated by the math! Works in 1.5.4
func = hybrid;  // This *must* work because it is dictated by the math! Works in 1.5.4

Strangely these assignments are actually allowed today (I assume for legacy reasons, to comply with some Javascript strangeness), but it is not at all obvious to be a natural thing to have. At any case, perhaps the designers decide, some day that some assignments don't make sense and should be outlawed? There is one in particular that I had doubts about:

interface ConstructorType {
    new (arg: boolean);
    prop: string;
}

let obj: ObjType;
let newable: ConstructorType;

// *Must* be possible if intersections are allowed between objects types
// and objects types with construct signatures! Forced by the math!
obj = newable; 

This additional example may not be seen as problematic for the design team (the assignment currently works, but if it's overlooked or controversial, please tell me and I will open a separate issue for it, as that would be off-topic here), and some of these combinations may not even be planned to be allowed in intersections (though multiple inheritance would accept them with no problems or implications whatsoever), but that's not the point.

The point is that by the mere act of introducing intersections (which to some might seem just like a minor, side feature), to some degree, you have sacrificed your type system to the "mercy" of the math gods. You have consciously reduced control over your own type system. Good luck!

[Edit: I had a mistake in the code that tested whether func = hybrid; works. It does actually work in 1.5.4, I modified the text accordingly]

[DanielRosenwasser]

in order for A & B to have any meaning, Val(A) and Val(B) must belong to the same superset!

This sounds incorrect. I think you mean that there is a set for which Val(A) and Val(B) overlap and form a "subset", unless I'm missing something.

[rotemdan]

@DanielRosenwasser

I guess I was describing the case for non-strict A and B. In general that may not correct.

The logic here is that in order to define the possible "expansions" of a non-strict type, it would need a superset to relate to. But in turn that superset would then dictate its super/subtype relationships with other types.

I'm not a math expert (I have a very weak understanding of type theory, if at all) but that seems reasonable to me.

[rotemdan]

I thought I should probably expand on why this wouldn't necessarily be a problem with inheritance:

interface ObjType {
    prop: string;
}

interface ConstructorType extends ObjType {
    new (arg: boolean);
}

let obj: ObjType;
let newable: ConstructorType;

Even if, say, it was decided that a constructor type is not generally assignable to an object type (again that is only used as an example and may not be real issue). It would still be possible to allow obj = newable through nominal subtyping (i.e. make that an exception if a relation is explicitly defined in the chain).

An even more powerful approach such as structural overloading/merging (or a similarly spirited alternative) may even completely disregard assignability and subtyping and work purely on the structure, so that wouldn't even be needed to be considered.

[danquirk]

Intersection types primarily exist to serve this purpose:

declare function mixin<T, U>(x: new (...args) => T, y: new (...args) => U): new () => T & U;

declare class Foo {
    x: string;
    y: string;
    z: string;
    doStuff(a: string): string;
}

declare class Bar {
    x: string;
    y: number;
    w: string;
    doStuff(a: number): string;
    doMore(x: number): string;
}

var FooBar = mixin(Bar, Foo);
var r = new FooBar();
var rx = r.x;
var ry = r.y;
var rz = r.z;
var rw = r.w;
var stuff = r.doStuff('hi');
var stuff2 = r.doStuff(1);
var more = r.doMore(1);

How does your proposal support functions like this which merge the properties of two types?

[rotemdan]

@danquirk

The subject here was more about pointing out a specific implication of intersection (this is not a completely mathematically rigorous statement, but a "real" mathematician might be able to formulate something close as a theorem):

Given non-strict interfaces A and B. Having A & B produce a nonempty, useful result (that is expressible in the programming language) which is itself a non-strict interface implicitly asserts that there is minimal expansion for A that is a subtype of B and a minimal expansion for B that is a subtype of A.

My style of writing turned out a bit harsh/inflammatory here, sorry for that. The intuitive idea is that intersection is "demanding" and requires strong assertions about the relationships between the types that are not always desirable. Inheritance, inheritance disregarding cycles, inheritance with function overloading, inheritance with function overloading and structural unions for non-function properties (which like intersection doesn't actually follow OOP style assignability so isn't real "inheritance" in general) are "raw", non-mathematical operations that are not usually subject to these problems.

---

Whether or not the original formulation or its variations can "imitate" various use cases for intersection was discussed at that issue (and probably would be off-topic here). Anyway, there were several observations that I mentioned:

In Javascript, it is not generally possible to automatically overload two functions, even with known signatures (unless perhaps Typescript provided some form of reflection):

function combineFunctions<F1, F2>(func1: F1, func2: F2): F1 & F2 {
  // How would this be possible in general without some form of reflection?
  // What should the combined function do when the arguments are undefined or null?
}

let func1 = (arg: number) => true;
let func2 = (arg: string) => 34;

let combinedFunction = combineFunctions<typeof func1, typeof func2>(func1, func2);

With a more "primitive" approach to merging, say, that simply overrides the first function with the second one if it is defined (the kind that is used by jQuery.extend) the func property would not be assignable to the intersection due to the way function overloading works (it "narrows" types, in contrast to a union that "widens" them):

interface Obj1 {
    func(arg: number): boolean;
}

interface Obj2 {
    func(arg: string): number;
}

let obj1: Obj1;
let obj2: Obj2;

// Equivalent to { func(arg: number): boolean; func(arg: string): number; }
let combinedObj: Obj1 & Obj2; 

combinedObj.func = obj1.func; // Error: incompatible types
combinedObj.func = obj2.func; // Error: incompatible types

// However this works, but should it?
obj1.func = combinedObj.func; // OK?
obj2.func = combinedObj.func; // OK?

So it turns out that using unions for function properties would model this common (maybe even idiomatic) real-world scenario better. However that would not be really useful without reflection because it would be impossible to determine which signature the property on the combined object has.

It is probably possible to formulate something that would provide all the functionality of intersection without the associated theoretical "burden", though many of those features (say, like intersecting unions) are rarely useful in practice. I mentioned the possibility of maintaining 100% backward compatibility with multiple inheritance and why I think it is important. There were many other issues and details, but since intersection is now finalized to Beta, I find less motivation in continuing discussing it.

[mhegazy]

Intersection types were not introduced as a new implementation of mixins or traits, it was introduced as is a way to model some existing JS constructs; and where it is possible, as noted in the OP, to model types that can not be implemented, in practice these are not common.

[rotemdan]

@mhegazy

The topic was about a theoretical issue with the concept of intersection. Namely that having an intersection of non-strict types which results in a non-strict type that is expressible in the language indirectly implies a sub-typing relationship between members of their families.

For example, allowing intersections between any constructor and non-constructor types, like:

interface A {
  new();
  a: number;
}

and

interface B {
  b: string
}

That yields an expected result:

interface A & B {
  new();
  a: number;
  b: string;
}

would imply that any constructor type that is structurally an "extension" of a non-constructor type, and say, only differ by, say, the new() signature:

ConstructorType {
  new();
  a: number;
}

PlainObjectType {
  a: number;
}

Must also be assignable to it. I.e.:

let o: PlainObjectType;
let c: ConstructorType;
o = c; // Must work because the type families are intersectable

That is not necessarily the case with inheritance or more purely structural operations, as an extension relationship between two types can either be declared through nominal subtyping (which would define an isolated relation that is only valid for the two type names), or using operations that don't have subtyping implications (like some of the ones I proposed as replacements to intersection).