JTL: the Java tools language

Abstract

We present an overview of JTL (the Java Tools Language, pronounced "Gee-tel"), a novel language for querying JAVA [8] programs. JTL was designed to serve the development of source code software tools for JAVA, and as a small language which to aid programming language extensions to JAVA. Applications include definition of pointcuts for aspect-oriented programming, fixing type constraints for generic programming, specification of encapsulation policies, definition of micro-patterns, etc. We argue that the JTL expression of each of these is systematic, concise, intuitive and general.JTL relies on a simply-typed relational database for program representation, rather than an abstract syntax tree. The underlying semantics of the language is restricted to queries formulated in First Order Predicate Logic augmented with transitive closure (FOPL).Special effort was taken to ensure terse, yet readable expression of logical conditions. The JTL pattern <B>public abstract class</B>, for example, matches all abstract classes which are publicly accessible, while <B>class</B> (<B>public</B> clone();) matches all classes in which method clone is public. To this end, JTL relies on a DATALOG-like syntax and semantics, enriched with quantifiers and pattern matching which all but entirely eliminate the need for recursive calls.JTL's query analyzer gives special attention to the fragility of the "closed world assumption" in examining JAVA software, and determines whether a query relies on such an assumption.The performance of the JTL interpreter is comparable to that of JQuery after it generated its database cache, and at least an order of magnitude faster when the cache has to be rebuilt.

References

1. A. V. Aho, B. W. Kernighan, and P. J. Weinberger. The AWK programming language. Addison-Wesley series in Computer Science. Addison-Wesley Publishing Company, Reading, Massachusetts, 1988.]]
2. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Publishing Company, Reading, Massachusetts, 1986.]]
3. J. E. Aldrich and C. Chambers. Ownership domains: Separating aliasing policy from mechanisms. In M. Odersky, editor, Proc. of the Eighteenth European Conference on Object-Oriented Programming (ECOOP'04), volume 3086 of Lecture Notes in Computer Science, pages 1--25, Oslo, Norway, June 2004. Springer Verlag.]]
4. J. E. Aldrich, V. Kostadinov, and C. Chambers. Alias annotations for program understanding. In Proc. of the Seventeenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'02), pages 311--330, Seattle, Washington, Nov. 4-8 2002. OOPSLA'02, ACM SIGPLAN Notices 37(11).]]
5. D. Ancona, G. Lagorio, and E. Zucca. Jam - designing a Java extension with mixins. ACM Transactions on Programming Languages and Systems, 25(5):641--712, 2003.]]
6. C. Andreae, J. Noble, S. Markstrum, and T. Millstein. A framework for implementing pluggable type systems. In Proceedings of the 21th Annual conference on Object-oriented programming, systems, languages, and applications (OOPSLA'06), Portland, Oregon, October 22-26 2006. ACM SIGPLAN Notices.]]
7. G. Antoniol, M. D. Penta, and E. Merlo. YAAB (Yet Another AST Browser): Using OCL to navigate ASTs. In Proc. of the Eleventh International Workshop on Program Comprehension (IWPC'03), pages 13--22, Portland, Oregon, USA, May 10-11 2003.]]
8. K. Arnold and J. Gosling. The Java Programming Language. The Java Series. Addison-Wesley Publishing Company, Reading, Massachusetts, 1996.]]
9. D. C. Atkinson and W. G. Griswold. The design of whole-program analysis tools. In Proc. of the Eighteenth International Conference on Software Engineering (ICSE'96), pages 16--27, Berlin, Germany, March 25-30 1996.]]
10. L. A. Barowski and J. H. Cross II. Extraction and use of class dependency information for Java. In Proc. of the Ninth Working Conference on Reverse Engineering (WCRE'02), pages 309--318, Richmond, Virginia, USA, Oct. 2002. IEEE Computer Society Press.]]
11. L. Bendix, A. Dattolo, and F. Vitali. Software configuration management in software and hypermedia engineering: A survey. In Handbook of Software Engineering and Knowledge Engineering, volume 1, pages 523--548. World Scientific Publishing, 2001.]]
12. A. Birka and M. D. Ernst. A practical type system and language for reference immutability. In J. M. Vlissides and D. C. Schmidt, editors, Proc. of the Nineteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'04), pages 35--49, Vancouver, BC, Canada, Oct. 2004. ACM SIGPLAN Notices 39 (10).]]
13. S. Boag, D. Chamberlin, M. F. Fernández, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML Query Language. W3C, 2005.]]
14. B. Bokowski and J. Vitek. Confined types. In Proc. of the Fourteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99), pages 82--96, Denver, Colorado, Nov.1-5 1999. OOPSLA'99, ACM SIGPLAN Notices 34 (10).]]
15. E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Perspectives of Mathematical Logic. Springer Verlag, 1997.]]
16. J. Brichau, K. Gybels, and R. Wuyts. Towards a linguistic symbiosis of an object-oriented and a logic programming language. In J. Striegnitz, K. Davis, and Y. Smaragdakis, editors, Proc. of the Workshop on Multiparadigm Programming with Object-Oriented Languages (MPOOL'02) at the European Conference on Object-Oriented Programming, June 2002.]]
17. S. Ceri, G. Gottlob, and L. Tanca. Logic programming and databases. Springer Verlag, New York, 1990.]]
18. C. Chambers. Object-oriented multi-methods in Cecil. In O. L. Madsen, editor, Proc. of the Sixth European Conference on Object-Oriented Programming (ECOOP92), volume 615 of Lecture Notes in Computer Science, pages 33--56, Utrecht,the Netherlands, June29-July3 1992. Springer Verlag.]]
19. Y.-F. Chen, M. Nishimoto, and C. Ramamoorthy. The C information abstraction system. IEEE Trans. Softw. Eng., 16(3):325--334, Mar. 1990.]]
20. T. Cohen and J. Gil. Self-calibration of metrics of Java methods. In Proc. of the Thirty Seventh International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'00 Pacific), pages 94--106, Sydney, Australia, Nov. 20-23 2000. Prentice-Hall, Englewood Cliffs, New Jersy 07632.]]
21. T. Cohen and J. Gil. AspectJ2EE = AOP + J2EE: Towards an aspect based, programmable and extensible middleware framework. In M. Odersky, editor, Proc. of the Eighteenth European Conference on Object-Oriented Programming (ECOOP'04), volume 3086 of Lecture Notes in Computer Science, pages 219--243, Oslo, Norway, June 2004. Springer Verlag.]]
22. M. Consens, A. Mendelzon, and A. Ryman. Visualizing and querying software structures. In CASCON'91, pages 17--35. IBM Press, 1991.]]
23. W. R. Cook and S. Rai. Safe query objects: statically typed objects as remotely executable queries. In B. N. Gruia-Catalin Roman, William G. Griswold, editor, Proc. of the Twenty Seventh International Conference on Software Engineering (ICSE'05), pages 97--106, St. Louis, MO, USA, May 15-21 2005. ACM Press, New York, NY, USA.]]
24. R. F. Crew. ASTLOG: A language for examining abstract syntax trees. In S. Kamin, editor, Proc. of the First USENIX Conference Domain Specific Languages (DSL'97), pages 229--242, Santa Barbara, Oct. 1997.]]
25. P. Deransart, L. Cervoni, and A. Ed-Dbali. Prolog: The Standard: reference manual. Springer-Verlag, London, UK, 1996.]]
26. P. T. Devanbu. GENOA-a customizable, front-end-retargetable source code analysis framework. ACM Trans. on Soft. Eng. and Methodology, 8(2):177--212, 1999.]]
27. M. Eichberg, M. Mezini, K. Ostermann, and T. Schäfer. XIRC: A kernel for cross-artifact information engineering in software development environments. In Proc. of the Eleventh Working Conference on Reverse Engineering (WCRE'04), pages 182--191, Delft, Netherlands, Nov. 8-12 2004. IEEE Computer Society Press.]]
28. M. Fähndrich and K. R. M. Leino. Declaring and checking non-null types in an object-oriented language. In R. Crocker and G. L. S. Jr., editors, Proc. of the Eighteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'03), pages 302--312, Anaheim, California, USA, Oct. 2003. ACM SIGPLAN Notices 38 (11).]]
29. C. Flanagan, K. R. M. Leino, M. Lillibridge, G. Nelson, J. B. Saxe, and R. Stata. Extended static checking for Java. In Proc. of the Conference on Programming Language Design and Implementation (PLDI) (PLDI'02), pages 234--245, Berlin, Germany, June 17-21 2002. Compaq Systems Research Center.]]
30. M. Fowler. Refactoring: Improving the Design of Existing Code. Object Technology Series. Addison-Wesley Publishing Company, Reading, Massachusetts, 2000.]]
31. R. Garcia, J. Järvi, A. Lumsdaine, J. Siek, and J. Willcock. A comparative study of language support for generic programming. In R. Crocker and G. L. S. Jr., editors, Proc. of the Eighteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'03), pages 115--134, Anaheim, California, USA, Oct. 2003. ACM SIGPLAN Notices 38 (11).]]
32. J. Gil and Y. Eckel. Statically checkable design level traits. In Proc. of the Thirteenth IEEE Conference on Automated Software Engineering (ASE'98), page 217, Honolulu, Hawaii, USA, Nov. 1998. IEEE Computer.]]
33. J. Gil and I. Maman. Micro patterns in Java code. In Proc. of the Twentieth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'05), San Diego, California, Oct.16-20 2005. ACM SIGPLAN Notices.]]
34. J. Gil and Y. Tsoglin. JAMOOS-a domain-specific language for language processing. J. Comp. and Inf. Tech., 9(4):305--321, 2001.]]
35. A. Goldberg. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley Publishing Company, Reading, Massachusetts, 1984.]]
36. S. Goldsmith, R. O'Callahan, and A. Aiken. Relational queries over program traces. In Proc. of the Twentieth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'05), pages 385--402, San Diego, California, Oct.16-20 2005. ACM SIGPLAN Notices.]]
37. I. Gorton and L. Zhu. Tool support for Just-in-Time architecture reconstruction and evaluation: An experience report. In B. N. Gruia-Catalin Roman, William G. Griswold, editor, Proc. of the Twenty Seventh International Conference on Software Engineering (ICSE'05), pages 514--523, St. Louis, MO, USA, May 15-21 2005. ACM Press, New York, NY, USA.]]
38. O. C. Z. Gotel and A. C. W. Finkelstein. An analysis of the requirements traceability problem. In Proc. of the First International Conference on Requirements Engineering (ICRE'94), pages 94--101, Colorado Springs, Colorado, Apr. 1994. IEEE Computer Society Press.]]
39. G. Gottlob, E. Grädel, and H. Veith. Linear time Datalog for branching time logic. In Logic-Based Artificial Intelligence. Kluwer, 2000.]]
40. J. E. Grass and Y. Chen. The C++ information abstractor. In Proc. of the USENIX C++ Conference, pages 265--277, San Fransisco, CA, Apr. 1990. AT&T Bell Laboratories, USENIX Association.]]
41. W. G. Griswold, D. C. Atkinson, and C. McCurdy. Fast, flexible syntactic pattern matching and processing. In Proc. of the Fourth Workshop on Program Comprehension (WPC '96), pages 144--153, Washington, DC, 1996. IEEE Computer Society Press.]]
42. K. Gybels and J. Brichau. Arranging language features for more robust pattern-based crosscuts. In Proc. of the Second International Conference on Aspect-Oriented Software Development (AOSD'03), pages 60--69, Boston, Massachusetts, USA, Mar. 17-21 2003. ACM Press, New York, NY, USA.]]
43. A. N. Habermann and D. Notkin. Gandalf: Software development environments. IEEE Trans. Softw. Eng., 12(12):1117--1127, Dec. 1986.]]
44. E. Hajiyev, M. Verbaere, and O. de Moor. Codequest: Scalable source code queries with datalog. In D. Thomas, editor, Proceedings of the 20th European Conference on Object-Oriented Programming (ECOOP'06), volume 4067 of Lecture Notes in Computer Science, pages 2--27, Berlin, Germany, 2006. Springer.]]
45. M. Harren et al. XJ: integration of XML processing into Java. In WWW Alt. '04: Proc. of the Thirteenth International World Wide Web Conference on Alternate track papers & posters, pages 340--341, New York, NY, USA, 2004. ACM Press, New York, NY, USA.]]
46. A. Hejlsberg, S. Wiltamuth, and P. Golde. The C# Programming Language. Addison-Wesley Publishing Company, Reading, Massachusetts, second edition, Oct. 2003.]]
47. R. Holmes and G. C. Murphy. Using structural context to recommend source code examples. In B. N. Gruia-Catalin Roman, William G. Griswold, editor, Proc. of the Twenty Seventh International Conference on Software Engineering (ICSE'05), pages 117--125, St. Louis, MO, USA, May 15-21 2005. ACM Press, New York, NY, USA.]]
48. D. Hovemeyer and W. Pugh. Finding bugs is easy. ACM SIGPLAN Notices, 39(12):92--106, 2004.]]
49. ISE. ISE EIFFEL The Language Reference. ISE, Santa Barbara, CA, 1997.]]
50. D. Janzen and K. D. Volder. Navigating and querying code without getting lost. In Proc. of the Second international conference on Aspect-Oriented Software Development (AOSD'03), pages 178--187, New York, NY, USA, 2003. ACM Press.]]
51. J. Järvi, J. Willcock, and A. Lumsdaine. Associated types and constraint propagation for mainstream object-oriented generics. In Proc. of the Twentieth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'05), San Diego, California, Oct.16-20 2005. ACM SIGPLAN Notices.]]
52. G. Kiczales, E. Hilsdale, J. Hugunin, M. Kersten, J. Palm, and W. G. Griswold. An overview of AspectJ. In J. L. Knudsen, editor, Proc. of the Fifteenth European Conference on Object-Oriented Programming (ECOOP'01), volume 2072 of Lecture Notes in Computer Science, pages 327--355, Budapest, Hungary, June 2001. Springer Verlag.]]
53. G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. V. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In M. Akşit and S. Matsuoka, editors, Proc. of the Eleventh European Conference on Object-Oriented Programming (ECOOP'97), volume 1241 of Lecture Notes in Computer Science, pages 220--242, Jyväskylä, Finland, June 9-13 1997. Springer Verlag.]]
54. K. Kontogiannis, J. Martin, K. Wong, R. Gregory, H. A. Müller, and J. Mylopoulos. Code migration through transformations. In S. A. MacKay and J. H. Johnson, editors, Proc. of the Conference of the Centre for Advanced Studies on Collaborative research (CASCON'98), page 13, Toronto, Ontario, Canada, Nov. 1998. IBM Press.]]
55. T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley Publishing Company, Reading, Massachusetts, second edition, 1999.]]
56. M. Martin, B. Livshits, and M. S. Lam. Finding application errors and security flaws using PQL: a program query language. In Proc. of the Twentieth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'05), pages 365--383, San Diego, California, Oct.16-20 2005. ACM SIGPLAN Notices.]]
57. R. A. McClure and I. H. Krüger. SQL DOM: compile time checking of dynamic SQL statements. In B. N. Gruia-Catalin Roman, William G. Griswold, editor, Proc. of the Twenty Seventh International Conference on Software Engineering (ICSE'05), pages 88--96, St. Louis, MO, USA, May 15-21 2005. ACM Press, New York, NY, USA.]]
58. B. Meyer. Object-Oriented Software Construction. Prentice-Hall, Englewood Cliffs, New Jersy 07632, Englewood Cliffs, New Jersy, second edition, 1997.]]
59. M. Mezini and K. Ostermann. Conquering aspects with Caesar. In Proc. of the Second International Conference on Aspect-Oriented Software Development (AOSD'03), pages 90--100, Boston, Massachusetts, USA, Mar. 17-21 2003. ACM Press, New York, NY, USA.]]
60. H. A. Müller and K. Klashinsky. Rigi-A system for programming-in-the-large. In Proc. of the Tenth International Conference on Software Engineering (ICSE'88), pages 80--86, Singapore, Apr. 1988. IEEE Computer Society Press.]]
61. G. C. Murphy, M. Kersten, M. P. Robillard, and D. Cubranic. The emergent structure of development tasks. In A. P. Black, editor, Proc. of the Ninetieth European Conference on Object-Oriented Programming (ECOOP'05), volume 3086 of Lecture Notes in Computer Science, pages 33--48, Glasgow, UK, July 25-29 2005. Springer Verlag.]]
62. I. Nassi and B. Shneiderman. Flowchart techniques for structured programming. ACM SIGPLAN Notices, 8(8):12--26, Aug. 1973.]]
63. N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for Java. In Proc. of the Twelfth International Conference on Compiler Construction (CC'03), pages 138--152, Warsaw, Poland, Apr. 2003. Springer Verlag.]]
64. K. Ostermann, M. Mezini, and C. Bockisch. Expressive pointcuts for increased modularity. In A. P. Black, editor, Proc. of the Ninetieth European Conference on Object-Oriented Programming (ECOOP'05), volume 3086 of Lecture Notes in Computer Science, pages 214--240, Glasgow, UK, July 25-29 2005. Springer Verlag.]]
65. J. K. Ousterhout. Tcl: An embeddable command language. In Proc. of the Winter 1990 USENIX Conference, pages 133--146, Wasington, D.C., Jan. 1990.]]
66. S. Paul and A. Prakash. Querying source code using an algebraic query language. In H. A. Müller and M. Georges, editors, Proc. of the Tenth IEEE International Conference on Software Maintenance (ICSM'94), pages 127--136, Victoria, BC, Canada, Sept. 1994. IEEE Computer.]]
67. Reasoning Systems. REFINE User's Manual, 1988.]]
68. N. Rutar, C. B. Almazan, and J. S. Foster. A comparison of bug finding tools for Java. In Proc. of the Fifteenth International Symposium on Software Reliability Engineering (ISSRE 2004), pages 245--256, Saint-Malo, Bretagne, France, Nov. 2-5 2004. IEEE Computer Society Press.]]
69. N. Schärli, S. Ducasse, O. Nierstrasz, and A. P. Black. Traits: Composable units of behavior. In L. Cardelli, editor, Proc. of the Seventeenth European Conference on Object-Oriented Programming (ECOOP'03), volume 2743 of Lecture Notes in Computer Science, pages 248--274, Darmstadt, Germany, July 21-25 2003. Springer Verlag.]]
70. N. Schärli, S. Ducasse, O. Nierstrasz, and R. Wuyts. Composable encapsulation policies. In M. Odersky, editor, Proc. of the Eighteenth European Conference on Object-Oriented Programming (ECOOP'04), volume 3086 of Lecture Notes in Computer Science, pages 26--50, Oslo, Norway, June 2004. Springer Verlag.]]
71. C. Smith and S. Drossopoulou. Chai: Traits for Java-like languages. In A. P. Black, editor, Proc. of the Ninetieth European Conference on Object-Oriented Programming (ECOOP'05), volume 3086 of Lecture Notes in Computer Science, Glasgow, Scotland, July 25-29 2005. Springer Verlag.]]
72. T. Strelich. The Software Life Cycle Support Environment (SLCSE): a computer based framework for developing soft. sys. In Proc. of the Third ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (SDE'88), pages 35--44, Boston, Massachusetts, 1988. ACM Press, New York, NY, USA.]]
73. B. Stroustrup. The C++ Programming Language. Addison-Wesley Publishing Company, Reading, Massachusetts, third edition, 1997.]]
74. B. Stroustrup and G. D. Reis. Concepts-design choices for template argument checking. ISO/IEC JTC1/SC22/WG21 no. 1536, 2003.]]
75. S. T. Taft and R. A. Duff, editors. Ada 95 Reference Manual, Language and Standard Libraries, International Standard ISO/IEC 8652: 1995(E), volume 1246 of LNCS. Springer Verlag, 1997.]]
76. M. Tatsubori, S. Chiba, K. Itano, and M.-O. Killijian. Openjava: A class-based macro system for java. In W. Cazzola, R. J. Stroud, and F. Tisato, editors, Proc. of the First OOPSLA Workshop on Reflection and Software Engineering, volume 1826 of Lecture Notes in Computer Science, pages 117--133, Denver, CO, USA, Nov. 1999. OOPSLA'99, Springer Verlag.]]
77. A. van Gelder, K. Ross, and J. S. Schlipf. The well-founded semantics for general logic programs. Journal of the ACM, 38(3):620--650, 1991.]]
78. J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analyses using binary decision diagrams. In Proc. of the Conference on Programming Language Design and Implementation (PLDI) (PLDI'04), pages 131--144,Washington, DC, June 9-11 2004. ACM Press, New York, NY, USA.]]
79. P.-C. Wu. On exponential-time completeness of the circularity problem for attribute grammars. ACM Transactions on Programming Languages and Systems, 26(1):186--190, 2004.]]
80. M. M. Zloof. Query By Example. In Proceedings of the National Computer Conference, pages 431--438, Anaheim, CA, May 1975.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages