Order-of-evaluation Analysis for Destructive Updates in Strict Functional Languages with Flat Aggregates
A.V.S. Sastry, William Clinger
Committee:
Technical Report(Dec 1969)
Keywords:

The aggregate update problem in functional languages is concerned with detecting cases where an update operation can be implemented destructively in constant time. Previous work on this problem has assumed a fixed order of evaluation of expressions. In this paper, we devise an analysis, for strict functional languages with flat aggregates, that derives a good order of evaluation for making the updates destructive. We show that our update analysis algorithm runs in polynomial time. We implemented the algorithm and tested it on some common example programs. The results show that a good choice of the order of evaluation indeed makes most of the updates destructive.