Article

Is Structural Subtyping Useful? An Empirical Study

Authors:

Donna Malayeri,

Jonathan AldrichAuthors Info & Claims

ESOP '09: Proceedings of the 18th European Symposium on Programming Languages and Systems: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

Pages 95 - 111

https://doi.org/10.1007/978-3-642-00590-9_8

Published: 28 March 2009 Publication History

Abstract

Structural subtyping is popular in research languages, but all mainstream object-oriented languages use nominal subtyping. Since languages with structural subtyping are not in widespread use, the empirical questions of whether and how structural subtyping is useful have thus far remained unanswered. This study aims to provide answers to these questions. We identified several criteria that are indicators that nominally typed programs could benefit from structural subtyping, and performed automated and manual analyses of open-source Java programs based on these criteria. Our results suggest that these programs could indeed be improved with the addition of structural subtyping. We hope this study will provide guidance for language designers who are considering use of this subtyping discipline.

References

[1]

Amadio, R., Cardelli, L.: Subtyping recursive types. ACM TOPLAS 15(4) (1993).

[2]

Baldi, P., Lopes, C., Linstead, E., Bajracharya, S.: A theory of aspects as latent topics. In: OOPSLA (2008).

[3]

Bloch, J.: Effective Java, 2nd edn. Addison-Wesley, Reading (2008).

[4]

Boyland, J., Castagna, G.: Parasitic methods: an implementation of multi-methods for Java. In: OOPSLA 1997, pp. 66-76 (1997).

[5]

Bracha, G., Griswold, D.: Strongtalk: typechecking Smalltalk in a production environment. In: OOPSLA 1993, pp. 215-230 (1993).

[6]

Bruce, K., Schuett, A., van Gent, R., Fiech, A.: PolyTOIL: A type-safe polymorphic objectoriented language. ACM Trans. Program. Lang. Syst. 25(2), 225-290 (2003).

[7]

Cardelli, L.: Structural subtyping and the notion of power type. In: POPL 1988 (1988).

[8]

Chalin, P., James, P.: Non-null references by default in Java: Alleviating the nullity annotation burden. In: Ernst, E. (ed.) ECOOP 2007. LNCS, vol. 4609, pp. 227-247. Springer, Heidelberg (2007).

[9]

Chambers, C.: Object-oriented multi-methods in Cecil. In: Lehrmann Madsen, O. (ed.) ECOOP 1992. LNCS, vol. 615, pp. 33-56. Springer, Heidelberg (1992).

[10]

Clifton, C., Millstein, T., Leavens, G., Chambers, C.: MultiJava: Design rationale, compiler implementation, and applications. ACM TOPLAS 28(3), 517-575 (2006).

[11]

Fisher, K., Reppy, J.: The design of a class mechanism for Moby. In: PLDI (1999).

[12]

Forster, F.: Cost and benefit of rigorous decoupling with context-specific interfaces. In: PPPJ 2006, pp. 23-30 (2006).

[13]

Gil, J., Maman, I.: Micro patterns in Java code. In: OOPSLA 2005, pp. 97-116 (2005).

[14]

Gil, J., Maman, I.: Whiteoak: Introducing structural typing into Java. In: OOPSLA (2008).

[15]

Leroy, X., Doligez, D., Garrigue, J., Rémy, D., Vouillon, J.: The Objective Caml system, release 3.10 (2007), http://caml.inria.fr/pub/docs/manual-ocaml).

[16]

Magnusson, B.: Code reuse considered harmful. Journal of Object-Oriented Programming 4(3) (November 1991).

[17]

Malayeri, D., Aldrich, J.: Integrating nominal and structural subtyping. In: Vitek, J. (ed.) ECOOP 2008. LNCS, vol. 5142, pp. 260-284. Springer, Heidelberg (2008).

[18]

Malayeri, D., Aldrich, J.: Is structural subtyping useful? An empirical study. Technical Report CMU-CS-09-100, School of Computer Science, Carnegie Mellon University (January 2009).

[19]

Sun Microsystems. Java collections API design FAQ (2003), http://java.sun.com/j2se/1.4.2/docs/guide/collections/designfaq.html).

[20]

Millstein, T., Chambers, C.: Modular statically typed multimethods. Inf. Comput. 175(1), 76-118 (2002).

[21]

Muschevici, R., Potanin, A., Tempero, E., Noble, J.:Multiple dispatch in practice. In: OOPSLA 2008 (October 2008).

[22]

Musser, D., Stepanov, A.: Generic programming. In: Gianni, P. (ed.) An Optimized Translation Process and Its Application to ALGOL 68. LNCS, vol. 38, pp. 13-25. Springer, Heidelberg (1989).

[23]

Pierce, B.: Types and Programming Languages. MIT Press, Cambridge (2002).

[24]

Steimann, F.: The infer type refactoring and its use for interface-based programming. Journal of Object Technology 6(2) (2007).

[25]

Tempero, E.D., Noble, J., Melton, H.: How do Java programs use inheritance? An empirical study of inheritance in Java software. In: Vitek, J. (ed.) ECOOP 2008. LNCS, vol. 5142, pp. 667-691. Springer, Heidelberg (2008).

Cited By

Coblenz MAldrich JMyers BSunshine JBoix EGabriel R(2018)Interdisciplinary programming language designProceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3276954.3276965(133-146)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276954.3276965
Jones TPearce D(2016)A Mechanical Soundness Proof for Subtyping Over Recursive TypesProceedings of the 18th Workshop on Formal Techniques for Java-like Programs10.1145/2955811.2955812(1-6)Online publication date: 17-Jul-2016
https://dl.acm.org/doi/10.1145/2955811.2955812
Callaú ORobbes RTanter ÉRöthlisberger DBergel A(2014)On the use of type predicates in object-oriented softwareACM SIGPLAN Notices10.1145/2775052.266109150:2(135-146)Online publication date: 14-Oct-2014
https://dl.acm.org/doi/10.1145/2775052.2661091
Show More Cited By

Recommendations

Combining structural subtyping and external dispatch
OOPSLA '07: Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion

By-name subtyping (or user-defined subtyping) and structural subtyping each have their own strengths and weaknesses. By-name subtyping allows programmers to explicitly express design intent, and, when types are associated with run time tags, enables run-...
Structural Subtyping as Parametric Polymorphism

Structural subtyping and parametric polymorphism provide similar flexibility and reusability to programmers. For example, both features enable the programmer to provide a wider record as an argument to a function that expects a narrower one. However, ...
Parametric Subtyping for Structural Parametric Polymorphism

We study the interaction of structural subtyping with parametric polymorphism and recursively defined type constructors. Although structural subtyping is undecidable in this setting, we describe a notion of parametricity for type constructors and then ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESOP '09: Proceedings of the 18th European Symposium on Programming Languages and Systems: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009

March 2009

409 pages

ISBN:9783642005893

Editor:
Giuseppe Castagna
CNRS, Université Denis Diderot, Paris 7, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Coblenz MAldrich JMyers BSunshine JBoix EGabriel R(2018)Interdisciplinary programming language designProceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3276954.3276965(133-146)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276954.3276965
Jones TPearce D(2016)A Mechanical Soundness Proof for Subtyping Over Recursive TypesProceedings of the 18th Workshop on Formal Techniques for Java-like Programs10.1145/2955811.2955812(1-6)Online publication date: 17-Jul-2016
https://dl.acm.org/doi/10.1145/2955811.2955812
Callaú ORobbes RTanter ÉRöthlisberger DBergel A(2014)On the use of type predicates in object-oriented softwareACM SIGPLAN Notices10.1145/2775052.266109150:2(135-146)Online publication date: 14-Oct-2014
https://dl.acm.org/doi/10.1145/2775052.2661091
Callaú ORobbes RTanter ÉRöthlisberger DBergel ABlack ATratt L(2014)On the use of type predicates in object-oriented softwareProceedings of the 10th ACM Symposium on Dynamic languages10.1145/2661088.2661091(135-146)Online publication date: 20-Oct-2014
https://dl.acm.org/doi/10.1145/2661088.2661091
Allende EFabry JTanter É(2013)Cast insertion strategies for gradually-typed objectsACM SIGPLAN Notices10.1145/2578856.250817149:2(27-36)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2578856.2508171
Allende EFabry JTanter ÉHosking AEugster PBolz C(2013)Cast insertion strategies for gradually-typed objectsProceedings of the 9th symposium on Dynamic languages10.1145/2508168.2508171(27-36)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2508168.2508171
Nistor LKurilova DBalzer SChung BPotanin AAldrich J(2013)WyvernProceedings of the 5th Workshop on MechAnisms for SPEcialization, Generalization and inHerItance10.1145/2489828.2489830(9-16)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1145/2489828.2489830
Callaú ORobbes RTanter ÉRöthlisberger Dvan Deursen AXie TZimmermann T(2011)How developers use the dynamic features of programming languagesProceedings of the 8th Working Conference on Mining Software Repositories10.1145/1985441.1985448(23-32)Online publication date: 21-May-2011
https://dl.acm.org/doi/10.1145/1985441.1985448
Wehr SThiemann P(2011)JavaGIACM Transactions on Programming Languages and Systems10.1145/1985342.198534333:4(1-83)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1145/1985342.1985343
Harrison WBorba PChiba S(2011)Modularity for the changing meaning of changingProceedings of the tenth international conference on Aspect-oriented software development10.1145/1960275.1960313(301-312)Online publication date: 21-Mar-2011
https://dl.acm.org/doi/10.1145/1960275.1960313

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents