HydroJ: object-oriented pattern matching for evolvable distributed systems

Abstract

In an evolving software system, components must be able to change independently while remaining compatible with their peers. One obstacle to independent evolution is the brittle parameter problem: the ability of two components to communicate can depend on a number of inessential details of the types, structure, and/or contents of the values communicated. If these details change, then the components can no longer communicate, even if the essential parts of the message remain unaffected.We present HydroJ, an extension of Java that addresses this problem. In HydroJ, components communicate using self-describing, semi-structured messages, and programmers use pattern matching to define the handling of messages. This design stems from two central ideas: first, that self-describing messages reduce dependence on inessential message format details; and second, that object-oriented pattern matching naturally focuses on the essential information in a message and is insensitive to inessential information.We have developed these ideas in the context of Rain, a distributed, heterogeneous messaging system for ubiquitous computing. To evaluate the design, we have constructed a prototype HydroJ compiler, implemented some Rain services in HydroJ, studied the evolution of an existing Rain service over time, and formalized HydroJ's key features in a core language.

References

1. F. Achermann, M. Lumpe, J.-G. Schneider, O. Nierstrasz. Piccola: A Small Composition Language. Formal Methods for Distributed Processing - A Survey of Object-Oriented Approaches, H. Bowman and J. Derrick, eds., pp. 403-426. Cambridge Univ. Press, 2001.
2. W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, J. Lilley. The Design and Implementation of an Intentional Naming System. In Proc. 17th ACM Symp. on Operating Systems Principles, pp. 186--201, Charleston SC, 1999.
3. J. Aldrich, C. Chambers, D. Notkin. ArchJava: Connecting Software Architecture to Implementation. In Proc. 24th Int'l Conf. on Software Engineering, pp. 187--197, Orlando FL, May 2002.
4. V. Bénzaken, G. Castagna, A. Frisch. CDuce: An XML-Centric General-Purpose Language. In Proc. ACM Int'l Conf. on Functional Programming, 2003.
5. A. D. Birrell, B. J. Nelson. Implementing Remote Procedure Calls. ACM Trans. on Computer Systems, 2(1):39--59, Feb. 1984.
6. C. Brabrand, A. Moller, M. I. Schwartzbach. The <bigwig> project. In ACM Trans. on Internet Technology, 2002.
7. D. Box et al. Simple Object Access Protocol (SOAP) 1.1. W3C Note, 8 May 2000. http://www.w3.org/TR/SOAP/.
8. C. Chambers, G. T. Leavens. Typechecking and Modules for Multimethods. ACM Transactions on Programming Languages and Systems 17(6):805--843, Nov. 1995.
9. C. Clifton, G. T. Leavens, C. Chambers, T. Millstein. MultiJava: Modular Open Classes and Symmetric Multiple Dispatch for Java. In Conf. on Object-Oriented Programming Systems, Languages, and Applications, pp. 130--145, Oct. 15-19, 2000.
10. B. O. Christiansen, M. Munke, K. Muller-Jones, W. Lamersdorf. Type Management: A Key to Software Reuse in Open Distributed Systems. In Proc. First Int'l Enterprise Distributed Object Computing Workshop, Gold Coast, Australia, Oct. 1997.
11. A. Colmerauer. An introduction to Prolog III. Communications of the ACM 33(7):69--90, July 1990.
12. H. Common, M. Dauchet, Rémy Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi. Tree Automata Techniques and Applications. Draft manuscript, Aug. 2003. http://www.grappa.univ-lille3.fr/tata/
13. The Common Object Request Broker: Architecture and Specification, Version 3.0. Object Management Group, Inc. July 2002. http://www.omg.org/cgi-bin/doc?formal/02-06-01
14. A. Carzinaga, D. S. Rosenblum, A. L. Wolf. Design and Evaluation of a Wide-Area Event Notification Service. ACM Trans. on Computer Systems, 19(3):332--383, Aug. 2001.
15. O.-J. Dahl, K. Nygaard. SIMULA --- an ALGOL- Based Simulation Language. Communications of the ACM 9(9):671--678, Sept. 1966.
16. R. Deline. A Catalog of Techniques for Resolving Packaging Mismatch. In Proc. 1999 Symp. on Software Reusability, pp. 44--53, Los Angeles CA, May 1999.
17. M. Ernst, C. Kaplan, C. Chambers. Predicate Dispatching: A Unified Theory of Dispatch. In Proc. 12th European Conf. on Object-Oriented Programming, pp. 186--211, Brussels, Belgium, 1998.
18. C. Flanagan, M. Felleisen. The Semantics of Future and Its Use in Program Optimization. In Proc. 22nd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pp. 209--220, Jan. 1995.
19. V. Gapeyev, B. C. Pierce. Regular Object Types. In Proc. 17th European Conf. on Object-Oriented Programming, LNCS 2743, Darmstadt, Germany, July 2003.
20. D. Garlan, R. Allen, J. Ockerbloom. Architectural Mismatch: Why Reuse Is So Hard. IEEE Software, 12(6):17--26, Nov. 1995.
21. F. Gécseg, M. Steinby. Tree Languages. Handbook of Formal Languages, 3:1-68. G. Rozenberg and A. Salomaa, eds. Springer-Verlag, 1997.
22. D. Gelernter. Generative Communication in Linda. ACM Trans. on Programming Languages and Systems, 7(1):80--112, 1985.
23. A. Goldberg, D. Robson. Smalltalk-80: The Language. Addison-Wesley, Jan. 1989.
24. Guide: Understanding Daily Life via Auto-Identification and Statistics. Project web site. http://seattleweb.intel-research.net/projects/guide/
25. M. Hicks, J. T. Moore, S. Nettles. Dynamic Software Updating. In Proc. ACM SIGPLAN'01 Conf. on Programming Language Design and Implementation, pp. 13--23, Snowbird UT, 2001.
26. J. Hightower, B. Brumitt, G. Borriello. The Location Stack: A Layered Model for Location in Ubiquitous Computing. In Proc. 4th IEEE Workshop on Mobile Computing Systems & Applications, pp. 22--28, Callicon NY, June 2002.
27. H. Hosoya, M. Murata. Validation and Boolean operations for Attribute-Element Constraints. In Informal Proc. of Workshop on Programming Language Technologies for XML: PLAN-X 2002, pp. 1--10. Pittsburgh PA, Oct. 3, 2002.
28. H. Hosoya, B. Pierce. Regular Expression Pattern Matching for XML. In Proc. 28th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pp 67--80, London, United Kingdom, 2001.
29. Hypertext Transfer Protocol --- HTTP/1.1. IETF RFC 2616. June 1999. http://www.w3.org/Protocols/rfc2616/rfc2616.txt
30. J.-H. Kang, M. Philipose, G. Borriello. River: An Infrastructure for Context Dependent, Reactive Communication Primitives. In 5th IEEE Workshop on Mobile Computing Systems & Applications, Monterey CA, Oct. 9-10 2003.
31. A. LaMarca, D. Koizumi, M. Lease, S. Sigurdsson, G. Borriello, W. Brunette, K. Sikorski, D. Fox. PlantCare: An Investigation in Practical Ubiquitous Systems. Intel Research, IRS-TR-02-007, Jul. 2002.
32. K. Lee, A. LaMarca, C. Chambers. HydroJ: Object-Oriented Pattern Matching for Evolvable Distributed Systems. Technical Report UW-CSE-03-08-01, University of Washington, 2003. Forthcoming. http://www.cs.washington.edu/research/projects/cecil/pubs/hydroj.html
33. D. MacQueen. Modules for Standard ML. In Proc. 1984 ACM Symp. on Lisp and Functional Programming, pp. 198--207, Austin TX, 1984.
34. E. Meijer, M. Shields. XMLambda: A Functional Programming Language for Constructing and Manipulating XML Documents. Drafr manuscript, 2002. http://www.cse.ogi.edu/~mbs/pub/xmlambda
35. E. Meijer, C. Szyperski. Overcoming Independent Extensibility Challenges. Communications of the ACM, 45(10):41--44, Oct. 2002.
36. M. Mezini, K. Lieberherr. Adaptive Plug-and-Play Components for Evolutionary Software Development. In Proc. Conf. on Object-Oriented Programming, Systems, Languages, and Applications, pp. 97--116, Vancouver, Canada, 1998.
37. M. Mezini, K. Ostermann. Integrating Independent Components with On-Demand Remodularization. In Proc. 17th ACM Conf. on Object-Oriented Programming, Systems, Languages and Applications, Seattle WA, Nov. 2002.
38. Microsoft Corporation. .NET Framework Developer's Guide: XML and SOAP Serialization. http://msdn.microsoft.com/library/en-us/cpguide/html/cpconserialization.asp+
39. T. Millstein, C. Bleckner, C. Chambers. Modular Typechecking for Hierarchically Extensible Datatypes and Functions. In Proc. Seventh ACM SIGPLAN Int'l Conf. on Functional Programming, pp. 110--122, Pittsburgh PA, Oct. 2002.
40. R. Milner. The Polyadic π-Calculus: A Tutorial. Logic of Algebra and Specification, F. L. Buaer, W. Brauer, H. Schwichtenberg, ed., pp. 203--246, Springer-Verlag, 1993.
41. R. Milner, M. Tofte, R. Harper, D. MacQueen. The Definition of Standard ML (Revised). Cambridge: MIT Press, May 1997.
42. P. Muckelbauer, V. F. Russo. Lingua Franca: An IDL for Structural Subtyping Distributed Object Systems. In Proc. 1995 USENIX Conf. on Object-Oriented Technologies, Monterey CA, June 1995.
43. N. Nystrom, M. R. Clarkson, A. C. Myers. Polyglot: An Extensible Compiler Framework for Java. In Proc. 12th Int'l Conf. on Compiler Construction, Warsaw, Poland, April 2003.
44. R. Pucella. Towards a Formalization for COM Part I: The Primitive Calculus. In Proc. 17th ACM Conf. on Object-Oriented Programming, Systems, Languages and Applications, Seattle, WA, USA, Nov. 2002.
45. RELAX NG Specification. Organization for the Advancement of Structured Information Standards. http://www.oasis-open.org/committees/relax-ng/
46. Relaxer home page. http://www.relaxer.org/
47. M. Rodrig, A. LaMarca. Decentralized Weighted Voting for P2P Data Management. In 3rd Int'l ACM Workshop on Data Engineering for Wireless and Mobile Access, San Diego, CA, USA, Sept. 2003.
48. D. Rogerson. Inside COM. Redmond, WA: Microsoft Press, 1997.
49. R. Srinivasan. XDR: External Data Representation Standard. IETF RFC 1832. Sun Microsystems, Inc., August 1995. http://www.ietf.org/rfc/rfc1832+
50. I. Stoica, R. Morris, D. R. Karger, M. F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proc. 2001 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 149--160, San Diego CA, 2001.
51. Sun Microsystems, Inc. Remote Method Invocation web site. http://java.sun.com/products/jdk/rmi
52. I. Tatarinov, S. D. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, C. Zhang. Storing and Querying Ordered XML Using a Relational Database System. In Proc. of the ACM SIGMOD Int'l Conf. on Management of Data, pp. 204--215, Madison, WI, 2002.
53. R. J. Walker, G. C. Murphy. Implicit Context: Easing Software Evolution and Reuse. In Proc. 8th ACM SIGSOFT Int'l Symp. on Foundations of Software Engineering, pp. 69--78, San Diego CA, 2000.
54. M. Weiser. The Computer for the 21st Century. Scientific American, 265(3):94--104, Sept. 1991.
55. XML-RPC Home Page. http://www.xmlrpc.com.
56. World Wide Web Consortium (W3C). Extensible Markup Language (XML) 1.0 (Second Edition). T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, eds. W3C Recommendation. 6 October 2000. http://www.w3.org/TR/REC-xml+
57. World Wide Web Consortium (W3C). Web Services Architecture. W3C Working Draft, August 2003. http://www.w3.org/TR/ws-arch+
58. World Wide Web Consortium (W3C). XML Path Language (XPath), Version 1.0. J. Clark and S. DeRose, eds. W3C Recommendation. Nov. 1999. http://www.w3.org/TR/xpath+
59. World Wide Web Consortium (W3C). XML Schema. W3C Recommendation. May 2001. http://www.w3c.org/XML/Schema
60. World Wide Web Consortium (W3C). XQuery: A Query Language for XML. W3C Working Draft, June 2001. http://www.w3.org/TR/xquery
61. A. M. Zaremski, J. M. Wing. Signature Matching: A Tool for Reusing Software Libraries. ACM Trans. on Software Engineering and Methodology, 4(2):146--170, Apr. 1995.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

      • Language types

        • Object oriented languages

  • Software organization and properties

    • Extra-functional properties

      • Interoperability