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. Masters thesis, Uppsala University.



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:Thesis (Masters)
ID Code:3688
Deposited By:Magnus Ņgren
Deposited On:12 Oct 2009
Last Modified:18 Nov 2009 16:25

Repository Staff Only: item control page