Expressive and modular predicate dispatch for Java

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Expressive and modular predicate dispatch for Java

Full text

Pdf (1.16 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 31 , Issue 2 (February 2009) table of contents

Article No. 7

Year of Publication: 2009

ISSN:0164-0925

Authors

Todd Millstein	University of California, Los Angeles, Los Angeles, CA
Christopher Frost	University of California, Los Angeles, Los Angeles, CA
Jason Ryder	University of California, Los Angeles, Los Angeles, CA
Alessandro Warth	University of California, Los Angeles, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 178, Citation Count: 0

Additional Information:

abstract references 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/1462166.1462168 What is a DOI?

ABSTRACT

Predicate dispatch is an object-oriented (OO) language mechanism for determining the method implementation to be invoked upon a message send. With predicate dispatch, each method implementation includes a predicate guard specifying the conditions under which the method should be invoked, and logical implication of predicates determines the method overriding relation. Predicate dispatch naturally unifies and generalizes several common forms of dynamic dispatch, including traditional OO dispatch, multimethod dispatch, and functional-style pattern matching. Unfortunately, prior languages supporting predicate dispatch have had several deficiencies that limit the practical utility of this language feature.

We describe JPred, a backward-compatible extension to Java supporting predicate dispatch. While prior languages with predicate dispatch have been extensions to toy or nonmainstream languages, we show how predicate dispatch can be naturally added to a traditional OO language. While prior languages with predicate dispatch have required the whole program to be available for typechecking and compilation, JPred retains Java's modular typechecking and compilation strategies. While prior languages with predicate dispatch have included special-purpose algorithms for reasoning about predicates, JPred employs general-purpose, off-the-shelf decision procedures. As a result, JPred's type system is more flexible, allowing several useful programming idioms that are spuriously rejected by those other languages. After describing the JPred language informally, we present an extension to Featherweight Java that formalizes the language and its modular type system, which we have proven sound. Finally, we discuss two case studies that illustrate the practical utility of JPred, including its use in the detection of several errors.

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	H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
	2	Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
	3	Ken Arnold , James Gosling , David Holmes, Java(TM) Programming Language, The (4th Edition), Addison-Wesley Professional, 2005
	4	Assaad, M. G. and Leavens, G. T. 2001. Alias-Free parameters in C for better reasoning and optimization. Tech. Rep. 01-11, Department of Computer Science, Iowa State University, Ames, Iowa. November.
	5	Barrett, C. and Berezin, S. 2004. CVC Lite: A new implementation of the cooperating validity checker. In Proceedings of the 16^th International Conference on Computer Aided Verification (CAV'04), R. Alur and D. A. Peled, Eds. Lecture Notes in Computer Science, vol. 3114. Springer, 515--518.
	6	Baumgartner, G., Jansche, M., and Laufer, K. revised March 2002. Half & Half: Multiple dispatch and retroactive abstraction for Java. Tech. rep. OSU-CISRC-5/01-TR08, Department of Computer and Information Science, The Ohio State University.
	7	Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
	8	Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
	9	John Boyland , Giuseppe Castagna, Parasitic methods: an implementation of multi-methods for Java, ACM SIGPLAN Notices, v.32 n.10, p.66-76, Oct. 1997
	10	Bray, T., Paoli, J., Sperberg-McQueen, C. M., Maler, E., and Yergeau, F. 2006. eXtensible markup language (XML) 1.0 (4th Edition). World Wide Web Consortium recommendation, http://www.w3.org/TR/REC-xml.
	11	Giuseppe Castagna, Covariance and contravariance: conflict without a cause, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.431-447, May 1995 [doi>10.1145/203095.203096]
	12	Giuseppe Castagna, Object-oriented programming: a unified foundation, Birkhauser Boston Inc., Cambridge, MA, 1997
	13	Giuseppe Castagna , Giorgio Ghelli , Giuseppe Longo, A calculus for overloaded functions with subtyping, Information and Computation, v.117 n.1, p.115-135, Feb. 15, 1995 [doi>10.1006/inco.1995.1033]
	14	Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
	15	Craig Chambers, Predicate Classes, Proceedings of the 7th European Conference on Object-Oriented Programming, p.268-296, July 26-30, 1993
	16	Chambers, C. 1997. The Cecil language specification and rationale: Version 2.1. www.cs.washington.edu/research/projects/cecil/pubs/cecil-spec.html.
	17	Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.238-255, November 01-05, 1999, Denver, Colorado, United States
	18	Clifton, C. 2001. MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch. Tech. rep. 01-10, Department of Computer Science, Iowa State University, Ames, Iowa. November.
	19	Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, ACM SIGPLAN Notices, v.35 n.10, p.130-145, Oct. 2000
	20	Curtis Clifton , Todd Millstein , Gary T. Leavens , Craig Chambers, MultiJava: Design rationale, compiler implementation, and applications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.3, p.517-575, May 2006 [doi>10.1145/1133651.1133655]
	21	CVC3. 2009. The CVC3 home page. http://www.cs.nyu.edu/acsys/cvc3.
	22	David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005 [doi>10.1145/1066100.1066102]
	23	Eclipse. 2007. Eclipse home page. http://www.eclipse.org.
	24	Emir, B., Odersky, M., and Williams, J. 2007. Matching objects with patterns. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), E. Ernst, Ed. Lecture Notes in Computer Science, vol. 4609. Springer, 273--298.
	25	Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
	26	Flanagan, C., Joshi, R., Ou, X., and Saxe, J. B. 2003. Theorem proving using lazy proof explication. In the International Conference on Computer Aided Verification (CAV).
	27	Frost, C. and Millstein, T. 2005. Featherweight JPred. Tech. rep. CSD-TR-050038, UCLA Computer Science Department. ftp://ftp.cs.ucla.edu/tech-report/2005-reports/050038.pdf.
	28	Frost, C. and Millstein, T. 2006. Modularly typesafe interface dispatch in JPred. In the International Workshop on Foundations and Developments of Object-Oriented Languages(FOOL/WOOD).
	29	Richard P. Gabriel , Jon L. White , Daniel G. Bobrow, CLOS: integrating object-oriented and functional programming, Communications of the ACM, v.34 n.9, p.29-38, Sept. 1991 [doi>10.1145/114669.114671]
	30	Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	31	Gapeyev, V. and Pierce, B. C. 2003. Regular object types. In Proceedings of the European Conference on Object-Oriented Programming. Lecture Notes in Computer Science, vol. 2743. Springer.
	32	David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
	33	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	34	Robert Otto Grimm , Brian Bershad, System support for pervasive applications, University of Washington, 2002
	35	Robert Grimm , Janet Davis , Eric Lemar , Adam Macbeth , Steven Swanson , Thomas Anderson , Brian Bershad , Gaetano Borriello , Steven Gribble , David Wetherall, System support for pervasive applications, ACM Transactions on Computer Systems (TOCS), v.22 n.4, p.421-486, November 2004 [doi>10.1145/1035582.1035584]
	36	Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
	37	Hosking, J. G., Hamer, J., and Mugridge, W. 1990. Integrating functional and object-oriented programming. In Proceedings of the International Conference on Technology of Obeject-Oriented Languages and Systems TOOLS Pacific, 345--355.
	38	Atsushi Igarashi , Benjamin C. Pierce , Philip Wadler, Featherweight Java: a minimal core calculus for Java and GJ, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.396-450, May 2001 [doi>10.1145/503502.503505]
	39	Daniel H. H. Ingalls, A simple technique for handling multiple polymorphism, Conference proceedings on Object-oriented programming systems, languages and applications, p.347-349, September 29-October 02, 1986, Portland, Oregon, United States
	40	Kiczales, G., Lamping, J., Menhdhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., and Irwin, J. 1997. Aspect-Oriented programming. In Proceedings of the 11th European Conference on Object-Oriented (ECOOP'97), M. Akşit and S. Matsuoka, Eds. Lecture Notes on Computer Science, vol. 1241. Springer, 220--242.
	41	Leavens, G. T. and Antropova, O. 1999. ACL — Eliminating parameter aliasing with dynamic dispatch. Tech. rep. 98-08a, Department of Computer Science, Iowa State University, Ames, Iowa. February.
	42	Keunwoo Lee , Anthony LaMarca , Craig Chambers, HydroJ: object-oriented pattern matching for evolvable distributed systems, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
	43	Jed Liu , Andrew C. Myers, JMatch: Iterable Abstract Pattern Matching for Java, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.110-127, January 13-14, 2003
	44	Todd David Millstein , Craig Chambers, Reconciling software extensibility with modular program reasoning, University of Washington, 2003
	45	Todd Millstein, Practical predicate dispatch, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
	46	Todd Millstein , Colin Bleckner , Craig Chambers, Modular typechecking for hierarchically extensible datatypes and functions, ACM SIGPLAN Notices, v.37 n.9, p.110-122, September 2002
	47	Todd Millstein , Colin Bleckner , Craig Chambers, Modular typechecking for hierarchically extensible datatypes and functions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.5, p.836-889, September 2004 [doi>10.1145/1018203.1018207]
	48	Millstein, T. and Chambers, C. 2002. Modular statically typed multimethods. Inf. Comput. 175, 1, 76--118.
	49	Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
	50	David A. Moon, Object-oriented programming with flavors, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-8, September 29-October 02, 1986, Portland, Oregon, United States
	51	Greg Nelson , Derek C. Oppen, Simplification by Cooperating Decision Procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.245-257, Oct. 1979 [doi>10.1145/357073.357079]
	52	Nystrom, N., Clarkson, M. R., and Myers, A. C. 2003. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction (CC). Springer.
	53	oneworld. 2008. one.world home page. http://cs.nyu.edu/rgrimm/one.world.
	54	Doug Orleans, Incremental programming with extensible decisions, Proceedings of the 1st international conference on Aspect-oriented software development, April 22-26, 2002, Enschede, The Netherlands [doi>10.1145/508386.508393]
	55	Vivek S. Pai , Peter Druschel , Willy Zwaenepoel, Flash: an efficient and portable web server, Proceedings of the annual conference on USENIX Annual Technical Conference, p.15-15, June 06-11, 1999, Monterey, California
	56	Polyglot for Java 5. Polyglot for Java 5 homepage. http://www.cs.ucla.edu/~milanst/projects/polyglot5.
	57	Didier Rémy , Jérôme Vouillon, Objective ML: an effective object-oriented extension to ML, Theory and Practice of Object Systems, v.4 n.1, p.27-50, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:1<27::AID-TAPO3>3.0.CO;2-4]
	58	Richard, A. and Lhotak, O. 2008. OOMatch: Pattern matching as dispatch in Java. In International Workshop on Foundations of Object-Oriented Languages.
	59	Salcianu, A. and Rinard, M. 2005. Purity and side effect analysis for Java programs. In Proceedings of the 6th International Conference on Verification, Model Checking and Abstract Interpretation.
	60	Guy Steele, Common Lisp: The Language, Digital Press, Newton, MA, 1990
	61	Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	62	Ucko, A. M. 2001. Predicate dispatching in the common lisp object system. Tech. rep. 2001-006, MIT Artificial Intelligence Laboratory.
	63	Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
	64	Andrew K. Wright , Matthias Felleisen, A syntactic approach to type soundness, Information and Computation, v.115 n.1, p.38-94, Nov. 15, 1994 [doi>10.1006/inco.1994.1093]