Possibilities of visualizing the solution process of constraint logicbased systems by the example of SWI-Prolog’s CLP(FD) library

Contents

Abstract

Contents

Figures

Abbreviations

1 Introduction

2 Literature review
2.1 Prolog and SWI Prolog
2.2 Constraint logic programming
2.3 SWI-Prolog’s CLP(FD) library
2.4 Existing visualization tools and other related work
2.4.1 Search tree visualization
2.4.2 Combining propagation information and search tree visualization
2.4.3 Visualizing variables and constraints
2.4.4 CLPGUI

3 Requirements

4 Architecture & Implementation
4.1 Owl Tracer
4.2 Owl Inspector
4.2.1 Technologies
4.2.2 Architecture & Implementation
4.2.3 3D View
4.2.4 Search tree
4.3 Data exchange
4.4 Additional Work

5 Results
5.1 Exploration of constraints and their resulting effect
5.2 Exploration of labeling strategies
5.3 Possible other applications
5.3.1 Exploration of failures
5.3.2 Performance debugging and general debugging

Contents v

6 Discussion

7 Conclusion

Acknowledgments

References

Abstract

Constraint logic programming is a useful and elegant way to solve complex problems. Through its declarative nature, problems can often be solved in a few lines of code. However, the implementation and flow of a program are of- ten hard to comprehend—even with proper documentation. This thesis ex- plores the possibilities of visualizing the solution process of constraint logic- based systems by the example of SWI-Prolog’s CLP(FD) library. It explores to what extent a dynamic, GUI-based visualization can help comprehend con- straint logic programs. To achieve that, the thesis focuses on the development of a GUI that is capable of visualizing the solving process of the SWI CLP(FD) system. As a result, the thesis presents, to the best of the author’s knowledge, the first application capable of visualizing SWI CLP(FD) programs and show- cases how this application can be used in an educational context.

Figures

Figure 1: A sample CLP program in SWI’s syntax

Figure 2: Posting the query to the Prolog interpreter

Figure 3: CLP execution

Figure 4: The map coloring problem by the example of the territories of Australia

Figure 5: Implementation of the map coloring problem

Figure 6: Solution to the map coloring problem

Figure 7: Abstraction of the search tree

Figure 8: The APT tool

Figure 9: OPL Studio’s search tree with the choice stack displayed on the lower left

Figure 10: The christmas tree view

Figure 11: Domain values over time as implemented in the VIFID tool. The top row shows the final value. Red marks the already reduced values

Figure 12: The proposed 3D view

Figure 13: 3D view as implemented in CLPGUI

Figure 14: CLPGUI’s 3D search tree

Figure 15: Example usage of the tracer predicate

Figure 16: Example of the tracer predicate with separate name assignments

Figure 17: The execution flow of the trace predicates

Figure 18: The Owl Tracer module in the context of the entire system

Figure 19: The annotated map coloring problem

Figure 20: Query of the annotated map coloring problem

Figure 21: The GUI’s React components

Figure 22: The GUI’s general layout with the Panel components highlighted in yellow

Figure 23: The axes of the 3D view

Figure 24: The time wind panel selecting timestamps from 2 to

Figure 25: Panel to toggle variables

Figure 26: 3D view visualizing the map coloring problem

Figure 27: The overall architecture of the GUI, the tracer, and their communication

Figure 28: A little annotated CLP program

Figure 29: The from the program in Figure 28 generated trace file

Figure 30: Example CLP program to showcase all_different/1 and all_distinct/

Figure 31: Propagation of all_diff/

Figure 32: Propagation of all_dist/

Figure 33: Sudoku problem with all_distinct/ Figures vii

Figure 34: Sudoku problem with all_different/1, failing to find a solution

Figure 35: Propagation of the problem with the default labeling strategy

Figure 36: Propagation of the problem with the max value selection strategy

Figure 37: The search tree view of the problem using the default labeling option. The time wind feature was used to focus on the labeling process exclusively

Figure 38: Figure 38: The search tree view of the problem using the min down labeling option. The time wind feature was used to focus on the labeling process exclusively

Abbreviations

Abbildung in dieser leseprobe nicht enthalten

1 Introduction

Constraint logic programming (CLP) has come a long way since its original in- troduction in 1987.¹ The CLP paradigm has managed to successfully combine logic programming with constraint programming² and is applied in a wide range of fields, such as bioinformatics, planning, scheduling problems, and data- bases.³

Alain Colmerauer, the original creator of Prolog,⁴ introduced the first CLP language with Prolog III,⁵ after laying the theoretical foundation for the CLP paradigm with Prolog II.⁶

Since then, almost any Prolog version and dialect has shipped with its own CLP library or extension. Today, SWI-Prolog is the most popular Prolog dialect and one of the few that are still in active development. It comes with its own set of built-in CLP libraries which have been originally introduced by Markus Triska. Triska’s CLP libraries are in many ways an evolution of previous existing libraries, especially in regard to their correctness.⁷

While CLP systems can be described in general, they usually are restricted and defined over certain domains. The most widely utilized is the domain over finite domains. CLP over finite domains, for short CLP(FD), is able to reason over a finite range of integers.⁸ This thesis concerns itself with CLP(FD) exclusively.

Through their expressive constraints and powerful constraint solvers, CLP sys- tems in general often allow to solve complex problems in a very declarative and elegant way—often resulting in surprisingly compact programs.⁹ This declarative nature, however, comes with its own set of problems. Combined with the non-transparent nature of the process of domain propagation, domain reduction and the at times counterintuitive behavior of Prolog’s backtracking search, CLP programs can be hard to comprehend and therefore hard to debug, understand, extend and improve.¹⁰

To address this issue, many graphical visualization tools for CLP systems have been developed and successfully applied. CLP programs need specialized visu- alization techniques, since traditional program visualizations are not sufficient to comprehend and faithfully display the execution of a CLP system.¹¹

While many different tools for a range of CLP languages do exist, there is, to the best of the author’s knowledge, no tool to visualize SWI-Prolog’s CLP(FD) system. The thesis sets out to fill this gap.

The aim of this work is to develop a modern graphical user interface that is ca- pable of visualizing the process of SWI-Prolog’s CLP(FD) system, its domain propagation, reduction, and labeling algorithm. It attempts to provide, by the means of different visualizations, all the information necessary to better com- prehend a given CLP program. The thesis especially focuses its efforts on devel- oping the GUI for an educational application. It attempts this by providing in- tuitive visualizations from which both the concepts of the CLP system in gen- eral and the implementation of a given CLP program can be taught and under- stood.

The thesis is structured as follows: Chapters 2.1 and 2.2 give a short history of Prolog and CLP. Chapter 2.3 discusses SWI-Prolog’s CLP(FD) system in great detail. Chapter 2.4 gives an overview of related literature and visualization tools, describing different approaches to visualize CLP systems. Then, Chapter

3 lays out the general requirements for the application. Chapter 4 elaborates on the architecture as well as the implementation of the application. Chapter 5 proceeds to evaluate the developed system by exploring first results of using the GUI to visualize SWI-Prolog CLP(FD) programs. Based on these results, Chapter 5 discusses how the requirements laid out were fulfilled and explores first findings obtained by using the implemented GUI practically. It also points to advantages and disadvantages of the chosen implementation and, building on that, discusses possible future improvements and extensions. Lastly, Chapter 6 gives a short conclusion.

2 Literature review

2.1 Prolog and SWI Prolog

Invented in 1970 by the French computer scientist Alain Colmerauer, Prolog is considered to be the first language and harbinger of the logic programming par- adigm.¹²

This is all the more fascinating considering that Prolog is still the most popular and widely used programming language of that category.¹³ Prolog’s most popular dialect is SWI-Prolog.¹⁴ It is released under the Simplified BSD License and its source code can be openly accessed at GitHub. SWI-Prolog is available crossplatform and provides feature-rich libraries one would expect from a modern programming language. It is hence well suited to implement Prolog applications on modern computing environments.¹⁵

2.2 Constraint logic programming

It is no coincidence that the original inventor of Prolog, Alain Colmerauer, can also be considered the forethinker and developer of the first CLP language.¹⁶ A CLP language is a fusion of a logic programming language with concepts from the constraint programming paradigm.¹⁷ Constraint programming describes the programming paradigm of finding a solution by imposing a set of constraints over variables. Finding a solution for a constraint satisfaction problem (CSP) is defined as assigning values to all involved variables so that all imposed con- straints are satisfied.¹⁸

Colmerauer first paved the way for the CLP paradigm with Prolog II’s term equation features and subsequently introduced the first CLP language with Prolog III.¹⁹

However, the key observation, that led to the CLP paradigm, was made by Jaffar and Lassez shortly after the introduction of Prolog II.²⁰ They observed that Prolog II’s ability to handle term equations were essentially just another form of applying constraints to variables (since constraints can be seen as relations). Furthermore, they showed that the constraint solving process can be seen as a generalization of Prolog’s unification process.

Logic programming and constraint programming also share similarities on a conceptual level. Both share a very declarative syntax. A CSP is, as stated by Triska, described as precise as possible, while the actual solution to the problem is left to the system.²¹

A CLP language is always described in relation to its domain. CLP(X) describes a CLP system over the domain of X. While there is a range of possible CLP domain types, most CSPs can be expressed and solved by CLP over the domain of finite integers, for short CLP(FD). CLP(FD) has the advantage that commonly known arithmetic relations can be used to constrain domains. CLP(FD) has become the most popular instance of constraint logic programming.²² This thesis concerns itself with CLP(FD) exclusively.

2.3 SWI-Prolog’s CLP(FD) library

Since Prolog III, almost all Prolog dialects have shipped with their own built-in CLP library. In SWI-Prolog, the CLP(FD) system was developed by Markus Triska.²³ His CLP(FD) library can be seen, in many ways, as an evolution of previous existing CLP libraries, especially in regards of its correctness.

In this and following chapters, SWI-Prolog’s CLP(FD) system is often referenced as the CLP system.

In contrast to all other CLP libraries at the time, Triska’s CLP(FD) library came with a range of novel features to increase the correctness of the system, the most notable features being:²⁴

- the first system to reason over infinitely large integers
- the first system which guarantees termination of the constraint propa- gation process (which is discussed momentarily)

Since Triska’s system is able to reason over arbitrarily large integers, one might ask why it is still an instance of CLP(FD), the answer gives Triska himself:

“ One can hardly speak of finite domain constraint solvers any more when domains can clearly be infinite as well. Still, given that there are always technological limits for the representation of any particular in- teger in a CLP(FD)system, calling them CLP(Z) seems at least equally deceiving. ” ²⁵

The subsequent paragraphs give a short introduction to SWI-Prolog’s CLP(FD) library and CLP in general. They discuss the execution flow of a CLP program and its terminology. First, based on Stuart and Peter, a formal description of a constraint satisfaction problem is given.²⁶ This description is then underlined by a practical example.

According to Stuart and Peter, a CSP can be defined as a set of variables which are constrained by a set of constraints :

Abbildung in dieser leseprobe nicht enthalten

For each variable, a domain is defined. Each domain is a set that contains all possible values can assume. In the case of SWI-Prolog’s CLP(FD), can be defined as follows:

Each domain can be restricted by one or multiple constraints. A constraint , according to Stuart and Peter, can be seen as a relation between a subset of variables in .

For example, let and let their corresponding domains

all have the domain !" #$. Also, the following constraints shall be defined:

Abbildung in dieser leseprobe nicht enthalten

Just by evaluating the constraints, the CLP system could easily compute the re-

sult set " ' ( which can be translated to ", ' (.

Figure 1 shows how this CSP can be solved in SWI-Prolog’s syntax.

In this scenario, the CLP system was able to find a concrete solution with constraint propagation and reduction only. A constraint propagator is a function that performs a reduction on a domain by filtering out all values that violate any constraints imposed on the domain’s corresponding variable.²⁷

In the given example, the constraint propagator of #</2 was able to reduce all the domains of to a single value. Therefore, yielding a valid solution.

Since constraints can be seen as relations between variables, the alteration of one variable’s domain likely affects other constraints in which the variable is involved in as well.²⁸ Consider, for example, the above given constraint : it constraints both and . Now, when is applied to as well, constraining it further and altering its domain, the change needs to be propagated to , so that may reason over the change. This propagation process is called domain propagation.²⁹

Thus, the reduction of any domain through a constraint may in turn trigger another constraint propagator acting on another domain which can lead to further domain reductions. In complex programs, one domain reduction can lead to a whole range of further propagators being executed.³⁰

Abbildung in dieser leseprobe nicht enthalten

Figure 1: A sample CLP program in SWI’s syntax

Abbildung in dieser leseprobe nicht enthalten

Figure 2: Posting the query to the Prolog interpreter

Since most CLP programs are far more complex than the given example, con- straint propagation alone seldom leads to a valid solution. Some form of search needs to be involved. This search is usually performed by systematically trying out different values from each variable’s domain until a set of values is found that satisfies all constraints, consequently yielding a solution. This process is called labeling.³¹

A variable can be instantiated or labeled to any value of its corresponding do- main. In Prolog, a variable that assumed a concrete value is called a ground var- iable.³²

As soon as a variable is ground to a value of its domain, the domain of the var- iable is obviously affected as well. The domain now formally consists of one value, the value to which the variable was ground. This triggers domain propa- gation and domain reductions. Thus, to find a valid solution, the labeling and domain propagation processes are interleaved. Should an instantiation of a var- iable to a value not yield a valid solution, backtracking on the variable is in- voked, and the variable becomes unground again. The search is then continued

from the latest choice point.³³ Figure 3 illustrates this process in a simplified depiction.

Abbildung in dieser leseprobe nicht enthalten

Figure 3: CLP execution

The well-known map coloring problem is an example of a CSP that can’t be solved by applying constraints alone.³⁴ Figure 5 shows an implementation in the SWI syntax. Figure 4 shows the corresponding map. A valid solution to this problem is a set of variables which depict the involved regions, assigned to col- ors under the constraint that all neighboring regions must be assigned different colors.³⁵

Abbildung in dieer Leseprobe nicht enthalten

Figure 4: The map coloring problem by the example of the territories of Australia³⁶

Abbildung in dieser leseprobe nicht enthalten

Figure 5: Implementation of the map coloring problem

Abbildung in dieser leseprobe nicht enthalten

Figure 6: Solution to the map coloring problem

Figures 5 and 6 show that the program is separated into two distinct parts:

1. the regions/1 predicate with the definition of all variables and their constraints
2. the search part, seen in Figure 6, utilizing the labeling predicate, posted as a query to the system

This is good practice, and usually how a CLP program is structured.³⁷

The labeling process gives opportunity to apply a range of different strategies. During the process, a choice must be made in which order the variables are in- stantiated, as well as the order in which values from the variable’s correspond- ing domain are tried out. The efficiency of these strategies may differ signifi- cantly from program to program, which is why no general recommendation can be given.³⁸

SWI-Prolog’s CLP(FD) library offers a range of predefined strategies.³⁹ The default variable instantiation strategy is to label the values in the order they appear in the given list. The default value selection strategy is trying the domain’s values in ascending order.

In Chapter 5, the thesis gives a comparison of some labeling strategies utilizing the through this thesis developed visualization tool.

In short, the execution of the CLP system can be roughly laid out as follows:

1. the evaluation of all posted constraints
2. the initial domain propagation leading to domain reductions and possi- bly further domain propagations
3. the labeling process systematically trying out values
4. further domain propagation and reduction
5. eventually, the obtainment of a valid result or the report of a failure

2.4 Existing visualization tools and other related work

This chapter provides a review of a range of literature discussing and presenting different visualization paradigms and how some of them are implemented in existing visualization tools.

The tools mentioned in this chapter being:

- APT Tool
- VIFID/TRIFID Tool
- ILOG OPL Studio
- CLPGUI

The following reviewed literature depicts, to the best of the author’s knowledge, the most recent contributions to this field of research. It must be noted though, that all of the programs reviewed in the subsequent paragraphs are no longer under active development, and for most no executable version and neither the source code can be acquired. Also, none of these tools are compatible with SWI- Prolog. However, much insight is still to be gained by examining previous ap- proaches and results made in the field. The focus of the subsequent paragraphs is on acquiring an overview of the applied visualization paradigms in the field; since the tools, especially their visualizations, have aged badly, the focus is not so much on their technical implementation.

Before reviewing any tool, however, it is essential to lay out some of the funda- mentals. Carro and Hermenegildo discuss the problems of applying traditional visualization techniques to CLP programs.⁴⁰ They note that program visualiza- tion usually focuses on the representation of the program flow or on the evolu- tion of the program’s variables over time. In imperative and functional pro- gramming, this process is relatively straightforward. However, classical repre- sentations of variables, such as flowcharts or block diagrams, can’t be readily applied to CLP systems. CLP variables are often complex structures which rep- resent their domain and the constraints imposed on them.⁴¹ Carro and Hermenegildo further add that the labeling process is a vital part of every CLP

system and is relying on many internal mechanics (domain propagation, do- main reduction, labeling). So a proper, specialized visualization of this process is mandatory to understand, debug and improve the CLP program. A sole value or control-based depiction is not sufficient to comprehend a CLP system to its full extent.⁴²

Carro and Hermenegildo also provide an interesting overview of different applications of CLP visualization tools, they categorize as follows:⁴³

- Debugging: Visualization can be a complimentary aide alongside asser- tions or text-based debugging
- Tuning and optimizing or performance debugging: Visualization may help to point out performance problems and bottlenecks
- Teaching: Visualization may help to generally better understand CLP systems and programs

However, these use cases don’t have to be looked at in isolation, as Carro and Hermenegildo state, they can coexist and even complement each other.

Fages et al. and Bracchi et al. provide a categorization from a technical point of view. Technically, they argue, visualization tools can be categorized as fol- lows:⁴⁴

- Dynamic visualization tools: The visualization is connected to the CLP system in real time, and both sides can exchange information and direc- tives with each other.
- Post-mortem visualization tools: Tools applied after the execution of the program. The data to visualize is obtained during the execution and saved for further processing.
- Dynamic visualization and control tools: In addition to a dynamic visu- alization, these tools also enable to alter or control the execution of the CLP program through the GUI.

Lastly, Carro and Hermenegildo argue that three visualization objectives exist:⁴⁵

- visualization of the execution or control flow
- visualization of variable values over time
- visualization of constraints over variables

According to Carro and Hermenegildo, these three visualization paradigms often exist alongside. And in fact, all visualization techniques discussed in the subsequent chapters implement and, in some form, combine these different paradigms to provide a better visualization result.

2.4.1 Search tree visualization

Any Prolog execution can be visualized in the form of a classic search tree.⁴⁶ Building on that, Carro and Hermenegildo discuss ways in which the execution flow of a CLP program can be visualized in the form of an augmented search tree.⁴⁷

According to them, the execution of a CLP program can be observed from the following contexts:

- the programmed search, meaning the actual execution of the predicates as programmed by the user
- the solver operations, meaning the internal operations performed, mostly during the labeling process

The visualization of the programmed search, so they argue, can be depicted by a search tree whose nodes represent predicate calls in the form of successes, redos, and failures.

They then propose to use the search tree of the programmed search as a framework on which further visualizations can be attached to. For example, clicking on a node may provide additional information about the internal state of the labeling process at this point.

[...]

---

¹ Jaffar and Lassez 1987.

² Apt 2003.

³ Wallace 1996; Backofen and Gilbert 2006; Gavanelli and Rossi 2010

⁴ Colmerauer and Roussel 1996.

⁵ Colmerauer 1990.

⁶ Jaffar and Lassez 1987.

⁷ Triska 2013.

⁸ Gavanelli and Rossi 2010.

⁹ Ibid.

¹⁰ Carro and Hermenegildo 2000a; Carro and Hermenegildo 2000b; Aggoun et al. 1997.

¹¹ Carro and Hermenegildo 2000a; Carro and Hermenegildo 2000b; Bracchi, Gefflot, and Paulin 2001; Fages, Soliman, and Coolen 2004.

¹² Colmerauer and Roussel 1996; Cohen 2004.

¹³ TIOBE Index | TIOBE - The Software Quality Company 2018.

¹⁴ Wielemaker et al. 2012.

¹⁵ Wielemaker 2017.

¹⁶ Cohen 2004.

¹⁷ Gavanelli and Rossi 2010.

¹⁸ Apt 2003.

¹⁹ Colmerauer 1990; Jaffar and Lassez 1987.

²⁰ Jaffar and Lassez 1987.

²¹ Triska 2013.

²² Gavanelli and Rossi 2010.

²³ Triska 2013.

²⁴ Ibid.

²⁵ Ibid., 42.

²⁶ Stuart and Peter 2003.

²⁷ Triska 2013.

²⁸ Stuart and Peter 2003; Gavanelli and Rossi 2010.

²⁹ Triska 2013.

³⁰ Ibid.

³¹ Ibid.

³² Wielemaker 2017, 104.

³³ Triska 2013, 11; Gavanelli and Rossi 2010, 67-69.

³⁴ Stuart and Peter 2003, 138.

³⁵ Ibid.

³⁶ Ibid.

³⁷ Wielemaker 2017, 420-421.

³⁸ Triska 2013, 13-14.

³⁹ Wielemaker et al. 2014, 396-397.

⁴⁰ Carro and Hermenegildo 2000b.

⁴¹ Ibid.

⁴² Ibid.; Aggoun et al. 1997.

⁴³ Carro and Hermenegildo 2000b.

⁴⁴ Bracchi, Gefflot, and Paulin 2001; Fages, Soliman, and Coolen 2004.

⁴⁵ Carro and Hermenegildo 2000b.

⁴⁶ Wielemaker et al. 2014, 24.

⁴⁷ Carro and Hermenegildo 2000b.