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

Abstract: 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.