skip to main content
10.1145/1394496.1394497acmotherconferencesArticle/Chapter ViewAbstractPublication PagesmodularityConference Proceedingsconference-collections
research-article

Redundancy-free residual dispatch: using ordered binary decision diagrams for efficient dispatch

Published: 01 April 2008 Publication History

Abstract

State-of-the-art implementations of common aspect-oriented languages weave residual dispatching logic for advice whose applicability cannot be determined at compile-time. But being derived from the residue's formula representation the woven code often implements an evaluation strategy which mandates redundant evaluations of atomic pointcuts. In order to improve upon the average-case run-time cost, this paper presents an alternative representation which enables efficient residual dispatch, namely ordered binary decision diagrams. In particular, this representation facilitates the complete elimination of redundant evaluations across all pointcuts sharing a join point shadow.

References

[1]
A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, Reading, MA, USA, 2nd edition, 2006.
[2]
The AspectJ Project. The AspectJ Programming Guide. http://www.eclipse.org/aspectj/doc/released/progguide/.
[3]
P. Avgustinov, A. S. Christensen, L. J. Hendren, S. Kuzins, J. Lhoták, O. Lhoták, O. de Moor, D. Sereni, G. Sittampalam, and J. Tibble. Optimising AspectJ. ACM SIGPLAN Notices, 40(6), 2005.
[4]
P. Avgustinov, A. S. Christensen, L. J. Hendren, S. Kuzins, J. Lhoták, O. Lhoták, O. de Moor, D. Sereni, G. Sittampalam, and J. Tibble. abc: An extensible AspectJ compiler. In Transactions on Aspect-Oriented Software Development I. Springer, Berlin, Germany, 2006.
[5]
C. Bockisch, M. Mezini, W. Havinga, L. Bergmans, and K. Gybels. Reference model implementation. Technical Report AOSD-Europe Deliverable D96, Technische Universität Darmstadt, 2007.
[6]
B. Bollig and I. Wegener. A very simple function that requires exponential size read-once branching programs. Information Processing Letters, 66(2), 1998.
[7]
K. S. Brace, R. L. Rudell, and R. E. Bryant. Efficient implementation of a BDD package. In Proceedings of the 27th Design Automation Conference, 1990.
[8]
R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 1986.
[9]
C. Chambers and W. Chen. Efficient multiple and predicated dispatching. ACM SIGPLAN Notices, 34(10), 1999.
[10]
F. Chen and G. Roşu. MOP: An efficient and generic runtime verification framework. In Proceedings of the 22nd OOPSLA Conference, 2007.
[11]
Y. Endoh, H. Masuhara, and A. Yonezawa. Continuation join points. In Proceedings of the 5th FOAL Workshop, 2006.
[12]
M. D. Ernst, C. S. Kaplan, and C. Chambers. Predicate dispatching: A unified theory of dispatch. In Proceedings of the 12th ECOOP Conference, 1998.
[13]
M. Fujita, H. Fujisawa, and Y. Matsunaga. Variable ordering algorithms for ordered binary decision diagrams and their evaluation. IEEE Transactions of Computer-Aided Design of Integrated Circuits and Systems, 12(1), 1993.
[14]
J. Gergov and C. Meinel. Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Transactions on Computers, 43(10), 1994.
[15]
J. Gosling, W. N. Joy, G. L. Steele, and G. Bracha. The Java Language Specification. Addison-Wesley, Reading, MA, USA, 3rd edition, 2005.
[16]
E. Hilsdale and J. Hugunin. Advice weaving in AspectJ. In Proceedings of the 3rd AOSD Conference, 2004.
[17]
G. Kiczales, E. Hilsdale, J. Hugunin, M. Kersten, J. Palm, and W. G. Griswold. An overview of AspectJ. In Proceedings of the 15th ECOOP Conference, 2001.
[18]
H. Masuhara and G. Kiczales. Modeling crosscutting in aspect-oriented mechanisms. In Proceedings of the 17th ECOOP Conference, 2003.
[19]
H. Masuhara, G. Kiczales, and C. Dutchyn. A compilation and optimization model for aspect-oriented programs. In Proceedings of the 12th Conference on Compiler Construction, 2003.
[20]
D. Orleans. Incremental programming with extensible decisions. In Proceedings of the 1st AOSD Conference, 2002.
[21]
M. C. Rinard, A. Salcianu, and S. Bugrara. A classification system and analysis for aspect-oriented programs. In Proceedings of the 12th ACM SIGSOFT, 2004.
[22]
D. Sieling and I. Wegener. Graph driven BDDs: A new data structure for Boolean functions. Theoretical Computer Science, 141(1 & 2), 1995.
[23]
M. Wand, G. Kiczales, and C. Dutchyn. A semantics for advice and dynamic join points in aspect-oriented programming. ACM Transactions on Programming Languages and Systems, 26(5), 2004.
[24]
I. Wegener. Branching Programs and Binary Decision Diagrams: Theory and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Cited By

View all
  • (2013)A fine-grained, customizable debugger for aspect-oriented programmingTransactions on Aspect-Oriented Software Development X10.5555/2554488.2554489(1-38)Online publication date: 1-Jan-2013
  • (2012)A fine-grained debugger for aspect-oriented programmingProceedings of the 11th annual international conference on Aspect-oriented Software Development10.1145/2162049.2162057(59-70)Online publication date: 25-Mar-2012
  • (2011)An overview of ALIA4JProceedings of the 49th international conference on Objects, models, components, patterns10.5555/2025896.2025907(131-146)Online publication date: 28-Jun-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
FOAL '08: Proceedings of the 7th workshop on Foundations of aspect-oriented languages
April 2008
56 pages
ISBN:9781605581101
DOI:10.1145/1394496
  • Program Chair:
  • Curt Clifton
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]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. advice
  2. aspect-oriented programming
  3. dispatch functions
  4. ordered binary decision diagrams
  5. pointcuts
  6. residual dispatch

Qualifiers

  • Research-article

Funding Sources

Conference

AOSD08

Acceptance Rates

Overall Acceptance Rate 5 of 6 submissions, 83%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)A fine-grained, customizable debugger for aspect-oriented programmingTransactions on Aspect-Oriented Software Development X10.5555/2554488.2554489(1-38)Online publication date: 1-Jan-2013
  • (2012)A fine-grained debugger for aspect-oriented programmingProceedings of the 11th annual international conference on Aspect-oriented Software Development10.1145/2162049.2162057(59-70)Online publication date: 25-Mar-2012
  • (2011)An overview of ALIA4JProceedings of the 49th international conference on Objects, models, components, patterns10.5555/2025896.2025907(131-146)Online publication date: 28-Jun-2011
  • (2011)Making aspects naturalProceedings of the tenth international conference on Aspect-oriented software development10.1145/1960275.1960312(285-300)Online publication date: 21-Mar-2011
  • (2011)An Overview of ALIA4JObjects, Models, Components, Patterns10.1007/978-3-642-21952-8_11(131-146)Online publication date: 2011
  • (2010)Supporting dynamic aspect-oriented featuresACM Transactions on Software Engineering and Methodology10.1145/1824760.182476420:2(1-34)Online publication date: 8-Sep-2010
  • (2008)A decision tree-based approach to dynamic pointcut evaluationProceedings of the 2nd Workshop on Virtual Machines and Intermediate Languages for emerging modularization mechanisms10.1145/1507504.1507508(1-10)Online publication date: 21-Oct-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media