TYPE

  PowerSet       = set(snum)
  PowerSetList   = list(PowerSet)
  State          = Var -> PowerSet

PROBLEM Sign_Propagation

  direction  : forward
  carrier    : State
  init       : [-> {}]
  init_start : [-> all]
  combine    : lub


TRANSFER

// in assignments calculate the new sign of the variable and add it to the state
  ASSIGN(variable, expression) = 
      @\[variable -> evalAExp(expression, @)]

// in procedure calls pass the sign of the actual argument to the formal parameter
  CALL(_, param, exp), call_edge = 
      @\[param -> evalAExp(exp, @)]

  CALL(_, _, _), local_edge = [-> {}]

// at the end of procedures reset the formal parameter
  END(_, param) =
      @\[param -> all]

SUPPORT

  evalAExp :: Expression * State -> PowerSet
  evalAExp(expression, state) =
    case expType(expression) of "ARITH_BINARY" =>
           case expOp(expression) of
        "+" => lublist([evalPlus(i, j) |
                i in evalAExp(expSubLeft(expression),  state);
                j in evalAExp(expSubRight(expression), state)]);
        "-" => lublist([evalMinus(k, o) |
                k in evalAExp(expSubLeft(expression),  state);
                o in evalAExp(expSubRight(expression), state)]);
        "*" => lublist([evalMulti(l, p) |
                l in evalAExp(expSubLeft(expression),  state);
                p in evalAExp(expSubRight(expression), state)]);
        "/" => if evalAExp(expSubRight(expression), state) = {0} then top else
               lublist([evalDiv(m, j) |
                m in evalAExp(expSubLeft(expression),  state);
                j in evalAExp(expSubRight(expression), state);
                j != 0]) endif;
        endcase;
      "ARITH_UNARY" => case expOp(expression) of
          "-" => {-n|n in evalAExp(expSub(expression),  state)};
        endcase;
      "VAR"   => state(expVar(expression));
      "CONST" => {sgn(expVal(expression))};
      _       => error("Runtime Error: evalAExp applied to nonarithmetic Expression");
    endcase

  evalPlus :: snum * snum -> PowerSet
  evalMinus :: snum * snum -> PowerSet
  evalMulti :: snum * snum -> PowerSet
  evalDiv :: snum * snum -> PowerSet
  lublist :: PowerSetList -> PowerSet

  evalPlus(L, R) = 
    if((L = 1 && R = -1) || (L = -1 && R = 1)) then {-1, 0, 1} else
    if(L = R) then {L} else
    if(L = 0) then {R} else {L} endif endif endif
  evalMinus(L, R) = evalPlus(L, -R)
  evalMulti(L, R) = 
    if(L = 0 || R = 0) then {0} else
    if(R = L) then {1} else {-1} endif endif
  // Don't call with R = zero (already filtered out)
  evalDiv(L, R) = 
    if(L = 0) then {0} else 
    if(R = L) then {1} else {-1} endif endif

  lublist([]) = {}
  lublist(a:b) = a lub lublist(b)