Incremental Computation via Partial Evaluation

Authors:

Raman S. Sundaresh and Paul Hudak

Abstract:

We present a general framework for incremental computation that helps in understand existing incremental algorithms, and facilitates (if not automates) the construction of new ones.  The framework is based on the recently popular notion of partial evaluation.  Besides providing a precise definition of the term "incremental program ," this framework offers:

  • A methodology to generate an incremental program from its non-incremental counterpart plus a specification of a partition of the input domain.
  • An algebraic basis for reasoning about the correctness of the incremental programs thus generated.
  • A comparative basis for better understanding existing incremental algorithms.  In particular, we have re-cast many existing incremental programs into our framework.
  • To overcome the overhead of "incremental interpretation," a method to generate "compiled" incremental programs using Futamura projections is described.

Bibtex:

 @inproceedings{inc-POPL91
    ,author={Sundaresh, R.S. and Hudak, P.}
    ,title={Incremental Computation via Partial Evaluation}
    ,booktitle={Proceedings 18th Symposium on Principles of Programming
           Languages}
    ,organization={ACM}
    ,month=Jan
    ,year=1991
    ,pages={1-13}
    } 

Links:

IncCompPE-POPL91.pdf