Undecidability of Liskov Substitution Principle
in [OOP]
|
Prev: Are you developing for the Web?
Next: C++ Programmer
From: n.torrey.pines on 21 Mar 2007 15:46 Esdger Dijkstra allegedly said "Object-oriented programming is an exceptionally bad idea which could only have originated in California." :-) I found this paper a while ago, and have been thinking about it often in my daily programming (in C++): http://okmij.org/ftp/Computation/Subtyping/ My summary of it would be: While the Liskov Substitution Principle can be used to determine when a subclass is a subtype, applying the principle is highly non-trivial and error-prone (the author says "undecidable"). This fact leads to OO code being fragile. I'm wondering what people thought about it (beyond cowboy coder's "I don't care about composability or fragility")
From: Daniel T. on 21 Mar 2007 18:54 n.torrey.pines(a)gmail.com wrote: > Esdger Dijkstra allegedly said "Object-oriented programming is an > exceptionally bad idea which could only have originated in > California." :-) > > I found this paper a while ago, and have been thinking about it often > in my daily programming (in C++): > > http://okmij.org/ftp/Computation/Subtyping/ > > My summary of it would be: While the Liskov Substitution Principle can > be used to determine when a subclass is a subtype, applying the > principle is highly non-trivial and error-prone (the author says > "undecidable"). This fact leads to OO code being fragile. Nonsense. I knew where his problem was as soon as I read: Suppose you are tasked with implementing a Set package. Your boss defined a set as an unordered collection where each element has a single occurrence. In fact, your boss even said that a set is a bag with no duplicates... If a set can't do everything a bag can do, then it can't derive from bag. > I'm wondering what people thought about it (beyond cowboy coder's "I > don't care about composability or fragility") Another issue: "All base classes should be abstract." Riel wrote that back in 1996.
From: Dmitry A. Kazakov on 22 Mar 2007 04:40 On 21 Mar 2007 12:46:23 -0700, n.torrey.pines(a)gmail.com wrote: > Esdger Dijkstra allegedly said "Object-oriented programming is an > exceptionally bad idea which could only have originated in > California." :-) What's wrong with California? I bet the weather is great there. (:-)) > I found this paper a while ago, and have been thinking about it often > in my daily programming (in C++): > > http://okmij.org/ftp/Computation/Subtyping/ [I guess this page is well known to all permanent members of comp.object.] > My summary of it would be: While the Liskov Substitution Principle can > be used to determine when a subclass is a subtype, applying the > principle is highly non-trivial and error-prone (the author says > "undecidable"). This fact leads to OO code being fragile. That depends on how LSP is defined. If it is in terms of [decidable] pre-/postconditions and invariants, then I don't see why it should be undecidable. The actual problem with [absolute] LSP is that it is too constraining to be any useful. > I'm wondering what people thought about it (beyond cowboy coder's "I > don't care about composability or fragility") LSP was discussed in comp.object on countless occasions. I suggest you just browse the archives. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Mark Nicholls on 22 Mar 2007 08:00 On 21 Mar, 19:46, n.torrey.pi...(a)gmail.com wrote: > Esdger Dijkstra allegedly said "Object-oriented programming is an > exceptionally bad idea which could only have originated in > California." :-) > > I found this paper a while ago, and have been thinking about it often > in my daily programming (in C++): > > http://okmij.org/ftp/Computation/Subtyping/ > > My summary of it would be: While the Liskov Substitution Principle can > be used to determine when a subclass is a subtype, applying the > principle is highly non-trivial and error-prone (the author says > "undecidable"). This fact leads to OO code being fragile. > > I'm wondering what people thought about it (beyond cowboy coder's "I > don't care about composability or fragility") I broadly agree it is in general undecidable....but that doesn't render the approach futile. The fragility is probably more due to a lack of formality rather than the limitations of that formality. The reason for the lack of formality is an open question, the cost in many cases (currently) may be prohibitive.
From: H. S. Lahman on 22 Mar 2007 12:35
Responding to N.torrey.pines... > Esdger Dijkstra allegedly said "Object-oriented programming is an > exceptionally bad idea which could only have originated in > California." :-) > > I found this paper a while ago, and have been thinking about it often > in my daily programming (in C++): > > http://okmij.org/ftp/Computation/Subtyping/ > > My summary of it would be: While the Liskov Substitution Principle can > be used to determine when a subclass is a subtype, applying the > principle is highly non-trivial and error-prone (the author says > "undecidable"). This fact leads to OO code being fragile. LPS is about type substitution. Classes are not types. So the notion of determining whether one has a subclass or a subtype using LSP seems both undecidable and meaningless. As far as the paper is concerned, the author postulates that a set is a bag without duplicates. That's fine. But then the author proceeds to provide other unrelated properties, implementation inheritance, overloading, and whatnot for the types without regard to LSP. Then when LSP is broken the author complains OO subtyping is fragile. I basically agree with Daniel T.: Don't Do That! If a developer provides implementations within an OO subtyping context it is the responsibility of the developer to ensure LSP is satisfied. If the developer can't ensure that for the candidate implementation then the developer has three choices: (A) change the implementation so that LSP is satisfied; (B) change the client contract with the supertype so that LSP is satisfied for the implementation; or (C) provide the implementation elsewhere (i.e., use delegation outside the subtyping tree). What the developer can't do is throw a new implementation into the subtype and walk away. As far as applying LSP is concerned, one needs to distinguish between recognizing LSP problems and resolving them. Recognizing LSP problems is a matter of DbC contracts with the supertype. If those are properly defined it is usually fairly easy to determine if a candidate implementation violates them. (Though properly defining those contracts can be a tad tedious.) The tricky part is fixing a candidate implementation when it does not satisfy LSP. LSP is a very strong constraint so it is often not possible to satisfy it with a given implementation (i.e., (A) above is not feasible). That, however, does not make OO development fragile. Quite the contrary, the strength of the constraint ensures OO applications will be robust because one can't use the wrong tool for the job in hand. ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl(a)pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info(a)pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH |