4 ms·

In general this doesn't work, the history rule says mutable types are not proper subtypes of immutable ones (and the converse is obvious). If you want to captur

In general this doesn't work, the history rule says mutable types are not proper subtypes of immutable ones (and the converse is obvious). If you want to capture mutability in your type system, it needs to be orthogonal to subtyping (like C/C++ const).

deleted 4y ago
[deleted]
a_t48 4y ago
C++ still has this problem - std::unordered_map<std::string, std::string>` and `std::unordered_map<std::string, const std::string>` are basically unrelated types - you can't const-cast the templated const away. (I may be misunderstanding here)
- masklinn 4y ago
  > you can't const-cast the templated const away. That seems like a good thing. If you're handed a map to const values you can't just go "imma gunna mutate them anyway".
  - morelisp 4y ago
    Normally (when containers are not involved) this is exactly the point of a const cast.
    - account42 4y ago
      No, the primary point of a const cast is "I need to pass this to an API that expects a non-const pointer even though it won't mutate it". Casting const away and then mutating is a footgun as you are in undefined behavior territory as soon as your pointer/reference is not just const itself but points to a const variable.
  - a_t48 4y ago
    Yup, it's definitely a bit of a code smell if you do. The issue is more the reverse, though - I can't make a mutable map, then hand it by pointer/reference to something that says it wants an immutable map later.
    - masklinn 4y ago
      Not necessarily a bad thing either, things can get odd if you're not the only owner and it's mutated under you unexpectedly.
      - deleted 4y ago
        [deleted]
      - a_t48 4y ago
        That only matters if you're storing it. The big issue is 99% of code out there uses mutable template types for containers, and if you ever declare a container that doesn't have a mutable template type, you stub your toe as your new container isn't compatible with anyone else's code. You can't even easily copy your way out. std::unordered_map<std::string, const std::string> m; m["foo"] = "bar"; std::unordered_map<std::string, std::string> m2 = m; doesn't compile.
        account42 4y ago
        > That only matters if you're storing it. Or if you (or something you call) mutate it trough another reference/pointer. Sometimes I wish there was a stronger const where the compiler (and programmer) could actually assume the object is not mutated while that reference/pointer is alive. Of course checking that is no longer doable with just the type system. > You can't even easily copy your way out. That depends on the type. std::unordered_maps could provide a copy constructor that does the conversion. And you can do the copy via iterators, although that is probably not as efficient as it could be because it needs to re-hash the keys. std::unordered_map<std::string, std::string> m2(m.begin(), m.end());
        4y ago
cogman10 4y ago
> the history rule I'm unfamiliar with this rule (and not finding anything good to google). Can you elaborate? I can't really think of a scenario where an immutable datastructure isn't a subset of actions against a mutable datastructure.
- kapep 4y ago
  I had to look it up too, it apparently is a constraint for subtypes defined in Liskovs substitution principle [1]. From Wikipedia: > History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Because subtypes may introduce methods that are not present in the supertype, the introduction of these methods may allow state changes in the subtype that are not permissible in the supertype. The history constraint prohibits this. It was the novel element introduced by Liskov and Wing. A violation of this constraint can be exemplified by defining a mutable point as a subtype of an immutable point. This is a violation of the history constraint, because in the history of the immutable point, the state is always the same after creation, so it cannot include the history of a mutable point in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods. Thus, one can define a circle with immutable center and mutable radius as a subtype of an immutable point without violating the history constraint. [1]: https://en.wikipedia.org/wiki/Liskov_substitution_principle#Principle https://en.wikipedia.org/wiki/Liskov_substitution_principle#...
  - aatd86 4y ago
    Just curious, isn't it obvious from a logical standpoint? I don't see how one could consider a mutable type to be a subtype of an immutable one. On the other hand, an immutable subtype of a mutable one seem plausible?
    - cogman10 4y ago
      Immutable from a mutable is just as implausible. You cannot remove a method from a subtype which results in mutating methods being disabled through other means (like throwing exceptions). This is also a violation of LSP and the open close principle. Consider a `List` with an `add` function. What would you do with that `add` function to make an `ImmutableList` subtype?
gowld 4y ago
Not quite. Conceptually, you can have constness in your subtype-system (as long as you are sticking with interfaces (methods), as Liskov's subtyping model does, and aren't inherting potentially-mutable fields). MutableMap and ImmutableMap are both subtypes of a hypothetical ReadableMap. ImmutableMap is the same as ReadableMap, but has an informal contract that subclasses shouldn't add mutability.

deleted 4y ago

[deleted]

a_t48 4y ago

C++ still has this problem - std::unordered_map<std::string, std::string>` and `std::unordered_map<std::string, const std::string>` are basically unrelated types - you can't const-cast the templated const away. (I may be misunderstanding here)

masklinn 4y ago
> you can't const-cast the templated const away. That seems like a good thing. If you're handed a map to const values you can't just go "imma gunna mutate them anyway".
- morelisp 4y ago
  Normally (when containers are not involved) this is exactly the point of a const cast.
  - account42 4y ago
    No, the primary point of a const cast is "I need to pass this to an API that expects a non-const pointer even though it won't mutate it". Casting const away and then mutating is a footgun as you are in undefined behavior territory as soon as your pointer/reference is not just const itself but points to a const variable.
- a_t48 4y ago
  Yup, it's definitely a bit of a code smell if you do. The issue is more the reverse, though - I can't make a mutable map, then hand it by pointer/reference to something that says it wants an immutable map later.
  - masklinn 4y ago
    Not necessarily a bad thing either, things can get odd if you're not the only owner and it's mutated under you unexpectedly.
    - deleted 4y ago
      [deleted]
    - a_t48 4y ago
      That only matters if you're storing it. The big issue is 99% of code out there uses mutable template types for containers, and if you ever declare a container that doesn't have a mutable template type, you stub your toe as your new container isn't compatible with anyone else's code. You can't even easily copy your way out. std::unordered_map<std::string, const std::string> m; m["foo"] = "bar"; std::unordered_map<std::string, std::string> m2 = m; doesn't compile.
      - account42 4y ago
        > That only matters if you're storing it. Or if you (or something you call) mutate it trough another reference/pointer. Sometimes I wish there was a stronger const where the compiler (and programmer) could actually assume the object is not mutated while that reference/pointer is alive. Of course checking that is no longer doable with just the type system. > You can't even easily copy your way out. That depends on the type. std::unordered_maps could provide a copy constructor that does the conversion. And you can do the copy via iterators, although that is probably not as efficient as it could be because it needs to re-hash the keys. std::unordered_map<std::string, std::string> m2(m.begin(), m.end());
        4y ago

cogman10 4y ago

> the history rule I'm unfamiliar with this rule (and not finding anything good to google). Can you elaborate? I can't really think of a scenario where an immutable datastructure isn't a subset of actions against a mutable datastructure.

kapep 4y ago
I had to look it up too, it apparently is a constraint for subtypes defined in Liskovs substitution principle [1]. From Wikipedia: > History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Because subtypes may introduce methods that are not present in the supertype, the introduction of these methods may allow state changes in the subtype that are not permissible in the supertype. The history constraint prohibits this. It was the novel element introduced by Liskov and Wing. A violation of this constraint can be exemplified by defining a mutable point as a subtype of an immutable point. This is a violation of the history constraint, because in the history of the immutable point, the state is always the same after creation, so it cannot include the history of a mutable point in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods. Thus, one can define a circle with immutable center and mutable radius as a subtype of an immutable point without violating the history constraint. [1]: https://en.wikipedia.org/wiki/Liskov_substitution_principle#Principle https://en.wikipedia.org/wiki/Liskov_substitution_principle#...
- aatd86 4y ago
  Just curious, isn't it obvious from a logical standpoint? I don't see how one could consider a mutable type to be a subtype of an immutable one. On the other hand, an immutable subtype of a mutable one seem plausible?
  - cogman10 4y ago
    Immutable from a mutable is just as implausible. You cannot remove a method from a subtype which results in mutating methods being disabled through other means (like throwing exceptions). This is also a violation of LSP and the open close principle. Consider a `List` with an `add` function. What would you do with that `add` function to make an `ImmutableList` subtype?

gowld 4y ago

Not quite. Conceptually, you can have constness in your subtype-system (as long as you are sticking with interfaces (methods), as Liskov's subtyping model does, and aren't inherting potentially-mutable fields). MutableMap and ImmutableMap are both subtypes of a hypothetical ReadableMap. ImmutableMap is the same as ReadableMap, but has an informal contract that subclasses shouldn't add mutability.