Document Open Access Logo

Global Type Inference for Featherweight Generic Java

Authors Andreas Stadelmeier, Martin Plümicke, Peter Thiemann

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.28.pdf
  • Filesize: 1.04 MB
  • 27 pages

Document Identifiers

Author Details

Andreas Stadelmeier
  • Duale Hochschule Baden-Württemberg Stuttgart, Campus Horb, Germany
Martin Plümicke
  • Duale Hochschule Baden-Württemberg Stuttgart, Campus Horb, Germany
Peter Thiemann
  • Institut für Informatik, Universität Freiburg, Germany

Cite As Get BibTex

Andreas Stadelmeier, Martin Plümicke, and Peter Thiemann. Global Type Inference for Featherweight Generic Java. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 28:1-28:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECOOP.2022.28

Abstract

Java’s type system mostly relies on type checking augmented with local type inference to improve programmer convenience.
We study global type inference for Featherweight Generic Java (FGJ), a functional Java core language. Given generic class headers and field specifications, our inference algorithm infers all method types if classes do not make use of polymorphic recursion. The algorithm is constraint-based and improves on prior work in several respects. Despite the restricted setting, global type inference for FGJ is NP-complete.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Language features
Keywords
  • type inference
  • Java
  • subtyping
  • generics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Davide Ancona, Ferruccio Damiani, Sophia Drossopoulou, and Elena Zucca. Polymorphic bytecode: compositional compilation for java-like languages. In Jens Palsberg and Martín Abadi, editors, Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, January 12-14, 2005, pages 26-37. ACM, 2005. URL: https://doi.org/10.1145/1040305.1040308.
  2. Christoph Beierle. Type inferencing for polymorphic order-sorted logic programs. In International Conference on Logic Programming, pages 765-779, 1995. Google Scholar
  3. Lorenzo Bettini, Viviana Bono, Mariangiola Dezani-Ciancaglini, Paola Giannini, and Venneri Betti. Java & lambda: A featherweight story. Logical Methods in Computer Science, 14(3:17):1-24, 2018. Google Scholar
  4. G.M. Bierman, M.J. Parkinson, and A.M. Pitts. MJ: An imperative core calculus for Java and Java with effects. Technical Report UCAM-CL-TR-563, University of Cambridge, Computer Laboratory, April 2003. URL: https://doi.org/10.48456/tr-563.
  5. Elias Castegren and Tobias Wrigstad. OOlong: an extensible concurrent object calculus. In Hisham M. Haddad, Roger L. Wainwright, and Richard Chbeir, editors, Proceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC 2018, Pau, France, April 09-13, 2018, pages 1022-1029. ACM, 2018. URL: https://doi.org/10.1145/3167132.3167243.
  6. Martin Emms and Hans Leiß. Extending the type checker of standard ML by polymorphic recursion. Theor. Comput. Sci., 212(1-2):157-181, 1999. URL: https://doi.org/10.1016/S0304-3975(98)00139-X.
  7. Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. A programmer’s reduction semantics for classes and mixins. In Jim Alves-Foss, editor, Formal Syntax and Semantics of Java, volume 1523 of Lecture Notes in Computer Science, pages 241-269. Springer, 1999. URL: https://doi.org/10.1007/3-540-48737-9_7.
  8. Michael Hanus. Parametric order-sorted types in logic programming. Proc. TAPSOFT 1991, LNCS(394):181-200, 1991. Google Scholar
  9. Fritz Henglein. Type inference with polymorphic recursion. ACM Trans. Program. Lang. Syst., 15(2):253-289, 1993. URL: https://doi.org/10.1145/169701.169692.
  10. Patricia M. Hill and Rodney W. Topor. A Semantics for Typed Logic Programs. In Frank Pfenning, editor, Types in Logic Programming, pages 1-62. MIT Press, 1992. Google Scholar
  11. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java: A minimal core calculus for Java and GJ. ACM Trans. Program. Lang. Syst., 23(3):396-450, 2001. URL: https://doi.org/10.1145/503502.503505.
  12. A. J. Kfoury, Jerzy Tiuryn, and Pawel Urzyczyn. Type reconstruction in the presence of polymorphic recursion. ACM Trans. Program. Lang. Syst., 15(2):290-311, 1993. URL: https://doi.org/10.1145/169701.169687.
  13. A. J. Kfoury, Jerzy Tiuryn, and Pawel Urzyczyn. The undecidability of the semi-unification problem. Inf. Comput., 102(1):83-101, 1993. URL: https://doi.org/10.1006/inco.1993.1003.
  14. A. Martelli and U. Montanari. An efficient unification algorithm. ACM Transactions on Programming Languages and Systems, 4:258-282, 1982. Google Scholar
  15. Robin Milner. A theory of type polymorphism in programming. J. Comput. Syst. Sci., 17(3):348-375, 1978. URL: https://doi.org/10.1016/0022-0000(78)90014-4.
  16. Martin Odersky, Matthias Zenger, and Christoph Zenger. Colored local type inference. Proc. 28th ACM Symposium on Principles of Programming Languages, 36(3):41-53, 2001. Google Scholar
  17. Johan Östlund and Tobias Wrigstad. Welterweight java. In Jan Vitek, editor, Objects, Models, Components, Patterns, 48th International Conference, TOOLS 2010, Málaga, Spain, June 28 - July 2, 2010. Proceedings, volume 6141 of Lecture Notes in Computer Science, pages 97-116. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13953-6_6.
  18. Benjamin C. Pierce and David N. Turner. Local type inference. In Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '98, pages 252-265, 1998. Google Scholar
  19. Martin Plümicke. Type Unification in Generic-Java. In Michael Kohlhase, editor, Proceedings of 18th International Workshop on Unification (UNIF'04), Cork, July 2004. Google Scholar
  20. Martin Plümicke. Typeless Programming in Java 5.0 with Wildcards. In Vasco Amaral, Luís Veiga, Luís Marcelino, and H. Conrad Cunningham, editors, 5th International Conference on Principles and Practices of Programming in Java, volume 272 of ACM International Conference Proceeding Series, pages 73-82, September 2007. Google Scholar
  21. Martin Plümicke. Java type unification with wildcards. In Dietmar Seipel, Michael Hanus, and Armin Wolf, editors, 17th International Conference, INAP 2007, and 21st Workshop on Logic Programming, WLP 2007, Würzburg, Germany, October 4-6, 2007, Revised Selected Papers, volume 5437 of Lecture Notes in Artificial Intelligence, pages 223-240. Springer-Verlag Heidelberg, 2009. Google Scholar
  22. Martin Plümicke. More type inference in Java 8. In Andrei Voronkov and Irina Virbitskaite, editors, Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, St. Petersburg, Russia, June 24-27, 2014. Revised Selected Papers, volume 8974 of Lecture Notes in Computer Science, pages 248-256. Springer, 2015. Google Scholar
  23. Martin Plümicke. Structural type inference in java-like languages. In Gemeinsamer Tagungsband der Workshops der Tagung Software Engineering 2016 (SE 2016), Wien, 23.-26. Februar 2016., pages 109-113, 2016. URL: http://ceur-ws.org/Vol-1559/paper09.pdf.
  24. Martin Plümicke and Andreas Stadelmeier. Introducing Scala-like function types into Java-TX. In Proceedings of the 14th International Conference on Managed Languages and Runtimes, ManLang 2017, pages 23-34, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3132190.3132203.
  25. J. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of ACM, 12(1):23-41, January 1965. Google Scholar
  26. Vincent Simonet. Type inference with structural subtyping: A faithful formalization of an efficient constraint solver. In Atsushi Ohori, editor, Programming Languages and Systems, First Asian Symposium, APLAS 2003, volume 2895 of Lecture Notes in Computer Science, pages 283-302, Beijing, China, November 2003. Springer. URL: https://doi.org/10.1007/978-3-540-40018-9_19.
  27. Gert Smolka. Logic Programming over Polymorphically Order-Sorted Types. PhD thesis, Department Informatik, University of Kaiserslautern, Kaiserslautern, Germany, May 1989. Google Scholar
  28. Andreas Stadelmeier, Martin Plümicke, and Peter Thiemann. Global type inference for Featherweight Generic Java, 2022. URL: https://arxiv.org/abs/2205.08768.
  29. Mads Torgersen, Erik Ernst, and Christian Plesner Hansen. Wild FJ. In Philip Wadler, editor, Proceedings of FOOL 12, Long Beach, California, USA, January 2005. ACM, School of Informatics, University of Edinburgh. URL: http://homepages.inf.ed.ac.uk/wadler/fool/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact