Hostname: page-component-8448b6f56d-jr42d Total loading time: 0 Render date: 2024-04-19T08:00:30.841Z Has data issue: false hasContentIssue false
  • English
  • Français

Lightweight family polymorphism*

Part of: JFP Research Articles

Published online by Cambridge University Press:  01 May 2008

CHIERI SAITO ,
ATSUSHI IGARASHI  and
MIRKO VIROLI
CHIERI SAITO
Affiliation:
Kyoto University, Japan (e-mail: saito@kuis.kyoto-u.ac.jp, igarashi@kuis.kyoto-u.ac.jp)
ATSUSHI IGARASHI
Affiliation:
Kyoto University, Japan (e-mail: saito@kuis.kyoto-u.ac.jp, igarashi@kuis.kyoto-u.ac.jp)
MIRKO VIROLI
Affiliation:
Alma Mater Studiorum – Università di Bologna a Cesena, Italy (e-mail: mirko.viroli@unibo.it)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Family polymorphism has been proposed for object-oriented languages as a solution to supporting reusable yet type-safe mutually recursive classes. A key idea of family polymorphism is the notion of families, which are used to group mutually recursive classes. In the original proposal, due to the design decision that families are represented by objects, dependent types had to be introduced, resulting in a rather complex type system. In this article, we propose a simpler solution of lightweight family polymorphism, based on the idea that families are represented by classes rather than by objects. This change makes the type system significantly simpler without losing much expressive power of the language. Moreover, “family-polymorphic” methods now take a form of parametric methods; thus, it is easy to apply method type argument inference as in Java 5.0. To rigorously show that our approach is safe, we formalize the set of language features on top of Featherweight Java and prove that the type system is sound. An algorithm for type inference for family-polymorphic method invocations is also formalized and proved to be correct. Finally, a formal translation by erasure to Featherweight Java is presented; it is proved to preserve typing and execution results, showing that our new language features can be implemented in Java by simply extending the compiler.

Type
Articles
Information
Journal of Functional Programming , Volume 18 , Issue 3 , May 2008 , pp. 285 - 331
Copyright
Copyright © Cambridge University Press 2007

References

Aspinall, D. & Hofmann, M. (2005) Dependent types. In Advanced Topics in Types and Programming Languages, Pierce, B. C. (ed), The MIT Press, pp. 45–86.Google Scholar
Bracha, G., Odersky, M., Stoutamire, D. & Wadler, P. (1998, October). Making the future safe for the past: Adding genericity to the Java programming language. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'98), pp. 103–200.CrossRefGoogle Scholar
Bruce, K. B. (2003) Some challenging typing issues in object-oriented languages. In Proceedings of Workshop on Object-Oriented Development (WOOD'03). Electronic Notes in Theoretical Computer Science, vol. 82, no. 8.CrossRefGoogle Scholar
Bruce, K. B. & Foster, J. N. (2004) LOOJ: Weaving LOOM into Java. In Proceedings of European Conference on Object-Oriented Programming (ECOOP2004). Lecture Notes on Computer Science, vol. 3086. Oslo, Norway: Springer-Verlag.Google Scholar
Bruce, K. B. & Vanderwaart, J. C. (1999) Semantics-driven language design: Statically type-safe virtual types in object-oriented languages. In Proceedings of 15th Conference on the Mathematical Foundations of Programming Semantics (MFPS XV). Electronic Notes in Theoretical Computer Science, vol. 20. New Orleans, LA: Elsevier. Available at: http://www.elsevie.nl/locate/entcs/volume20.htmlGoogle Scholar
Bruce, K. B., Cardelli, L., Castagna, G., The Hopkins Objects Group, Leavens, G. T. & Pierce, B. (1996) On binary method. Theory Pract. Object Systems. 1 (3), 221–242.CrossRefGoogle Scholar
Bruce, K. B., Petersen, L. & Fiech, A. (1997) Subtyping is not a good “match” for object-oriented languages. In Proceedings of 11th European Conference on Object-Oriented Programming (ECOOP'97). Lecture Notes on Computer Science, vol. 1241. Jyväskylä, Finland: Springer-Verlag, pp. 104–127.CrossRefGoogle Scholar
Bruce, K. B., Odersky, M. & Wadler, P. (1998) A statically safe alternative to virtual types. Proceedings of 12th European Conference on Object-Oriented Programming (ECOOP'98). Lecture Notes on Computer Science, vol. 1445. Brussels, Belgium: Springer-Verlag, pp.Google Scholar
Canning, P., Cook, W., Hill, W., Olthoff, W. & Mitchell, J. C. (1989) F-bounded polymorphism for object-oriented programming. In Proceedings of ACM Conference on Functional Programming and Computer Architecture (FPCA'89). London, England: ACM Press, pp. 273–280.Google Scholar
Clarke, D., Drossopoulou, S., Noble, J. & Wrigstad, T. (2007, March). Tribe: A simple virtual class calculus. In Proceedings of International Conference on Aspect-Oriented Software Design (AOSD'07), pp. 121–134.CrossRefGoogle Scholar
Ernst, E. (1999 June) gbeta—A Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance. Ph.D. thesis, Department of Computer Science, University of Aarhus, Aarhus, Denmark.CrossRefGoogle Scholar
Ernst, E. (2001) Family polymorphism. In Proceedings of European Conference on Object-Oriented Programming (ECOOP2001). Lecture Notes on Computer Science, vol. 2072. Budapest, Hungary: Springer-Verlag, pp. 303–326.Google Scholar
Ernst, E. (2003). Higher-order hierarchies. In Proceedings of European Conference on Object-Oriented Programming (ECOOP2003). Lecture Notes on Computer Science, vol. 2743. Darmstadt, Germany: Springer-Verlag, pp. 303–328.Google Scholar
Ernst, E., Ostermann, K. & Cook, W. R. (2006, January). A virtual class calculus. In Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL2006), pp. 270–282.CrossRefGoogle Scholar
Flatt, M., Krishnamurthi, S. & Felleisen, M. (1998, January). Classes and mixins. In Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'98), pp. 171–183.CrossRefGoogle Scholar
Igarashi, A. & Viroli, M. (2007, January). Variant path types for scalable extensibility. In Proceedings of the International Workshop on Foundations and Developments of Object-Oriented Languages (FOOL/WOOD 2007). Available at: http://foolwood07.cs.uchicago.edu/.CrossRefGoogle Scholar
Igarashi, A., Pierce, B. C. & Wadler, P. (2001). Featherweight Java: A minimal core calculus for Java and GJ. ACM transactions on programming languages and systems, 23 (3), 396–450. A preliminary summary appeared in Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'99) ACM SIGPLAN Notices, vol. 34, no. 10, pp. 132–146, October 1999.CrossRefGoogle Scholar
Igarashi, A., Saito, C. & Viroli, M. (2005). Lightweight family polymorphism. In Proceedings of the 3rd Asian Symposium on Programming Languages and Systems (APLAS2005). Lecture Notes in Computer Science, vol. 3780. Tsukuba, Japan: Springer-Verlag, pp. 101–177.Google Scholar
Jolly, P., Drossopoulou, S., Anderson, C. & Ostermann, K. (2004, June). Simple dependent types: Concord. In Proceedings of 6th ECOOP Workshop on Formal Techniques for Java-like Programs (FTfJP2004).Google Scholar
Madsen, O. L. & Mφller-Pedersen, B. (1989, October). Virtual classes: A powerful mechanism in object-oriented programming. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'89), pp. 397–406.CrossRefGoogle Scholar
Nystrom, N., Chong, S. & Myers, A. C. (2004, October) Scalable extensibility via nested inheritance. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'04).CrossRefGoogle Scholar
Odersky, M. (2002, January) Inferred type instantiation for GJ. Available at: http://lampwww.epfl.ch/odersky/papers/localti02.html.Google Scholar
Odersky, M., Cremet, V., Röckl, C. & Zenger, M. (2003). A nominal theory of objects with dependent types. In Proceedings of European Conference on Object-Oriented Programming (ECOOP'03). Lecture Notes on Computer Science, vol. 2743. Darmstadt, Germany: Springer-Verlag, pp. 201–224.Google Scholar
Thorup, K. K. & Torgersen, M. (1999) Unifying genericity: Combining the benefits of virtual types and parameterized classes. In Proceedings of 13th European Conference on Object-Oriented Programming (ECOOP'99). Lecture Notes on Computer Science, vol. 1628. Lisbon, Portugal: Springer-Verlag, pp. 186–204.CrossRefGoogle Scholar
Torgersen, M. (2004, June) The expression problem revisited: Four new solutions using generics. Proceedings of European Conference on Object-Oriented Programming (ECOOP2004). Lecture Notes on Computer Science, vol. 3086, pp. 123–146.CrossRefGoogle Scholar
Wright, A. K. & Felleisen, M. (1994). A syntactic approach to type soundness. Inform. and Comput. 115 (1), 38–94.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.