Complications with multiple upper bounds

[RossTate]

@titzer's Jawa system made use of importing types with multiple upper-bound constraints. More generally, permitting type variables to have multiple upper-bound constraints is often quite useful for low-level type systems. For example, a user-level casting operation often takes the run-time representations of two unknown types (represented as type variables) and returns a boolean that, if equal to true, guarantees that one type variable is a subtype of another, thereby imposing an additional upper bound on the former type variable. (Such an operation is often useful for, say, optimizing multiple assignments into a covariant array in reified polymorphic code: perform one cast of the type parameter to the array's unknown element type, after which all assignments are safe because the two unknowns are known to be subtypes.)

Unfortunately, having multiple upper bounds also causes a number of complications that one needs to plan ahead for if one wants to support this feature. For example, suppose $A has both $B and $C as upper bounds. Suppose $B has the upper bound [] -> [i32] and $C has the upper bound [] -> [f64]. Then what type does call_ref have when the input is a ref $A? i32 or f64? In this case, we might reason that any such function must necessarily be a [] -> ⊥, as the return types are incompatible. But what if instead the upper bounds were [] -> [(ref $B)] and [] -> [(ref $C)] respectively? In that case, the return types are compatible (a function returning ref $A would have both signatures), but there is no way to represent their combined return types. This means the type-checker would have to attempt to type-check the remainder using both possible return types.

This is one of the many subtleties that arises from designing a type system around structural subtyping. For a structural MVP, the likely viable solutions are the following (though I find neither of them to be great):

1. Permanently annotate all type-directed instructions with the restricted type form(s) to upcast the relevant reference(s) to (like what struct.get currently does) or with the type(s) to upcast the resulting value(s) to.
2. Permanently disallow multiple upper bounds.

Edit: I had said lower bounds when I meant upper bounds. Post is now correct.

[rossberg]

@titzer's Jawa system made use of importing types with multiple lower-bound constraints.

They were upper bounds. But they can be problematic nonetheless.

[titzer]

As @rossberg mentions, they are subtype constraints, i.e. upper bounds.

Given that,

For example, suppose $A has both $B and $C as lower bounds. Suppose $B has the lower bound [] -> [i32] and $C has the lower bound [] -> [f64]. Then what type does call_ref have when the input is a ref $A? i32 or f64? In this case, we might reason that any such function must necessarily be a [] -> ⊥, as the return types are incompatible.

Well, sort of agree. The type $A must meet both constraints $B and $C, so it represents an intersection. The intersection of i32 and f64 is empty, so there is actually no type binding that can be supplied for $A that meets both constraints.

But what if instead the lower bounds were [] -> [(ref $B)] and [] -> [(ref $C)] respectively? In that case, the return types are compatible (a function returning ref $A would have both signatures), but there is no way to represent their combined return types. This means the type-checker would have to attempt to type-check the remainder using both possible return types.

I don't quite see where you would need to represent "both possible return types", or how it has "both signatures". A function has one signature. I.e. where in the typechecking algorithm that (intermediate) type arises.

[titzer]

While we are on the topic, I'll point out another subtlety that tripped up my intuition. If we import $A <: $B, $C and import $D <: $B, it is not actually the case that $D <: $A. But that's probably just my rustiness with intersection types :-)

[RossTate]

Oops, for some reason I always flip upper and lower bounds. Post has been fixed. Thanks for the catch!

The type $A must meet both constraints $B and $C, so it represents an intersection.

$A is not necessarily the intersection of $B and $C. It is just a subtype of both. In particular, other types can be subtypes of both $B and $C but not a subtype of $A.

I don't quite see where you would need to represent "both possible return types", or how it has "both signatures".

Because $A is a subtype of two function types, it can be implicitly upcast to either function type (such is the role of non-coercive subtypes). So the call_ref can either by type-checked to return ref $B or to return ref $C. The type-checker does not which is the correct choice and so has to try both in type-checking the subsequent instructions.

---

Note that I could construct similar examples using structs if struct.get did not have an annotation indicating what type to upcast the reference to. $B and $C could each be subtypes of different structs, and then the return type of struct.get 0 would be the type of the first field in one of these two struct types, but the type-checker doesn't know which to use.

[titzer]

$A is not necessarily the intersection of $B and $C. It is just a subtype of both. In particular, other types can be subtypes of both $B and $C but not a subtype of $A.

Well, I meant something specific about set theory. Types represent (potentially infinite) sets of values, so $A is a variable that represents an unknown set of values which is constrained to be a subset of the intersection of $B and $C. It is not equivalent to the intersection, no.

[titzer]

Because $A is a subtype of two function types, it can be implicitly upcast to either function type (such is the role of non-coercive subtypes). So the call_ref can either by type-checked to return ref $B or to return ref $C. The type-checker does not which is the correct choice and so has to try both in type-checking the subsequent instructions.

But again, if you have a function reference of type [] -> $A, when you apply the function with call.ref, you get an $A return value. Where do more complicated internal types (e.g. representing an intersection) get introduced in type checking?

[RossTate]

But again, if you have a function reference of type [] -> $A, when you apply the function with call.ref, you get an $A return value. Where do more complicated internal types (e.g. representing an intersection) get introduced in type checking?

Ah. In the example, you have a ref $A, which is not necessarily a function reference of type [] -> $A (because $A is not necessarily the intersection of $B and $C, just a subtype thereof).

[tlively]

@RossTate, I still don't quite understand where the intersection is actually used. We have this situation (with changed names):

$A <: [] -> [(ref $A')]
$B <: [] -> [(ref $B')]
$C <: $A
$C <: $B

And we are trying to type a call.ref of a value with type (ref $C). I can see that this call could be typed with either [] -> [(ref $A')] or [] -> [(ref $B')], but it's not clear to me that the type checking algorithm won't be able to choose a correct option immediately based on its context. What is a situation in which the type checking algorithm would have to consider both options for a nontrivial number of steps?

[RossTate]

but it's not clear to me that the type checking algorithm won't be able to choose a correct option immediately based on its context

So "based on its context" is where you are peeking ahead. You are essentially type-checking the following instructions with both options and seeing which one pans out. How long that takes depends on the types involved and how the instruction set is designed. For example, if your $A' and $B' were each subtypes of functions, then another call_ref wouldn't be enough to determine which is right. (And if they were each subtypes of multiple functions, you could have even more cases to consider after a second call_ref.) If $A' and $B' were instead $A and $B, then you could type-check an arbitrary-length sequence of call_ref instructions before learning which was the correct choice.

This peek-ahead strategy is exponential time. To see why, consider the following:

$A <: [] -> [(ref $t0) (ref $C)]
$B <: [] -> [(ref $t1) (ref $C)]
$C <: $A
$C <: $B

(block ([(ref $C)] -> [...])
  (call_ref)^n
)

Note that I can replace ... with any n-length sequence of ref $t0 and ref $t1s. Each such sequence is possible depending on the choice of how to resolve each of the n copies of call_ref. In theory, a type-checker can figure out that each of these choices is independent, but that requires rather smart reasoning (especially when dealing with extensions like dup and rotate), so a more practical type-checker would likely take exponential time. In fact, if we had pick and if struct.get and struct.set were unannotated, I figured out how to reduce graph 3-coloring to the problem, thereby making it NP-hard.

[conrad-watt]

$A <: [] -> [(ref $t0) (ref $C)]
$B <: [] -> [(ref $t1) (ref $C)]
$C <: $A
$C <: $B

In order for this subtyping arrangement to be possible, there must be some common subtype between $t0 and $t1. Would the problem you describe above be avoided if the type of $C (EDIT: and $A and $B I guess) was required to be explicitly declared in addition to declaring its subtyping constraints?

EDIT:
i.e.

$A ::= [] -> [(ref $t0) (ref $C)]
$B ::= [] -> [(ref $t1) (ref $C)]

$C ::= [] -> [(ref $t2) (ref $C)]

$t2 <: $t0
$t2 <: $t1

$C <: $A
$C <: $B

[RossTate]

But then $C isn't a type variable.

[conrad-watt]

Does it need to be, in the sense you're talking about, for @titzer's purposes?

[RossTate]

I believe so. In @titzer's presentation, the idea was that the Jawa module would import all the required types, solely specifying the required subtyping relations through multiple upper-bound constraints, and then import accessors and mutators of the types. That way the runtime could generate the type after linking, when all the fields could be determined, and provide the generated type and the relevant accessors and mutators to the Jawa module.

[titzer]

Ok, I see the problem now, but your example involves mutually recursive type constraints.

In what I propose, type imports have to be topologically sorted and their constraints can only refer to prior types and type imports. Further, for relaxed section order, types can only be mutually recursive within a block of declarations, so this:

 $A <: [] -> [(ref $t0) (ref $C)]
 $B <: [] -> [(ref $t1) (ref $C)]
 $C <: $A
 $C <: $B
 
 (block ([(ref $C)] -> [...])
   (call_ref)^n
 )

wouldn't be legal.

 $A <: [] -> [(ref $t0)]
 $B <: [] -> [(ref $t1)]
 $C <: $A
 $C <: $B
 
 (block ([(ref $C)] -> [...])
   (call_ref)
 )

Would however. And this is where I think the intersection type pops up in the middle of type checking; the return value of the call_ref is the intersection of ref $t1 and ref $t0.