Relational programming with CrocoPat

ABSTRACT

Many structural analyses of software systems are naturally formalized as relational queries, for example, the detection of design patterns, patterns of problematic design, code clones, dead code, and differences between the as-built and the as-designed architecture. This paper describes CrocoPat, an application-independent tool for relational programming. Through its efficiency and its expressive language, CrocoPat enables practically important analyses of real-world software systems that are not possible with other graph analysis tools, in particular analyses that involve transitive closures and the detection of patterns in graphs. The language is easy to use, because it is based on the well-known first-order predicate logic. The tool is easy to integrate into other software systems, because it is a small command-line tool that uses a simple text format for input and output of relations.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 2: G. Antoniol , R. Fiutem , L. Cristoforetti, Design Pattern Recovery in Object-Oriented Software, Proceedings of the 6th International Workshop on Program Comprehension, p.153, June 24-26, 1998
• 3: Basil Becker , Dirk Beyer , Holger Giese , Florian Klein , Daniela Schilling, Symbolic invariant verification for systems with dynamic structural adaptation, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134297]
• 4: Rudolf Berghammer , Barbara Leoniuk , Ulf Milanese, Implementation of Relational Algebra Using Binary Decision Diagrams, Revised Papers from the 6th International Conference and 1st Workshop of COST Action 274 TARSKI on Relational Methods in Computer Science, p.241-257, October 16-21, 2001
• 5: Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 6: Dirk Beyer , Claus Lewerentz, CrocoPat: Efficient Pattern Analysis in Object-Oriented Programs, Proceedings of the 11th IEEE International Workshop on Program Comprehension, p.294, May 10-11, 2003
• 7: D. Beyer and A. Noack. Crocopat 2.1 Introduction and reference manual. Technical Report CSD-04-1338, University of California, Berkeley, 2004.
• 8: Dirk Beyer , Andreas Noack , Claus Lewerentz, Efficient Relational Calculation for Software Analysis, IEEE Transactions on Software Engineering, v.31 n.2, p.137-149, February 2005 [doi>10.1109/TSE.2005.23]
• 9: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 10: J. R. Burch , E. M. Clarke , K. L. McMillan , D. L. Dill , L. J. Hwang, Symbolic model checking: 1020 states and beyond, Information and Computation, v.98 n.2, p.142-170, June 1992 [doi>10.1016/0890-5401(92)90017-A]
• 11: Yih-Farn Chen , Emden R. Gansner , Eleftherios Koutsofios, A C++ Data Model Supporting Reachability Analysis and Dead Code Detection, IEEE Transactions on Software Engineering, v.24 n.9, p.682-694, September 1998 [doi>10.1109/32.713323]
• 12: Oliver Ciupke, Automatic Detection of Design Problems in Object-Oriented Reengineering, Proceedings of the Technology of Object-Oriented Languages and Systems, p.18, August 01-05, 1999
• 13: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 14: Hoda Fahmy , Richard C. Holt, Software Architecture Transformations, Proceedings of the International Conference on Software Maintenance (ICSM'00), p.88, October 11-14, 2000
• 15: L. Feijs , R. Krikhaar , R. Van Ommering, A relational approach to support software architecture analysis, Software—Practice & Experience, v.28 n.4, p.371-400, April 10, 1998 [doi>10.1002/(SICI)1097-024X(19980410)28:4<371::AID-SPE154>3.0.CO;2-1]
• 16: Mehdi T. Harandi , Jim Q. Ning, Knowledge-Based Program Analysis, IEEE Software, v.7 n.1, p.74-81, January 1990 [doi>10.1109/52.43052]
• 17: John Hartman, Understanding natural programs using proper decomposition, Proceedings of the 13th international conference on Software engineering, p.62-73, May 13-17, 1991, Austin, Texas, United States
• 18: Richard C. Holt, Structural Manipulations of Software Architecture Using Tarski Relational Algebra, Proceedings of the Working Conference on Reverse Engineering (WCRE'98), p.210, October 12-14, 1998
• 19: Daniel Jackson, Automating first-order relational logic, Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering: twenty-first century applications, p.130-139, November 06-10, 2000, San Diego, California, United States
• 20: Daniel Jackson, Alloy: a lightweight object modelling notation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.2, p.256-290, April 2002 [doi>10.1145/505145.505149]
• 21: R. Kazman , M. Burth, Assessing Architectural Complexity, Proceedings of the 2nd Euromicro Conference on Software Maintenance and Reengineering ( CSMR'98), p.104, March 08-11, 1998
• 22: Rudolf K. Keller , Reinhard Schauer , Sébastien Robitaille , Patrick Pagé, Pattern-based reverse-engineering of design components, Proceedings of the 21st international conference on Software engineering, p.226-235, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302622]
• 23: Christian Kramer , Lutz Prechelt, Design Recovery by Automated Search for Structural Design Patterns in Object-Oriented Software, Proceedings of the 3rd Working Conference on Reverse Engineering (WCRE '96), p.208, November 08-10, 1996
• 24: Jens Krinke, Identifying Similar Code with Program Dependence Graphs, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.301, October 02-05, 2001
• 25: Juergen Ebert , Bernt Kullbach , Andreas Winter, Querying as an Enabling Technology in Software Reengineering, Proceedings of the Third European Conference on Software Maintenance and Reengineering, p.42, March 03-05, 1999
• 26: B. J. MacLennan, Overview of relational programming, ACM SIGPLAN Notices, v.18 n.3, March 1983 [doi>10.1145/988209.988213]
• 27: A. O. Mendelzon and J. Sametinger. Reverse engineering by visualizing and querying. Software -- Concepts and Tools, 16(4):170--182, 1995.
• 28: Kim Mens , Roel Wuyts , Theo D'Hondt, Declaratively Codifying Software Architectures Using Virtual Software Classifications, Proceedings of the Technology of Object-Oriented Languages and Systems, p.33, June 07-10, 1999
• 29: Gail C. Murphy , David Notkin , Kevin J. Sullivan, Software Reflexion Models: Bridging the Gap between Design and Implementation, IEEE Transactions on Software Engineering, v.27 n.4, p.364-380, April 2001 [doi>10.1109/32.917525]
• 30: Jörg Niere , Wilhelm Schäfer , Jörg P. Wadsack , Lothar Wendehals , Jim Welsh, Towards pattern-based design recovery, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581382]
• 31: Richard A. O'Keefe, The craft of Prolog, MIT Press, Cambridge, MA, 1990
• 32: Alex Quilici, A memory-based approach to recognizing programming plans, Communications of the ACM, v.37 n.5, p.84-93, May 1994 [doi>10.1145/175290.175301]
• 33: Charles Rich , Linda M. Wills, Recognizing a Program's Design: A Graph-Parsing Approach, IEEE Software, v.7 n.1, p.82-89, January 1990 [doi>10.1109/52.43053]
• 34: J. T. Schwartz, Automatic data structure choice in a language of very high level, Communications of the ACM, v.18 n.12, p.722-728, Dec. 1975 [doi>10.1145/361227.361235]
• 35: Mohlalefi Sefika , Aamod Sane , Roy H. Campbell, Monitoring compliance of a software system with its high-level design models, Proceedings of the 18th international conference on Software engineering, p.387-396, March 25-29, 1996, Berlin, Germany
• 36: F. Shull, W. L. Melo, and V. R. Basili. An inductive method for discovering design patterns from object-oriented software systems. Technical Report CS-TR-3597, University of Maryland, 1996.
• 37: Swedish Institute of Computer Science. Quintus Prolog User's Manual, 2003.
• 38: Paolo Tonella , Giulio Antoniol, Object Oriented Design Pattern Inference, Proceedings of the IEEE International Conference on Software Maintenance, p.230, August 30-September 03, 1999
• 39: Michael Widenius , Paul DuBois , Davis Axmark, Mysql Reference Manual, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 40: K. Wong. Rigi User's Manual, Version 5.4.4, 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Data abstraction
        D.2.13 Reusable Software
            Subjects: Reusable libraries
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Design, Languages

Keywords:
BDD, graph models, pattern matching, predicate logic, relational algebra, software analysis, transitive closure