Finite Differencing of Computable Expressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finite Differencing of Computable Expressions

Full text

Pdf (2.68 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 4 , Issue 3 (July 1982) table of contents

Pages: 402 - 454

Year of Publication: 1982

ISSN:0164-0925

Authors

Robert Paige	Department of Computer Science, Hill Center for the Mathematical Sciences, Rutgers--The State University of New Jersey, Busch Campus, New Brunswick, NJ
Shaye Koenig	Department of Computer Science, Hill Center for the Mathematical Sciences, Rutgers--The State University of New Jersey, Busch Campus, New Brunswick, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 74, Citation Count: 66

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/357172.357177 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 , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	2	ALLEN, F.E. Program optimization. Annu. Rev. Aurora. Program. 5 (1969), 239-307.
	3	ALLEN, F.E., COCKE, J., AND KENNEDY, K. Reduction of operator strength. In Program Flow Analysis, S. Muchnick and N. Jones (Eds.). Prentice-Hall, Englewood Cliffs, N.j., 1981, pp. 79-101.
	4	BAUER, F.L., ANI) THE C.I.P. LANGUAGE GROUP. Report on a wide spectrum language for program specification and development. Tech. Rep. TUM-I8104, Institut f/Jr informatik, Technische Universitiit Miinchen, M, mich, W. Germany, May 1981.
	5	BROY, M., PARTSCH, H., PEPPER, P., AND WIRSING, M. Semantic relations in programming languages. In Information Processing 80 (1980), 101-106.
	6	BVRGE, W. An optimizing technique for high level programming languages. Computer Science Tech. Rep. RC 5834, #25271, IBM Research Center, Yorktown Heights, N.Y., 1976.
	7	R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
	8	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]
	9	COCKE, J., A~D MARKSTEIN, P. Strength reduction for division and modulo with application to accessing a multilevel store. Computer Science Tech. Rep. RC 7013, #30059, IBM Research Center, Yorktown Heights, N.Y., 1978.
	10	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	11	DEWAR, R.B.K. The SETL programming language. Unpublished manuscript.
	12	Robert K. Dewar , Arthur and Ssu-Cheng Liu and Jacob T. Schwartz and Edmond Schonberg, Programming by Refinement, as Exemplified by the SETL Representation Sublanguage, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.27-49, July 1979 [doi>10.1145/357062.357064]
	13	EARLEY, J. High level iterators and a method for automatically designing data structure representation. Comput. Lang. 1, 4 (1975), 321-342.
	14	FEATHER, M.S. A System for Developing Programs by Transformation. Ph.D. dissertation, Dep. of Artificial Intelligence, Univ. of Edinburgh, Edinburgh, Scotland, 1979.
	15	Amelia C. Fong, Inductively computable constructs in very high level languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567755]
	16	Amelia C. Fong, Generalized common subexpressions in very high level languages, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.48-57, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512956]
	17	Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
	18	FREUDENBERGER, S.M. SETL data structures. SETL Newsl. 189B, Dep. of Computer Science, New York Univ., New York, N.Y., May 1980.
	19	GAREY, M.R., AND JOHNSON, D.S. Computers and Intractability. W.H. Freeman, San Francisco, 1979.
	20	Susan L. Gerhart, Correctness-preserving program transformations, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.54-66, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512983]
	21	GOLDSTINE, H.H. A History of Numerical Analysis. Springer-Verlag, New York, 1977.
	22	Herman H. Goldstine, The computer from Pascal to von Neumann, Princeton University Press, Princeton, NJ, 1980
	23	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	24	C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
	25	KENNEDY, K. A survey of compiler optimization techniques. In Program Flow Analysis, S. Muchnick and N. Jones (Eds.). Prentice-Hall, Englewood Cliffs, N.J., 1981, pp. 5-54.
	26	KENNEDY, K. Variable subsumption with constant folding. SETL Newsl. 123, Dep. of Computer Science, New York Univ., New York, N.Y., Feb. 1974.
	27	KENNEDY, K. Global dead computation elimination. SETL Newsl. 111, Dep. of Computer Science, New York Univ., New York, N.Y., Aug. 1973.
	28	KENNEDY, K. An algorithm to compute compacted use definition chains. SETL Newsl. 112, Dep. of Computer Science, New York Univ., New York, N.Y., Aug. 1973.
	29	KENNEDY, K. Linear function test replacement. SETL Newsl. 107, Dep. of Computer Science, New York Univ., New York, N.Y., May 1973.
	30	KENNEDY, K. Reduction in strength using hashed temporaries. SETL Newsl. 102, Dep. of Computer Science, New York Univ., New York, N.Y., Mar. 1973.
	31	KOENIG, S., AND PAIGE, R. A transformational framework for the automatic control of derived data. In Proceedings, 7th International Conference on Very Large Data Bases, Cannes, France, Sept. 9-11, 1981, pp. 306-318.
	32	MORCENSTERN, M. Automated Design and Optimization of Management Information System Software. Ph.D. dissertation, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., Sept. 1976.
	33	PAICE, R. Formal Differentiation. UMI Research Press, Ann Arbor, Mich., 1981. Revision of Ph.D. dissertation, Dep. of Computer Science, New York Univ., New York, N.Y., June 1979.
	34	PAIGE, R., A~D KOENiG, S. Finite differencing of computable expressions. Tech. Rep. LCSR- TR-8, Dep. of Computer Science, Rutgers Univ., New Brunswick, N.J., Aug. 1980.
	35	Bob Paige , J. T. Schwartz, Expression continuity and the formal differentiation of algorithms, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.58-71, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512957]
	36	ROSEN, B.K. Degrees of availability. In Program Flow Analysis, S. Muchnick and N. Jones (Eds.). Prentice-Hall, Englewood Cliffs, N.J., 1981, pp. 55-76.
	37	Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.126-143, April 1981 [doi>10.1145/357133.357135]
	38	SCHWARTZ, J.T. Correct program technology. Courant Computer Science Rep. 12, Dep. of Computer Science, New York Univ., New York, N.Y., Sept. 1977.
	39	SCHWARTZ, J.T. On the "base form" of algorithms. SETL Newsl. 159, Dep. of Computer Science, New York Univ., New York, N.Y., Nov. 1975.
	40	SCHWARTZ, J.T. Optimization of very high level languages, parts I and II. Comput. Lang. 1, 2-3 (1975), 161-218.
	41	SCHWARTZ, J.T. On Programming' An Interim Report on the SETL Project, Installments I and H. Courant Institute of Mathematical Sciences, New York Univ., New York, N.Y., 1974.
	42	SCHWARTZ, J.T. Structureless programming, or the notion of "rubble," and the reduction of programs to rubble. SETL Newsl. 135A, Dep. of Computer Science, New York Univ., New York, N.Y., July 1974.
	43	Micha Sharir, Some Observations Concerning Formal Differentiation of Set Theoretic Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.196-225, April 1982 [doi>10.1145/357162.357166]
	44	SRIDHARAN, N. Private communication, 1980.
	45	STANDISH, T., HARRIMAN, D., KIBLER, D., AND NEIGHBORS, J. The Irvine program transformation catalogue. Tech. Rep., Dep. of Information and Computer Science, Univ. of California, Irvine, Irvine, Calif., Jan. 1976.
	46	Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
	47	Aaron Melvin Tenenbaum, Type determination for very high level languages., 1974

CITED BY 66

	Alberto Pettorossi , Maurizio Proietti, Program specialization via algorithmic unfold/fold transformations, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998
	Roger Hoover , Tim Teitelbaum, Efficient incremental evaluation of aggregate values in attribute grammars, ACM SIGPLAN Notices, v.21 n.7, p.39-50, July 1986
	Bob Paige, Research Retrospective, Higher-Order and Symbolic Computation, v.16 n.1-2, p.7-13, March-June 2003
	H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983
	Tim Teitelbaum , Richard Chapman, Higher-order attribute grammars and editing environments, ACM SIGPLAN Notices, v.25 n.6, p.197-208, Jun. 1990
	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
	R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984
	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
	Dan E. Willard, Optimal sample cost residues for differential database batch query problems, Journal of the ACM (JACM), v.38 n.1, p.104-119, Jan. 1991
	D. Yellin , R. Strom, INC: a language for incremental computations, ACM SIGPLAN Notices, v.23 n.7, p.115-124, July 1988
	Jiazhen Cai , Robert Paige, Towards increased productivity of algorithm implementation, ACM SIGSOFT Software Engineering Notes, v.18 n.5, p.71-78, Dec. 1993
	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
	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
	Dan E. Willard, Quasilinear algorithms for processing relational calculus expressions (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-257, April 02-04, 1990, Nashville, Tennessee, United States
	Saumya Debray, Abstract interpretation and low-level code optimization, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-121, June 21-23, 1995, La Jolla, California, 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
	Daniel M. Yellin , Robert E. Strom, INC: a language for incremental computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.211-236, April 1991
	Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
	John Sieg, Jr., A tool supporting query optimization and program transformation techniques, Proceedings of the 1990 ACM annual conference on Cooperation, p.15-21, February 20-22, 1990, Washington, D.C., United States
	Tore Risch , René Reboh , Peter E. Hart , Richard O. Duda, A functional approach to integrating database and expert systems, Communications of the ACM, v.31 n.12, p.1424-1437, Dec. 1988
	Yanhong A. Liu , Scott D. Stoller, Program optimization using indexed and recursive data structures, ACM SIGPLAN Notices, v.37 n.3, p.108-118, March 2002
	J. Cai , R. Paige, Binding performance at language design time, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.85-97, January 21-23, 1987, Munich, West Germany
	Allen Goldberg , Robert Paige, Stream processing, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.53-62, August 06-08, 1984, Austin, Texas, United States
	Robert Paige, Future directions in program transformations, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	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
	Laurent Michel , Pascal Van Hentenryck, A constraint-based architecture for local search, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, ACM SIGPLAN Notices, v.34 n.11, p.73-82, Nov. 1999
	Dan E Willard, Efficient processing of relational calculus expressions using range query theory, ACM SIGMOD Record, v.14 n.2, June 1984
	Alan Demers , Anne Rogers , Frank Kenneth Zadeck, Attribute propagation by message passing, ACM SIGPLAN Notices, v.20 n.7, p.43-59, July 1985
	Levent V. Orman, Differential Relational Calculus for Integrity Maintenance, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.328-341, March 1998
	X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991
	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
	Yanhong A. Liu , Scott D. Stoller, From datalog rules to efficient programs with time and space guarantees, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.172-183, August 27-29, 2003, Uppsala, Sweden
	Robert J. Hall, Call Path Refinement Profiles, IEEE Transactions on Software Engineering, v.21 n.6, p.481-496, June 1995
	Alberto Pettorossi , Maurizio Proietti, Rules and strategies for transforming functional and logic programs, ACM Computing Surveys (CSUR), v.28 n.2, p.360-414, June 1996
	Yanhong A. Liu , Scott D. Stoller, Eliminating dead code on recursive data, Science of Computer Programming, v.47 n.2-3, p.221-242, May 2003
	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
	Oege De Moor , David Lacey , Eric Van Wyk, Universal Regular Path Queries, Higher-Order and Symbolic Computation, v.16 n.1-2, p.15-35, March-June 2003
	D. R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Transactions on Software Engineering, v.16 n.9, p.1024-1043, September 1990
	Markus Müller-Olm , Helmut Seidl, Precise interprocedural analysis through linear algebra, ACM SIGPLAN Notices, v.39 n.1, p.330-341, January 2004
	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
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	Deepak Goyal, Transformational Derivation of an Improved Alias Analysis Algorithm, Higher-Order and Symbolic Computation, v.18 n.1-2, p.15-49, June 2005
	Yanhong A. Liu , Scott D. Stoller , Michael Gorbovitski , Tom Rothamel , Yanni Ellen Liu, Incrementalization across object abstraction, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Alberto Pettorossi , Maurizio Proietti , Sophie Renault, Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism, Higher-Order and Symbolic Computation, v.18 n.1-2, p.121-210, June 2005
	Friedrich Ludwig Bauer , Bernhard Möller , Helmut Partsch , Peter Pepper, Formal Program Construction by Transformations-Computer-Aided, Intuition-Guided Programming, IEEE Transactions on Software Engineering, v.15 n.2, p.165-180, February 1989
	Gautam , S. Rajopadhye, Simplifying reductions, ACM SIGPLAN Notices, v.41 n.1, p.30-41, January 2006
	Yanhong A. Liu , Scott D. Stoller, Optimizing Ackermann's function by incrementalization, ACM SIGPLAN Notices, v.38 n.10, p.85-91, October 2003
	Yanhong A. Liu , Scott D. Stoller , Ning Li , Tom Rothamel, Optimizing aggregate array computations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.91-125, January 2005
	Yanhong A. Liu , Chen Wang , Michael Gorbovitski , Tom Rothamel , Yongxi Cheng , Yingchao Zhao , Jing Zhang, Core role-based access control: efficient implementations by transformations, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina
	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
	Katia Hristova , Tom Rothamel , Yanhong A. Liu , Scott D. Stoller, Efficient type inference for secure information flow, Proceedings of the 2006 workshop on Programming languages and analysis for security, June 10-10, 2006, Ottawa, Ontario, Canada
	Tom Rothamel , Yanhong A. Liu, Efficient implementation of tuple pattern based retrieval, Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 15-16, 2007, Nice, France
	Ajeet Shankar , Rastislav Bodík, DITTO: automatic incrementalization of data structure invariant checks (in Java), ACM SIGPLAN Notices, v.42 n.6, June 2007
	Shaye Koenig , Robert Paige, A transformational framework for the automatic control of derived data, Proceedings of the seventh international conference on Very Large Data Bases, p.306-318, September 09-11, 1981, Cannes, France
	Katia Hristova , K. Tuncay Tekle , Yanhong A. Liu, Efficient trust management policy analysis from rules, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
	Douglas R. Smith, Requirement enforcement by transformation automata, Proceedings of the 6th workshop on Foundations of aspect-oriented languages, p.5-14, March 13-13, 2007, Vancouver, British Columbia, Canada
	Françoise Fabret , Mireille Régnier , Eric Simon, An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.455-466, August 24-27, 1993
	E Mark Gold, Incremental reduction with nested constraints, ACM SIGPLAN Notices, v.26 n.2, p.25-34, Feb. 1991
	Markus Müller-Olm , Helmut Seidl, Analysis of modular arithmetic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.5, p.29-es, August 2007
	Tom Rothamel , Yanhong A. Liu, Generating incremental implementations of object-set queries, Proceedings of the 7th international conference on Generative programming and component engineering, October 19-23, 2008, Nashville, TN, USA
	Michael Gorbovitski , Tom Rothamel , Yanhong A. Liu , Scott D. Stoller, Efficient runtime invariant checking: a framework and case study, Proceedings of the 2008 international workshop on dynamic analysis: held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008), July 21-21, 2008, Seattle, Washington
	Diptikalyan Saha, Extending logical attack graphs for efficient vulnerability analysis, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	Mark Perlin, Call-graph caching: transforming programs into networks, Proceedings of the 11th international joint conference on Artificial intelligence, p.122-128, August 20-25, 1989, Detroit, Michigan
	Jack Mostow , Donald Cohen, Automating program speedup by deciding what to cache, Proceedings of the 9th international joint conference on Artificial intelligence, p.165-172, August 18-23, 1985, Los Angeles, California
	Yanhong A. Liu , Scott D. Stoller, From datalog rules to efficient programs with time and space guarantees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.6, p.1-38, August 2009