INC: a language for incremental computations

ABSTRACT

An incremental computation is one that is performed repeatedly on nearly identical inputs. Incremental computations occur naturally in many environments, such as compilers, language-based editors, spreadsheets, and formatters. This article describes a proposed tool for making it easy to write incremental programs. The tool consists of a programming language, INC, and a set of compile-time transformations for the primitive elements of INC. A programmer defines an algorithm in INC without regard to efficient incremental execution. The transformations automatically convert this algorithm into an efficient incremental algorithm. INC is a functional language. The implementation of an INC program is a network of processes. Each INC function is transformed into a process that receives and transmits messages describing changes to its inputs and outputs. We give an overview to the language and illustrate the incremental techniques employed by INC. We present the static and incremental complexity bounds for the primitive INC functions. We also present some example programs illustrating INC's flexibility.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 2: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 3: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 4: Paul John Asente, Editing graphical objects using procedural representations, Stanford University, Stanford, CA, 1988
• 5: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 6: A. Michael Berman , Marvin C. Paull , Barbara G. Ryder, Proving relative lower bounds for incremental algorithms, Acta Informatica, v.27 n.7, p.665-683, 1990
• 7: BURKE, M., AND RYDER, B.G. Incremental iterative data fiow analysis algorithms. Tech. Rep. LCSR-TR-96, Dept. of Computer Science, Rutgers Univ., Aug. 1987.
• 8: J. Cai , R. Paige, Program derivation by fixed point computation, Science of Computer Programming, v.11 n.3, p.197-261, April 1989 [doi>10.1016/0167-6423(88)90033-0]
• 9: CHEN, P., HARmSON, M., AND MINAKAT5, I. Incremental document formatting. Tech. Rep., Computer Science Div. Univ. of California, Berkeley, June 1988.
• 10: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 11: HARmSON, P., AND KHOSHNEVTSAN, H. An introduction to FP and the FP style of programming. Computers and their Applications, Ellis-Horwood, Chichester, England, 1987, pp. 44-56.
• 12: J. Heering , P. Klint , J. Rekers, Incremental generation of parsers, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.179-191, June 19-23, 1989, Portland, Oregon, United States
• 13: 13. HENn~so~, P., AND WmSER, M. The Visiprog environment. Tech. Rep., State Univ. of New York at Stony Brook, 1988. An abridged version appeared in the Proceedings of the 8th International Conference on Software Engineering.
• 14: Roger Hoover, Dynamically bypassing copy rule chains in attribute grammars, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.14-25, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512646]
• 15: Roger Hoover , Tim Teitelbaum, Efficient incremental evaluation of aggregate values in attribute grammars, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.39-50, June 25-27, 1986, Palo Alto, California, United States
• 16: HO~SPOOL, N. Incremental generation of LR parsers. Tech. Rep., Computer Science Dept., Univ. of Victoria, March 1988.
• 17: Susan Horwitz , Tim Teitelbaum, Generating editing environments based on relations and attributes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.577-608, Oct. 1986 [doi>10.1145/6465.6512]
• 18: P~G~, W., J~. Incremental computation and the incremental evaluation of functional programs. Ph.D. thesis, Cornell Univ. Ithaca, N.Y., Aug. 1988.
• 19: R. R. Karinthi , M. Weiser, Incremental re-execution of programs, Papers of the Symposium on Interpreters and interpretive techniques, p.38-44, June 24-26, 1987, St. Paul, Minnesota, United States
• 20: William Leler, Constraint programming languages: their specification and generation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 21: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 22: PAruE, R. Prog~camming with invariants. IEEE Sofiw. 3, i (Jan. 1986), 56-69.
• 23: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 24: Thomas William Reps, Generating language-based environments, 1982
• 25: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 26: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 27: B. G. Ryder , T. J. Marlowe , M. C. Paull, Conditions for incremental iteration: examples and counterexamples, Science of Computer Programming, v.11 n.1, p.1-15, Oct. 1988 [doi>10.1016/0167-6423(88)90061-5]
• 28: Robert E. Strom , David F. Bacon , Arthur P. Goldberg , Andy Lowry , Daniel M. Yellin , Shaula Alexander Yemini, Hermes: a language for distributed computing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 29: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 30: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 31: H. H. Vogt , S. D. Swierstra , M. F. Kuiper, Higher order attribute grammars, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.131-145, June 19-23, 1989, Portland, Oregon, United States
• 32: R. C. Waters, Efficient interpretation of synchronizable series expressions, Papers of the Symposium on Interpreters and interpretive techniques, p.74-85, June 24-26, 1987, St. Paul, Minnesota, United States
• 33: YELLIN, D. M. A dynamic transitive closure algorithm. Tech. Rep. RC 13535, IBM T J. Watson Research Center, June 1988. Revised Oct. 1990.
• 34: Daniel Yellin, Representing sets with constant time equality testing, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.64-73, January 22-24, 1990, San Francisco, California, United States
• 35: D. Yellin , R. Strom, INC: a language for incremental computations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.115-124, June 20-24, 1988, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: INC

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages

Keywords:
dynamic algorithms, finite differencing, incremental complexity, incrementality, static complexity