SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 5
Handout E5
Oct. 18, 2000
Due Oct. 25

Incremental Programs and Incrementalization. (Due at class time next Wednesday.)

To derive an incremental program, we may reuse the previous computation result, the intermediate results, and auxiliary information, as explained in class.

Give an additional example that you can best think of now for each of the three cases. For each example, give the program f, input change operation +, and the incremental program f'. If your example is large, you may give only the description of f, +, and f', not necessarily the precise code. Don't forget to analyze the efficiencies.

Bonus. How do you think incrementalization is related to (1) tupling / memo / tabulation, (2) fusion / combination / stream processing, and (3) partial evaluation / specialization, respectively? We will discuss this next time.