Multi-methods/multiple dispatch implemented in ruby

multi_methods.rb

class Type
  attr_accessor :name
  attr_accessor :supertype

  def initialize(name, supertype = nil)
    @name = name
    @supertype = supertype
  end

  def is?(type)
    return true if self == type
    return false if @supertype.nil?
    @supertype.is?(type)
  end

  def distance(type)
    # We only want to consider the chain not the tree so we don't consider types from different branches. e.g. Real and String
    raise "Not a subtype" unless is?(type)
    # If we are at the same type, we are 0 distance away
    return 0 if self == type
    # We are whatever distance `type` away from our supertype + 1.
    # Example:
    #   real.distance(any) = 1 + complex.distance(any)
    #                      = 1 + 1 + number.distance(any)
    #                      = 1 + 1 + 1 + any.distance(any)
    #                      = 1 + 1 + 1 + 0
    #                      = 3
    1 + @supertype.distance(type)
  end

  def to_s
    @name
  end

  def ==(other)
    @name == other.name
  end
end

class Signature
  attr_accessor :types

  def initialize(types)
    @types = types
  end

  def conforms?(signature)
    # for a signature to conform to this one:
    # 1. it must have the same number of types
    return false if signature.types.length != @types.length
    # 2. each type must be a subtype of the corresponding type in this signature
    @types.zip(signature.types).all? { |a, b| a.is?(b) }
  end

  def distance(signature)
    # the distance between two signatures is the sum of the distances between the types
    @types.zip(signature.types).sum { |a, b| a.distance(b) }
  end

  def to_s
    "(#{@types.map(&:to_s).join(", ")})"
  end

  def ==(other)
    @types == other.types
  end
end

class FunctionTable
  attr_accessor :functions

  def initialize()
    @functions = []
  end

  def add(function)
    raise "Function already exists" if @functions.include?(function)
    @functions << function
  end

  def find(function)
    # find all the signatures that conform to the given signature
    candidates = @functions.select { |m| function.signature.conforms?(m.signature) && m.name == function.name }
    # sort them by distance from closest to furthest.
    sorted_by_distance = candidates.sort_by { |m| function.signature.distance(m.signature) }

    # find the closest one.
    # There may be more than one with the same distance, so we find all of them.
    distances = sorted_by_distance.map { |m| function.signature.distance(m.signature) }
    min_distance = distances.min
    closest_functions = sorted_by_distance.select { |m| function.signature.distance(m.signature) == min_distance }
    raise "Ambiguous function call between #{closest_functions}" if closest_functions.length > 1
    closest_functions.first
  end
end

class Function
  attr_accessor :name, :signature

  def initialize(name, signature)
    @name = name
    @signature = signature
  end

  def to_s
    "#{@name}#{@signature}"
  end

  def ==(other)
    @name == other.name && @signature == other.signature
  end
end

any = Type.new("Any")
number = Type.new("Number", any)
complex = Type.new("Complex", number)
real = Type.new("Real", complex)

f1 = Function.new("f", Signature.new([number, number]))
f2 = Function.new("f", Signature.new([complex, complex]))
f3 = Function.new("f", Signature.new([real, real]))

table = FunctionTable.new
table.add(f1)
table.add(f2)
table.add(f3)

call_signature = Signature.new([real, real])
puts table.find(Function.new("f", call_signature)) == f3 # true