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

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;