Skip to content

Instantly share code, notes, and snippets.

@practicingruby
Created February 26, 2012 00:17
Show Gist options
  • Save practicingruby/3f53d4094759c0508e19 to your computer and use it in GitHub Desktop.
Save practicingruby/3f53d4094759c0508e19 to your computer and use it in GitHub Desktop.

Answers to the problem set in Practicing Ruby 3.8. Directly based on problems discussed in Liskov/Wing's "Behavioral notion of subtyping", and Bob Martin's article on the LSP, with a Ruby twist.

Problem 1: Stacks and Bags

Our goal is to make it so that we have a stack equality operator that is both a stand-in replacement for bag's equality operator and does the right thing when dealing with a stack operation. Liskov suggests that you could define something like Bag#bag_equal?, which Stack must expose and implement to match Bag's behavior, and that you could add a second stack_equal? method for doing ordered comparisons. However, this feels like a kludge to me, and so I tried to take another angle, following a pattern found in Ruby's Numeric class (i.e. its integer? and float? methods):

require "set"

class Bag
  # other code similar to before
  
  def ==(other)
    [Set.new(data), limit] == [Set.new(other.send(:data)), other.send(:limit)]
  end

  # returns true if the collection is an ordered collection,
  # false otherwise. This defaults to returning false, but 
  # may be overridden by subtypes to return either true or false.
  def ordered?
    false
  end

  private
  
  attr_accessor :data, :limit
end

class Stack
  # other code similar to before

  def ordered?
    true
  end

  # use of send() is ugly here but I don't like making data public
  def ==(other)
    if other.ordered?
      [other.send(:data), other.send(:limit)] == [data, limit]
    else
      [Set[*other.send(:data)], other.send(:limit)] == [Set[*data], limit]
    end
  end
 
  private

  attr_accessor :data, :limit
end

The end result is actually just as ugly (implementation-wise) as what Liskov recommended, but leads to slightly nicer behavior for the end user. Comparing two bags, or a bag and a stack uses bag equality behavior, comparing two stacks use stack equality behavior. But the fundamental difference between these two operations makes me wonder if it'd be better to avoid attempting to make these two objects have a subtype relationship at all, and have a simple Stack#to_bag method that would make it easy to convert a stack into a Bag. Since the whole exercise is a bit contrived, I won't take that line of reasoning further, but I'd be curious to hear the solutions that our readers came up with, so please do share if you have ideas!

Problem 2: Squares and Rectangles

The problems with the LSP violations between squares and rectangles can be trivially solved by making the structures immutable rather than mutable, which is probably a better design anyway. The way I might implement this is shown below:

module Rectangular
  def area
    width * height
  end
end

class Rectangle
  include Rectangular

  def initialize(width, height)
    self.width  = width
    self.height = height
  end

  attr_reader :width, :height

  private

  attr_writer :width, :height
end

class Square 
  include Rectangular

  def initialize(size)
    self.size = size
  end

  attr_reader  :size

  alias_method :width,  :size
  alias_method :height, :size

  private

  attr_writer :size
end

If you wanted to go the aggregation route, you could build something similar to the implementation below:

require "forwardable"

class RectangularShape
  extend Forwardable

  delegate [:width, :height] => :shape

  def initialize(shape)
    self.shape = shape
  end

  def area
    width * height
  end

  private

  attr_accessor :shape
end

class Rectangle
  def initialize(width, height)
    self.width  = width
    self.height = height
  end

  attr_reader :width, :height

  private

  attr_writer :width, :height
end

class Square 
  def initialize(size)
    self.size = size
  end

  attr_reader  :size

  alias_method :width,  :size
  alias_method :height, :size

  private

  attr_writer :size
end

With such a simple example this feels pretty pedantic, but with a more complex set of behaviors, it provides clean encapsulation that module mixins cannot.

Problem 3: Sets and Persistent Sets

Unfortunately, I did not come up with a satisfying answer to this problem. In practice it may be okay to just deal with the subtle incompatibility, since it only fails to be fully compatible due to an obscure edge case. That said, complete compatibility on a more limited subset of functionality can be gained by introducing a third object which wraps both Set and PersistentSet in an API that exposes only the non-mutative set operations. Calls to this adapter would be guaranteed to work safely on both Set and PersistentSet objects, but would be more limited in functionality.

class ImmutableSet
  def initialize(set)
    self.data = set
  end

  include Enumerable

  def member?(element)
    data.member?(element)
  end

  def each
    data.each { |e| yield(e) }
  end

  # any other non-modifying operations can be exposed here.

  private

  attr_accessor :data
end

As with my solutions to problems #1 and #2, I find the cost of fixing this problem to be high enough for me to seriously consider sacrificing purity in the name of pragmatism. Behavioral sub-typing has a much higher cost than simple duck typing, it seems.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment