Document Open Access Logo

Mixin Composition Synthesis Based on Intersection Types

Authors Jan Bessai, Andrej Dudenhefner, Boris Düdder, Tzu-Chun Chen, Ugo de’Liguoro, Jakob Rehof

PDF

File

Thumbnail PDF
PDF
LIPIcs.TLCA.2015.76.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • Record Calculus
  • Combinatory Logic
  • Type Inhabitation
  • Mixin
  • Intersection Type

Metrics

Abstract

We present a method for synthesizing compositions of mixins using type inhabitation in intersection types. First, recursively defined classes and mixins, which are functions over classes, are expressed as terms in a lambda calculus with records. Intersection types with records and record-merge are used to assign meaningful types to these terms without resorting to recursive types. Second, typed terms are translated to a repository of typed combinators. We show a relation between record types with record-merge and intersection types with constructors. This relation is used to prove soundness and partial completeness of the translation with respect to mixin composition synthesis. Furthermore, we demonstrate how a translated repository and goal type can be used as input to an existing framework for composition synthesis in bounded combinatory logic via type inhabitation. The computed result corresponds to a mixin composition typed by the goal type.

Cite As Get BibTex

Jan Bessai, Andrej Dudenhefner, Boris Düdder, Tzu-Chun Chen, Ugo de’Liguoro, and Jakob Rehof. Mixin Composition Synthesis Based on Intersection Types. In 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 38, pp. 76-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.TLCA.2015.76

Author Details

Jan Bessai
Andrej Dudenhefner
Boris Düdder
Tzu-Chun Chen
Ugo de’Liguoro
Jakob Rehof

References

  1. Martín Abadi and Luca Cardelli. A Theory of Objects. Springer, 1996. Google Scholar
  2. Steffen Van Bakel. Strict intersection types for the lambda calculus. ACM Comput. Surv., 43(3):20:1-20:49, April 2011. Google Scholar
  3. H. Barendregt. The Lambda Calculus - Its Syntax and Semantics, volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1984. Google Scholar
  4. H. Barendregt, M. Coppo, and M. Dezani-Ciancaglini. A Filter Lambda Model and the Completeness of Type Assignment. Journal of Symbolic Logic, 48(4):931-940, 1983. Google Scholar
  5. Jan Bessai, Boris Düdder, Andrej Dudenhefer, and Moritz Martens. Delegation-based mixin composition synthesis. http://www-seal.cs.tu-dortmund.de/seal/downloads/papers/paper-ITRS2014.pdf, 2014.
  6. Jan Bessai, Boris Düdder, Andrej Dudenhefner, Tzu-Chun Chen, and Ugo de'Liguoro. Typing classes and mixins with intersection types. arXiv preprint arXiv:1503.04911, 2015. Google Scholar
  7. Jan Bessai, Andrej Dudenhefner, Boris Düdder, Moritz Martens, and Jakob Rehof. Combinatory Logic Synthesizer. In Tiziana Margaria and Bernhard Steffen, editors, ISoLA'14, volume 8802, pages 26-40, 2014. Google Scholar
  8. Viviana Bono, Amit Patel, and Vitaly Shmatikov. A core calculus of classes and mixins. In ECOOP, volume 1628 of Lecture Notes in Computer Science, pages 43-66, 1999. Google Scholar
  9. Gilad Bracha. The Programming Language JIGSAW: Mixins, Modularity and Multiple Inheritance. PhD thesis, Univeristy of Utha, 1992. Google Scholar
  10. Gilad Bracha and William R. Cook. Mixin-based inheritance. In OOPSLA/ECOOP, pages 303-311, 1990. Google Scholar
  11. Kim B. Bruce. Foundations of Object-Oriented Languages - Types and Semantics. MIT Press, 2002. Google Scholar
  12. Peter S. Canning, William R. Cook, Walter L. Hill, Walter G. Olthoff, and John C. Mitchell. F-bounded polymorphism for object-oriented programming. In FPCA, pages 273-280, 1989. Google Scholar
  13. Luca Cardelli. A semantics of multiple inheritance. In Semantics of Data Types, volume 173, pages 51-67, 1984. Google Scholar
  14. Adriana B. Compagnoni and Benjamin C. Pierce. Higher-order intersection types and multiple inheritance. Mathematical Structures in Computer Science, 6(5):469-501, 1996. Google Scholar
  15. William R. Cook, Walter L. Hill, and Peter S. Canning. Inheritance is not subtyping. In POPL'90, pages 125-135. ACM Press, 1990. Google Scholar
  16. Ugo de'Liguoro. Characterizing convergent terms in object calculi via intersection types. In TLCA, pages 315-328, 2001. Google Scholar
  17. Ugo de'Liguoro and Tzu chun Chen. Semantic Types for Classes and Mixins. http://www.di.unito.it/~deligu/papers/UdLTC14.pdf, 2014.
  18. Boris Düdder. Automatic Synthesis of Component & Connector-Software Architectures with Bounded Combinatory Logic. Dissertation, TU Dortmund, 2014. Google Scholar
  19. Boris Düdder, Moritz Martens, and Jakob Rehof. Staged composition synthesis. In ESOP, volume 8410 of Lecture Notes in Computer Science, pages 67-86, 2014. Google Scholar
  20. Boris Düdder, Moritz Martens, Jakob Rehof, and PawełUrzyczyn. Bounded Combinatory Logic. In Proceedings of CSL'12, volume 16, pages 243-258. Schloss Dagstuhl, 2012. Google Scholar
  21. Standard Ecma. ECMA-262 ECMAScript Language Specification, 2011. Google Scholar
  22. Tihomir Gvero, Viktor Kuncak, Ivan Kuraj, and Ruzica Piskac. Complete Completion using Types and Weights. SIGPLAN Notices, 48(6):27-38, 2013. Google Scholar
  23. Oleg Kiselyov and Ralf Lämmel. Haskell’s overlooked object system. CoRR, abs/cs/0509027, 2005. Google Scholar
  24. Martin Odersky and Matthias Zenger. Scalable component abstractions. In OOPSLA, pages 41-57. ACM, 2005. Google Scholar
  25. Benjamin C. Pierce. Intersection types and bounded polymorphism. Mathematical Structures in Computer Science, 7(2):129-193, 1997. Google Scholar
  26. Didier Rémy. Typing record concatenation for free. In POPL'92, pages 166-176, 1992. Google Scholar
  27. Mitchell Wand. Type inference for record concatenation and multiple inheritance. Inf. Comput., 93(1):1-15, 1991. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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