Applying commutative and associative laws to syntax trees

catree.rb

#!/usr/bin/env ruby

# catree.rb : applying commutative and associative laws to syntax trees
#   by takehikom

module CATree
  class Manager
    def initialize(size = 4)
      @factor_size = size
      setup_node
      @count_associative = 0
      @count_commutative = 0
    end
    attr_accessor :initial_node

    def setup_node
      @node_h = {}
      @node_a = []
      @rel_h = {}

      n0 = Node.new
      c = "a"
      ary = []
      @factor_size.times { ary << c; c = c.succ }

      ary.each_with_index do |c, i|
        if i == 0
          n0.left = Node.new(c)
        elsif i == 1
          n0.right = Node.new(c)
        else
          n1 = Node.new
          n1.left = n0
          n1.right = Node.new(c)
          n0 = n1
        end
      end
      @initial_node = n0
    end

    def check_print
      puts @initial_node
      puts @initial_node.traverse(true).inspect
      @initial_node.traverse.each do |item|
        node, path = item
        node2 = @initial_node.subtree(path)
        puts "CHECK: #{path.inspect} : #{node2} : #{node === node2 ? 'ok' : 'ng'}"
      end
    end

    def new_node(n)
      puts "new expression: #{n}"
      @node_h[n.to_s] = n
      @node_a << n
    end

    def registered?(n)
      @node_h.key?(n.to_s)
    end

    def search_neighbor(n0 = @initial_node)
      n0.traverse.each do |item|
        n1, path = item

        # commutative: xy=yx
        if n1.has_left_child? && n1.has_right_child?
          n2 = Marshal.load(Marshal.dump(n0))
          n3 = n2.subtree(path)
          n3.left, n3.right = n3.right, n3.left

          new_relation(n0, n2, :commutative)
        end

        # associative: (xy)z=x(zy)
        if n1.has_left_child? && n1.has_right_child? &&
            n1.left.has_left_child? && n1.left.has_right_child?
          n2 = Marshal.load(Marshal.dump(n0))
          n3 = n2.subtree(path)
          n4, n5, n6 = n3.left.left, n3.left.right, n3.right
          n7 = Node.new
          n7.left, n7.right = n5, n6
          n3.left, n3.right = n4, n7

          new_relation(n0, n2, :associative)
        end

      end
    end

    def new_relation(n1, n2, sym)
      if registered?(n2)
        n2 = @node_h[n2.to_s]
      else
        new_node(n2)
      end

      n1_s, n2_s = n1.to_s, n2.to_s
      if !@rel_h.key?("#{n1_s}:#{n2_s}")
        puts "#{sym}: #{n1_s} = #{n2_s}"
        @rel_h["#{n1_s}:#{n2_s}"] = @rel_h["#{n2_s}:#{n1_s}"] = true
        case sym
        when :commutative
          @count_commutative += 1
        when :associative
          @count_associative += 1
        end
      end
    end

    def start
      new_node(@initial_node)
      @node_a = [@initial_node]
      until @node_a.empty?
        search_neighbor(@node_a.shift)
      end
      print "#{@factor_size} factors: "
      print "#{@node_h.keys.size} expressions / "
      print "#{@count_commutative} commutative / "
      puts "#{@count_associative} associative"
    end
  end

  class Node
    def initialize(label_ = nil)
      @label = label_
      @left = nil
      @right = nil
    end
    attr_accessor :label, :left, :right, :rel

    def to_s
      s = ""
      if has_left_child?
        s1 = @left.to_s
        s1 = "(#{s1})" if s1.length > 1
      else
        s1 = ""
      end
      s2 = @label || ""
      if has_right_child?
        s3 = @right.to_s
        s3 = "(#{s3})" if s3.length > 1
      else
        s3 = ""
      end
      s1 + s2 + s3
    end

    def has_no_child?
      @left.nil? && @right.nil?
    end
    alias :leaf? :has_no_child?

    def has_child?
      !has_no_child?
    end

    def has_left_child?
      !@left.nil?
    end

    def has_right_child?
      !@right.nil?
    end

    def traverse(option_use_label = false)
      if has_left_child?
        a1 = @left.traverse(option_use_label).map {|item| [item[0], [:left] + item[1]]}
      else
        a1 = []
      end
      a2 = [option_use_label ? @label : self, []]
      if has_right_child?
        a3 = @right.traverse(option_use_label).map {|item| [item[0], [:right] + item[1]]}
      else
        a3 = []
      end
      a1 + [a2] + a3
    end

    def subtree(path)
      if path.empty?
        self
      else
        path2 = path.dup
        dir = path2.shift
        send(dir).subtree(path2)
      end
    end
  end
end

if __FILE__ == $0
  m = CATree::Manager.new((ARGV.shift || 4).to_i)
  # m.check_print
  m.start
end