Support negative values in Linear Expressions

[Kalashnikovni]

A simple program such as:

-1

returns the following error:

ERROR>>EvalNat: trying to evaluate arithmetic UnaryOp -1

This prohibits the use of negative numbers in linear expressions, which should be supported.

[Kalashnikovni]

In EvalExpr::operator()(AST::UnaryOp v) a Util::MD_NAT value was returned as result, for a potential negative value. The issue was solved by returning a Rational in all possible cases.

[Kalashnikovni]

As expressions weren't parsed correctly, a refactor was needed, which included:

• Addition of AST::UnOp::div.
• Rewriting of the AST::Expr parser. Now it is possible to write rationals as p/q; any value in such format will be interpreted as rational. The format r(p, q) was also preserved for compatibility.
• Deletion of AST::Boolean and AST::MDNatural which aren't used in SBG programs.

[Kalashnikovni]

The following SBG program was evaluated:

// SCC test with O(N) executing time

N = 100

V1 = N

E1 = 1/2*N-1
E2 = 1/2*N-1+E1
E3 = 1+E2

off1b = 1
off2b = N-2
off3b = N

off1d = -1
off2d = N-4
off3d = N-1

scc(
  V %= {[1:1:V1]};
  Vmap %= <<{[1:1:V1]} -> 0*x+1>>; 
  mapB %= <<{[1:1:E1]} -> 2*x+off1b, {[E1+1:1:E2]} -> 2*x-off2b, {[E2+1:1:E3]} -> 0*x+off3b>>;
  mapD %= <<{[1:1:E1]} -> 2*x+off1d, {[E1+1:1:E2]} -> 2*x-off2d, {[E2+1:1:E3]} -> 0*x+off3d>>;
  Emap %= <<{[1:1:E1], [E1+1:1:E2], [E2+1:1:E3]} -> 0*x+1>>;
)

producing incoherent results. It was then discovered that the evaluator decided incorrectly the Set implementation to use (OrdSet or UnordSet), as /eval/visitor/check_opt_conds.cpp didn't check the slopes of expressions. This also was corrected.

In addition, in the execution of the SCC algorithm it was noted that the subE_map partition wasn't preserved. Debugged.

[Kalashnikovni]

A simple program such as:

100-600

resulted in:

-------------------------
Parsing succeeded
-------------------------
>>>>>> Eval result <<<<<<
-------------------------

100-600
  --> 18446744073709551116

as both values were parsed as naturals, and the result saved in a Util::NAT struct. This was corrected modifying the evaluator to support this operation, returning a Util::RATIONAL.

[Kalashnikovni]

In addition it was decided to use a semicolon to separate assignments and expressions in a SBG program, to avoid ambiguities. Also the use of the "%=" symbol for defining SBGs was changed for a colon, as the previous symbol gave the idea of assignment, which didn't occur while defining a SBG.

[Kalashnikovni]

While rewriting all tests to suit the new grammar it was discovered that scc2.test

// SCC test, where the matching is a simple recursion with two
// border conditions in the middle of the long path

N = 90000;
N2 = 30000;
N3 = 60000;

V1 = 1;
V2 = 1+V1;
V3 = N-1+V2;
V4 = N+V3;

E1 = 1;
E2 = 1+E1;
E3 = N-1+E2;
E4 = N-1+E3;

off1b = V1-E1;
off2b = V2-E2;
off3b = V3-E3;
off4b = V3-E4;

off1d = V4-E1-N3;
off2d = V4-E2-N2;
off3d = V4-E3-1;
off4d = V4-E4;

matchSCC(
V: {[1:1:V1], [V1+1:1:V2], [V2+1:1:V3], [V3+1:1:V4]}
Vmap: <<{[1:1:V1]} -> 0*x+1, {[V1+1:1:V2]} -> 0*x+2, {[V2+1:1:V3]} -> 0*x+3
  , {[V3+1:1:V4]} -> 0*x+4>> 
map1: <<{[1:1:E1]} -> 1*x+off1b, {[E1+1:1:E2]} -> 1*x+off2b, {[E2+1:1:E3]} -> 1*x+off3b
  , {[E3+1:1:E4]} -> 1*x+off4b>>
map2: <<{[1:1:E1]} -> 1*x+off1d, {[E1+1:1:E2]} -> 1*x+off2d, {[E2+1:1:E3]} -> 1*x+off3d
  , {[E3+1:1:E4]} -> 1*x+off4d>>
Emap: <<{[1:1:E1]} -> 0*x+1, {[E1+1:1:E2]} -> 0*x+2
  , {[E2+1:1:E3], [E3+1:1:E4]} -> 0*x+3>>
, 1
);

didn't execute in constant time. This was due to the following condition in the SCC algorithm:

for (; dg.Vmap().restrict(dmap.dom()).sharedImage().isEmpty();) {

which executed the loop until two vertices in the dmap belonged to the same set-vertex. The example has a recursion 3 -> 4 -> ... -> 30 -> 31 -> 1 where 3 to 31 belong to the same set-vertex. As the subset-edges map was partitioned more than needed, the closest vertices of the recursion (30, 31) were discovered individually. This way, in the next iteration the dmap added both vertices to its domain with distance equal to 0 and ended adding other vertices. This way the not_cycle_edges was an empty set, and in turn ER was also empty. The condition was changed to:

for (; dmap.dom().intersection(Vc.intersection(VR)).isEmpty();) {

which executes the loop until a recursive vertex that changed its representative is found in dmap.

[Kalashnikovni]

The execution of the SBG program:

// SCC test with O(N) executing time

N = 10;

V1 = N;

E1 = 1/2*N-1;
E2 = 1/2*N-1+E1;
E3 = 1+E2;

off1b = 1;
off2b = N-2;
off3b = N;

off1d = -1;
off2d = N-4;
off3d = N-1;

V: {[1:1:V1]}
Vmap: <<{[1:1:V1]} -> 0*x+1>>
mapB: <<{[1:1:E1]} -> 2*x+off1b, {[E1+1:1:E2]} -> 2*x-off2b, {[E2+1:1:E3]} -> 0*x+off3b>>
mapD: <<{[1:1:E1]} -> 2*x+off1d, {[E1+1:1:E2]} -> 2*x-off2d, {[E2+1:1:E3]} -> 0*x+off3d>>
Emap: <<{[1:1:E1], [E1+1:1:E2], [E2+1:1:E3]} -> 0*x+1>>;

scc(
  V: {[1:1:V1]}
  Vmap: <<{[1:1:V1]} -> 0*x+1>>
  mapB: <<{[1:1:E1]} -> 2*x+off1b, {[E1+1:1:E2]} -> 2*x-off2b, {[E2+1:1:E3]} -> 0*x+off3b>>
  mapD: <<{[1:1:E1]} -> 2*x+off1d, {[E1+1:1:E2]} -> 2*x-off2d, {[E2+1:1:E3]} -> 0*x+off3d>>
  Emap: <<{[1:1:E1], [E1+1:1:E2], [E2+1:1:E3]} -> 0*x+1>>
);

produced the following result:

<<{[1:1]} -> 2, {[3:3]} -> 2, {[5:5]} -> 2, {[4:4]} -> x-2, {[6:6]} -> x-4, {[8:8]} -> x-6, {[10:10]} -> x-8, {[9:9], [7:7]} -> 2, {[2:2]} -> x>>

which is clearly incorrect, as each vertex is an individual SCC. This was because after handling a recursion, if a recursive rmap was proposed, it wasn't then compared to the original rmap to pick the minimum representative between the two of them. This was corrected with the following code:

PW rmap_plus = rec_rmap.combine(rmap);
rmap_plus = rmap_plus.mapInf();
rmap = rmap.minMap(rmap_plus).compact();