Traits: A mechanism for fine-grained reuse

Abstract

Inheritance is well-known and accepted as a mechanism for reuse in object-oriented languages. Unfortunately, due to the coarse granularity of inheritance, it may be difficult to decompose an application into an optimal class hierarchy that maximizes software reuse. Existing schemes based on single inheritance, multiple inheritance, or mixins, all pose numerous problems for reuse. To overcome these problems we propose traits, pure units of reuse consisting only of methods. We develop a formal model of traits that establishes how traits can be composed, either to form other traits, or to form classes. We also outline an experimental validation in which we apply traits to refactor a nontrivial application into composable units.

References

1. America, P. and van der Linden, F. 1990. A parallel object-oriented language with inheritance and subtyping. In Proceedings OOPSLA/ECOOP '90, ACM SIGPLAN Notices. Vol. 25. 161--168.]]
2. Ancona, D., Lagorio, G., and Zucca, E. 2000. Jam---a smooth extension of Java with mixins. In ECOOP 2000. Number 1850 in Lecture Notes in Computer Science. 145--178.]]
3. Bak, L., Grarup, G. B. S., Griesemer, R., Griswold, D., and Hölzle, U. 2002. Mixins in Strongtalk. In ECOOP '02 Workshop on Inheritance.]]
4. Barrett, K., Cassels, B., Haahr, P., Moon, D. A., Playford, K., and Withington, P. T. 1996. A monotonic superclass linearization for dylan. In Proceedings OOPSLA '96, ACM SIGPLAN Notices. 69--82.]]
5. Batory, D. and O'Malley, S. 1992. The design and implementation of hierarchical software systems with reusable components. ACM Trans. Softw. Eng. Meth.]]
6. Batory, D., Sarvela, J. N., and Rauschmayer, A. 2003. Scaling step-wise refinement. In Proceedings of the 25th International Conference on Software Engineering. IEEE Computer Society, 187--197.]]
7. Black, A. P. and Schärli, N. 2004. Traits: Tools and methodology. In Proceedings ICSE 2004. 676--686.]]
8. Black, A. P., Schärli, N., and Ducasse, S. 2003. Applying traits to the Smalltalk collection hierarchy. In Proceedings of OOPSLA'03 (International Conference on Object-Oriented Programming Systems, Languages and Applications). ACM SIGPLAN Notices, Vol. 38. 47--64.]]
9. Bobrow, D. G. and Goldstein, I. P. 1980. Representing design alternatives. In Proceedings of the Conference on Artificial Intelligence and the Simulation of Behavior.]]
10. Bobrow, D. G. and Winograd, T. 1977. An overview of KRL, a knowledge representation language. Cognitive Science 1, 1, 3--46.]]
11. Borning, A. 1981. The programming language aspects of ThingLab, a constraint-oriented simulation laboratory. ACM Trans. Prog. Lang. Syst. 3, 4 (Oct.), 353--387.]]
12. Bouraqadi, N. 2004. Safe metaclass composition using mixin-based inheritance. J. Comput. Lang. Syst. Struct. 30, 1--2 (Apr.), 49--61.]]
13. Bouraqadi-Saadani, N. M. N., Ledoux, T., and Rivard, F. 1998. Safe metaclass programming. In Proceedings OOPSLA '98. 84--96.]]
14. Bracha, G. 1992. The programming language Jigsaw: Mixins, modularity and multiple inheritance. Ph.D. thesis, Dept. of Computer Science, University of Utah.]]
15. Bracha, G. and Cook, W. 1990. Mixin-based inheritance. In Proceedings of OOPSLA/ECOOP '90, ACM SIGPLAN Notices. Vol. 25. 303--311.]]
16. Bracha, G. and Griswold, D. 1993. Strongtalk: Typechecking Smalltalk in a production environment. In Proceedings of OOPSLA '93, ACM SIGPLAN Notices. Vol. 28. 215--230.]]
17. Bruce, K. B., Cardelli, L., Castagna, G., Group, T. H. O., Leavens, G. T., and Pierce, B. 1995. On binary methods. Theory and Practice of Object Systems 1, 3, 221--242.]]
18. Bucci, P., Hollingsworth, J. E., Krone, J., and Weide, B. W. 1994. Part iii: implementing components in RESOLVE. SIGSOFT Softw. Eng. Notes 19, 4, 40--51.]]
19. Cannon, H. I. 1982. Flavors: A non-hierarchical approach to object-oriented programming. Tech. rep., Symbolics Inc.]]
20. Castagna, G. 1995. Covariance and contravariance: conflict without a cause. ACM Trans. Prog. Lang. Syst. 17, 3, 431--447.]]
21. Cointe, P. 1987. Metaclasses are first class: the ObjVlisp model. In Proceedings of OOPSLA '87, ACM SIGPLAN Notices. ACM SIGPLAN Notices, Vol. 22. 156--167.]]
22. Cook, S. 1987. OOPSLA '87 Panel P2: Varieties of inheritance. In OOPSLA '87 Addendum To The Proceedings. ACM Press, 35--40.]]
23. Cook, W., Hill, W., and Canning, P. 1990. Inheritance is not subtyping. In Proceedings of POPL '90. San Francisco. ACM Press, 125--135.]]
24. Cook, W. and Palsberg, J. 1989. A denotational semantics of inheritance and its correctness. In Proceedings of OOPSLA '89. ACM SIGPLAN Notices, Vol. 24. 433--443.]]
25. Cook, W. R. 1992. Interfaces and Specifications for the Smalltalk-80 Collection Classes. In Proceedings of OOPSLA '92 (7th Conference on Object-Oriented Programming Systems, Languages and Applications). Vol. 27. ACM Press, 1--15.]]
26. Curry, G., Baer, L., Lipkie, D., and Lee, B. 1982. TRAITS: an approach to multiple inheritance subclassing. In Proceedings of ACM SIGOA, Newsletter. Vol. 3. Philadelphia.]]
27. Danforth, S. and Forman, I. R. 1994. Derived metaclass in SOM. In Proceedings of TOOLS EUROPE '94. 63--73.]]
28. Dixon, R., McKee, T., Vaughan, M., and Schweizer, P. 1989. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings OOPSLA '89, ACM SIGPLAN Notices. Vol. 24. 211--214.]]
29. Ducasse, S., Schärli, N., and Wuyts, R. 2005. Uniform and safe metaclass composition. J. Comput. Lang. Syst. Struct. 31, 3--4 (May), 143--164.]]
30. Ducournau, R., Habib, M., Huchard, M., and Mugnier, M. 1992. Monotonic conflict resolution mechanisms for inheritance. In Proceedings of OOPSLA '92, ACM SIGPLAN Notices. Vol. 27. 16--24.]]
31. Duggan, D. and Techaubol, C.-C. 2001. Modular mixin-based inheritance for application frameworks. In Proceedings of OOPSLA 2001. 223--240.]]
32. Edwards, S. H., Heym, W. D., Long, T. J., Sitaraman, M., and Weide, B. W. 1994. Part ii: specifying components in RESOLVE. SIGSOFT Softw. Eng. Notes 19, 4, 29--39.]]
33. Flatt, M., Krishnamurthi, S., and Felleisen, M. 1998. Classes and mixins. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 171--183.]]
34. Forman, I. R. and Danforth, S. 1999. Putting Metaclasses to Work: A New Dimension in Object-Oriented Programming. Addison-Wesley.]]
35. Goldberg, A. and Robson, D. 1983. Smalltalk 80: the Language and its Implementation. Addison Wesley, Reading, Mass.]]
36. Goldstein, I. P. and Bobrow, D. G. 1980a. Descriptions for a programming environment. In Proceedings of the First Annual Conference of the National Association for Artificial Intelligence.]]
37. Goldstein, I. P. and Bobrow, D. G. 1980b. Extending object-oriented programming in Smalltalk. In Proceedings of the Lisp Conference. 75--81.]]
38. Goldstein, I. P. and Roberts, R. B. 1977. Nudge, a knowledge-based scheduling program. In Proceedings of the Fifth International Joint Conference on Artifical Intelligence. 257--263.]]
39. Graube, N. 1989. Metaclass compatibility. In Proceedings of OOPSLA '89, ACM SIGPLAN Notices. Vol. 24. 305--316.]]
40. Guttag, J. V., Horning, J. J., and Wing, J. M. 1985. The Larch family of specification languages. IEEE Trans. Softw. Eng. 2, 5 (Sept.), 24--36.]]
41. Harrison, W. and Ossher, H. 1993. Subject-oriented programming (a critique of pure objects). In Proceedings of OOPSLA '93, ACM SIGPLAN Notices. Vol. 28. 411--428.]]
42. Hollingsworth, J. E. 1992. Software component design-for-reuse: A language independent discipline applied to ada. Ph.D. thesis, Dept. of Computer & Information Science, The Ohio State University, Columbus, OH.]]
43. Hollingsworth, J. E., Blankenship, L., and Weide, B. W. 2000. Experience report: Using RESOLVE/C++ for commercial software. In SIGSOFT '00/FSE-8: Proceedings of the 8th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM Press, 11--19.]]
44. Hollingsworth, J. E., Sreerama, S., Weide, B. W., and Zhupanov, S. 1994. Part iv: RESOLVE components in Ada and C++. SIGSOFT Softw. Eng. Notes 19, 4, 52--63.]]
45. Ingalls, D. 1976. The Smalltalk-76 programming system design and implementation. In POPL'76, Principles of Programming Languages. ACM Press, 9--16.]]
46. Ingalls, D., Kaehler, T., Maloney, J., Wallace, S., and Kay, A. 1997. Back to the future: The story of Squeak, A practical Smalltalk written in itself. In Proceedings of OOPSLA '97, ACM SIG-PLAN Notices. ACM Press, 318--326.]]
47. Järvi, J., Powell, G., and Lumsdaine, A. 2003. The lambda library: unnamed functions in C++. Softw. Pract. Exper. 33, 3, 259--291.]]
48. Keene, S. E. 1989. Object-Oriented Programming in Common-Lisp. Addison Wesley.]]
49. Kiczales, G., des Rivières, J., and Bobrow, D. G. 1991. The Art of the Metaobject Protocol. MIT Press.]]
50. Kiczales, G., Hilsdale, E., Hugunin, J., Kersten, M., Palm, J., and Griswold, W. G. 2001. An overview of AspectJ. In Proceedings of ECOOP 2001. Number 2072 in LNCS. Springer Verlag, 327--353.]]
51. Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., and Irwin, J. 1997. Aspect-Oriented Programming. In Proceedings of ECOOP '97, M. Aksit and S. Matsuoka, Eds. LNCS, vol. 1241. Springer-Verlag, Jyvaskyla, Finland, 220--242.]]
52. Kniesel, G. 1999. Type-safe delegation for run-time component adaptation. In Proceedings of ECOOP '99, R. Guerraoui, Ed. LNCS, vol. 1628. Springer-Verlag, Lisbon, Portugal, 351--366.]]
53. LaLonde, W. and Pugh, J. 1991. Subclassing ≠ Subtyping ≠ Is-a. J. Object-Oriented Prog. 3, 5 (Jan.), 57--62.]]
54. LaLonde, W. R. 1989. Designing families of data types using exemplars. ACM Trans. Prog. Lang. Syst. 11, 2 (Apr.), 212--248.]]
55. Ledoux, T. and Cointe, P. 1996. Explicit metaclasses as a tool for improving the design of class libraries. In Proceedings of ISOTAS '96, LNCS 1049. JSSST-JAIST, 38--55.]]
56. Lienhard, A. 2004. Bootstrapping Traits. M.S. thesis, University of Bern.]]
57. Madsen, O. L., Magnusson, B., and Moller-Pedersen, B. 1990. Strong typing of object-oriented languages revisited. In Proceedings OOPSLA/ECOOP '90, ACM SIGPLAN Notices. Vol. 25. 140--150.]]
58. Mens, T. and van Limberghen, M. 1996. Encapsulation and composition as orthogonal operators on mixins: A solution to multiple inheritance problems. Object Oriented Systems 3, 1, 1--30.]]
59. Meyer, B. 1988. Object-oriented Software Construction. Prentice-Hall.]]
60. Meyer, B. 1992. Eiffel: The Language. Prentice-Hall.]]
61. Meyer, B. 1997. Object-Oriented Software Construction, Second ed. Prentice-Hall.]]
62. Mezini, M. 1997. Dynamic object evolution without name collisions. In Proceedings of ECOOP '97. Springer-Verlag, 190--219.]]
63. Mezini, M. and Ostermann, K. 2002. Integrating independent components with on-demand remodularization. In Proceedings OOPSLA 2002. 52--67.]]
64. Mohnen, M. 2002. Interfaces with default implementations in Java. In Conference on the Principles and Practice of Programming in Java. ACM Press, Dublin, Ireland, 35--40.]]
65. Moon, D. A. 1986. Object-oriented programming with Flavors. In Proceedings of OOPSLA '86, ACM SIGPLAN Notices. Vol. 21. 1--8.]]
66. Moura, P. 2003. Logtalk. Ph.D. thesis, Universidade da Beira Interior.]]
67. Musser, D. R. and Saini, A. 1996. STL Tutorial and Reference Guide. Addison Wesley.]]
68. Odersky, M., Altherr, P., Cremet, V., Emir, B., Maneth, S., Micheloud, S., Mihaylov, N., Schinz, M., Stenman, E., and Zenger, M. 2004. An overview of the Scala programming language. Tech. Rep. 64, école Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland.]]
69. Ogden, W. F., Sitaraman, M., Weide, B. W., and Zweben, S. H. 1994. Part i: the RESOLVE framework and discipline: a research synopsis. SIGSOFT Softw. Eng. Notes 19, 4, 23--28.]]
70. Riel, A. J. 1996. Object-Oriented Design Heuristics. Addison Wesley.]]
71. Rivard, F. 1997. évolution du comportement des objets dans les langages à classes réflexifs. Ph.D. thesis, Ecole des Mines de Nantes, Université de Nantes, France.]]
72. Sakkinen, M. 1989. Disciplined inheritance. In Proceedings of ECOOP '89, S. Cook, Ed. Cambridge University Press, Nottingham, 39--56.]]
73. Sakkinen, M. 1992. The darker side of C++ revisited. Structured Programming 13, 4, 155--177.]]
74. Schärli, N. 2005. Traits---composing classes from behavioral building blocks. Ph.D. thesis, University of Berne.]]
75. Schärli, N. and Black, A. P. 2003. A browser for incremental programming. Tech. Rep. CSE-03-008, OGI School of Science & Engineering, Beaverton, Oregon, USA. Apr.]]
76. Schärli, N., Ducasse, S., Nierstrasz, O., and Black, A. 2003. Traits: Composable units of behavior. In Proceedings of ECOOP 2003 (European Conference on Object-Oriented Programming). LNCS, vol. 2743. Springer Verlag, 248--274.]]
77. Schärli, N., Ducasse, S., Nierstrasz, O., and Wuyts, R. 2004. Composable encapsulation policies. In Proceedings of ECOOP 2004 (European Conference on Object-Oriented Programming). LNCS 3086. Springer Verlag, 26--50.]]
78. Sitaraman, M. and Weide, B. 1994. Component-based software using RESOLVE. SIGSOFT Softw. Eng. Notes 19, 4, 21--22.]]
79. Smaragdakis, Y. 2002. Layered development with (Unix) dynamic libraries. In Proceedings of ICSR 2002, C. Gacek, Ed. Lecture Notes in Computer Science, vol. 2319. Springer, 33--45.]]
80. Smaragdakis, Y. and Batory, D. 1998. Implementing layered design with mixin layers. In Proceedings of ECOOP '98, E. Jul, Ed. LNCS, vol. 1445. Brussels, Belgium, 550--570.]]
81. Smaragdakis, Y. and Batory, D. 2000. Mixin-based programming in C++. In 2nd Symposium on Generative and Component-Based Software Engineering (GCSE 2000). Erfurth, Germany.]]
82. Snyder, A. 1986. Encapsulation and inheritance in object-oriented programming languages. In Proceedings of OOPSLA '86, ACM SIGPLAN Notices. Vol. 21. 38--45.]]
83. Steele, G. L. 1990. Common Lisp The Language, Second ed. Digital Press.]]
84. Stefik, M. and Bobrow, D. G. 1985. Object-oriented programming: Themes and variations. The AI Magazine.]]
85. Stroustrup, B. 1986. The C++ Programming Language. Addison Wesley, Reading, Mass.]]
86. Stroustrup, B. 1997. The C++ Programming Language, Third ed. Addison Wesley.]]
87. Sweeney, P. F. and Gil, J. Y. 1999. Space and time-efficient memory layout for multiple inheritance. In Proceedings of OOPSLA '99. ACM Press, 256--275.]]
88. Taivalsaari, A. 1996. On the notion of inheritance. ACM Comput. Surv. 28, 3 (Sept.), 438--479.]]
89. Tarr, P., Ossher, H., Harrison, W., and Sutton, Jr, S. M. 1999. N Degrees of Separation: Multi-dimensional Separation of Concerns. In Proceedings of ICSE '99. Los Angeles CA, USA, 107--119.]]
90. Ungar, D., Chambers, C., Chang, B.-W., and Hölzle, U. 1991. Organizing programs without classes. LISP and SYMBOLIC COMPUTATION: An international journal 4, 3.]]
91. Ungar, D. and Smith, R. B. 1987. Self: The power of simplicity. In Proceedings of OOPSLA '87, ACM SIGPLAN Notices. Vol. 22. 227--242.]]
92. VanHilst, M. and Notkin, D. 1996a. Using C++ Templates to Implement Role-Based Designs. In JSSST International Symposium on Object Technologies for Advanced Software. Springer Verlag, 22--37.]]
93. VanHilst, M. and Notkin, D. 1996b. Using Role Components to Implement Collaboration-Based Designs. In Proceedings of OOPSLA '96. ACM Press, 359--369.]]
94. Wegner, P. and Zdonik, S. B. 1988. Inheritance as an incremental modification mechanism or what like is and isn't like. In Proceedings of ECOOP '88, S. Gjessing and K. Nygaard, Eds. LNCS, vol. 322. Springer-Verlag, Oslo, 55--77.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Classes and objects

        • Inheritance