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.

Improve this question
$\endgroup$
3
  • $\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, 2018 at 18:32
  • $\begingroup$ Here is one thing I found. apocalisp.wordpress.com/2010/10/06/… $\endgroup$
    – Jim Newton
    Sep 13, 2018 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, 2018 at 22:02

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is the "induced subtyping rule" ? Is that the arrow-types subtyping rule I stated above? $\endgroup$
    – Jim Newton
    Sep 14, 2018 at 8:15
  • $\begingroup$ I've added a similar question elsewhere. cs.stackexchange.com/questions/97310/… $\endgroup$
    – Jim Newton
    Sep 14, 2018 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, 2018 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.