Multiple ownership

ABSTRACT

Existing ownership type systems require objects to have precisely one primary owner, organizing the heap into an ownership tree. Unfortunately, a tree structure is too restrictive for many programs, and prevents many common design patterns where multiple objects interact.

Multiple Ownership is an ownership type system where objects can have more than one owner, and the resulting ownership structure forms a DAG. We give a straightforward model for multiple ownership, focusing in particular on how multiple ownership can support a powerful effects system that determines when two computations interfere-in spite of the DAG structure.

We present a core programming language MOJO, Multiple ownership for Java-like Objects, including a type and effects system, and soundness proof. In comparison to other systems, MOJO imposes absolutely no restrictions on pointers, modifications or programs' structure, but in spite of this, MOJO's effects can be used to reason about or describe programs' behaviour.

REFERENCES

• 1: Marwan Abi-Antoun and Jonathan Aldrich. Ownership domains in the real world. In IWACO workshop at ECOOP, 2007.
• 2: Jonathan Aldrich and Craig Chambers. Ownership domains: Separating aliasing policy from mechanism. In ECOOP, 2004.
• 3: Christopher Alexander. A city is not a tree. Design, (206), 1966.
• 4: Paulo Sérgio Almeida. Balloon types: Controlling sharing of state in data types. In ECOOP, 1997.
• 5: Chris Andreae, Yvonne Coady, Celina Gibbs, James Noble, Jan Vitek, and Tian Zhao. Scoped types and aspects for real-time java. In ECOOP, 2006.
• 6: Gareth Baxter , Marcus Frean , James Noble , Mark Rickerby , Hayden Smith , Matt Visser , Hayden Melton , Ewan Tempero, Understanding the shape of Java software, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 7: Jan Vitek , Boris Bokowski, Confined types, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.82-96, November 01-05, 1999, Denver, Colorado, United States
• 8: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 9: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 10: John Tang Boyland , William Retert, Connecting effects and uniqueness with adoption, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.283-295, January 12-14, 2005, Long Beach, California, USA
• 11: Nicholas Cameron, Erik Ernst, and Sophia Drossopoulou. Towards an existential types model for Java with wildcards. In FTfJP workshop at ECOOP, 2007.
• 12: David Gerard Clarke, Object ownership and containment, University of New South Wales, New South Wales, Australia, 2003
• 13: Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 14: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 15: Curtis Charles Clifton , Gary T. Leavens, A design discipline and language features for modular reasoning in aspect-oriented programs, Iowa State University, Ames, IA, 2005
• 16: Curtis Clifton, Gary T. Leavens, and James Noble. Ownership and effects for more effective reasoning about aspects. In ECOOP, 2007.
• 17: Gilles Deleuze and Félix Guattari. A Thousand Plateaus: Capitalism and Schizophrenia. U. Minnesota, 1987.
• 18: Werner Dietl, Sophia Drossopoulou, and Peter Müller. Generic universe types. In ECOOP, 2007.
• 19: Sophia Drossopoulou. The benefits of putting objects into boxes. ESOP, 2006. Invited Talk.
• 20: Cormac Flanagan, Stephen N. Freund, and Marina Lifshin. Type inference for atomicity. In TLDI, 2005.
• 21: Joseph (Yossi) Gil , John Howse , Stuart Kent, Towards a Formalization of Constraint Diagrams, Proceedings of the IEEE 2001 Symposia on Human Centric Computing Languages and Environments (HCC'01), p.72, September 05-07, 2001
• 22: Aaron Greenhouse , John Boyland, An Object-Oriented Effects System, Proceedings of the 13th European Conference on Object-Oriented Programming, p.205-229, June 14-18, 1999
• 23: Christian Grothoff , Jens Palsberg , Jan Vitek, Encapsulating objects with confined types, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.241-255, October 14-18, 2001, Tampa Bay, FL, USA
• 24: Ralf Hinze. The Fun of Programming, chapter Fun with Phantom Types, pages 245--262. Palgrave Macmillan, 2003.
• 25: John Hogg, Islands: aliasing protection in object-oriented languages, Conference proceedings on Object-oriented programming systems, languages, and applications, p.271-285, October 06-11, 1991, Phoenix, Arizona, United States
• 26: Atshushi Igarashi , Benjamin Pierce , Philip Wadler, Featherwieght Java: a minimal core calculus for Java and GJ, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.132-146, November 01-05, 1999, Denver, Colorado, United States
• 27: Daniel Jackson, Aspect: detecting bugs with abstract dependences, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.2, p.109-145, April 1995 [doi>10.1145/210134.210135]
• 28: Neel Krishnaswami , Jonathan Aldrich, Permission-based ownership: encapsulating state in higher-order typed languages, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 29: K. R. M. Leino and P. Müller. Object invariants in dynamic contexts. In ECOOP, 2004.
• 30: K. Rustan M. Leino, Data groups: specifying the modification of extended state, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.144-153, October 18-22, 1998, Vancouver, British Columbia, Canada
• 31: Yi Lu , John Potter, Protecting representation with effect encapsulation, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.359-371, January 11-13, 2006, Charleston, South Carolina, USA
• 32: Yi Lu and John Potter. Object invariants and effects. In ECOOP, 2007.
• 33: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• 34: Nick Mitchell. The runtime structure of object ownership. In ECOOP, 2006.
• 35: Peter Müller, Modular specification and verification of object-oriented programs, Springer-Verlag New York, Inc., New York, NY, 2002
• 36: Peter Müller. Reasoning about object structures using ownership. In Verified Software: Theories, Tools, Experiments, LNCS. Springer-Verlag, 2007.
• 37: James Noble, Robert Biddle, Ewan Tempero, Alex Potanin, and Dave Clarke. Towards a model of encapsulation. In IWACO workshop at ECOOP, 2003.
• 38: James Noble , Jan Vitek , John Potter, Flexible Alias Protection, Proceedings of the 12th European Conference on Object-Oriented Programming, p.158-185, July 20-24, 1998
• 39: Martin Odersky , Matthias Zenger, Scalable component abstractions, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 40: Matthew Parkinson , Gavin Bierman, Separation logic and abstraction, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-258, January 12-14, 2005, Long Beach, California, USA
• 41: Alex Potanin. Generic Ownership-A Practical Approach to Ownership and Confinement in OO Programming Languages. PhD thesis, 2007.
• 42: Alex Potanin , James Noble , Dave Clarke , Robert Biddle, Generic ownership for generic Java, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 43: Alex Potanin , James Noble , Marcus Frean , Robert Biddle, Scale-free geometry in OO programs, Communications of the ACM, v.48 n.5, p.99-103, May 2005 [doi>10.1145/1060710.1060716]
• 44: John C. Reynolds, Syntactic control of interference, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-46, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512766]
• 45: Frederick Smith , David Walker , J. Gregory Morrisett, Alias Types, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.366-381, April 02, 2000
• 46: Matthew Smith. Effects system for ownership domains. In FTfJP workshop at ECOOP, 2005.
• 47: Matthew Smith. A Model of Effects with an application to Ownership Types. PhD thesis, Imperial College, 2007.
• 48: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 49: Mads Torgersen , Christian Plesner Hansen , Erik Ernst , Peter von der Ahé , Gilad Bracha , Neal Gafter, Adding wildcards to the Java programming language, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968162]
• 50: Tobias Wrigstad and Dave Clarke. Existential owners for ownership types. JOT, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages, Theory

Keywords:
effects, ownership types, type and effect systems