Testing structures with meta variables, as unification.

gistfile1.rb

# Testing two structures if they are unifiable.
#
module UnifierAssertion
  def unify(es, s = {}, &block)
    return s if es.empty?
    
    e = es.shift
    a,b = e

    a = s[a] || a
    b = s[b] || b

    if Hash === a and Hash === b
      if block_given?
        yield a.keys.sort, b.keys.sort
      else
        return nil unless a.keys.sort == b.keys.sort
      end
      a.keys.each do |key|
        es << [a[key], b[key]]
      end
    elsif Array === a and Array === b
      es += a.zip(b)
    elsif Symbol === a and a.to_s =~ /^'/
      s = self.subst(s, a, b).merge!(a => b)
    elsif Symbol === b and b.to_s =~ /^'/
      s = self.subst(s, b, a).merge!(b => a)
    else
      p a,b
      if block_given?
        yield a, b
      else
        return nil unless a == b
      end
    end
    
    unify(es, s, &block)
  end
  
  # Substitute any occurance of x in hash to y.
  # ie compute hash[x -> y]
  def subst(hash, x, y)
    result = {}
    hash.each do |key, value|
      if key == x
        key = y
      end
      if value == x
        value = y
      end
      
      result[key] = value
    end
  end
  
  def assert_unify(a, b, message = "")
    self.unify([[a, b]]) do |x, y|
      assert_equal x, y, message
    end
  end
end