Tracing and Explaining the Execution of CLP(FD) Programs in SICStus Prolog

Ågren, Magnus (2002) Tracing and Explaining the Execution of CLP(FD) Programs in SICStus Prolog. [SICS Report]



The increasing interest in Constraint Programming (CP) we now witness gives rise to a demand for new and improved debugging techniques. Graphical tools, such as constraint- and search-tree visualizers, seem to be appropriate to get a general understanding of the complex process of constraint solving. However, many such tools have been built in an ad hoc way, forcing the developer to, for each new tool, provide relevant information from the constraint solver. In this thesis, we present a solution to the problem, limiting ourselves to Constraint Logic Programming over Finite Domains (\clpfd). In order to do this, we come up with a trace structure for describing the execution of \clpfd\ programs in detail. The trace structure consists of various trace events, each trace event containing different information depending on when in the solving process it is created. Among other things, the trace structure contains information about constraint posting, constraint awakening and domain narrowing. We also incorporate explanations in the trace structure, i.e.\ reasons for why certain solver actions occur. Furthermore, we come up with a format for describing the execution of the filtering algorithms of global constraints. An implementation of the trace structure in \sicstus\ Prolog is also presented, as well as a tool using the trace; an extension to the ordinary Prolog debugger.

Item Type:SICS Report
Uncontrolled Keywords:Constraint, Finite Domain, Debugging, Event Trace, SICStus, Prolog
ID Code:2260
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:03

Repository Staff Only: item control page