Rust type system and the Circle-ellipse problem

[burakumin]

Just some informal thoughts about a classical problem and a possibly interesting proposition to improve it in Rust. Maybe the topic has too few practical impacts for Rust to care about. But at least I’d be interesting in feedback.

I suppose many of us already know the Circle-ellipse problem, which is a conceptual problem demonstrating the discrepancy between our natural perception of the specific/generic relation and what the sub-typing relation (in the sense of Liskov) allows. Of course Rust has no subtyping between concrete types (structs, enums, tuples, …) but it does define a hierarchy of traits so the same issue may apply. As a reminder this is how we could explain the Circle-ellipse problem with Rust traits:

trait Ellipse {
	fn getRadiuses(&self) -> (f64, f64);
	fn setRadiuses(&mut self, minor: f64, major: f64);
}

trait Circle : Ellipse {
	fn getRadius(&self) -> f64;
	fn setRadius(&mut self, radius: f64);
}

Although semantically we naturally consider that every circle is also an ellipse, the design above introduces an issue: how should the function setRadiuses behave for implementations of Circle? We can arguably consider it does not make sense in this context but as a consequence we will have to either remove this method from Ellipse or give up the sub-typing relation between the traits. As generally pointed, the problem is rooted in the interaction between categories and mutability: a change of state for a given item might preserve its membership to a very generic category while at the same time invalidating its membership to a more specific category (as another concrete example, a citizen that got naturalized is still a citizen but he/she might not be a Chinese citizen anymore). Few programming languages define mutability as a syntactic concept and as a consequence they generally cannot provide very satisfying solution. Rust is one of the few languages that includes mutability in its type system. So what about this:

trait Circle : const Ellipse {
	fn getRadius(&self) -> f64;
	fn setRadius(&mut self, radius: f64);
}

The idea is to provide a weaker kind of relation for traits (that we may call weak or const sub-typing). As a weak sub-trait of Ellipse, Circle only imports the part of its interface where self or Self appears as non-mutable references in parameters, which excludes setRadiuses. I guess cases where Self appears inside non-mutable references of complex types (like &[Self]) could also be considered as valid. This extension of the type system means that any trait now defines two interfaces: a weak one and the standard (complete) one. This naturally leads to at least 3 additional extensions:

• An implementation may be restricted to a weak trait.
• Any weak trait may appear as a trait bound.
• Const references on trait object may handle instances of a broader set of concrete types (as they naturally require a weaker interface).

I’m aware that for short traits (in particular one-method traits) this is useless as there is no sub-interface to extract. So as said in the introduction in practice that might bring limited benefits if the general philosophy is to have strong restrictions on the traits size (but as a counter-argument trait hierarchy naturally increases the size of traits even when they have only a limited number of proper methods).

[withoutboats]

Do you have a practical example in which this feature would be useful?

The circle-ellipse problem doesn’t seem convincing to me; my interpretation of this contradiction is that a Circle just isn’t a subtype of Ellipse as Circle and Ellipse are defined here (you cannot modify a circle and have it remain a circle in the same way you can modify an ellipse and have it remain an ellipse). And while it is the case in this example that only the mutative methods violate the subtyping relation, I expect there are other “intuitive subset relations” which are not subtypes but do not require mutation.

If there are use cases, this feature could be compelling, I’m just saying that this problem is not a problem with the program but a problem with our reasoning about the program. There is a small syntax problem in that const T has been proposed for identifying constant parameters, and so having impl<const T: usize> and impl<T: const Num> mean totally unrelated things seems non-ideal, but that can be addressed obviously.

[cuviper]

I think it’s better to explicitly separate the concepts of what makes an ellipse. Something like

• trait Ellipse with fn getRadiuses
• trait ReshapableEllipse: Ellipse adding fn setRadiuses
• trait Circle: Ellipse – not reshapable.

[tomaka]

All your argumentation is based on one thing:

semantically we naturally consider that every circle is also an ellipse

Why do you thing it’s important that your code respects real-life facts? Your program does not manipulate Ellipses and Circles, it manipulates data. The way you design your code should not be influenced by real-life semantics but by things like cache locality, avoidance of errors, etc.

[peter_bertok]

I can maybe provide a more practical example: “read only / const” interfaces.

It would be very convenient to be able to trivially “split” a complex trait into the read/write and read-only versions without having to explicitly crate two traits, one inheriting from the other.

IReadOnlyList from C# is a good example of how retrofitting this is painful, whereas Rust naturally has a “self” and “mut self” variants instead of the combined “this” reference in C#, which makes this split trivial.

In essence, we could get a “ReadOnlyFoo” trait for every “Foo” trait trivially.

[glaebhoerl]

@tomaka I think I completely disagree with that, unless I’m misinterpreting it. By “real-life facts”, do you mean “mathematics”? Given that computer science is essentially a sub-branch of mathematics, saying that programs should be unconcerned with it seems surprising at a minimum. Other languages get a lot of mileage out of expressing various algebraic abstractions (from semigroups and monoids on up) inside the languages using tools like type classes (traits), and it’s not immediately obvious to me why other mathematical concepts like ellipses and circles should be considered qualitatively different.

@peter_bertok My sense is also that the right thing to do within the current language would be to split the methods where Self is in positive resp. negative (co/contravariant) positions into separate traits. An &mut is both at the same time, so for full generality you might have three traits: one with the input-only methods, one with the output-only methods, and one inheriting from both, and adding the both-input-and-output (i.e. &mut) methods. These would correspond to “at least an ellipse”, “at most an ellipse”, and “exactly an ellipse”. Depending on whether you’re looking at things from the input or the output side, either Circle <: Ellipse, or vice versa – and likewise with Ellipse and whatever is one level of abstraction before it. (This is essentially the same thing as the more general issue of whether an abstraction can be said to be more powerful if more things can be instances of it (it has more models), or if you can do more things with it: these are always inversely proportional.)

At the language level, there’s been some speculation about the possibility of “mutability polymorphism”, driven by the concrete use case of e.g. not having to write the same code twice for methods on collections in & as well as &mut versions, so you’d have something like a type-level representation of “shared” and mut you could abstract over. (I am not at all sure this is the right way to go about it, but that’s the most obvious idea.) I wonder if that could be used to express the things you’re thinking of, instead of some kind of ad-hoc feature for the purpose.

[nikomatsakis]

I think your intuition is good here, but usually when I’ve chased down this line of thought, I’ve decided that it seems simpler to split the single trait (Ellipse) into two, one for “read-only” and one for mutation (as others have suggested on this thread). This is a fairly common pattern in other languages.

It’s true that since Rust offers &mut self methods, one might hope that you could unify the “read-only” and “mutable” views, but it would introduce a number of complications that don’t quite seem to carry their weight, due to the way that traits work in Rust. Basically const Foo would have be a separate kind of trait that one can implement – e.g., a type implementation Circle would then want to only implement const Ellipse so that it can skip implementing the setRadiuses method. Similarly, generic fns would take T: const Ellipse. You can see how this is pretty isomorphic to just defining a trait ConstEllipse and a trait Ellipse: ConstEllipse and Circle: ConstEllipse. (And I’ve not even gotten into what to do with associated fns that do not take &self or &mut self but rather self or indeed no self at all!)

[tomaka]

[quote=“glaebhoerl, post:6, topic:3057”] I think I completely disagree with that, unless I’m misinterpreting it. By “real-life facts”, do you mean “mathematics”? Given that computer science is essentially a sub-branch of mathematics, saying that programs should be unconcerned with it seems surprising at a minimum. Other languages get a lot of mileage out of expressing various algebraic abstractions (from semigroups and monoids on up) inside the languages using tools like type classes (traits), and it’s not immediately obvious to me why other mathematical concepts like ellipses and circles should be considered qualitatively different.[/quote]

There is no 1:1 mapping between traits and mathematical groups. Traits exist to expose an object’s API, not to mathematically describe an object.

[huon]

There is no 1:1 mapping between traits and mathematical groups. Traits exist to expose an object’s API, not to mathematically describe an object.

One can certainly use a trait to model a group i.e. implemented by things that expose the operations, aka the API, that a mathematical group has. For instance, a hierarchy of traits like @glaebhoerl was mentioning might start like:

trait Semigroup {
    fn combine(self, other: Self) -> Self;
}
trait Monoid: Semigroup {
    fn identity() -> Self;    
}
trait Group: Monoid {
    fn invert(self) -> Self;
}

That said, your comment sounds like you think @glaebhoerl is suggesting mapping the set of all traits into the set of all groups or something?

Going back to the original comment, traits certainly don’t fundamentally exist because they improve cache locality or because they reduce errors¹, they exist because they can be used to model shared behaviours, and shared behaviours often match (or at least are influenced by) the “real world”, aka the world in which those behaviours exist. (Incidentally, “modelling shared behaviours” is a pretty reasonable description of mathematics as a field of study.)

¹This is possibly debatable, since one could reasonably argue that reducing errors is a/the motivating reason to abstract shared behaviours.

[tomaka]

The stdlib contains a lot of traits that exist purely for programming-related purposes and not to model mathematics or the real world: CommandExt, Debug, Reflect, ToOwned, AsRef, etc.

Some other traits like Extend, Hash or Iterator do correspond to real-life behaviors, but exist primarily because it makes it easier to code with them.

As far as I can see, only traits like Add or Eq exist for both mathematical and pragmatic reasons.

My point is that you shouldn’t create a trait just because it corresponds to a real-world behavior. You should create a trait for pragmatic reasons first, like “I need a variable that can store multiple types of objects”. And therefore, to answer the OP, I don’t think the traits system of Rust needs to be changed just because it can’t express some real-life behaviors.

[withoutboats]

This conversation is rather off the topic, but I think it is ontologically false to describing some traits as “math” and others as “not math;” all traits describe some sort of logical relation between sets of types. The problem here is that by the definition of ellipse presented, a circle is not an ellipse, because the definition claims that an ellipse can be constructed from any pair of f64 values, and this is not true of a circle. A circle does meet the definition for immutable ellipses, of course, which is the “reason given” for this proposal.

But this is not actually what the proposal is about, the proposal is about a feature whereby types can be bound to subsets of traits determined by the receiver of the method in that type. The most immediate problem with this proposal is as @nikomatsakis mentioned: all items defined by a trait aren’t either &self methods or &mut self methods, there are also self methods, associated functions, associated types, and associated consts. How would it be determined which of these is included by a T: const Trait bound? But there is also the question: is this actually useful enough to not just define a separate trait? Especially when the flexibility of specialization/mutual exclusion are worked out, I think it would be fairly easy (possibly even backward compatible) to refactor a single trait into multiple traits.

[burakumin]

@tomaka I had started a long answer about “programming, maths and real life”. But as withoutboats reminded it, this is not the point here. I didn’t declare the ellipse-circle problem to be something programming (or more precisely type theory) should be interested in. People did it long before me. Take it as an introduction example for a more generic problem.

@cuviper @nikomatsakis @withoutboats I could have mentioned other known solutions. Of course introducing more specific intermediate traits/interface that represent immutable versions is a possibility. But it’s not perfect. The main problem is that it places a burden (and additional work) on the shoulders of the provider: He/she need to anticipate the need of extracting the const subinterface. Anticipation is difficult. peter_bertok’s example of C# ReadOnly interfaces is relevant. They failed to anticipate and now they can only partially fix the system (or rather they consider it is too much work to modify the language itself to fix the problem). Rust offers you the flexibility to implement on a type you do not own (which is cool) but it does not allow you to define a super-trait for a trait you don’t own. Compare with Go where this issue does not exist as interfaces are structural rather than declarative (I do not mean go’s way to do it is per se a better solution but at least it does not suffer from this precise limitation). Of course the separation could be encouraged as a systematic guideline for developers. Is it the case today in Rust ? Is it done systematically in any language you know ? (and where this would be useful, I’m not talking about Haskell of course)

This is a fairly common pattern in other languages.

Because they have nothing better to offer. Providing the solution naturally built inside the semantics of the language removes the issue. The dev does not have to anticipate a separation of interface. The const trait is available if needed … for free.

but it would introduce a number of complications that don’t quite seem to carry their weight, due to the way that traits work in Rust.

Certainly we have to evaluate the benefit/complexity ratio.

Basically const Foo would have be a separate kind of trait that one can implement.

How would that be a complication? It does not add new constrains. It offers new possibilities.

These would correspond to “at least an ellipse”, “at most an ellipse”, and “exactly an ellipse”.

@glaebhoerl I’m curious about situations where “at most X” would be useful in a programming language. This idea had already crossed my mind but I couldn’t clarify in what situation that would be beneficial.

At the language level, there’s been some speculation about the possibility of “mutability polymorphism”, driven by the concrete use case of e.g. not having to write the same code twice for methods on collections in & as well as &mut versions, so you’d have something like a type-level representation of “shared” and mut you could abstract over. (I am not at all sure this is the right way to go about it, but that’s the most obvious idea.)

Generics for mutability would be a powerful tool IMHO, but I’m afraid that train left a long time ago. Abstracting over such pervasive concepts as mutability may require radical changes on the syntax. But I guess this might be worth it looking deeper into that question.

all items defined by a trait aren’t either &self methods or &mut self methods, there are also self methods, associated functions, associated types, and associated consts. How would it be determined which of these is included by a T: const Trait bound?

@withoutboats, aren’t they exciting questions ? But sure a more complete analyse is needed. I will try to propose one.

I think it would be fairly easy (possibly even backward compatible) to refactor a single trait into multiple traits.

Again only if you own the type.

[glaebhoerl]

@burakumin Presumably anyplace where you aren’t consuming an ellipse but producing one. Where this happens in practice is a separate question - but ellipses and circles were only for the sake of example anyways. I would be interested in this myself. It seems like it should be useful somewhere - when you have a duality and one half of it is useful, most of the time the other is too.

[withoutboats]

Again only if you own the type.

This is a good point. I look forward to hearing a more detailed proposal.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.