Article

Incrementalization across object abstraction

Authors:

Yanhong A. Liu,

Scott D. Stoller,

Michael Gorbovitski,

Yanni Ellen LiuAuthors Info & Claims

OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Pages 473 - 486

https://doi.org/10.1145/1094811.1094848

Published: 12 October 2005 Publication History

Abstract

Object abstraction supports the separation of what operations are provided by systems and components from how the operations are implemented, and is essential in enabling the construction of complex systems from components. Unfortunately, clear and modular implementations have poor performance when expensive query operations are repeated, while efficient implementations that incrementally maintain these query results are much more difficult to develop and to understand, because the code blows up significantly, and is no longer clear or modular.This paper describes a powerful and systematic method that first allows the "what" of each component to be specified in a clear and modular fashion and implemented straightforwardly in an object-oriented language; then analyzes the queries and updates, across object abstraction, in the straightforward implementation; and finally derives the sophisticated and efficient "how" of each component by incrementally maintaining the results of repeated expensive queries with respect to updates to their parameters. Our implementation and experimental results for example applications in query optimization, role-based access control, etc. demonstrate the effectiveness and benefit of the method.

References

[1]

M. A. Ali, A. A. A. Fernandes, and N. W. Paton. Movie: an incremental maintenance system for materialized object views. Data Knowl. Eng., 47(2):131--166, 2003.

Digital Library

[2]

American National Standards Institute, Inc. Role-based access control. ANSI INCITS 359-2004. Approved Feb. 19, 2004. http://csrc.nist.gov/rbac/.

[3]

C. S. Ananian and M. Rinard. Data size optimizations for Java programs. In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems, pages 59--68. ACM Press, 2003.

Digital Library

[4]

F. Bachmann et al. Volume II: Technical concepts of component-based software engineering, 2nd edition. Technical Report CMU/SEI-2000-TR-008, Software Engineering Institute, 2000.

[5]

D. F. Bacon and P. F. Sweeney. Fast static analysis of c++ virtual function calls. In Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 324--341. ACM Press, 1996.

Digital Library

[6]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487--504, Oct. 1984.

Digital Library

[7]

B. Bloom and R. Paige. Transformational design and implementation of a new efficient solution to the ready simulation problem. Science of Computer Programming, 24(3):189--220, 1995.

Digital Library

[8]

J. Cai, P. Facon, F. Henglein, R. Paige, and E. Schonberg. Type analysis and data structure selection. In Möller {33}, pages 126--164.

[9]

S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. In Proceedings of the 17th International Conference on Very Large Data Bases, pages 577--589. Morgan Kaufmann Publishers Inc., 1991.

Digital Library

[10]

J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the 20th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 232--245, Charleston, South Carolina, 1993.

Digital Library

[11]

J. Cocke and K. Kennedy. An algorithm for reduction of operator strength. Commun. ACM, 20(11):850--856, Nov. 1977.

Digital Library

[12]

D. Cohen, N. Goldman, and K. Narayanaswamy. Adding performance information to ADT interface. In Proceedings of the Workshop on Interface Definition Languages, pages 84--93, 1994. Published as SIGPLAN Notices, 29(8).

Digital Library

[13]

J. Dean, G. DeFouw, D. Grove, V. Litvinov, and C. Chambers. Vortex: an optimizing compiler for object-oriented languages. In Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 83--100. ACM Press, 1996.

Digital Library

[14]

E. W. Dijkstra. The humble programmer. Commun. ACM, 15(10):859--866, 1972.

Digital Library

[15]

A. Diwan, K. S. McKinley, and J. E. B. Moss. Using types to analyze and optimize object-oriented programs. ACM Trans. Program. Lang. Syst., 23(1):30--72, 2001.

Digital Library

[16]

D. Goyal and R. Paige. The formal reconstruction and improvement of the linear time fragment of willard's relational calculus subset. In R. Bird and L. Meertens, editors, Algorithmic Languages and Calculi, pages 382--414. Chapman & Hall, London, U.K., 1997.

Digital Library

[17]

D. Gries. The Science of Programming. Springer-Verlag, New York, 1981.

Digital Library

[18]

D. Gries. A note on a standard strategy for developing loop invariants and loops. Science of Computer Programming, 2:207--214, 1984.

[19]

A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 157--166, May 1993.

Digital Library

[20]

C. A. R. Hoare. Proof of correctness of data representation. Acta Informatica, 1:271--281, 1972.

Digital Library

[21]

S. D. Johnson, Y. A. Liu, and Y. Zhang. A systematic incrementalization technique and its application to hardware design. International Journal on Software Tools for Technology Transfer, 4(2):211--223, 2003.

[22]

S. Katz. Program optimization using invariants. IEEE Trans. Softw. Eng., SE-4(5):378--389, Nov. 1978.

Digital Library

[23]

G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In M. Aksit and S. Matsuoka, editors, Proceedings of the 11th Europeen Conference on Object-Oriented Programming, volume 1241 of LNCS, pages 220--242. Springer Verlag, 1997.

[24]

D. Le Métayer. Ace: An automatic complexity evaluator. ACM Trans. Program. Lang. Syst., 10(2):248--266, Apr. 1988.

Digital Library

[25]

D. Liang, M. Pennings, and M. J. Harrold. Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java. In Proceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 73--79. ACM Press, 2001.

Digital Library

[26]

B. Liskov and S. Zilles. Programming with abstract data types. In Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages, pages 50--59, Apr. 1974.

Digital Library

[27]

Y. A. Liu and S. D. Stoller. From Datalog rules to efficient programs with time and space guarantees. In Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pages 172--183, Aug. 2003.

Digital Library

[28]

Y. A. Liu, S. D. Stoller, N. Li, and T. Rothamel. Optimizing aggregate array computations in loops. ACM Trans. Program. Lang. Syst., 27(1):91--125, Jan. 2005.

Digital Library

[29]

Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Trans. Program. Lang. Syst., 20(3):546--585, May 1998.

Digital Library

[30]

Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Strengthening invariants for efficient computation. Science of Computer Programming, 41(2):139--172, Oct. 2001. An earlier version appeared in Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages, 1996.

Digital Library

[31]

Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Science of Computer Programming, 24(1):1--39, Feb. 1995.

Digital Library

[32]

L. G. L. T. Meertens, editor. Program Specification and Transformation. North-Holland, Amsterdam, 1987. Proceedings of the IFIP TC2/WG 2.1 Working Conference on Program Specification and Transformation, Bad Tölz, FRG, April 1986.

Digital Library

[33]

B. Möller, editor. Constructing Programs from Specifications. North-Holland, Amsterdam, 1991.

[34]

H. Nakamura. Incremental computation of complex object queries. In Proceedings of the 16th ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, pages 156--165. ACM Press, 2001.

Digital Library

[35]

F. Nielson, H. R. Nielson, and H. Seidl. Automatic complexity analysis. In Proceedings of the 11th European Symposium on Programming, volume 2305 of LNCS, pages 243--261. Springer-Verlag, Berlin, 2002.

Digital Library

[36]

R. Paige. Programming with invariants. IEEE Software, 3(1):56--69, Jan. 1986.

Digital Library

[37]

R. Paige. Real-time simulation of a set machine on a RAM. In Computing and Information, Vol. II, pages 69--73. Canadian Scholars Press, 1989. Proceedings of ICCI '89: The International Conference on Computing and Information, Toronto, Canada, May 23-27, 1989.

[38]

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst., 4(3):402--454, July 1982.

Digital Library

[39]

R. Paige and R. Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16(6):973--989, Dec. 1987.

Digital Library

[40]

D. L. Parnas. A technique for software module specification with examples. Commun. ACM, 15(5):330--336, May 1972.

Digital Library

[41]

H. A. Partsch. Specification and Transformation of Programs---A Formal Approach to Software Development. Springer-Verlag, Berlin, 1990.

Digital Library

[42]

T. Rothamel. On automatic data structure selection. Technical Report DAR 04-13, Computer Science Department, SUNY Stony Brook, May 2004.

[43]

E. Schonberg, J. Schwartz, and M. Sharir. An automatic technique for the selection of data representations in SETL programs. ACM Trans. Program. Lang. Syst., 3(2):126--143, Apr. 1981.

Digital Library

[44]

U. P. Schultz, J. L. Lawall, and C. Consel. Automatic program specialization for java. ACM Trans. Program. Lang. Syst., 25(4):452--499, 2003.

Digital Library

[45]

D. R. Smith. KIDS: A semiautomatic program development system. IEEE Trans. Softw. Eng., 16(9):1024--1043, Sept. 1990.

Digital Library

[46]

D. R. Smith. A generative approach to aspect-oriented programming. In Proceedings of the 3rd International Conference on Generative Programming and Component Engineering, volume 3286 of LNCS, pages 39--54, Vancouver, Canada, Oct. 2004. Springer-Verlag.

[47]

J. M. Spivey. The Z Notation: A Reference Manual. Prentice-Hall, 2 edition, 1992.

Digital Library

[48]

J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 187--206. ACM Press, 1999.

Digital Library

[49]

D. E. Willard. Quasilinear algorithms for processing relational calculus expressions (preliminary report). In Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 243--257. ACM Press, 1990.

Digital Library

[50]

D. M. Yellin and R. E. Strom. INC: A language for incremental computations. ACM Trans. Program. Lang. Syst., 13(2):211--236, Apr. 1991.

Digital Library

Cited By

Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Stoller SLiu Y(2019)Algorithm Diversity for Resilient SystemsData and Applications Security and Privacy XXXIII10.1007/978-3-030-22479-0_19(359-378)Online publication date: 11-Jun-2019
https://doi.org/10.1007/978-3-030-22479-0_19
Liu YGeorgiou CSchiller E(2018)Logical Clocks Are Not FairProceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems10.1145/3231104.3231109(21-27)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3231104.3231109
Show More Cited By

Index Terms

Recommendations

Incrementalization across object abstraction
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applications

Object abstraction supports the separation of what operations are provided by systems and components from how the operations are implemented, and is essential in enabling the construction of complex systems from components. Unfortunately, clear and ...
Efficiency by Incrementalization: An Introduction

Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each output efficiently by exploiting the previous output. This paper gives an overview of a general and systematic approach to ...
Dynamic Programming via Static Incrementalization

Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

October 2005

562 pages

ISBN:1595930310

DOI:10.1145/1094811

Conference Chairs:
Ralph Johnson
University of Illinois, Urbana-Champaign, Urbana, IL
,
Elisa Baniassad
Chinese University of Hong Kong
,
Program Chairs:
Richard P. Gabriel
Sun Microsystems Laboratories
,
James Noble
Victoria University of Wellington
,
Brian Marick
Exampler Consulting

ACM SIGPLAN Notices Volume 40, Issue 10
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applications
October 2005
531 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1103845
Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA05

Sponsor:

OOPSLA05: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 16 - 20, 2005

CA, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
380
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Stoller SLiu Y(2019)Algorithm Diversity for Resilient SystemsData and Applications Security and Privacy XXXIII10.1007/978-3-030-22479-0_19(359-378)Online publication date: 11-Jun-2019
https://doi.org/10.1007/978-3-030-22479-0_19
Liu YGeorgiou CSchiller E(2018)Logical Clocks Are Not FairProceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems10.1145/3231104.3231109(21-27)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3231104.3231109
Liu YStoller SLin B(2017)From Clarity to Efficiency for Distributed AlgorithmsACM Transactions on Programming Languages and Systems10.1145/299459539:3(1-41)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/2994595
Liu YBrandvein JStoller SLin BCheney JVidal G(2016)Demand-driven incremental object queriesProceedings of the 18th International Symposium on Principles and Practice of Declarative Programming10.1145/2967973.2968610(228-241)Online publication date: 5-Sep-2016
https://dl.acm.org/doi/10.1145/2967973.2968610
Mitschke RErdweg SKöhler MMezini MSalvaneschi G(2014)i3QLACM SIGPLAN Notices10.1145/2714064.266024249:10(417-432)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660242
Mitschke RErdweg SKöhler MMezini MSalvaneschi GBlack AMillstein T(2014)i3QLProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660242(417-432)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660242
Demetrescu CFinocchi IRibichini A(2014)Reactive Imperative Programming with Dataflow ConstraintsACM Transactions on Programming Languages and Systems10.1145/262320037:1(1-53)Online publication date: 17-Nov-2014
https://dl.acm.org/doi/10.1145/2623200
Nerella VMadria SWeigert T(2014)Efficient Caching and Incrementalization of Object Queries on Collections in Programming CodesProceedings of the 2014 IEEE 38th Annual Computer Software and Applications Conference10.1109/COMPSAC.2014.31(229-238)Online publication date: 21-Jul-2014
https://dl.acm.org/doi/10.1109/COMPSAC.2014.31
Maier IOdersky M(2013)Higher-Order reactive programming with incremental listsProceedings of the 27th European conference on Object-Oriented Programming10.1007/978-3-642-39038-8_29(707-731)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39038-8_29
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents