I feel like the explanation is overcomplicated. Types are properties of values, not variables. Mutability is a property of variable, not of a value.
So it's kind of a categorical error. (I want to joke here that all categorical errors are just type errors in category theory.) When we speak of "type of a variable", we mean this variable can only be assigned (bound to) values of certain type. This has nothing to do with whether it can be reassigned (i.e. mutability).
So you don't even need the notion of subtyping to explain this.
Also, one could probably define variable as a monad over its type.
This post is about data structures, which are values, but like variables, they also contain values. Therefore they can be mutable. You can argue that a mutable data structure is an object not a value, I suppose. But it can go in the same place as a value, so it makes sense to talk about subtyping.
Experimentally, at least one major programming language (Rust) places mutability into the type system.
Whether or not something belongs into a type system is ultimately determined by the type system. We can choose whether or not mutability is considered a part of a type.
> When we speak of "type of a variable", we mean this variable can only be assigned (bound to) values of certain type. This has nothing to do with whether it can be reassigned (i.e. mutability).
This is a bit too simplistic IMO. You're talking about name bindings, the article is talking more about things like interior mutability.
Rebinding a name is ... generally not a type system concern by my understanding.
You have a point; I am looking at it from quite functional programming perspective, because that's how type systems are typically understood. So from that perspective, interior mutability is a form of rebinding.
When you say "we can choose mutability as a part of a type", the question is, what kind of errors are we trying to prevent? What is the semantics we want to give? From that it should be obvious whether it can be subtype or not.
A system programming language needs to match hardware where mutability is associated with memory addresses, something functional languages can afford to abstract away.
> So from that perspective, interior mutability is a form of rebinding
really? i honestly dont have _too_ much experience with functional languages, basically only elixir and consequently some amount of erlang in that vain... but i'd feel like thats not the same? but it may be that my point of view is too narrow.
from my experience with that functional language, the equivalent to this scenario would be a struct - and wherever i can mutate properties within it -- or need to reconstruct the struct from scratch.
both have technical consequences, eg if i passed the struct into a consumer somewhere which keeps it, it would get the "modified" version automatically when the property was changed
but on reconstruction, it'd have to introduce some kind of event listener to handle the reconstruction.
simple example for such a scenario would be eg a session within a SSE api.
the mutated struct would trivially allow for an uninterrupted stream no matter how long the session is extended, the latter needs to pay attention so its not opening a memory leak to support that feature.
In computer science, specifically programming language theory, types are properties of terms (syntactic expressions). It wouldn’t be possible in general to typecheck a program before running it if you had to have a value before you could discover its type.
In semantics, types are properties of values and expressions. Type safety is about whether the type of an expression always matches the type of the value it evaluates to.
If you pair mutability with exclusive access then you have handled the objection raised by the (some may say overly) strict definition of subtyping here and also the attempt to argue over the objection. No code which asks for an immutable instance will ever observe the mutability because the ask for an immutable reference is exclusive. Therefore, you could pass the mutable reference but so long as something holds onto that reference the mutability is no longer available to other code.
So mutability xor aliasing provides this strict subtyping relation. Of course, you also then need ways of loosening this by providing objects without such a contract and you enter the land of interior mutability, where again the mutable methods can be understood as a part of a subtype because a holder of the reference without mutable methods was explicitly told that there was no the guarantee that the object wouldn't change.
What i dont understand is why does everything have to be so brief. Take car and cdr there is only one character difference, more character differences is a good thing not bad.
More short names fit in your fovea than long names so for the most common operations they are the easiest to read. It’s the same reason the most common words in human languages are the shortest (and programming languages are for humans to use so subject to the same pressure.
Also, Back In The Old Days memory was very expensive and precious so short identifiers were important. Often labels were tightly constrained, for example being limited to six upper-case characters so they would fit in a single word.
The usual convention (which also occurs in natural languages) is that often-used words should be short, rarely used should (and can afford to be) more descriptive.
Most people actually write small amounts of code in a day, saving a single character here and there typing hardly matters. Its a saving that amounts to seconds for a days work.
More characters on the other hand prevents many potential types of mistakes, such as meaning one statement of target and actually entering another.
> What i dont understand is why does everything have to be so brief.
The concept is to make things easier for people who are familiar with the language. Making things harder for that group is always counterproductive, because they are the only people who can do any useful work.
So the problem is that the semantic of methods (car, cdr) is not well defined: it is either "give me that member" or "give me that member and guarantee next time the result will be same". And the solution is to clearly separate those by adding more method names.
The cons example is conflating implementation details (return the value passed in to cons) with the semantics (return the left-side of this pair that was instantiated by cons). In the first case it is a category error to think about mutability. In the second mutability makes perfect sense.
Moreover, I suspect it is possible to construct an interface such that to prove statically that you can Liskov Substitute a type into it would be equivalent to deciding Halt: All you need are extensional semantics in your type system.
Yep, I wondered that for a few optimizations in Racket. It's harder than it looks, probably something about covariant or contravariant types, I gave up.
Good one, yes. It was like that in Objective-C, and in the early versions of Swift. I know you know this, but it's useful to summarize for myself:
Basically inheritance is the wrong tool for this kind of stuff. NSMutableArray inherits from NSArray, so it can be passed to anywhere NSArray is expected (upcasting).
So you design your classes and expect them to be immutable, but you can't use NSArray anywhere. Because otherwise, it'll be mutable after all. You can do a runtime check as a workaround.
(I truly believe OOP should only be taught in computer science as a relic).
You just misinterpreted what NSArray is. It’s not an immutable type, it’s a read-only type. As others already mentioned that’s different things. If you have a read-only variable and exclusive access to it, then you can rely on immutability as well. This is what Rust has, for example. Many languages use this definition as well as it’s much more useful than having some sort of pure immutable type guarantee (which some languages do have with const).
Another language that uses this is Kotlin: List is a read-only type. MutableList is a subtype of List. You can get a “const” List by only keeping a reference to the value via a List binding. This can be worked around via casting and reflection, but even in Haskell you can do unsafe things that mutate a immutable value, so I don’t think that undermines the idea.
Because if mutable is a sub type of immutable, it wouldnt be right to give a mutable value when the receiver expected immutable values. The same is also true if one reverses the relationship, the mutable operations should not be defined on the immutable, and if they were that would be dumb because the immutable implementations should fail, which is silly.
I would phrase it in terms of subsets. All cats are mammals, therefore "cat" is a subtype of "mammal". So the possible values of the type "cat" are a subset of the possible values of the type "mammal".
In contrast, neither are the mutable things a subset of the immutable things nor the other way round. It's not the case that everything mutable is immutable nor that everything immutable is mutable. The two types are disjoint.
One of the problems with this comes if you're able to dynamically promote something that was passed to you as an "immutable" type to its actual implementation type, you can break this "contract".
I'm currently being annoyed by python's type hinting system, which has exactly this sort of hierarchy for containers, but there's nothing stopping a caller/callee from using type-narrowing to "discover" that the underlying type is actually e.g. a (mutable) list, and then modifying it without any complaints from the type checker. The only way to enforce this would be to actually convert to an immutable implementation type, involving unnecessary copying.
The fact that it requires so much explanation, indicates the level of degradation in the reasoning ability of the audience. A value of a subtype shall deliver all of the expectations of its super type, because it is wearing both the hats of super type and sub type.
If the article is written for human consumption, then it fails the primary goal (or logic?) of being useful. If a human has to digest a flood of this logic slop just to get convinced about this simple concept, they are not going to be able to do anything useful.
What part of GP's one-sentence explanation is not strictly logical? Does obfuscating a simple logical concept by describing it in academia-wanky-terms like Liskov's Substitution Principle make it More Logical? Or does it just make the author and their in-crowd feel more intelligent?
Note, also, that the article isn't even objective. It asserts that the definition of a subtype is Liskov's principle. However, Liskov's principle is only one of multiple possible definitions. In other words, the article is really only invoking Liskov's name as an appeal to authority. So much for strict logic.
I feel like the explanation is overcomplicated. Types are properties of values, not variables. Mutability is a property of variable, not of a value.
So it's kind of a categorical error. (I want to joke here that all categorical errors are just type errors in category theory.) When we speak of "type of a variable", we mean this variable can only be assigned (bound to) values of certain type. This has nothing to do with whether it can be reassigned (i.e. mutability).
So you don't even need the notion of subtyping to explain this.
Also, one could probably define variable as a monad over its type.
This post is about data structures, which are values, but like variables, they also contain values. Therefore they can be mutable. You can argue that a mutable data structure is an object not a value, I suppose. But it can go in the same place as a value, so it makes sense to talk about subtyping.
Experimentally, at least one major programming language (Rust) places mutability into the type system.
Whether or not something belongs into a type system is ultimately determined by the type system. We can choose whether or not mutability is considered a part of a type.
> When we speak of "type of a variable", we mean this variable can only be assigned (bound to) values of certain type. This has nothing to do with whether it can be reassigned (i.e. mutability).
This is a bit too simplistic IMO. You're talking about name bindings, the article is talking more about things like interior mutability.
Rebinding a name is ... generally not a type system concern by my understanding.
You have a point; I am looking at it from quite functional programming perspective, because that's how type systems are typically understood. So from that perspective, interior mutability is a form of rebinding.
When you say "we can choose mutability as a part of a type", the question is, what kind of errors are we trying to prevent? What is the semantics we want to give? From that it should be obvious whether it can be subtype or not.
A system programming language needs to match hardware where mutability is associated with memory addresses, something functional languages can afford to abstract away.
> So from that perspective, interior mutability is a form of rebinding
really? i honestly dont have _too_ much experience with functional languages, basically only elixir and consequently some amount of erlang in that vain... but i'd feel like thats not the same? but it may be that my point of view is too narrow.
from my experience with that functional language, the equivalent to this scenario would be a struct - and wherever i can mutate properties within it -- or need to reconstruct the struct from scratch.
both have technical consequences, eg if i passed the struct into a consumer somewhere which keeps it, it would get the "modified" version automatically when the property was changed
but on reconstruction, it'd have to introduce some kind of event listener to handle the reconstruction.
simple example for such a scenario would be eg a session within a SSE api. the mutated struct would trivially allow for an uninterrupted stream no matter how long the session is extended, the latter needs to pay attention so its not opening a memory leak to support that feature.
> Types are properties of values, not variables.
In computer science, specifically programming language theory, types are properties of terms (syntactic expressions). It wouldn’t be possible in general to typecheck a program before running it if you had to have a value before you could discover its type.
A nitpick: Types are properties of expressions, not values. Type errors happen at compile time, before code runs. Values only exist at run time.
Fair enough. Although I don't fully subscribe to the dichotomy of compile vs run time, we can say that.
In semantics, types are properties of values and expressions. Type safety is about whether the type of an expression always matches the type of the value it evaluates to.
Doesn’t this break down with dependent type systems?
So really there are 2 orthogonal axes:
- A: can I change the value
- B: can something else change the value (can I depend on a predictable stable value)
Because the axes are orthogonal, hierarchical based subtyping (inheritance) breaks, but type classes (interfaces), ad hoc polymorphism, would work.
In C, const answers A
In rust, due to pointer aliasing restrictions (either one mut pointer xor any amount of read only pointers), (lack of) mut answers both A and B
In C, const can also answer B, but only in non-pointer contexts.
If you pair mutability with exclusive access then you have handled the objection raised by the (some may say overly) strict definition of subtyping here and also the attempt to argue over the objection. No code which asks for an immutable instance will ever observe the mutability because the ask for an immutable reference is exclusive. Therefore, you could pass the mutable reference but so long as something holds onto that reference the mutability is no longer available to other code.
So mutability xor aliasing provides this strict subtyping relation. Of course, you also then need ways of loosening this by providing objects without such a contract and you enter the land of interior mutability, where again the mutable methods can be understood as a part of a subtype because a holder of the reference without mutable methods was explicitly told that there was no the guarantee that the object wouldn't change.
As a total aside, the names `car` and `cdr` for "head" and "tail" are honestly some of the most baffling historical relics in all of computing.
What i dont understand is why does everything have to be so brief. Take car and cdr there is only one character difference, more character differences is a good thing not bad.
More short names fit in your fovea than long names so for the most common operations they are the easiest to read. It’s the same reason the most common words in human languages are the shortest (and programming languages are for humans to use so subject to the same pressure.
Also, Back In The Old Days memory was very expensive and precious so short identifiers were important. Often labels were tightly constrained, for example being limited to six upper-case characters so they would fit in a single word.
The usual convention (which also occurs in natural languages) is that often-used words should be short, rarely used should (and can afford to be) more descriptive.
Why waste time say (write) lot (long) word when few (short) word do trick?
Most people actually write small amounts of code in a day, saving a single character here and there typing hardly matters. Its a saving that amounts to seconds for a days work.
More characters on the other hand prevents many potential types of mistakes, such as meaning one statement of target and actually entering another.
> What i dont understand is why does everything have to be so brief.
The concept is to make things easier for people who are familiar with the language. Making things harder for that group is always counterproductive, because they are the only people who can do any useful work.
So the problem is that the semantic of methods (car, cdr) is not well defined: it is either "give me that member" or "give me that member and guarantee next time the result will be same". And the solution is to clearly separate those by adding more method names.
The cons example is conflating implementation details (return the value passed in to cons) with the semantics (return the left-side of this pair that was instantiated by cons). In the first case it is a category error to think about mutability. In the second mutability makes perfect sense.
Moreover, I suspect it is possible to construct an interface such that to prove statically that you can Liskov Substitute a type into it would be equivalent to deciding Halt: All you need are extensional semantics in your type system.
In other words, immutable != read only.
In C# ReadOnlyCollection<T> and ImmutableArray<T> are two completely different things for this exact reason.
as far as my set theoretical intuition goes, immutable has to be a subtype of mutable, if anything.
Yep, I wondered that for a few optimizations in Racket. It's harder than it looks, probably something about covariant or contravariant types, I gave up.
Isn't NSMutableArray a subclass of NSArray in a few languages?
Good one, yes. It was like that in Objective-C, and in the early versions of Swift. I know you know this, but it's useful to summarize for myself:
Basically inheritance is the wrong tool for this kind of stuff. NSMutableArray inherits from NSArray, so it can be passed to anywhere NSArray is expected (upcasting).
So you design your classes and expect them to be immutable, but you can't use NSArray anywhere. Because otherwise, it'll be mutable after all. You can do a runtime check as a workaround.
(I truly believe OOP should only be taught in computer science as a relic).
You just misinterpreted what NSArray is. It’s not an immutable type, it’s a read-only type. As others already mentioned that’s different things. If you have a read-only variable and exclusive access to it, then you can rely on immutability as well. This is what Rust has, for example. Many languages use this definition as well as it’s much more useful than having some sort of pure immutable type guarantee (which some languages do have with const). Another language that uses this is Kotlin: List is a read-only type. MutableList is a subtype of List. You can get a “const” List by only keeping a reference to the value via a List binding. This can be worked around via casting and reflection, but even in Haskell you can do unsafe things that mutate a immutable value, so I don’t think that undermines the idea.
"Was" like that? .... Some of us still use Objective-C!
Yes, that’s ObjC, any NSMutableArray is an NSArray (and an NSObject) - classes passed by reference.
Swift is completely different. Standard arrays are structures, always mutable - value types passed by value
Because if mutable is a sub type of immutable, it wouldnt be right to give a mutable value when the receiver expected immutable values. The same is also true if one reverses the relationship, the mutable operations should not be defined on the immutable, and if they were that would be dumb because the immutable implementations should fail, which is silly.
I would phrase it in terms of subsets. All cats are mammals, therefore "cat" is a subtype of "mammal". So the possible values of the type "cat" are a subset of the possible values of the type "mammal".
In contrast, neither are the mutable things a subset of the immutable things nor the other way round. It's not the case that everything mutable is immutable nor that everything immutable is mutable. The two types are disjoint.
One of the problems with this comes if you're able to dynamically promote something that was passed to you as an "immutable" type to its actual implementation type, you can break this "contract".
I'm currently being annoyed by python's type hinting system, which has exactly this sort of hierarchy for containers, but there's nothing stopping a caller/callee from using type-narrowing to "discover" that the underlying type is actually e.g. a (mutable) list, and then modifying it without any complaints from the type checker. The only way to enforce this would be to actually convert to an immutable implementation type, involving unnecessary copying.
The fact that it requires so much explanation, indicates the level of degradation in the reasoning ability of the audience. A value of a subtype shall deliver all of the expectations of its super type, because it is wearing both the hats of super type and sub type.
Not all all. It merely indicates that this is an strict logic approach to the topic.
https://commonplacefacts.com/2022/07/27/principia-mathematic...
If the article is written for human consumption, then it fails the primary goal (or logic?) of being useful. If a human has to digest a flood of this logic slop just to get convinced about this simple concept, they are not going to be able to do anything useful.
What part of GP's one-sentence explanation is not strictly logical? Does obfuscating a simple logical concept by describing it in academia-wanky-terms like Liskov's Substitution Principle make it More Logical? Or does it just make the author and their in-crowd feel more intelligent?
Note, also, that the article isn't even objective. It asserts that the definition of a subtype is Liskov's principle. However, Liskov's principle is only one of multiple possible definitions. In other words, the article is really only invoking Liskov's name as an appeal to authority. So much for strict logic.
intelligence is overrated