Caching intermediate results for program improvement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Caching intermediate results for program improvement

Full text

Pdf (1.25 MB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation table of contents

La Jolla, California, United States

Pages: 190 - 201

Year of Publication: 1995

ISBN:0-89791-720-0

Authors

Yanhong A. Liu	Department of Computer Science, Cornell University, Ithaca, NY
Tim Teitelbaum	Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 6, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/215465.215590 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.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	3	F. E. Allen, J. Cocke, and K. Kennedy. Reduction of operator strength. In S. Muchnick and N. Jones, editors, Program Flow Analysis, pages 79-101. Prentice- Hall, Englewood Cliffs, New Jersey, 1981.
	4	Robert A. Ballance , Susan L. Graham , Michael L. Van De Vanter, The Pan language-based editing system, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.1, p.95-127, Jan. 1992 [doi>10.1145/125489.122804]
	5	R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
	6	Robert Cartwright, Recursive programs as definitions in first order logic, SIAM Journal on Computing, v.13 n.2, p.374-408, May 1984 [doi>10.1137/0213026]
	7	Wei-Ngan Chin, Towards an automated tupling strategy, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.119-132, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154643]
	8	Wei-Ngan Chin , Siau-Cheng Khoo, Tupling Functions with Multiple Recursion Parameters, Proceedings of the Third International Workshop on Static Analysis, p.124-140, September 22-24, 1993
	9	John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
	10	Norman H. Cohen, Eliminating Redundant Recursive Calls., ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.265-299, July 1983 [doi>10.1145/2166.2167]
	11	J. Earley. High level iterators and a method for automatically designing data structure representation. Journal of Computer Languages, 1:321-342, 1976.
	12	Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
	13	R. J. Hall. Program improvement by automatic redistribution of intermediate results: An overview. In M. R. Lowry and R. D. McCartney, editors, Automating Software Design, chapter 14, pages 339-372. AAAI Press/The MIT Press, 1991. Proceedings of the Workshop on Automating Software Design, AAAI '88.
	14	Roger Hoover, Alphonse: incremental computation as a programming abstraction, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.261-272, June 15-19, 1992, San Francisco, California, United States
	15	John Hughes, Lazy memo-functions, Proc. of a conference on Functional programming languages and computer architecture, p.129-146, January 1985, Nancy, France
	16	Fahimeh Jalili , Jean H. Gallier, Building friendly parsers, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.196-206, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582175]
	17	Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
	18	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]
	19	Robert M. Keller , M. R. Sleep, Applicative caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.88-108, Jan. 1986 [doi>10.1145/5001.5004]
	20	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
	21	J. Launchbury. Projection factorisations in partial evaluation. Ph.d. thesis, Department of Computing, University of Glasgow, 1989.
	22	John Launchbury, Strictness and binding-time analyses: two for the price of one, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.80-91, June 24-28, 1991, Toronto, Ontario, Canada
	23	Julia L. Lawall , Olivier Danvy, Separating stages in the continuation-passing style transformation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.124-136, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158613]
	24	Peter Lipps , Ulrich Möncke , Matthias Olk , Reinhard Wilhelm, Attribute (re)evaluation in OPTRAN, Acta Informatica, v.26 n.3, p.213-239, Nov. 1988 [doi>10.1007/BF00299633]
	25	Yanhong A. Liu , Tim Teitelbaum, Caching Intermediate Results for Program Improvement, Cornell University, Ithaca, NY, 1995
	26	Yanhong A. Liu , Tim Teitelbaum, Incremental Computation for Transformational Software Development, Cornell University, Ithaca, NY, 1995
	27	Yanhong A. Liu , Tim Teitelbaum, Systematic derivation of incremental programs, Science of Computer Programming, v.24 n.1, p.1-39, Feb. 1995 [doi>10.1016/0167-6423(94)00031-9]
	28	D. Michie. "memo" functions and machine learning. Nature, 218:19-22, April 1968.
	29	D. J. Mostow and D. Cohen. Automating program speedup by deciding what to cache. In Proceedings of the Ninth IJCAL pages 165-172, Los Angeles, August 1985.
	30	Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567076]
	31	R. Paige, Symbolic finite differencing, part I (invited lecture), Proceedings of the third European symposium on programming on ESOP '90, p.36-56, May 1990, Copenhagen, Denmark
	32	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]
	33	Helmut A. Partsch, Specification and transformation of programs: a formal approach to software development, Springer-Verlag New York, Inc., New York, NY, 1990
	34	Alberto Pettorossi, A powerful strategy for deriving efficient programs by transformation, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.273-281, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802044]
	35	A. Pettorossi, Strategical derivation of on-line programs, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.73-88, June 1987, Bad To:9Ailz, Germany
	36	G. D. Plotkin. Call-by-nurse, call-by-value and the )~-calculus. Theoretical Computer Science, 1:125-159, 1975.
	37	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]
	38	W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
	39	Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
	40	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]
	41	Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
	42	D. S. Scott. Lectures on a mathematical theory of computation. In M. Broy and G. Schmidt, editors, Theoretical Foundations o} Programming Methodology, pages 145-292. D. Reidel Publishing Company, 1982. Lecture Notes of 1981 Marktoberdorf Summer School on Theoretical Foundations of Programming Methodology, directed by F.L. Bauer, E.W. Dijkstra, and C.A.R. Hoare.
	43	D. R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Transactions on Software Engineering, v.16 n.9, p.1024-1043, September 1990 [doi>10.1109/32.58788]
	44	R. S. Sundaresh , Paul Hudak, A theory of incremental computation and its application, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99587]
	45	K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
	46	Philip Wadler , R. J. M. Hughes, Projections for strictness analysis, Proc. of a conference on Functional programming languages and computer architecture, p.385-407, October 1987, Portland, Oregon, United States
	47	A. B. Webber. A formal definition of unnecessary computation in functional programs. Technical Report TR 92-1260, Department of Computer Science, Cornell University, Ithaca, New York, January 1992.
	48	Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
	49	W Wells, III, Efficient synthesis of Gaussian filters by cascaded uniform filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.234-239, March 1986 [doi>10.1109/TPAMI.1986.4767776]
	50	D. Yeh , U. Kastens, Improvements of an incremental evaluation algorithm for ordered attribute grammars, ACM SIGPLAN Notices, v.23 n.12, p.45-50, Dec. 1988 [doi>10.1145/57669.57672]
	51	Ramin Zabih , Oussama Khatib, Individuating unknown objects by combining motion and stereo, 1994

CITED BY 6

	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.
	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
	Todd B. Knoblock , Erik Ruf, Data specialization, ACM SIGPLAN Notices, v.31 n.5, p.215-225, May 1996
	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
	Alexander D. Stoyen , Plamen V. Petrov, Towards a Mobile Code Management Environment for Complex,Real-Time, Distributed Systems, Real-Time Systems, v.21 n.1-2, p.165-189, July-September 2001
	Thomas W. Reps , Louis B. Rall, Computational Divided Differencing and Divided-Difference Arithmetics, Higher-Order and Symbolic Computation, v.16 n.1-2, p.93-149, March-June 2003