Practical predicate dispatch

ABSTRACT

<i>Predicate dispatch</i> 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 its utility in practice.

We introduce JPred, a backward-compatible extension to Java supporting predicate dispatch. While prior languages with predicate dispatch have been extensions to toy or non-mainstream 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 type-checking 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 and type system, we present a case study illustrating the utility of JPred in a real-world application, including its use in the detection of several errors.

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: Davide Ancona , Giovanni Lagorio , Elena Zucca, A Formal Framework for Java Separate Compilation, Proceedings of the 16th European Conference on Object-Oriented Programming, p.609-636, June 10-14, 2002
• 3: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: M. G. Assaad and G. T. Leavens. Alias-free parameters in C for better reasoning and optimization. Technical Report 01-11, Department of Computer Science, Iowa State University, Ames, Iowa, Nov. 2001.
• 5: C. Barrett. Personal communication, Mar. 2004.
• 6: 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
• 7: D. Blei, C. Harrelson, R. Jhala, R. Majumdar, G. C. Necula, S. P. Rahul, W. Weimer, and D. Weitz. Vampyre: A Proof Generating Theorem Prover. http://www.cs.ucla.edu/~rupak/Vampyre.
• 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: Tim Bray , Jean Paoli , C. M. Sperberg-McQueen, Extensible markup language, World Wide Web Journal, v.2 n.4, p.29-66, Winter 1997
• 10: 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]
• 11: 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
• 12: Craig Chambers, Predicate Classes, Proceedings of the 7th European Conference on Object-Oriented Programming, p.268-296, July 26-30, 1993
• 13: C. Chambers. The Cecil language specification and rationale: Version 2.1. www.cs.washington.edu/research/projects/cecil/pubs/cecil-spec.html, Mar. 1997.
• 14: 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
• 15: C. Clifton. MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch. Technical Report 01-10, Department of Computer Science, Iowa State University, Ames, Iowa, Nov. 2001.
• 16: Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.130-145, October 2000, Minneapolis, Minnesota, United States
• 17: CVC Lite home page. http://verify.stanford.edu/CVCL.
• 18: D. Detlefs, G. Nelson, and J. B. Saxe. Simplify: A theorem prover for program checking. Technical Report HPL-2003-148, HP Labs, 2003.
• 19: Sophia Drossopoulou , Susan Eisenbach , David Wragg, A Fragment Calculus Towards a Model of Separate Compilation, Linking and Binary Compatibility, Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, p.147, July 02-05, 1999
• 20: 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
• 21: Manuel Fahndrich , Robert DeLine, Adoption and focus: practical linear types for imperative programming, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 22: C. Flanagan, R. Joshi, X. Ou, and J. B. Saxe. Theorem proving using lazy proof explication. In CAV: International Conference on Computer Aided Verification, Boulder, Colorado, USA, July 2003.
• 23: Jeffrey S. Foster , Tachio Terauchi , Alex Aiken, Flow-sensitive type qualifiers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 24: 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]
• 25: 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
• 26: V. Gapeyev and B. C. Pierce. Regular object types. In Proceedings of the 2003 European Conference on Object-Oriented Programming, LNCS 2743, Darmstadt, Germany, July 2003. Springer-Verlag.
• 27: 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
• 28: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 29: Robert Otto Grimm , Brian Bershad, System support for pervasive applications, 2002
• 30: 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
• 31: J. G. Hosking, J. Hamer, and W. Mugridge. Integrating functional and object-oriented programming. In Proceedings of the 1990 TOOLS Pacific, pages 345--355, 1990.
• 32: 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
• 33: G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In M. Aksoit and S. Matsuoka, editors, ECOOP '97 - Object-Oriented Programming 11th European Conference, Jyväskylä, Finland, LNCS 1241, pages 220--242. Springer-Verlag, New York, NY, June 1997.
• 34: G. T. Leavens and O. Antropova. ACL -Eliminating parameter aliasing with dynamic dispatch. Technical Report 98-08a, Department of Computer Science, Iowa State University, Ames, Iowa, Feb. 1999.
• 35: 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
• 36: 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
• 37: Todd David Millstein , Craig Chambers, Reconciling software extensibility with modular program reasoning, 2003
• 38: 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
• 39: T. Millstein and C. Chambers. Modular statically typed multimethods. Information and Computation, 175(1):76--118, May 2002.
• 40: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 41: 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
• 42: MzScheme home page. http://www.plt-scheme.org/software/mzscheme.
• 43: 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]
• 44: N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for Java. In Proceedings of CC 2003: 12'th International Conference on Compiler Construction. Springer-Verlag, Apr. 2003.
• 45: OCaml home page. http://www.ocaml.org.
• 46: one.world home page. http://cs.nyu.edu/rgrimm/one.world.
• 47: 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]
• 48: V. S. Pai, P. Druschel, and W. Zwaenepoel. Flash: An efficient and portable web server. In Proceedings of the 1999 USENIX Annual Technical Conference (USENIX-99), pages 199--212, Berkeley, CA, June 6-11 1999. USENIX Association.
• 49: 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]
• 50: The Scala language home page. http://lamp.epfl.ch/~odersky/scala.
• 51: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 52: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 53: Aaron Stump , Clark W. Barrett , David L. Dill, CVC: A Cooperating Validity Checker, Proceedings of the 14th International Conference on Computer Aided Verification, p.500-504, July 27-31, 2002
• 54: A. M. Ucko. Predicate Dispatching in the Common Lisp Object System. Technical Report 2001-006, MIT Artificial Intelligence Laboratory, June 2001.
• 55: P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]
• 56: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Inheritance; Procedures, functions, and subroutines; Classes and objects

General Terms:
Design, Languages

Keywords:
dynamic dispatch, modular typechecking, predicate dispatch