On Variance-Based Subtyping for Parametric Types | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Variance-Based Subtyping for Parametric Types

  • Conference paper
  • First Online:
ECOOP 2002 — Object-Oriented Programming (ECOOP 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2374))

Included in the following conference series:

Abstract

We develop the mechanism of variant parametric types, inspired by structural virtual types by Thorup and Torgersen, as a means to enhance synergy between parametric and inclusive polymorphism in object-oriented languages. Variant parametric types are used to control both subtyping between different instantiations of one generic class and the visibility of their fields and methods. On one hand, one parametric class can be used as either covariant, contravariant, or bivariant by attaching a variance annotation—which can be either +, -, or *, respectively—to a type argument. On the other hand, the type system prohibits certain method/field accesses through variant parametric types, when those accesses can otherwise make the program unsafe. By exploiting variant parametric types, a programmer can write generic code abstractions working on a wide range of parametric types in a safe way. For instance, a method that only reads the elements of a container of strings can be easily modified so that it can accept containers of any subtype of string.

The theoretical issues are studied by extending Featherweight GJ—an existing core calculus for Java with generics—with variant parametric types. By exploiting the intuitive connection to bounded existential types, we develop a sound type system for the extended calculus.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ole Agesen, Stephen N. Freund, and John C. Mitchell. Adding type parameterization to the Java language. In Proc. of ACM OOPSLA, pages 49–65, Atlanta, GA, October 1997.

    Google Scholar 

  2. Pierre America and Frank van der Linden. A parallel object-oriented language with inheritance and subtyping. In Proc. of OOPSLA/ECOOP, pages 161–168, Ottawa, Canada, October 1990.

    Google Scholar 

  3. Gilad Bracha. The Strongtalk type system for Smalltalk. In Proc. of the OOP SLA96 Workshop on Extending the Smalltalk Language, 1996. Also available electronically through http://java.sun.com/people/gbracha/nwst.html.

  4. Gilad Bracha and David Griswold. Strongtalk: Typechecking Smalltalk in a production environment. In Proc. of ACM OOPSLA, pages 215–230, Washington, DC, October 1993.

    Google Scholar 

  5. Gilad Bracha, Martin Odersky, David Stoutamire, and Philip Wadler. Making the future safe for the past: Adding genericity to the Java programming language. In Proc. of ACM OOPSLA, pages 183–200, Vancouver, BC, October 1998.

    Google Scholar 

  6. Kim B. Bruce. A paradigmatic object-oriented programming language: Design, static typing and semantics. Journal of Functional Programming, 4(2), April 1994. Preliminary version in POPL 1993, under the title “Safe type checking in a statically typed object-oriented programming language”.

    Google Scholar 

  7. Kim B. Bruce, Martin Odersky, and Philip Wadler. A statically safe alternative to virtual types. In Proc. of the 12th ECOOP, LNCS 1445, pages 523–549, Brussels, Belgium, July 1998. Springer-Verlag.

    Google Scholar 

  8. Kim B. Bruce, Leaf Petersen, and Adrian Fiech. Subtyping is not a good “match” for object-oriented languages. In Proc. of the 11th European Conference on Object-Oriented Programming (ECOOP’97), LNCS 1241, pages 104–127, Jyväskylä, Finland, June 1997. Springer-Verlag.

    Google Scholar 

  9. Kim B. Bruce, Angela Schuett, and Robert van Gent. PolyTOIL: A type-safe polymorphic object-oriented language. In W. Olthoff, editor, Proc. of ECOOP, LNCS 952, pages 27–51, Aarhus, Denmark, August 1995. Springer-Verlag.

    Google Scholar 

  10. Kim B. Bruce and Joseph C. Vanderwaart. Semantics-driven language design: Statically type-safe virtual types in object-oriented languages. In Proc. of the 15th Conference on the Mathematical Foundations of Programming Semantics (MFPS XV), volume 20 of Electronic Notes in Theoretical Computer Science, New Orleans, LA, April 1999. Elsevier. Available through http://www.elsevier.nl/locate/entcs/volume20.html.

  11. Peter Canning, William Cook, Walter Hill, Walter Olthoff, and John Mitchell. F-bounded quantification for object-oriented programming. In Proc. of ACM FPCA, pages 273–280, September 1989.

    Google Scholar 

  12. Luca Cardelli and Peter Wegner. On understanding types, data abstraction, and polymorphism. Computing Surveys, 17(4):471–522, December 1985.

    Google Scholar 

  13. Robert Cartwright and Guy L. Steele Jr. Compatible genericity with run-time types for the Java programming language. In Proc. of ACM OOPSLA, pages 201–215, Vancouver, BC, October 1998.

    Google Scholar 

  14. William Cook. A proposal for making Eiffel type-safe. In Proc. of the 3rd ECOOP, pages 57–70, Nottingham, England, July 1989. Cambridge University Press.

    Google Scholar 

  15. Mark Day, Robert Gruber, Barbara Liskov, and Andrew C. Meyers. Subtypes vs. where clauses: Constraining parametric polymorphism. In Proc. of ACM OOPSLA, pages 156–168, Austin, TX, October 1995.

    Google Scholar 

  16. Interactive Software Engineering. An Eiffel tutorial. Available through http://www.eiffel.com/doc/online/eiffel50/intro/language/tutorial-00.html, 2001.

  17. Giorgio Ghelli and Benjamin Pierce. Bounded existentials and minimal typing. Theoretical Computer Science, 193:75–96, 1998.

    Article  MathSciNet  MATH  Google Scholar 

  18. Robert Harper and Mark Lillibridge. A type-theoretic approach to higher-order modules with sharing. In Proc. of ACM POPL, pages 123–137, Portland, OR, January 1994.

    Google Scholar 

  19. Atsushi Igarashi and Benjamin C. Pierce. Foundations for virtual types. Information and Computation, 2002. An earlier version in Proc. of the 13th ECOOP, Springer LNCS 1628, pages 161–185, 1999.

    Google Scholar 

  20. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java: A minimal core calculus for Java and GJ. ACM Transactions on Programming Languages and Systems, 23(3):396–450, May 2001. A preliminary summary appeared in proc. of OOPSLA’ 99, pages 132-146, Denver, CO, October 1999.

    Google Scholar 

  21. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. A recipe for raw types. In Informal Proc. of the 8th International Workshop on Foundations of Object-Oriented Languages (FOOL8), London, England, January 2001. Available through http://www.cs.williams.edu/~kim/FOOL/FOOL8.html.

  22. Xavier Leroy. Manifest types, modules and separate compilation. In Proc. of ACM POPL, pages 109–122, Portland, OR, January 1994.

    Google Scholar 

  23. Chu-Cheow Lim and A. Stolcke. Sather language design and performance evaluation. Technical Report TR-91-034, International Computer Science Institute, University of California, Berkeley, May 1991.

    Google Scholar 

  24. Ole Lehrmann Madsen and Birger Møller-Pedersen. Virtual classes: A powerful mechanism in object-oriented programming. In Proc. of ACM OOPSLA, pages 397–406, New Orleans, LA, 1989.

    Google Scholar 

  25. Andrew C. Meyers, Joseph A. Bank, and Barbara Liskov. Parameterized types for Java. In Proc. of ACM POPL, pages 132–145. ACM, 1997.

    Google Scholar 

  26. Microsoft Corporation. The.NET Common Language Runtime. Information available through http://msdn.microsoft.com/net/, 2001.

  27. John C. Mitchell and Gordon D. Plotkin. Abstract types have existential types. ACM Transactions on Programming Languages and Systems, 10(3):470–502, 1988. Preliminary version appeared in Proc. of the 12th ACM POPL, 1985.

    Article  Google Scholar 

  28. Olivier Raynaund and Eric Thierry. A quasi optimal bit-vector encoding of tree hierarchies, application to efficient type inclusion tests. In Proc. of the 15th ECOOP, LNCS 2072, pages 165–180. Springer-Verlag, June 2001.

    Google Scholar 

  29. Sun Microsystems. Adding generic types to the Java programming language. Java Specification Request JSR-000014, http://jcp.org/jsr/detail/014.jsp, 1998.

  30. Don Syme and Andrew Kennedy. Design and implementation of generics for the.NET Common Language Runtime. In Proc. of ACM PLDI. ACM, June 2001.

    Google Scholar 

  31. Clemens Szyperski, Stephen Omohundro, and Stephan Murer. Engineering a programming language: The type and class system of Sather. In Jurg Gutknecht, editor, Programming Languages and System Architectures, LNCS 782, pages 208–227. Springer-Verlag, November 1993.

    Chapter  Google Scholar 

  32. Kresten Krab Thorup. Genericity in Java with virtual types. In Proc. of the 11th ECOOP, LNCS 1241, pages 444–471, Jyväskylä, Finland, June 1997. Springer-Verlag.

    Google Scholar 

  33. Kresten Krab Thorup and Mads Torgersen. Unifying genericity: Combining the benefits of virtual types and parameterized classes. In Proc. of the 13th ECOOP, LNCS 1628, pages 186–204, Lisbon, Portugal, June 1999. Springer-Verlag.

    Google Scholar 

  34. Mads Torgersen. Virtual types are statically safe. In Proc. of the 5th Workshop on Foundations of Object-Oriented Languages (FOOL), San Diego, CA, January 1998. Available through http://www.cs.williams.edu/~kim/FOOL/FOOL5.html.

  35. Mirko Viroli. Parametric polymorphism in Java: an efficient implementation for parametric methods. In Proc. of the ACM Symposium on Applied Computing, pages 610–619, March 2001.

    Google Scholar 

  36. Mirko Viroli and Antonio Natali. Parametric polymorphism in Java: an approach to translation based on reflective features. In Proc. of ACM OOPSLA, pages 146–165, Oct 2000.

    Google Scholar 

  37. Andrew K. Wright and Matthias Felleisen. A syntactic approach to type soundness. Information and Computation, 115(1):38–94, November 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan

    Atsushi Igarashi

  2. DEIS, Università degli Studi di Bologna, via Rasi e Spinelli 176, 47023, Cesena, FC, Italy

    Mirko Viroli

Authors
  1. Atsushi Igarashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mirko Viroli
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Lund, Box 118, 211 00, Lund, Sweden

    Boris Magnusson

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Igarashi, A., Viroli, M. (2002). On Variance-Based Subtyping for Parametric Types. In: Magnusson, B. (eds) ECOOP 2002 — Object-Oriented Programming. ECOOP 2002. Lecture Notes in Computer Science, vol 2374. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47993-7_19

Download citation

  • DOI: https://doi.org/10.1007/3-540-47993-7_19

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43759-8

  • Online ISBN: 978-3-540-47993-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation