JDLV is a new programming framework blending DLV with Java programming.

The framework is based on JASP, an hybrid language that transparently supports a bilateral interaction between Answer Set Programming and Java. A key ingredient of JASP is the mapping between (collections of) Java objects and ASP facts. Java Objects are mapped to logic facts (and vice versa) by adopting a structural mapping strategy similar to the one employed by ORM tools for retrieving/saving persistent objects from/to relational databases. In particular, JASP specifications are compliant with the JPA standard for Object-Relational Mapping to perfectly fit extensively-adopted enterprise application technologies.

The JDLV framework is tailored for DLV and includes:

  • JDLVc a compiler from JASP to Java
  • JDLV-plugin a plugin for the Eclipse TM Platform (www.eclipse.org)

JDLV Usage Example

A Java programmer can embed an DLV program inside obtaining a .jdlv file. For example the following Graph class has a method solving the well-known 3Colorability problem by exploiting a DLV program.

In detail, we define the Graph class has a method compute3Coloring(), which computesa 3-coloring of the instance at hand. The ASP code is embedded as-it-is in a module statement efining the body of method compute3Coloring(). Fields (containing collections of Java objects), such as arcs and nodes, are mapped to corresponding predicates arc and node, respectively. Moreover, the local variable res is mapped as output variable corresponding to predicate col. Intuitively, the meaning of this program is the following: when compute3Coloring() is called, the set nodes is transformed in a series of unary facts of the form node(x), one fact for each string x in nodes; similarly, each instance of Arc stored in variable arcs is transformed in a binary fact. Then, the generated facts are added to the ASP program which is evaluated. In case no 3-coloring exists variable res is set to null; else, when the first answer set is computed,for each fact col contained in the solution a new objectof the class Colored is created and added to res, which,in turn, is returned by the method. The above specification is specified in the file Graph.jdlv, that can be compiled by exploiting the JDLVccompiler to obtain a plain Java class embedding a call to DLV. The produced code is based on The DLV Wrapper Library.

JDLVc Overview

The JDLVccompiler produces plain Java classes which manage the generation of logic programs and control statements for the underlying call to DLV. Jdlvc is written in Java, and uses Java Reflection to analyze mappings (compile-time) and actual object types (runtime). An enhanced version of the DLV Java Wrapper library is used to implement the solving process trough a call to DLV. JDLVc’s compilation consists of fours steps: (1) input parsing and data structures creation; (2) predicate schemas creation and validation; generation of proper Java statements for (3) managing logic program creation, and (4) for controllingASP-solver execution and output-handling procedures.

JDLV-plugin Overview

The JDLVplugin extends Eclipse with the possibility of editing files in the JASP syntaxin a friendly environment featuring:

  • automatic completion for assisted editing logic program rules;
  • dynamic code checking and errors highlighting;
  • outline view, a visual representation and indexing JASP statements, and
  • automatic generation of Java code, by means of our Jdlvc compiler

Performance Data

Compiler performance

The following table reports the execution time needed by JDLVc to compile some test cases based thetwo largest encodings in Line of Code (LOC) employed in the System Track of the Third ASP Competition, and two synthetic examples:TwentyCalls.jdlv, a JASP filecontaining 20 JASP modules corresponding to 20 calls to DLV, and Huge.jdlv a huge JASP specification of 188938 LOC!!! The hardware used for the measurements is an 2.40GHzIntelTM Core i5 with 4,00 GB of RAM running WindowsTM 7 and Java TM 6.0.23

File name Size(KB) Size (LOC) DLV calls Compile time
SokobanDecizion.jdlv 9 205 1 70 ms
WeightAssignmentTree.jdlv 4 123 1 30 ms
TwentyCalls.jdlv 47 1509 20 51 ms
Huge.jdlv 7456 188938 1 4871 ms

JDLVc is very efficient, indeed in common cases it requires less than 0,7 seconds to process input files; the performance is not influenced by the presence of several calls to DLV in the same file.Note that, also in the presence of a very huge input file of 188938 Line Of Code (LOC) compilation times stay below 5 seconds for a large file of 7,5MB!.

Performance of the code produced by JDLVc

In order to compare the efficiency of the source code produced by JDLVc, we developed two Java programs that employ DLV for solving two well-known problems: Reachability and 3Colorability:

  • Reachability amounts to computing the transitive closure of a graph, and in particular we asked whether there exists a path from a given node X to a given node Y. Reachability is a Polynomial problem and is a typical Deductive Database benchmark.
  • 3Colorabilitys the problem of assigning to each node of a graph exactly one colour among three given ones in such a way that there is no pair of nodes connected by an arch having assigned the same color. 3Colorability is an NP-complete problem.

We have implemented, for each of the two problems, two equivalentversions of the above-mentioned Java programs, the first entirely developed in JASP and the second,developed by hand, implementing a call to DLV by exploiting the DLV Wrapper. The JASP version was obviously compiled by using JDLVc.

We have measured the execution times needed by for solving a number of instances of growing size of the two problems.

Overall Result

There is no noticeable difference in performance between the manually-encoded version and the one specified in JASP and generated by JDLVc in both Reachability and 3Colorability instances.

The overall time elapsed for solving all the instance is due to logic program evaluation, thus the object-to fact and fact-to object procedures produced by JDLVc are efficient.

Detailed results follow.

Reachability

The following two plots report the comparison between the manually encoded and the JDLVC-generated Java program calling DLV to solve the Reachability problem. The graph on the right report the execution times elapsed to solve instances from 330 KB up to 8250 KB. The two lines basically overlap, thus the code automatically generated is as efficient as the ad hoc solution. The same conclusion can be drawn by looking at the scatter plot on the left.

The following plot compares the overall execution timeof the JDLVc-generated version with an estimation of the time spent for generating facts from Java objects and generating Java Objects from the result computed by DLV.

Note that the object-to fact and fact-to object procedures coded by the compiler are very efficient and require only a minor part of the execution time and scale better than the entire process.

3Colorability

The following two plots report the comparison between the manually encoded and the JDLVC-generated Java program calling DLV to solve the 3Colorability problem. The graph on the right report the execution times elapsed to solve graph instances from 180 up to 500 nodes. The two lines basically overlap, thus the code automatically generated is as efficient as the ad hoc solution. The same conclusion can be drawn by looking at the scatter plot on the left.

The following plot compares the overall execution time of the JDLVc-generated version with an estimation of the time spent for generating facts from Java objects and generating Java Objects from the result computed by DLV.

Note that the object-to fact and fact-to object procedures coded by the compiler are very efficient and require only a minor part of the execution time and scale better than the entire process.

Programs and Instances

The package containing the Java code and the instances employed in the experiments reported above can be downloaded form this link.

Download