Generic functions in Ruby

multi.rb

# Generic functions in Ruby
#
# How to use it:
#
#     plus = Multi.new
#     plus.add_method(Numeric, Numeric) { |a, bi| a + b }
#     plus.call(1, 2) #=> 3
#
# For some more fun:
#
#     define_method :plus, do |*args|
#       plus.call(*args)
#     end
#
# Now it looks more like Ruby
#
#     plus 1, 2 #=> 3
#
# Sadly, this doesn't work when calling it with zero arguments
#
#     plus #=> #<Multi:0x007fc2f35bc1c0 ...>
#
# You'd have to do it this way
#
#     plus()
#
# More like CoffeeScript :'(

class Multi
  def initialize
    @mt = MethodTable.new
  end
  
  def add_method(*types, &block)
    unless types.all? { |t| t.is_a? Class }
      raise ArgumentError, "All arguments to add_method must be classes"
    end
    
    @cache.bust! if @cache
    
    @mt.set(types, block)
  end
  
  def call(*args)
    types = args.map(&:class)
    
    block = lookup(types)
    
    unless block
      raise ArgumentError, "No method with signature `#{types.join ", "}`"
    end
    
    block.call(*args)
  end
  
  def cache!
    @cache = Cache.new(@mt)
  end
  
  private
  
  def lookup(types)
    if @cache
      @cache.lookup(types)
    else
      @mt.lookup(types)
    end    
  end
  
  class Cache
    def initialize(mt)
      @mt = mt
    end
    
    def bust!
      @types = @method = nil
    end
    
    def lookup(types)
      if @types == types
        @method
      else
        @types = types
        @method = @mt.lookup(types)

        @method
      end
    end
  end

  class MethodTable
    def initialize
      @entries = {}
    end
    
    def lookup(types)
      if types.empty?
        @method
      else
        t = types[0]

        until t.nil?
          mt = @entries[t]
          
          break if mt
          
          t = t.superclass
        end
        
        if mt
          mt.lookup(types[1..-1])
        end
      end
    end
    
    def set(types, block)
      if types.empty?
        @method = block and return
      end
                
      if @entries.key?(types[0])
        mt = @entries[types[0]]
      else
        mt = @entries[types[0]] = MethodTable.new
      end
      
      mt.set(types[1..-1], block)
    end
  end
end

if __FILE__ == $0
  plus = Multi.new

  define_method :plus do |*args|
    plus.call(*args)
  end

  1.upto(10) do |i|
    plus.add_method(*Array.new(i, Numeric)) { |*args| args.reduce(:+) }
  end

  require 'benchmark'

  ARGS = [1, 2.5, 3, 4.5, 5, 6.5, 7, 8.5, 9, 10.5]

  Benchmark.bm(19) do |x|
    1.upto(10) do |n|
      args = ARGS.take(n)
    
      x.report("#{n} args, no caching") do
        1_000_000.times do
          plus(*args)
        end
      end
    end
    
    plus.cache!
  
    1.upto(10) do |n|
      args = ARGS.take(n)
      
      x.report("#{n} args, caching") do
        1_000_000.times do
          plus(*args)
        end
      end
    end
  end
  
  # 1.7 GHz Core i5-2557M (Mid-2011 13-inch MacBook Air)
  #                           user     system      total        real
  # 1 args, no caching    4.530000   0.020000   4.550000 (  4.562706)
  # 2 args, no caching    5.980000   0.020000   6.000000 (  6.014936)
  # 3 args, no caching    8.070000   0.060000   8.130000 (  8.243900)
  # 4 args, no caching   11.990000   0.100000  12.090000 ( 12.178635)
  # 5 args, no caching   13.480000   0.060000  13.540000 ( 13.619575)
  # 6 args, no caching   14.280000   0.040000  14.320000 ( 14.342066)
  # 7 args, no caching   16.680000   0.110000  16.790000 ( 16.965493)
  # 8 args, no caching   17.240000   0.090000  17.330000 ( 17.406953)
  # 9 args, no caching   18.790000   0.040000  18.830000 ( 18.864472)
  # 10 args, no caching  21.370000   0.160000  21.530000 ( 21.793551)
  # 1 args, caching       3.010000   0.030000   3.040000 (  3.073743)
  # 2 args, caching       3.420000   0.030000   3.450000 (  3.527428)
  # 3 args, caching       3.520000   0.030000   3.550000 (  3.564672)
  # 4 args, caching       5.810000   0.040000   5.850000 (  5.882164)
  # 5 args, caching       6.530000   0.050000   6.580000 (  6.657122)
  # 6 args, caching       7.080000   0.070000   7.150000 (  8.009572)
  # 7 args, caching       6.790000   0.090000   6.880000 (  7.080871)
  # 8 args, caching       8.290000   0.120000   8.410000 ( 10.059922)
  # 9 args, caching       7.670000   0.100000   7.770000 (  8.028576)
  # 10 args, caching      7.370000   0.080000   7.450000 (  7.539959)
end