7 - Conclusion

Summary

We have shown a systematic method that succeeds in designing efficient implementations for many problems in many application domains starting with clear specifications of these problems using high-level language constructs. The method is systematic by being based on the language constructs used in the specifications and being guided by the cost considerations taken from the application domains.

The method, even though consisting of Steps Iterate, Incrementalize, and Implement in order, is driven by the middle step—Step Incrementalize. Because efficient computations on nontrivial input must proceed repeatedly on incremented input, Step Incrementalize aims to make the computation on each incremented input efficient by storing and reusing values computed on the previous input. Steps Iterate and Implement are enabling mechanisms: to maximize reuse by Step Incrementalize, Step Iterate determines a minimum input increment to take repeatedly; to support efficient access of the stored values by Step Incrementalize, Step Implement designs a combination of linked and indexed data structures to hold the values.

We first take a deeper look at incrementalization, showing how to systematically exploit the previous result, intermediate results, and auxiliary values for incremental computation. This will use simple examples specified using recursive functions, followed by several different sorting programs as additional examples. We then discuss abstractions in general, focusing on the importance of and principles for not only building up, but also breaking through, abstractions. The latter may sound surprising at first, but it is natural when query functions are incrementalized with respect to updates.