bloom-lang / bud

Prototype Bud runtime (Bloom Under Development)
http://bloom-lang.net
Other
854 stars 60 forks source link

Incorrect stratification error #321

Closed neilconway closed 10 years ago

neilconway commented 10 years ago

Given this program:

class StratShouldWork
  include Bud

  state do
    scratch :r2
    table :t4
    scratch :t5
    table :t20
  end

  bloom do
    r2 <= t4.notin(t5)
    t5 <= (t5 * t20).lefts
  end
end

Bud mistakenly claims this program is unstratifiable:

TestStratErrors#test_strat_ok:
Bud::CompileError: unstratifiable program: r2,t5
palvaro commented 10 years ago

the algorithm used by calc_stratum() looks broken. as we explore a path, if we visit a node we've already visited, AND anywhere on the path we've crossed a negated edge, we throw unstratifiable. we should only do so if the negated edge was IN the cycle. fix coming.

someone remind me why this is no longer done "declaratively" in depanalysis by testing if a node is reachable from itself on a path with negation?