CrocoPat: A Tool for Simple and Efficient Relational Programming
Simon Fraser University (SFU), CanadaEcole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
University of California at Berkeley, USA
Brandenburg University of Technology at Cottbus, Germany
Objectives
- Relational programming
CrocoPat manipulates relations of any arity, including graphs (which are binary relations). Its simple and expressive query and manipulation language RML is based on first-order predicate calculus. The implementation is based on the data structure binary decision diagram (BDD), which is well-known as a compact representation of large relations in computer-aided verification. CrocoPat is easy to integrate with other tools because it reads and writes relations from and to files in the simple relational text format RSF. One way of extracting relations in RSF format from a given source-code project is to use a combination of Doxygen and CCVisu.
- Comprehension and assessment
of
large
software systems
Many structural analyses of software systems can be formalized as relational queries, for example the detection of design patterns, of patterns of problematic design, of code clones, of dead code, and of differences between the as-built and the as-designed architecture. 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.
- High level
BDD package
While standard BDD packages provide operations for manipulating relations over bits, the CrocoPat library allows the manipulation of relations over strings. It relieves programmers of mapping strings to binary encodings and user variables to BDD variables.
Download
- CrocoPat is free software (LGPL License)
- Current version: Browse through repository, or Check it out.
- CrocoPat 2.1.4 (2008-02-15): Download zipped source code, or Browse through repository,
or download binaries for GNU/Linux x86_64 and x86_32, or Win32 (based on cygwin, download cygwin1.dll).
- Benchmarks used in our
TSE'05 article "Efficient Relational Calculation for Software Analysis" (browse directory)
for comparison with RelView, Grok, MySQL and Quintus Prolog.
(includes source-code repository and downloads).
Archive: Download old binaries, C++ sources, and examples
FSF Free Software Directory: http://directory.fsf.org/math/CrocoPat.html
Documentation
CrocoPat 2.1 Introduction and Reference Manual (html version, all)API and Source-Code Documentation: Files and Classes
Fact Extractors: There are several tools around for extracting relations from software systems. We currently use a combination of Doxygen and CCVisu to generate RSF files as input for CrocoPat.
Full references and electronic versions of the articles are available at our Publications page.
- Dirk Beyer. Relational Programming with CrocoPat. ICSE 2006.
Tool paper.
- Dirk Beyer, Andreas Noack, Claus Lewerentz. Efficient
Relational Calculation for Software Analysis. TSE 2005.
Introduces RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. Evaluates RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system.
- Dirk Beyer, Andreas Noack. CrocoPat
2.1
Introduction and Reference Manual. Technical Report 2004.
A tutorial and user's guide for CrocoPat, defines and explains the syntax and semantics of the extended language. - Dirk Beyer, Andreas Noack,
Claus Lewerentz. Simple
and Efficient Relational Querying of Software Structures. WCRE 2003.
CrocoPat's language, an introduction to the BDD-based implementation, application examples, and performance measurements. - Dirk Beyer, Claus Lewerentz. CrocoPat:
Efficient Pattern
Analysis in Object-Oriented Programs. IWPC 2003.
A short overview of the main features of CrocoPat.
Users and Friends of CrocoPat
- A performance comparison of three tools for pattern detection:
Lajos Jeno Fülöp, Tamas Gyovai, Rudolf Ferenc. Evaluating C++ Design Pattern Miner Tools. Proc. SCAM, pages 127-138, IEEE, 2006.
Author: Dirk Beyer, my project pages: BLAST, CCVisu, Chic, CrocoPat, CSIsat, Rabbit