Document Open Access Logo

Type Inference for Place-Oblivious Objects

Authors Riyaz Haque, Jens Palsberg

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2015.371.pdf
  • Filesize: 0.54 MB
  • 25 pages

Document Identifiers

Author Details

Riyaz Haque
Jens Palsberg

Cite AsGet BibTex

Riyaz Haque and Jens Palsberg. Type Inference for Place-Oblivious Objects. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 371-395, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ECOOP.2015.371

Abstract

In a distributed system, access to local data is much faster than access to remote data. As a help to programmers, some languages require every access to be local. A program in those languages can access remote data via first a shift of the place of computation and then a local access. To enforce this discipline, researchers have presented type systems that determine whether every access is local and every place shift is appropriate. However, those type systems fall short of handling a common programming pattern that we call place-oblivious objects. Such objects safely access other objects without knowledge of their place. In response, we present the first type system for place-oblivious objects along with an efficient inference algorithm and a proof that inference is P-complete. Our example language extends the Abadi-Cardelli object calculus with place shift and existential types, and our implementation has inferred types for some microbenchmarks.
Keywords
  • parallelism
  • locality
  • types

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martín Abadi and Luca Cardelli. A Theory of Objects. Springer-Verlag, 1996. Google Scholar
  2. Shivali Agarwal, RajKishore Barik, V. Nandivada, Rudrapatna Shyamasundar, and Pradeep Varma. Static detection of place locality and elimination of runtime checks. In G. Ramalingam, editor, Programming Languages and Systems, volume 5356 of Lecture Notes in Computer Science, pages 53-74. Springer Berlin / Heidelberg, 2008. Google Scholar
  3. Roberto M. Amadio, Gérard Boudol, and Cédric Lhoussaine. The receptive distributed π-calculus. ACM Trans. Program. Lang. Syst., 25(5):549-577, September 2003. Google Scholar
  4. Roberto M. Amadio, Gerard Boudol, Cedric Lhoussaine, and Roberto M. Amadio. The receptive distributed π-calculus, 1999. Google Scholar
  5. Satish Chandra, Vijay Saraswat, Vivek Sarkar, and Rastislav Bodik. Type inference for locality analysis of distributed data structures. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, PPoPP'08, pages 11-22, New York, NY, USA, 2008. ACM. Google Scholar
  6. Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. X10: an object-oriented approach to non-uniform cluster computing. In Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA'05, pages 519-538, New York, NY, USA, 2005. ACM. Google Scholar
  7. Cedric Fournet and Georges Gonthier. The join calculus: A language for distributed mobile programming. In Gilles Barthe, Peter Dybjer, Luís Pinto, and João Saraiva, editors, Applied Semantics, volume 2395 of Lecture Notes in Computer Science, pages 268-332. Springer Berlin Heidelberg, 2002. Google Scholar
  8. Andrew D. Gordon and Paul D. Hankin. A concurrent object calculus: Reduction and typing, 1998. Google Scholar
  9. Riyaz Haque and Jens Palsberg. Type inference for place-oblivious objects. Full version of a paper with the same title in ECOOP 2015, URL: http://www.cs.ucla.edu/~palsberg/paper/ecoop15full.pdf.
  10. Fritz Henglein. Breaking through the n³ barrier: Faster object type inference. In The Fourth International Workshop on Foundations of Object-Oriented Languages, 1997. Google Scholar
  11. Matthew Hennessy and James Riely. Resource access control in systems of mobile agents. Information and Computation, 173:2002, 1998. Google Scholar
  12. Paul N. Hilfinger, Dan Oscar Bonachea, Kaushik Datta, David Gay, Susan L. Graham, Benjamin Robert Liblit, Geoffrey Pike, Jimmy Zhigang Su, and Katherine A. Yelick. Titanium language reference manual, version 2.19. Technical Report UCB/EECS-2005-15, EECS Department, University of California, Berkeley, Nov 2005. Google Scholar
  13. A. S. A. Jeffrey. A distributed object calculus. In Proc. Foundations of Object Oriented Languages, 2000. Google Scholar
  14. Jonathan K. Lee and Jens Palsberg. Featherweight X10: a core calculus for async-finish parallelism. In Proceedings of PPOPP'10, 15th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, Bangalore, India, January 2010. Google Scholar
  15. Cedric Lhoussaine. Type inference for a distributed π-calculus. In Pierpaolo Degano, editor, Programming Languages and Systems, volume 2618 of Lecture Notes in Computer Science, pages 253-268. Springer Berlin Heidelberg, 2003. Google Scholar
  16. Ben Liblit and Alexander Aiken. Type systems for distributed data structures. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL, pages 199-213, 2000. Google Scholar
  17. David McAllester. On the complexity analysis of static analyses. Journal of the ACM, 49(4):512-537, 2002. Google Scholar
  18. Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, i. Inf. Comput., 100(1):1-40, September 1992. Google Scholar
  19. Greg Morrisett, David Walker, Karl Crary, and Neal Glew. From System F to typed assembly language. ACM Trans. Program. Lang. Syst., 21(3):527-568, May 1999. Google Scholar
  20. Jens Palsberg. Efficient inference of object types. Information and Computation, 123(2):198-209, 1995. Preliminary version in Proceedings of LICS'94, Ninth Annual IEEE Symposium on Logic in Computer Science, pages 186-195, Paris, France, July 1994. Google Scholar
  21. Benjamin C. Pierce. Types and programming languages. MIT Press, Cambridge, MA, USA, 2002. Google Scholar
  22. Benjamin C. Pierce. Advanced Topics in Types and Programming Languages. The MIT Press, Cambridge, MA, USA, 2004. Google Scholar
  23. Vijay Saraswat, Bard Bloom, Igor Peshansky, Olivier Tardieu, and David Grove. X10 language specification. Technical report, IBM, January 2012. Google Scholar
  24. Peter Sewell. Global/local subtyping and capability inference for a distributed π-calculus. In In Proceedings of ICALP'98, LNCS 1443, pages 695-706. Springer-Verlag, 1998. Google Scholar
  25. Andrew K. Wright and Matthias Felleisen. A syntactic approach to type soundness. Information and Computation, 115:38-94, 1992. Google Scholar
  26. Katherine A. Yelick, Luigi Semenzato, Geoff Pike, Carleton Miyamoto, Ben Liblit, Arvind Krishnamurthy, Paul N. Hilfinger, Susan L. Graham, David Gay, Phillip Colella, and Alexander Aiken. Titanium: A high-performance Java dialect. Concurrency - Practice and Experience, 10(11-13):825-836, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact