Vincent Bloemen - Extending the Finite Domain Solver of GNU Prolog

author:Vincent Bloemen
title:Extending the Finite Domain Solver of GNU Prolog
company:Axini
keywords:model based testing, test data, test generation
committee:prof.dr. J.C. van de Pol (1st supervisor)
ir. H.M. van der Bijl
graduation date:1 May 2014

internship Axini

Abstract

In this project, several extensions to the GNU Prolog tool have been implemented. The underlying reason for these extensions is to improve the practical applicability of the tool for Axini’s purposes. This is because Axini makes use of GNU Prolog’s finite domain constraint solver in its Model-based Testing tool, called TestManager. The intended extensions for GNU Prolog constraint solver are:

to include negative values in the finite domain variables.
to improve the usability by preventing overflows from occurring.
to reduce/remove the limitations of the sparse domain representation.

This report discusses the methodology and techniques used for implementing the extensions. A focus is laid on correctness and performance. The report analyzes each extension in detail, after which possible alternatives are discussed. The chosen approaches are motivated and the implementation is discussed with the use of examples.

The results show that each extension is successfully implemented. The performance evaluation of this initial implementation shows encouraging results, with a limited slowdown factor compared to the original constraint solver. The developers of GNU Prolog are pleased with the results and aim to incorporate the extensions in a future release of GNU Prolog. 

 

References

  1. Vincent Bloemen, Daniel Diaz, Machiel van der Bijl and Salvador Abreu: Extending the Finite Domain Solver of GNU Prolog. In: Proceedings of the International Joint Workshop on Implementation of Constraint and Logic Programming Systems and Logic-based Methods in Programming Environments. RWTH Aachen Technical Report 2014-09. 2014 (Digital version available here)