Incremental computation via function caching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Incremental computation via function caching

Full text

Pdf (1.55 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Austin, Texas, United States

Pages: 315 - 328

Year of Publication: 1989

ISBN:0-89791-294-2

Authors

W. Pugh	Dept. of Computer Science, Cornell University, Ithaca, NY and Dept. of Comp. Sci., Univ. of Maryland, College Park, Md.
T. Teitelbaum	Dept. of Computer Science, Cornell University, Ithaca, NY

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 44, Citation Count: 37

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75277.75305 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ACR+87	B. All~.~m, A. Carle, B.Rosen, P. Sweeney, and K. Zadeck. lncr~tal evalaution of attributed graphs. Technical Report RC 13205, IBM, Thomas J. Watson Research Center, Yorktown Heights, New York 10598, October 1987.
	All78	John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
	DRT81	Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
	Hoo86	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]
	Hoo87	R. Hoover, Incremental graph evaluation (attribute grammar), Cornell University, Ithaca, NY, 1987
	HT86	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]
	Kat84	Takuya Katayama, Translation of attribute grammars into procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.345-369, July 1984 [doi>10.1145/579.586]
	Knu73	Donald Knuth, Sorting and Searching, The Art of Computer Programming, Vol. 3,1973.
	Meh84	Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, 1984.
	Mic68	D. Michie. "Memo" functions and machine learniing. Nature, (218):19-22, April 1968.
	Par78	Luis {sidoro Trabb Pardo, Set Representation and Set Intersection, Ph.D. thesis, Stanford University, 1978
	Pug88a	William Pugh, An improved replacement strategy for function caching, Proceedings of the 1988 ACM conference on LISP and functional programming, p.269-276, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62719]
	Pug88b	William Worthington Pugh, Jr., Incremental computation and the incremental evaluation of functional programs, 1988
	RA84	Thomas Reps , Bowen Alpern, Interactive proof checking, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.36-45, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800514]
	Rep82	Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
	Rep84	Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
	SG76	M. Sassa and E. Goto, A hashing method for fast set operations. Inf. Proc. l.~t. 5(2):31-34, June 1976.
	TK84	H. Taylor and S. Karlin. An Introduction to Stochastic Modeling, Academic Press, Orlando, Florida, 1984.
	YS88	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

CITED BY 37

	K. V. Seshu Kumar, Value reuse optimization: reuse of evaluated math library function calls through compiler generated cache, ACM SIGPLAN Notices, v.38 n.8, August 2003
	Roger Hoover, Alphonse: incremental computation as a programming abstraction, ACM SIGPLAN Notices, v.27 n.7, p.261-272, July 1992
	John Field , Tim Teitelbaum, Incremental reduction in the lambda calculus, Proceedings of the 1990 ACM conference on LISP and functional programming, p.307-322, June 27-29, 1990, Nice, France
	K. Mehlhorn , R. Sundar , C. Uhrig, Maintaining dynamic sequences under equality-tests in polylogarithmic time, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 23-25, 1994, Arlington, Virginia, United States
	Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
	Todd B. Knoblock , Erik Ruf, Data specialization, ACM SIGPLAN Notices, v.31 n.5, p.215-225, May 1996
	Vivek Nirkhe , William Pugh, Partial evaluation of high-level imperative programming languages with applications in hard real-time systems, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.269-280, January 19-22, 1992, Albuquerque, New Mexico, United States
	Bradley T. Vander Zanden , Richard Halterman , Brad A. Myers , Rich McDaniel , Rob Miller , Pedro Szekely , Dario A. Giuse , David Kosbie, Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.776-796, November 2001
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Yanhong A. Liu , Tim Teitelbaum, Caching intermediate results for program improvement, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-201, June 21-23, 1995, La Jolla, California, United States
	R. Sundar , R. E. Tarjan, Unique binary search tree representations and equality-testing of sets and sequences, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.18-25, May 13-17, 1990, Baltimore, Maryland, United States
	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
	G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States
	Allan Heydon , Roy Levin , Yuan Yu, Caching function calls using precise dependencies, ACM SIGPLAN Notices, v.35 n.5, p.311-320, May 2000
	Brian Guenter , Todd B. Knoblock , Erik Ruf, Specializing shaders, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.343-350, September 1995
	Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003
	Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Umut A. A. Acar , Guy E. Blelloch , Robert Harper, Selective memoization, ACM SIGPLAN Notices, v.38 n.1, p.14-25, January 2003
	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990
	Daniel M. Yellin, Algorithms for subset testing and finding maximal sets, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.386-392, September 1992, Orlando, Florida, United States
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	Mohamed F. Younis , Thomas J. Marlowe , Alexander D. Stoyen , Grace Tsai, Statically Safe Speculative Execution for Real-Time Systems, IEEE Transactions on Software Engineering, v.25 n.5, p.701-721, September 1999
	Beatrice Luca , Stefan Andrei , Hugh Anderson , Siau-Cheng Khoo, Program transformation by solving recurrences, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina
	Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, ACM SIGPLAN Notices, v.37 n.1, p.247-259, Jan. 2002
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998
	Abhishek Chugh , Maria Hybinette, Towards adaptive caching for parallel and discrete event simulation, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Umut A. Acar , Guy E. Blelloch , Matthias Blume , Kanat Tangwongsan, An experimental analysis of self-adjusting computation, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.990-1034, November 2006
	Ajeet Shankar , Rastislav Bodík, DITTO: automatic incrementalization of data structure invariant checks (in Java), ACM SIGPLAN Notices, v.42 n.6, June 2007
	Umut A. Acar , Amal Ahmed , Matthias Blume, Imperative self-adjusting computation, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Haiying Xu , Christopher J. F. Pickett , Clark Verbrugge, Dynamic purity analysis for java programs, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.75-82, June 13-14, 2007, San Diego, California, USA
	Matthew A. Hammer , Umut A. Acar, Memory management for self-adjusting computation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Gurvan Le Guernic , Julien Perret, FLIC: Application to Caching of a Dynamic Dependency Analysis for a 3D Oriented CRS, Electronic Notes in Theoretical Computer Science (ENTCS), 219, p.3-18, November, 2008
	Ruy Ley-Wild , Matthew Fluet , Umut A. Acar, Compiling self-adjusting programs with continuations, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Ruy Ley-Wild , Umut A. Acar , Matthew Fluet, A cost semantics for self-adjusting computation, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Yin Xiong , Maria Hybinette , Eileen Kraemer, Transparent and adaptive computation-block caching for agent-based simulation on a PDES core, Proceedings of the 40th Conference on Winter Simulation, December 07-10, 2008, Miami, Florida
	Matthew A. Hammer , Umut A. Acar , Yan Chen, CEAL: a C-based language for self-adjusting computation, ACM SIGPLAN Notices, v.44 n.6, June 2009