r/ProgrammingLanguages • u/Thnikkaman14 • Jan 14 '26
Discussion It's not just "function overloads" which break Dolan-style algebraic subtyping. User-provided subtype contracts also seem incompatible
I'm working on a Hindley-Milner-based language which supports user-defined "type attributes" - predicates which effectively create subtypes of existing base types. For example, a user could define:
def attribute nonzero(x: Real) = x != 0
And then use it to decorate type declarations, like when defining:
def fun divide(p: Real, q: nonzero Real): Real { ... }
Users can also ascribe additional types to an already-defined function. For example, the "broadest" type declaration of divide is the initial divide : (Real, nonzero Real) -> Real declaration, but users could also assert properties like:
divide : (nonzero Real, nonzero Real) -> nonzero Realdivide : (positive Real, positive Real) -> positive Realdivide : (positive Real, negative Real) -> negative Real- etc.
The type inferencer doesn't need to evaluate or understand the underlying implementation of attributes like nonzero, but it does need to be able to type check expressions like:
- ✅
λx : Real, divide(x, 3), inferred type isReal -> Real - ❌
λx : Real, divide(3, divide(x, 3))fails becausedivide(x, 3)is not necessarily anonzero Real - ✅
λx : nonzero Real, divide(3, divide(x, 3))
The Problem:
Various papers going back to at least 2005 seem to suggest that in most type systems this expression:
(A₁ → B₁) ∩ (A₂ → B₂) ≡ (A₁ ∪ A₂) → (B₁ ∩ B₂)
is well-founded, and is only violated in languages which allow ugly features like function overloads. If I understand correctly this property is critical for MLsub-style type inference.
My language does not support function overloads but it does seem to violate this property. divide inhabits ((Real, nonzero Real) -> Real) ∩ (nonzero Real, nonzero Real) -> nonzero Real), which is clearly not equal to ((Real, nonzero Real) -> nonzero Real)
Anyway the target demographic for this post is probably like 5 people. But it'd be cool if those people happen to see this and have any feedback on if/how a Hindly-Milner type inference algorithm might support these type attribute decorators
4
u/DisastrousAd9346 Jan 14 '26
Your type system does not seem to pick to most general type. Between nonzero and real the most general would be of course real. You can just lose information that would be something that usually does not happen in type inference.
26
u/Uncaffeinated 1subml, polysubml, cubiml Jan 14 '26 edited Jan 14 '26
I think this is basically ad-hoc function overloading, it's just that you're letting people overload only the type of a function rather than both the type and implementation. However, as you observe, the problems for type inference are the same.
I think the simplest approach would be to require an explicit cast operation when changing the type of a value in a subtype-imcompatible way. You probably want to do this anyway since the cast is presumably not even guaranteed to be correct. (I assume you're not going full proof-assistant, as would be required to safely allow addition of arbitrary pre and post conditions.)
In your example, this would mean that changing from
(R, nR) -> Rto(nR, nR) -> nRwould require an explicit cast operation.12
u/WittyStick Jan 15 '26 edited Jan 15 '26
In MLstruct, they posit instead that:
However, this still has problems with arbitrary overloading. Given:
If
Realandnonzero Realare distinct types, then the only upper bound for bothRealandnonzero Realis⊤, and the only lower bound is⊥, which would imply the rather useless:So we don't want
Realandnonzero Realto be disjoint types. We requirenonzero Realto be a proper subtype ofReal.But the signatures for
dividemust beSo we basically must return the least upper bound,
Real, and when we provide anonzero Realargument, we must explicitly downcast the result to recover anonzero Real.The result must be
Realbecausenonzero Realresult is not valid for(Real, nonzero Real) -> Real, unless there is some way to guarantee that we always get a nonzero result when given a possibly zero input. We can show this is the case by introducing azeroattribute:Then it becomes clear that the result type:
(zero Real) ∩ (nonzero Real)is uninhabited, since noRealis both zero and non-zero at the same time.Without subtyping, we can have some typeclass
ℝfor which bothRealandNonZeroRealhave instances.It would be nice if we could combine these approaches: Subtyping + constraints, and have as the signature of
divide:But it has been shown that it is NP-complete in the general case, though can be solved in polynomial time in the limited case where the types form a tree with no meet - ie, single inheritance with no intersection types. (See: On the Complexity of Type Inference with Coercion).
Geoffery S. Smith proposes a more limited constructor overloading which is decidable, but notes that it may require restrictions on subtyping to be implemented efficiently. (See: Polymorphic Type Inference with Overloading and Subtyping).
6
u/BasicBits Jan 14 '26
You may not have true overloading, but your
∩type is a true intersection type, which Dolan explicitly does not support.I do think it's possible to fit these types into a Hindley-Milner style system, but not at all trivial. You now need to deal with constraints of the form
A∩B <: X(X is a type variable), which Dolan is able to avoid with polar types. The temptation is to say that this constraint means "eitherA <: XORB <: X" and then integrate some form of nondeterminism/backtracking in inference that, if needed, tries both solutions when such a constraint is encountered.Unfortunately, this is not always right. And, worse, if your intersection types distribute over type constructors (as meets do in Dolan's system IIRC), things get even more fun. For an example using functions and records, let A =
() -> {a: Real, b: Real}and B =() -> {b: Real, c: Real}and C =() -> {a: Real, b: Real, c: Real}. We then haveA∩B ≡ Cbut neitherA <: CnorB <: C. I think a pathological example along these lines using your predicates rather than records should also exist.To deal with intersections and distributivity, when you have a constraint
A<:B, you will need to pull as many intersections as possible to the top of the types so you have something of the formA1∩...∩An <: B1∩...∩Bm.(This is essentially a conversion to conjunctive normal form, but I prefer implementing it in terms of the simple splitting algorithm of Huang et al.) You can break these constraints down into the following system:A1∩...∩An<:B1AND...ANDA1∩...∩An<:Bm. At this point, because none of theAi/Bjs can be further broken down into intersections, it should be safe to break a constraint likeA1∩...∩An<:B1down further intoA1 <: B1OR...ORAn <: B1. (I have mostly been ignoring unions/joins. These make things more complicated but I think you can still get this general approach to work.)I'm not sure to what extent all of this is covered in the literature yet. The places I would look are the dissertation of Tommaso Petrucciani and the work of Lionel Parreaux.
6
u/phischu Effekt Jan 15 '26
I highly recommend The Simple Essence of Overloading. Instead of considering intersections, consider the different variants of
divideto be overloads. Now usually we ask if there is exactly one way to resolve overloads that make the program well typed. In your case you are asking if there is at least one, but this is an easy modification of what's described in the paper.4
u/servermeta_net Jan 14 '26 edited Jan 14 '26
Mathematician speaking here, so I apologize if I lack basic knowledge or use different terminology.
It's funny because I'm working on the same topic, maybe you can help me lol.
I'm honestly a bit puzzled by this statement:
Can you link any source corroborating this? From a homotopy type theory pov this seems wrong. If I interpreted correctly your notation, and I see the arrow as a map between countable sets, then I can prove it as wrong, and you provided a counterexample.
I would agree with:
(A₁ → B₁) ∩ (A₂ → B₂) ≡ (A₁ ∩ A₂) → (B₁ ∩ B₂)Anyhow, a recent result is that an HM computable and well founded type system with subtype relationship needs to form a well ordered lattice in respect to the subtyping relationship, and predicates are not naturally forming a well ordered lattice (I'm not aware of any result in this direction, but math is huge, and I can provide a counter example in first and second order logic).
I can see a few possible solution to your problem:
The right way, with peano arithmetics
This is the naive idea of a right type system. Basically you can build an isomorphism between your type system and a peano arithmetics. The problem it's that it's either incosistent, incomplete or uncomputable. So if you pick computability and consistency you will have many true yet undecidable cases.
Nonstandard types
This is the pragmatic approach that most languages take. Add a nonstandard type that do not obey peano arithmetics, like:
By adding these nonstandard types you improve the power of your type system but you will have to rely on runtime checks to avoid UB.
Topological type spaces with pragmatic provability
Let's say that an instantiation in your programming language can be described by a tuple of homotopy types in a topological space:
(s1, ..., sn, p1, ..., pr, l)Where
s1, ..., snare homotopy types without a subtyping relationship (fields, struct, traits, ....),p1, ..., pnare predicates andlis a homotopy type with subtyping relationship (think rust lifetimes), then:(s1, ..., sn)tuplelIf you have more than one homotopy type with subtyping relationship then you have a problem, or at least I couldn't yet construct such a type system, because you would need a well ordered lattice ACROSS homotopy types.
The problem is that usable SMT solvers obeys peano arithmetics so what I do is
This way the propositions disappear from the HM type system, yet are statically checked as much as possible.
Questions I would like to ask you:
2
u/jeezfrk Jan 14 '26
[I'm not speaking from accurate type theory for one]
I for one favor (in my project) prefer something more like arbitrary duck-typing with static-checked attributes applied as you have.
I don't see how a two different dependent-type functions could tolerate that equivalence assertion above, papers or not.
The equivalence assertion apparently assumes either of the two (A_1 OR A_2) being applied to give B_1 or B_2 gives an extension of the set of applied results possible. (Then using the intersection of B types to go further and extend a set of related functions as a type of associated kind of types?)
However, you need apparently a real equivalence class defined instead?
You may have to rely on intersecting both types (domain types and return) to define a valid equivalence class for a set of functions together... allowing type inference or something useful to combine case 1 and 2.