Document Open Access Logo

Formal Language Recognition with the Java Type Checker

Authors Yossi Gil, Tomer Levy

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.10.pdf
  • Filesize: 0.91 MB
  • 27 pages

Document Identifiers

Author Details

Yossi Gil
Tomer Levy

Cite AsGet BibTex

Yossi Gil and Tomer Levy. Formal Language Recognition with the Java Type Checker. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 10:1-10:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ECOOP.2016.10

Abstract

This paper is a theoretical study of a practical problem: the automatic generation of Java Fluent APIs from their specification. We explain why the problem's core lies with the expressive power of Java generics. Our main result is that automatic generation is possible whenever the specification is an instance of the set of deterministic context-free languages, a set which contains most "practical" languages. Other contributions include a collection of techniques and idioms of the limited meta-programming possible with Java generics, and an empirical measurement demonstrating that the runtime of the "javac" compiler of Java may be exponential in the program's length, even for programs composed of a handful of lines and which do not rely on overly complex use of generics.
Keywords
  • Parser Generators
  • Generic Programming
  • Fluent API

Metrics

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

References

  1. David Abrahams and Aleksey Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. C++ in Depth Series. Addison-Wesley, 2004. Google Scholar
  2. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, 1986. Google Scholar
  3. Jonathan Aldrich, Joshua Sunshine, Darpan Saini, and Zachary Sparks. Typestate-oriented programming. In Gary Leavens, editor, Proc. of the 24superscriptth Ann. Conf. on OO Prog. Sys., Lang., &Appl. (OOPSLA'09), pages 1015-1022, Orlando, FL, USA, October 2009. ACM Press. URL: http://doi.acm.org/10.1145/1639950.1640073, URL: http://dx.doi.org/10.1145/1639950.1640073.
  4. Ken Arnold and James Gosling. The Java Programming Language. The Java Series. Addison-Wesley, Reading, MA, 1996. Google Scholar
  5. Matthew H. Austern. Generic programming and the STL: using and extending the C++ Standard Template Library. Addison-Wesley, 1998. Google Scholar
  6. Jean-Michel Autebert, Jean Berstel, and Luc Boasson. Context-Free Languages and Pushdown Automata. Springer, 1997. Google Scholar
  7. Roland Backhouse, Patrik Jansson, Johan Jeuring, and Lambert Meertens. Generic programming. In Advanced Functional Programming, pages 28-115. Springer, 1999. Google Scholar
  8. Nels E. Beckman, Duri Kim, and Jonathan Erik Aldrich. An empirical study of object protocols in the wild. In Mira Mezini, editor, Proc. of the 25superscriptth Euro. Conf. on OO Prog. (ECOOP'11), volume 6813 of LNCS, pages 2-26, Lancaster, UK, June25-29 2011. Springer. Google Scholar
  9. Kevin Bierhoff and Jonathan Erik Aldrich. Lightweight object specification with typestates. In Michel Wermelinger and Harald C. Gall, editors, Proc. of the 10superscriptth European Soft. Eng. Conf. and 13superscriptth ACM SIGSOFT Symp. on the Foundations of Soft. Eng. (ESEC/FSE'05), pages 217-226, Lisbon, Portugal, September 2005. ACM Press. Google Scholar
  10. Eric Bodden. TS4J : A fluent interface for defining and computing typestate analyses. In Proceedings of the \nth3 ACM SIGPLAN International Workshop on the State of the Art in \Java Program Analysis - SOAP '14, pages 1-6, 2014. URL: http://dl.acm.org/citation.cfm?doid=2614628.2614629 http://www.bodden.de/pubs/bodden14ts4j.pdf, URL: http://dx.doi.org/10.1145/2614628.2614629.
  11. Gilad Bracha, Martin Odersky, David Stoutamire, and Philip Wadler. Making the future safe for the past: Adding genericity to the Java programming language. In Bjørn N. -Benson Freeman and Craig Chambers, editors, Proc. of the 13superscriptth Ann. Conf. on OO Prog. Sys., Lang., &Appl. (OOPSLA'98), pages 183-200, Vancouver, BC, Canada, October18-22 1998. ACM SIGPLAN Notices 33(10). Google Scholar
  12. Noam Chomsky. Formal properties of grammars. Addison-Wesley, 1963. Google Scholar
  13. John Cocke. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York University, 1969. Google Scholar
  14. Bruno Courcelle. On jump-deterministic pushdown automata. Math. Sys. Theory, 11:87-109, 1977. Google Scholar
  15. James C. Dehnert and Alexander Stepanov. Fundamentals of generic programming. In Generic Programming, pages 1-11. Springer, 2000. Google Scholar
  16. Arie Van Deursen, Paul Klint, and Joost Visser. Domain-specific languages: an annotated bibliography. ACM Sigplan Notices, 35(6):26-36, 2000. URL: http://portal.acm.org/citation.cfm?doid=352029.352035, URL: http://dx.doi.org/10.1145/352029.352035.
  17. Charles Donnelly and Richard Stallman. Bison, 2015. Google Scholar
  18. Jay Earley. An efficient context-free parsing algorithm. Comm. of the ACM, 13(2):94-102, 1970. URL: http://dx.doi.org/10.1145/362007.362035.
  19. Sebastian Erdweg, Lennart C.L. Kats, Tillmann Rendel, Christian Kästner, Klaus Ostermann, and Eelco Visser. Sugarj: Library-based language extensibility. In Kathleen Fisher, editor, Proc. of the 26superscriptth Ann. Conf. on OO Prog. Sys., Lang., &Appl. (OOPSLA'10), pages 187-188, Portland OR, USA, October22-27 2011. ACM Press. Google Scholar
  20. Steve Freeman and Nat Pryce. Evolving an embedded domain-specific language in \Java. In Peri L. Tarr and William R. Cook, editors, Proc. of the OOPSLA'06 Companion. ACM Press, October22-26 2006. Google Scholar
  21. Ronald Garcia, Jaakko Järvi, Andrew Lumsdaine, Jeremy Siek, and Jeremiah Willcock. A comparative study of language support for generic programming. In Ron Crocker and Guy L. Steele Jr., editors, Proc. of the 18superscriptth Ann. Conf. on OO Prog. Sys., Lang., &Appl. (OOPSLA'03), pages 115-134, Anaheim, CA, USA, October 2003. ACM SIGPLAN Notices 38 (11). URL: http://www.informatik.uni-trier.de/~ley/db/conf/oopsla/oopsla2003p.html.
  22. Joseph Gil and Zvi Gutterman. Compile time symbolic derivation with C++ templates. In Proc. of the USENIX C++ Conf., pages 249-264, Santa Fe, NM, April 1998. USENIX Association. Google Scholar
  23. Joseph (Yossi) Gil and Keren Lenz. Simple and safe SQL queries with \scriptsize\oldCc##1 templates. In Charles Consel, editor, Proc. of the 6superscriptth Conf. on Generative Prog. &Component Eng., LNCS, pages 13-24, Salzburg, Austria, October 2007. ACM Press. Google Scholar
  24. Adele Goldberg. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley, Reading, MA, 1984. Google Scholar
  25. Zvi Gutterman. Turing templates - on \scriptsize\oldCc##1 compile time power. Master’s thesis, Technion - Israel Institute of Technology, 2003. Google Scholar
  26. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, \nth2 edition, 2001. Google Scholar
  27. Claus Ibsen and Jonathan Anstey. Camel in action. Manning Publications Co., Shelter Island, NY, 2010. Google Scholar
  28. JBoss Group. Hibernate product homepage. http://www.hibernate.org/, 2006. Google Scholar
  29. Jevgeni Kabanov and Rein Raudjärv. Embedded typesafe domain specific languages for \Java. Proceedings of the \nth6 international symposium on Principles and practice of programming in \Java - PPPJ '08, 2008. URL: http://dx.doi.org/10.1145/1411732.1411758.
  30. Donald Ervin Knuth. On the translation of languages from left to right. Information and Control, 8(6):607-639, 1965. URL: http://dx.doi.org/10.1016/S0019-9958(65)90426-2.
  31. Robert Larsen. Fluenty: A type safe query API. Master’s thesis, University of Oslo, 2012. Google Scholar
  32. Peter Linz. An Introduction to Formal Languages and Automata. Jones & Bartlett Learning, 2011. Google Scholar
  33. Erik Meijer, Brian Beckman, and Gavin Bierman. LINQ: Reconciling objects, relations and XML in the .NET framework. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data (ICMD'2006), Chicago, Illinois, 2006. Google Scholar
  34. David R. Musser and Alexander A. Stepanov. Generic programming. In Symbolic and Algebraic Computation, pages 13-25. Springer, 1989. Google Scholar
  35. Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. An overview of the Scala programming language. Technical Report IC 64, EPFL Lausanne, Switzerland, 2004. Google Scholar
  36. Matthew M Papi. Practical pluggable types for \Java. Master’s thesis, Massachusetts Institute of Technology, 2008. URL: http://portal.acm.org/citation.cfm?doid=1390630.1390656, URL: http://dx.doi.org/10.1145/1390630.1390656.
  37. Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, Reading, MA, 3superscriptrd edition, 1997. Google Scholar
  38. David Vandevoorde and Nicolai M. Josuttis. \CC Templates: The Complete Guide. Addison-Wesley, 2002. Google Scholar
  39. Todd L. Veldhuizen. Expression templates. C++ Report, 7(5):26-31, June 1995. Google Scholar
  40. Daniel H. Younger. Recognition and parsing of context-free languages in time n³. Information and Control, 10(2):189-208, 1967. URL: http://www.sciencedirect.com/science/article/pii/S001999586780007X, URL: http://dx.doi.org/10.1016/S0019-9958(67)80007-X.
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 Imprint Privacy Contact