CrocoPat: A Tool for Simple and Efficient Relational Programming
Simon Fraser University (SFU), Canada
Ecole 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.
- 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
Project page available at Google Code: http://crocopat.googlecode.com/
(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
Author: Dirk
Beyer, my project pages: BLAST, CCVisu, Chic, CrocoPat, CSIsat, Rabbit