problems.md

Problems from Practicing Ruby 3.8, taken directly from examples in Liskov/Wing's "Behavioral Notion of Subtyping", and Bob Martin's article on LSP, but given a Ruby twist.

Problem 1: Bags and Stacks

The problem with implementing a Stack#== method which works as expected for both Stack objects and bag Bag objects is that to compare two stacks the order of the data MUST be considered, but such a constraint does not exists for bags. This causes a substitutability problem, as shown by the example code below.

If bag_a and bag_b are both instances of Bag, we assume the following statements are equivalent.

bag_a == bag_b
bag_b == bag_a

However, if bag_b is a an instance of Stack, then we run into a dilemma if Stack#== enforces an order dependency. Assuming bag_a and bag_b both contained the same items but in a different order, we'd end up with the following results.

bag_a == bag_b #=> true
bag_b == bag_a #=> false

Liskov defines Stack== in her paper to be the same as Bag==, which solves this problem but introduces a new one, in that Stack#== does not consider order and so is not useful for comparing stack objects with each other. She mentions an alternative to solve this problem (which you can look up yourself if you want a spoiler), but it's not a very natural solution for Ruby. Can we do better by augmenting the contracts of these two objects a bit?

Problem 2: Squares and Rectangles

Having a mutable Square object with accessors for both width and height presents a dilemma. If we allow width and height to vary independently, the Square object can become inconsistent with the mathematical definition of a square. If we add a constraint that whenever the width is updated so is the height, this solves the consistency problem but leads to confusing behavior. For example, one might reasonably write a test that looks like this:

def assert_area(area, rect)
  fail "Invalid area calculation" unless area == rect.width * rect.height
end

rect = Rectangle.new
rect.width  = 10
rect.height = 15

# will fail if rect swapped with square
assert_area(150, rect)

A strict interpretation of the LSP would say that we should be able to swap out an instance of the Rectangle object with an instance of a Square and have this code work as expected, but that would not be the case in this code. While it's true that the error here is in the client code and not the Square object, it does lend itself to confusing situations like this. Can we do better if we change the way we model the relationship between Rectangle and Square?

Problem 3: Set and PersistentSet

Creating a transparent delegation proxy on top of Set may on the surface seem to introduce no changes to the method signatures, and so the LSP violation in this scenario might be hard to spot. However, if we recall that exceptions form part of a method's signature, and we consider the following example, the problem becomes easy to see:

>> require "pstore"
=> true
>> store = PStore.new("foo.store")
=> #<PStore:0x000001009e9a70 @filename="foo.store", @abort=false, @ultra_safe=false, @thread_safe=false, @lock=#<Mutex:0x000001009e9958>>
>> store.transaction { store[:foo] = lambda { |x| x + 1 } }
TypeError: no _dump_data is defined for class Proc
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/lib/ruby/1.9.1/pstore.rb:495:in `dump'
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/lib/ruby/1.9.1/pstore.rb:495:in `dump'
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/lib/ruby/1.9.1/pstore.rb:453:in `save_data'
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/lib/ruby/1.9.1/pstore.rb:329:in `block in transaction'
	from <internal:prelude>:10:in `synchronize'
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/lib/ruby/1.9.1/pstore.rb:316:in `transaction'
	from (irb):3
	from /Users/seacreature/.rvm/rubies/ruby-1.9.3-p0/bin/irb:16:in `<main>'

Because our PersistentSet serializes all Set data, it is limited to storing the kinds of objects that can be serialized in Ruby, which makes creating a set of proc objects or anonymous classes (or certain other things) impossible. This means that adding such an element will work if dealing with a Set object but not a PersistentSet object, breaking the subtype relationship. Is there a way we can redefine the shared behaviors between these objects to solve this problem?