SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 10
Handout E10
Dec. 6, 2000
Due Dec. 13

Finite Differencing of Set Expressions. (Due at class time next Wednesday.)

Problem 1. Finite differencing rules.

For E=#{x in s|f(x)=v} where v is a free variable that can undergo arbitrary change in the range of f, we need to maintain auxiliary expression

   E' = {[v,#{x in s|f(x)=v}] : x in s, v=f(x)}
a map from any value v in range of f(x), where x in s, to the number of element in s such that f(x)=v. For any z, we have E'(z) = #{x in s |f(x)=z}.

What are the derivatives for each of the update as handled in finite differencing rule C1 part 1?

Problem 2. Composition.

When we exploit composability for finite differencing, we say that we can combine the use of sequential composition rule and the use of chain rule. Does it make a difference applying any one of these two rules before the other? Why?

Problem 3. Determining auxiliary expressions.

For finite differencing rule H2, there is a typo in the auxiliary expression to maintain. How to change it to make it correct?

Problem 4. Finite differencing for cycle test.

Given a graph e, the following high-level SETL program, taken from solution to Problem 2 in Assignment 9, computes the largest subset s of vertices each containing a successor belonging to s, and prints out whether s is nonempty. Note that graph e contains a cycle if and only if the resulting set s is nonempty. Use finite differencing to maintain expensive computations through the while loop.

    program cycle1;
      read(e);

      s := domain e;
      while exists x in s| e{x} * s = {} loop
        s less := x;
      end loop;

      print(s/={});
    end;