Article

A virtual class calculus

Authors:

Klaus Ostermann,

William R. CookAuthors Info & Claims

POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 270 - 282

https://doi.org/10.1145/1111037.1111062

Published: 11 January 2006 Publication History

Abstract

Virtual classes are class-valued attributes of objects. Like virtual methods, virtual classes are defined in an object's class and may be redefined within subclasses. They resemble inner classes, which are also defined within a class, but virtual classes are accessed through object instances, not as static components of a class. When used as types, virtual classes depend upon object identity -- each object instance introduces a new family of virtual class types. Virtual classes support large-scale program composition techniques, including higher-order hierarchies and family polymorphism. The original definition of virtual classes in BETA left open the question of static type safety, since some type errors were not caught until runtime. Later the languages Caesar and gbeta have used a more strict static analysis in order to ensure static type safety. However, the existence of a sound, statically typed model for virtual classes has been a long-standing open question. This paper presents a virtual class calculus, VC, that captures the essence of virtual classes in these full-fledged programming languages. The key contributions of the paper are a formalization of the dynamic and static semantics of VC and a proof of the soundness of VC.

References

[1]

K. Barrett, B. Cassels, P. Haahr, D. Moon, K. Playford, and P. T. Withington. A monotonic superclass linearization for Dylan. In Proceedings OOPSLA '96, pages 69--82. ACM Press, 1996.]]

Digital Library

[2]

D. Batory, V. Singhal, J. Thomas, S. Dasari, B. Geraci, and M. Sirkin. The genvoca model of software-system generators. IEEE Software, 11(5), 1994.]]

Digital Library

[3]

G. Bracha and W. Cook. Mixin-based inheritance. In Proceedings OOPSLA/ECOOP'90. ACM SIGPLAN Notices 25(10), pages 303--311. ACM, 1990.]]

Digital Library

[4]

K. B. Bruce, M. Odersky, and P. Wadler. A statically safe alternative to virtual types. In Proceedings ECOOP '98. LNCS 1445, pages 523--549. Springer, 1998.]]

Digital Library

[5]

W. Cook. Object-oriented programming versus abstract data types. In Proc. of the REX Workshop/School on the Foundations of Object-Oriented Languages, LNCS 173. Springer-Verlag, 1990.]]

Digital Library

[6]

S. Drossopoulou, F. Damiani, M. Dezani-Ciancaglini, and P. Giannini. More dynamic object re-classification: FickleII. ACM Transactions On Programming Languages and Systems, 24(2):153--191, 2002.]]

Digital Library

[7]

E. Ernst. Propagating class and method combination. In Proceedings ECOOP'99, LNCS 1628, pages 67--91, Lisboa, Portugal, June 1999. Springer-Verlag.]]

Digital Library

[8]

E. Ernst. Family polymorphism. In Proceedings ECOOP '01, LNCS 2072, pages 303--326. Springer, 2001.]]

Digital Library

[9]

E. Ernst. Higher-order hierarchies. In Proceedings ECOOP '03, LNCS. Springer, 2003.]]

[10]

E. Ernst, K. Ostermann, and W. Cook. A virtual class calculus. Technical report, University of Aarhus, Aarhus, Denmark, 2005.]]

[11]

K. Fisher and J. Reppy. Statically typed traits. Technical Report TR-2003-13, University of Chicago, Chicago, USA, 2003.]]

[12]

M. Flatt, S. Krishnamurthi, and M. Felleisen. A programmer's reduction semantics for classes and mixins. In Formal Syntax and Semantics of Java, pages 241--269, London, UK, 1999. Springer-Verlag.]]

Digital Library

[13]

E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns. Addison Wesley, 1995.]]

[14]

C. A. Gunter. Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press, 1992.]]

Digital Library

[15]

R. Harrejon, D. Batory, and W. R. Cook. Evaluating support for features in advanced modularization technologies. In Proceedings ECOOP '05. Springer, 2005.]]

Digital Library

[16]

A. Igarashi and B. Pierce. Foundations for virtual types. Information and Computation, 175(1):34--49, 2002.]]

[17]

A. Igarashi, B. C. Pierce, and P. Wadler. Featherweight Java: a minimal core calculus for Java and GJ. ACM Trans. Program. Lang. Syst., 23(3):396--450, 2001.]]

Digital Library

[18]

A. Igarashi and M. Viroli. On variance-based subtyping for parametric types. In Proceedings of ECOOP '02. Springer LNCS 2374, 2002.]]

Digital Library

[19]

S. Krishnamurthi, M. Felleisen, and D. P. Friedman. Synthesizing object-oriented and functional design to promote re-use. In Proceedings of ECOOP '98, LNCS 1445, 1998.]]

Digital Library

[20]

O. L. Madsen, B. Møller-Pedersen, and K. Nygaard. Object Oriented Programming in the Beta Programming Language. Addison-Wesley, 1993.]]

Digital Library

[21]

O. L. Madsen and B. Møller-Pedersen. Virtual classes: A powerful mechanism in object-oriented programming. In Proceedings of OOPSLA '89. ACM SIGPLAN Notices 24(10), pages 397--406, 1989.]]

Digital Library

[22]

M. Mezini and K. Ostermann. Integrating independent components with on-demand remodularization. In Proceedings OOPSLA '02, ACM SIGPLAN Notices 37(11), pages 52--67, 2002.]]

Digital Library

[23]

M. Mezini and K. Ostermann. Conquering aspects with Caesar. In Proceedings AOSD '03, pages 90--99. ACM, 2003.]]

Digital Library

[24]

M. Mezini and K. Ostermann. Modules for crosscutting models. In International Conference on Reliable Software Technologies. Springer LNCS 2655, 2003.]]

[25]

N. Nystrom, S. Chong, and A. C. Myers. Scalable extensibility via nested inheritance. In Proceedings OOPSLA '04, pages 99--115. ACM Press, 2004.]]

Digital Library

[26]

M. Odersky, V. Cremet, C. RÃ¶ckl, and M. Zenger. A nominal theory of objects with dependent types. In Proceedings ECOOP '03. Springer LNCS, 2003.]]

[27]

M. Odersky and M. Zenger. Scalable component abstractions. In OOPSLA '05: Proceedings ACM SIGPLAN Conference on Object oriented programming systems languages and applications, pages 41--57. ACM Press, 2005.]]

Digital Library

[28]

K. Ostermann. Dynamically composable collaborations with delegation layers. In Proceedings of ECOOP '02. LNCS 2374, pages 89--110. Springer, 2002.]]

Digital Library

[29]

B. C. Pierce. Types and Programming Languages. MIT Press, 2002.]]

Digital Library

[30]

Y. Smaragdakis and D. Batory. Implementing layered designs with mixin-layers. In Proceedings of ECOOP '98, LNCS 1445, pages 550--570, 1998.]]

Digital Library

[31]

P. Tarr, H. Ossher, W. Harrison, and S. M. Sutton. N degrees of separation: Multi-dimensional separation of concerns. In Proceedings International Conference on Software Engineering (ICSE) '99, pages 107--119. ACM Press, 1999.]]

Digital Library

[32]

K. K. Thorup. Genericity in Java with virtual types. In Proceedings ECOOP '97. LNCS 1241, pages 444--471, 1997.]]

[33]

K. K. Thorup and M. Torgersen. Unifying genericity - combining the benefits of virtual types and parameterized classes. In Proceedings ECOOP '99, 1999.]]

Digital Library

[34]

M. Torgersen. The expression problem revisited. In European Conference on Object-Oriented Programming, 2004.]]

[35]

M. Torgersen, E. Ernst, C. P. Hansen, P. von~der Ahé, G. Bracha, and N. Gafter. Adding wildcards to the Java programming language. Journal of Object Technology, 3(11):97--116, Dec. 2004. http://www.jot.fm/issues/issue_2004_12/article5.]]

[36]

P. Wadler. The expression problem. Message to java-genericity electronic mailing list, November 1998.]]

[37]

M. Zenger. Personal communication, 2003.]]

[38]

M. Zenger and M. Odersky. Independently extensible solutions to the expression problem. Technical Report IC/2004/33, École Polytechnique Fédérale de Lausanne, 2004.]]

Cited By

Ye WSun YOliveira B(2024)Imperative Compositional Programming: Type Sound Distributive Intersection Subtyping with References via Bidirectional TypingProceedings of the ACM on Programming Languages10.1145/36897828:OOPSLA2(2010-2039)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689782
Kravchuk-Kirilyuk AFeng GIskander JZhang YAmin N(2024)Persimmon: Nested Family Polymorphism with Extensible Variant TypesProceedings of the ACM on Programming Languages10.1145/36498368:OOPSLA1(698-724)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649836
Jin EAmin NZhang Y(2023)Extensible Metatheory Mechanization via Family PolymorphismProceedings of the ACM on Programming Languages10.1145/35912867:PLDI(1608-1632)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591286
Show More Cited By

Index Terms

A virtual class calculus
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Classes and objects
        Inheritance
        Polymorphism
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Object oriented constructs
      2. Type structures
    2. Program semantics
      1. Operational semantics

Recommendations

Tribe: a simple virtual class calculus
AOSD '07: Proceedings of the 6th international conference on Aspect-oriented software development

Beginning with BETA, a range of programming language mechanisms such as virtual classes (class-valued attributes of objects) have been developed to allow inheritance in the presence of mutually dependent classes. This paper presents Tribe, a type system ...
A virtual class calculus
Proceedings of the 2006 POPL Conference

Virtual classes are class-valued attributes of objects. Like virtual methods, virtual classes are defined in an object's class and may be redefined within subclasses. They resemble inner classes, which are also defined within a class, but virtual ...
Virtual class support at the virtual machine level
VMIL '09: Proceedings of the Third Workshop on Virtual Machines and Intermediate Languages

This paper describes how virtual classes can be supported in a virtual machine. Main-stream virtual machines such as the Java Virtual Machine and the .NET platform dominate the world today, and many languages are being executed on these virtual machines ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2006

432 pages

ISBN:1595930272

DOI:10.1145/1111037

General Chair:
Greg Morrisett
Harvard University, USA
,
Program Chair:
Simon Peyton Jones
Microsoft Research, UK

ACM SIGPLAN Notices Volume 41, Issue 1
Proceedings of the 2006 POPL Conference
January 2006
421 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1111320
Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

POPL06

Sponsor:

POPL06: The 33rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 2006

January 11 - 13, 2006

South Carolina, Charleston, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

134
Total Citations
View Citations
735
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ye WSun YOliveira B(2024)Imperative Compositional Programming: Type Sound Distributive Intersection Subtyping with References via Bidirectional TypingProceedings of the ACM on Programming Languages10.1145/36897828:OOPSLA2(2010-2039)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689782
Kravchuk-Kirilyuk AFeng GIskander JZhang YAmin N(2024)Persimmon: Nested Family Polymorphism with Extensible Variant TypesProceedings of the ACM on Programming Languages10.1145/36498368:OOPSLA1(698-724)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649836
Jin EAmin NZhang Y(2023)Extensible Metatheory Mechanization via Family PolymorphismProceedings of the ACM on Programming Languages10.1145/35912867:PLDI(1608-1632)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591286
Lee JHelal A(2022)Modeling and Reasoning of Contexts in Smart Spaces Based on Stochastic Analysis of Sensor DataApplied Sciences10.3390/app1205245212:5(2452)Online publication date: 26-Feb-2022
https://doi.org/10.3390/app12052452
Sun YDhandhania UOliveira B(2022)Compositional embeddings of domain-specific languagesProceedings of the ACM on Programming Languages10.1145/35632946:OOPSLA2(175-203)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563294
Steimann F(2022)Containerless Plurals: Separating Number from Type in Object-Oriented ProgrammingACM Transactions on Programming Languages and Systems10.1145/352763544:4(1-56)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1145/3527635
Stucki NBrachthäuser JOdersky MKuchen HSinger J(2021)Virtual ADTs for portable metaprogrammingProceedings of the 18th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3475738.3480717(36-44)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1145/3475738.3480717
Giarrusso PStefanesco LTimany ABirkedal LKrebbers R(2020)Scala step-by-step: soundness for DOT with step-indexed logical relations in IrisProceedings of the ACM on Programming Languages10.1145/34089964:ICFP(1-29)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408996
Zhao WHou YChen JZhu JYin ESu HWen J(2020)Learning Semantic Representations from Directed Social Links to Tag Microblog Users at ScaleACM Transactions on Information Systems10.1145/337755038:2(1-30)Online publication date: 7-Mar-2020
https://dl.acm.org/doi/10.1145/3377550
Dagnino FBono VZucca EDezani-Ciancaglini M(2020)Soundness Conditions for Big-Step SemanticsProgramming Languages and Systems10.1007/978-3-030-44914-8_7(169-196)Online publication date: 27-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-44914-8_7
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents