Order-of-evaluation Analysis for Destructive Updates in Strict Functional Languages with Flat Aggregates

The aggregate update problem in functional languages is concerned with detecting cases where a functional array 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 a simple analysis, for strict functional languages with flat aggregates, that derives a good order of evaluation for making the updates destructive. Our work improves Hudak's work [14] on abstract reference counting, which assumes fixed order of evaluation and uses the domain of sticky reference counts. Our abstract reference counting uses a 2-point domain. We show that for programs with no aliasing, our analysis is provably more precise than Hudak's approach (even if the fixed order of evaluation chosen by Hudak happens to be the right order). We also show that our analysis algorithm runs in polynomial time. To the best of our knowledge, no previous work shows polynomial time complexity. We suggest ..