Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/2340820.2340827guidebooksArticle/Chapter ViewAbstractPublication PagesBookacm-pubtype
chapter

Subtyping for f-bounded quantifiers and equirecursive types

Published: 01 January 2012 Publication History

Abstract

<em>Equirecursive types</em> consider a recursive type to be equal to its unrolling and have no explicit term-level coercions to change a term's type from the former to the latter or vice versa. This equality makes deciding type equality and subtyping more difficult than the other approach--<em>isorecursive types</em>, in which the types are not equal, but isomorphic, witnessed by explicit term-level coercions. Previous work has built intuition, rules, and polynomial-time decision procedures for equirecursive types for first-order type systems. Some work has been done for type systems with parametric polymorphism, but that work is incomplete (see below). This chapter will give an intuitive theory of equirecursive types for second-order type systems, sound and complete rules, and a decision procedure for subtyping.

References

[1]
Amadio, R., Cardelli, L.: Subtyping recursive types. ACM Transactions on Progamming Languages and Systems 15(4), 575-631 (1993)
[2]
Canning, P., Cook, W., Hill, W., Mitchell, J., Olthoff, W.: F-bounded quantification for object-oriented programming. In: 4th ACM Conference on Functional Programming and Computer Architecture, London, UK, pp. 273-280. ACM Press (September 1989)
[3]
Colazzo, D., Ghelli, G.: Subtyping recursive types in kernel fun. In: 1999 Symposium on Logic in Computer Science, Trento, Italy, pp. 137-146 (July 1999)
[4]
Glew, N.: An efficient class and object encoding. In: ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Minneapolis, MN, USA. ACM Press (October 2000)
[5]
Glew, N.: A theory of second-order trees. In: European Symposium on Programming 2002, Grenoble, France (April 2002)
[6]
Glew, N.: A theory of second-order trees. Technical Report TR2001-1859, Department of Computer Science, Cornell University, 4130 Upson Hall, Ithaca, NY 14853-7501, USA (January 2002)
[7]
Glew, N.: Subtyping for F-bounded quantifiers and equirecursive types (extended version). arXiv:1202.2486 (February 2012), http://arXiv.org/
[8]
Gauthier, N., Pottier, F.: Numbering matters: First-order canonical forms for second-order recursive types. In: 9th ACMSIGPLAN International Conference on Functional Programming, Snowbird, UT, USA, pp. 150-161. ACM Press (September 2004)
[9]
Kozen, D., Palsberg, J., Schwartzbach, M.: Efficient recursive subtyping. Mathematical Structures in Computer Science 5(1), 113-125 (1995)
[10]
Pierce, B.: Bounded quantification is undecidable. Information and Computation 112, 131-165 (1994)

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide books
Logic and Program Semantics: essays dedicated to Dexter Kozen on the occasion of his 60th birthday
January 2012
355 pages
ISBN:9783642294846
  • Editors:
  • Robert L. Constable,
  • Alexandra Silva

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2012

Qualifiers

  • Chapter

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Nov 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media