2
$\begingroup$

This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)?

LSP seems to have two meanings in the literature I've seen. One statement is the rule that determines whether one function type is a subtype of another? I.e, A->Y is a subtype of B->X, if B is a subtype of A and Y is a subtype of X. The other statement is that in an object oriented language, a method in subclasses should be element of the subtype of the type of the method in the parent class.

The principle that B<:A, X<:Y implies A->X <: B->Y was a known principle well before the name "Liskov Substitution Principle" was ever coined. I have found references to this principle from the early 80s.

For example, https://cl-su-ai.cddddr.org/msg04614.html, here is an email from 1987 where the author describes what he calls "PROBLEM II". It is the definition and justification for the definition of arrow types described above. Furthermore, this presentation, http://www.softwarepreservation.org/projects/LISP/crisp_ibm370_sdc/CRISP-talk.pdf, claims it was known in the early 1970s.

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ I've never seen the subtyping rule for functional types $A\to B$ being referred to as LSP. Where did you found that being called LSP? $\endgroup$ – chi Sep 13 '18 at 18:32
  • $\begingroup$ Here is one thing I found. apocalisp.wordpress.com/2010/10/06/… $\endgroup$ – Jim Newton Sep 13 '18 at 22:00
  • $\begingroup$ Maybe I'm wrong. Perhaps this was simply a misconception I had which was never challenged. What is the contravariance subtype rule for arrow types called? $\endgroup$ – Jim Newton Sep 13 '18 at 22:02
3
$\begingroup$

I don't think either of these is the Liskov substitution principle. My understanding of the principle is that for $S$ to be a subtype of $T$, it must be the case that we can substitute a value of type $S$ anywhere a value of type $T$ is required without compromising the correctness of our program.

Now, the subtyping rule for functions is probably a sufficient condition for the Liskov principle to be satisfied, as long as functions are sufficiently abstract. But this is not "the" principle, because it says nothing about anything that isn't functions.

Also, this page argues that subclassing in most OOP languages is insufficient to ensure the Liskov principle is satisfied. That is, it only ensures that the principle is satisfied with respect to other simple, declared subtyping relationships like you mentioned. It does not ensure that implicit invariants are respected, and indeed, it is possible to violate these invariants in a subclass. So the Liskov principle would say that sometimes sub-class does not imply sub-type.

It's probably also possible for this second argument to apply to "functions" in a language as well (although it would be pretty unsatisfactory), in which case the Liskov principle would not validate the induced subtyping rule.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ What is the "induced subtyping rule" ? Is that the arrow-types subtyping rule I stated above? $\endgroup$ – Jim Newton Sep 14 '18 at 8:15
  • $\begingroup$ I've added a similar question elsewhere. cs.stackexchange.com/questions/97310/… $\endgroup$ – Jim Newton Sep 14 '18 at 9:15
  • $\begingroup$ Sorry, I don't know that I've seen a name for that rule. I can mention some related concepts, though. I'll do so later on your linked question if someone else doesn't get there first. $\endgroup$ – Dan Doel Sep 14 '18 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.