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.