Instantly share code, notes, and snippets.

# practicingruby/problems.md Secret

Created February 25, 2012 17:09
Show Gist options
• Save practicingruby/15b50f918c88bccd6eac to your computer and use it in GitHub Desktop.

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?