Notin not working properly

[andreaimprovised]

Peter and I ran into a case where "notin" is not outputing the correct results. Here is the example program, as tiny as I though I could make it. In summary, it uses the bud meta-table t_depends to compute the strongly connected components of the predicate dependency graph.

We use "notin" when we calculate the edges in the dependency graph that have neither of their vertexes contained in a strongly connected component:

    no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
    no_scc <= no_scc_intmd.notin(scc, :body => :predicate)

However, this is not returning the proper results. The equivalent way of performing this computation contains the right results:

    temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
    temp :correct_no_scc <= no_scc_intmd do |x|
      x unless matches.include? x
    end

I've copied and pasted the test program below:

require 'rubygems'
require 'bud'
require 'set'

module Paths

  state do
    # table :t_depends, [:rule_id, :lhs, :op, :body] => [:nm]

    # SCC stuff
    scratch :dep_tc, [:from, :to, :path]
    scratch :cycle, [:predicate, :path]
    scratch :scc, [:predicate] => [:path]
    scratch :all_scc, [:path]

    # new dependency relationship stuff
    scratch :no_scc_intmd, t_depends.schema
    scratch :no_scc, t_depends.schema
    table :labels, [:rule_id, :lhs, :body, :label, :scc]
  end

  bloom :redun do
    # finds all "paths" in bud collection dependency graph
    dep_tc <= t_depends {|d| [d.body, d.lhs, [d.lhs]]}
    dep_tc <= (dep_tc * t_depends).pairs(:to => :body) do |t, d|
      [t.from, d.lhs, Set.new([d.lhs]) | t.path]
    end 

    # finds all cycles in the set of paths
    cycle <= dep_tc{|d| [d.from, d.path] if d.from == d.to}

    # finds all strongly connected components from known cycles
    scc <= cycle.reduce({}) do |memo, i|
      memo[i.predicate] ||= Set.new
      memo[i.predicate] = memo[i.predicate] | i.path
      memo
    end
    all_scc <= scc{|s| [s.path]}

    stdio <~ all_scc.inspected
  end

  bloom :make_dag do
    # HERE IS THE BUG
    # finds all edges that don't participate in a SCC
    no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
    no_scc <= no_scc_intmd.notin(scc, :body => :predicate)

    # Here is the correct output
    temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
    temp :correct_no_scc <= no_scc_intmd do |x|
      x unless matches.include? x
    end
    stdio <~ correct_no_scc.inspected
    stdio <~ no_scc.inspected
  end

end

class TestPaths
  include Paths
  include Bud
end

a = TestPaths.new
a.tick

[jhellerstein]

I did see the bug report.

Hope to get a look at it this week, but if not I'll punt it to someone.

J

On Feb 22, 2012, at 12:14 PM, andyisimprovised wrote:

Peter and I ran into a case where "notin" is not outputing the correct results. Here is the example program, as tiny as I though I could make it. In summary, it uses the bud meta-table t_depends to compute the strongly connected components of the predicate dependency graph.

We use "notin" when we calculate the edges in the dependency graph that have neither of their vertexes contained in a strongly connected component:

   no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
   no_scc <= no_scc_intmd.notin(scc, :body => :predicate)

However, this is not returning the proper results. The equivalent way of performing this computation contains the right results:

   temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
   temp :correct_no_scc <= no_scc_intmd do |x|
     x unless matches.include? x
   end

I've copied and pasted the test program below:

require 'rubygems'
require 'bud'
require 'set'

module Paths

 state do
   # table :t_depends, [:rule_id, :lhs, :op, :body] => [:nm]

   # SCC stuff
   scratch :dep_tc, [:from, :to, :path]
   scratch :cycle, [:predicate, :path]
   scratch :scc, [:predicate] => [:path]
   scratch :all_scc, [:path]

   # new dependency relationship stuff
   scratch :no_scc_intmd, t_depends.schema
   scratch :no_scc, t_depends.schema
   table :labels, [:rule_id, :lhs, :body, :label, :scc]
 end

 bloom :redun do
   # finds all "paths" in bud collection dependency graph
   dep_tc <= t_depends {|d| [d.body, d.lhs, [d.lhs]]}
   dep_tc <= (dep_tc * t_depends).pairs(:to => :body) do |t, d|
     [t.from, d.lhs, Set.new([d.lhs]) | t.path]
   end 

   # finds all cycles in the set of paths
   cycle <= dep_tc{|d| [d.from, d.path] if d.from == d.to}

   # finds all strongly connected components from known cycles
   scc <= cycle.reduce({}) do |memo, i|
     memo[i.predicate] ||= Set.new
     memo[i.predicate] = memo[i.predicate] | i.path
     memo
   end
   all_scc <= scc{|s| [s.path]}

   stdio <~ all_scc.inspected
 end

 bloom :make_dag do
   # HERE IS THE BUG
   # finds all edges that don't participate in a SCC
   no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
   no_scc <= no_scc_intmd.notin(scc, :body => :predicate)

   # Here is the correct output
   temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
   temp :correct_no_scc <= no_scc_intmd do |x|
     x unless matches.include? x
   end
   stdio <~ correct_no_scc.inspected
   stdio <~ no_scc.inspected
 end

end

class TestPaths
 include Paths
 include Bud
end

a = TestPaths.new
a.tick

---

Reply to this email directly or view it on GitHub: https://github.com/bloom-lang/bud/issues/261

[sriram-srinivasan]

I have not fully analyzed this, but it seems the code that prints the "correct" output is not correct.

This is a dump of t_depends (1, "dep_tc", "<=", "dep_tc", false) (8, "matches", "<=", "no_scc_intmd", false) (8, "matches", "<=", "scc", false) (2, "cycle", "<=", "dep_tc", false) (1, "dep_tc", "<=", "t_depends", false) (7, "no_scc", "<=", "no_scc_intmd", false) (6, "no_scc_intmd", "<=", "scc", true) (4, "all_scc", "<=", "scc", false) (9, "correct_no_scc", "<=", "matches", true) (0, "dep_tc", "<=", "t_depends", false) (10, "stdio", "<~", "no_scc", true) (3, "scc", "<=", "cycle", true) (7, "no_scc", "<=", "scc", true) (5, "stdio", "<~", "all_scc", true) (9, "correct_no_scc", "<=", "no_scc_intmd", false) (6, "no_scc_intmd", "<=", "t_depends", false)]

There is just one scc, a trivial self-loop on "dep_tc". Everything else is acyclic.

Since you are looking for edges that don't touch an scc, the correct output should include all edges that do not contain dep_tc on either end. Yet it does:

correct_no_scc: ... // other edges removed (3, "scc", "<=", "cycle", true)]

Now, you are right that the notin implementation does not work in this version.

However, this is computed correctly in the newer version of Bud that's cooking in my fork.

[neilconway]

Andy, can you double-check that the current mainline code (i.e., Sriram's new runtime) produces the correct results? No hurry.

[neilconway]

AFAIK this is fixed.