TYPE

  ConstFlattened = flat(snum)
  BoolFlattened = flat(bool)
  State          = Var -> ConstFlattened


PROBLEM Constant_Propagation

  direction  : forward
  carrier    : State
  init       : bot
  init_start : [-> top]
  combine    : lub


TRANSFER

// in assignments calculate the new value of the variable and add it to the state
  ASSIGN(variable, expression) = if (@ = bot) then @ else
      @\[variable -> evalAExp(expression, @)] endif

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

  CALL(_, _, _), local_edge = bot

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

  // test conditions
  IF(expression), true_edge = branch(expression,@,true)

  IF(expression), false_edge = branch(expression,@,false)

  // loop conditions
  WHILE(expression), true_edge = branch(expression,@,true)

  WHILE(expression), false_edge = branch(expression,@,false)


SUPPORT

  evalAExp :: Expression * State -> ConstFlattened
  evalAExp(expression, state) =
    case expType(expression) of
      "ARITH_BINARY" => case expOp(expression) of
        "+" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft + valRight);
        "-" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft - valRight);
        "*" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft * valRight);
        "/" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 if valRight = 0 then
                   top
                 else lift(valLeft / valRight) endif;
        endcase;
      "ARITH_UNARY" =>
	case expOp(expression) of
          "-" => let value <= evalAExp(expSub(expression), state) in
                   lift(-(value));
        endcase;
      "VAR"   => state ( expVar(expression) );
      "CONST" => lift(expVal(expression));
      _       => error("Runtime Error: evalAExp applied to nonarithmetic Expression");
    endcase


   evalBExp :: Expression * State -> BoolFlattened
   evalBExp(expression,state) = 
     case expType(expression) of 
       "TRUE" => lift(true);
       "FALSE" => lift(false);
      "BOOL_UNARY" => let value <= evalBExp(expSub(expression), state) in lift(!value);
       "BOOL_BINARY" => case expOp(expression) of
         "<" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft < valRight);
         "<=" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft <= valRight);
         ">" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft > valRight);
         ">=" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft >= valRight);
         "=" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft = valRight);
         "<>" => let valLeft  <= evalAExp(expSubLeft(expression),  state),
                   valRight <= evalAExp(expSubRight(expression), state) in
                 lift(valLeft != valRight);
         endcase;
       _ => top;
     endcase


   branch :: Expression * State * bool -> State
   branch(expression, state, edge) = let valexp = evalBExp(expression,state) in 
      if valexp = top then state else if drop(valexp) = edge then state else bot endif endif