Recursion is nowadays taught to students since their rst programming days in order to embed it deeply in their brains. However, students' rst impact on Prolog programs execution sometimes weakens their faith in recursive programming thus invalidating our initial e orts. The selection and computation rules implemented by all Prolog systems, although clearly explained in textbooks, are hard to be interiorized by students also due to the poor system debugging primitives. Problems increase in Constraint Logic Programming when uni cation is replaced by constraint simpli cation in a suitable constraint domain. In this paper, we extend PrettyProlog, a light-weight Prolog interpreter written in Java capable of system primitives for SLD tree visualization, to deal with Constraint Logic Programming over Finite Domains. The user, in particular, can select the propagation strategies (e.g. arc consistency vs bound consistency) and can view the (usually hidden) details of the constraint propagation stage.
PrettyProlog was developed two years ago by a team of the University of
Genova, for providing concrete answers to demands raised by Prolog novices [
interpreter exist, starting from W-Prolog2. Although at a prototypical stage, PrettyProlog presents three features that, to the best of our knowledge, cannot be found together in any other Prolog implementation:
The desirable architectural features of PrettyProlog have been exploited in the research activity described in this paper where PrettyProlog has been extended for dealing with Constraint Logic Programming on Finite Domains (brie y, CLP(FD)). As a matter of fact, experience in teaching CLP(FD) evidenced further problems for students, rst of all the replacement of uni cation with constraint solving. The term 1 + 3 does not unify with the term 3 + 1. However, they are both considered as 4 by CLP(FD). Moreover, the constraint propagation stage is parametric on some choices. For instance, bounds consistency and arc consistency return di erent \results" to the constraint 2X = Y where the domain DX and DY of the variables X and Y are both the intervals 0::3 (DX = f0; 1g; DY = f0; 1; 2g in the former case, DX = f0; 1g; DY = f0; 2g in the latter case). Although di erent propagation techniques are studied in theory, Prolog interpreters supporting CLP(FD) usually implement only one of them, and students using di erent systems can be confused. Another source of confusion is introduced by some implementations of the SLD resolution with constraints that manage the ordering of literals in goals in a di erent way depending on whether they are constraint literals or user-de ned literals. Moreover, during constraint's solution search (if explicitly required by a labeling) an auxiliary tree named prop-labeling tree is created and visited. This tree is sometimes wrongly confused with the SLD tree.
The proposed extension of PrettyProlog, called PrettyCLP, has been developed to help the new CLP programmers in a deeper understanding of what happens during the execution of a CLP(FD) program. The basic procedures for constraint propagation have been implemented in Java, either in the case of (hyper) arc consistency or in the case of (hyper) bounds consistency. A labeling built-in has also been developed for the solution's search using a prop-labeling tree.
This paper is organized in the following way: Section 2 recalls the functionalities of PrettyProlog and its implementation; Section 3 provides some background on CLP; Section 4 describes the original contribution of this paper, namely the design and implementation of PrettyCLP. In particular, it discusses PrettyCLP syntax, the supported mechanism for constraint propagation and labeling, and the output renderer. Section 5 analyzes the related work and concludes by outlining some future extensions. 2 http://waitaki.otago.ac.nz/~michael/wp/
Functionalities PrettyProlog implements a Prolog engine able to deal with basic data types (integer and real numbers, lists, strings), and o ering metaprogramming facilities that, combined with the \cut" predicate, make the de nition of negation as failure possible. Despite to some simpli cations that were made during its design and implementation, sophisticated programs may be implemented with PrettyProlog thanks to these features.
The main functionality of PrettyProlog, however, is that it allows the user to visualize how the Stack and the SLD Tree evolve during a computation made by the interpreter to solve a given goal.
The SLD tree viewer panel shows the steps the PrettyProlog engine has performed as a tree. Each branch represents the selection of a clause from the theory, which can be selected in the \theory panel", whereas leaves are either solutions or dead ends, i.e. goals that could not be solved. The substitution that was valid at a given point is shown aside the corresponding node in the tree. Also, the SLD tree shows which frames are removed from the stack as the e ect of a cut, by printing them with a di erent font and icon.
Figure 1 shows the SLD tree of a Prolog program that implements a classical instance of a search problem: that of moving from a city in Romania (Arad, in our case) to Bucharest [11, Chapter 3]. We implemented a depth rst search with control of cycles, as well as the auxiliary not and member predicates.
Because of space constraints, we do not show here the code of the
implemented \DFS with control of cycles" program. It can be found in [
Besides showing what happens both to the stack and to the SLD tree (while it is built), PrettyProlog correctly visualizes the e ect of a \cut" on the SLD tree. In the upper part of Figure 1 there are goals written in italic (from not(member(arad, [oradea, zerind, arad])), ... to !, fail, write(....) ). These nodes are cut after the execution of the ! in the rst clause de ning not, called with member(arad, [oradea, zerind, arad])) as argument. PrettyProlog SLD viewer keeps the cut goals for didactic purposes, but shows them in a di erent font to emphasize that they no longer belong to the tree. The system predicates supported by PrettyProlog, although limited, include simple predicates for input-output, such as write and nl.
The stack viewer shows each frame pushed onto the stack. When the user clicks on a frame, its content is displayed: the goal that still had to be solved at the time the frame was pushed on the stack; the substitution that is the partial solution to such goal at this point; the clause that has been used to obtain the goal; the index from where, on backtracking, the engine will search for the next clause.
When the PrettyProlog engine solves a goal step-by-step, the clause used in each resolution step is highlighted in the theory panel. 2.2 Implementation PrettyProlog is made of several modules, each one corresponding roughly to a Java package. Modules are pretty much organized in a layered fashion, with the lower-level ones providing services to the upper-level ones. Currently implemented modules include: the Data Types Module, the Parser Module, the Engine Module, the GUI Module.
{ The Data Types Module includes data types that are commonly used throughout many other PrettyProlog modules. From this point of view, the Data Types Module is the lowest-level one. { The Parser Module contains the Parser class and some parser exception classes. This module lies just above the Data Types Module; its task is to read characters from a stream and produce instances of PrettyProlog data types, or throw an exception if something goes wrong. { The GUI Module includes the classes that make up the PrettyProlog GUI, including the viewers for the Stack, Theory, and SLD Tree. { The Engine Module is the main PrettyProlog module. It contains the Engine class as well as many helper classes such as Theory, Goal and Clause. This module contains also two sub-modules: EventListeners , which provides classes and interfaces used to attach listeners to the Engine, the Stack, and the Theory; and Syspreds, which de nes the built-in system predicates and gives the programmer the possibility to easily add new ones.
The classes that make up the Engine Module are the following: Unifier. This class provides a single public method, unify(Term, Term), that returns a substitution that uni es the two terms passed as arguments, or null if they are not uni able. This class exists as a separate class for reasons of modularity and extensibility.
Clause. A clause is an object made of a Callable (the head) and a body, again a nameless callable.
Theory. This class implements a list of clauses, with the usual operations for adding to, removing from, or navigating through the list.
Frame. A Frame is a single piece of data that is contained in a stack. Stack. In addition to the usual stack operations, this class can register StackListeners which are noti ed of every change in the stack's state. The lack of an explicit representation of the stack in many prolog implementations, and the requirement to have such a data structure for inspecting the behavior of the Prolog engine were the main motivations for building a new interpreter from scratch.
Goal. A goal is a list of callables.
Engine. The main class of the Engine module. 3
We brie y recall here some basic notions of Constraint Logic Programming
(CLP). The reader is referred to [
Let us consider a rst-order language h ; F ; Vi, where ; F ; V are the sets of predicate symbols, functional symbols, and variables, respectively. The set is partitioned in the two sets C and P ( = C [ P and C \ P = ;).
C ( P ) is the set of constraints (resp., program de ned\) predicate symbols.
C is assumed to contain the equality symbol \=". Similarly, F is partitioned into FC and FP . In this paper we focus on CLP on nite domains (CLP(FD)), therefore, we assume that FC contains the binary arithmetic function symbols +; ; ; =; mod etc. as well as a constant symbol for any integer number, and
C contains ; <, etc. false is assumed to be a special predicate in P which has no rules de ning it. domain is assumed to be a predicate in C assigning a domain to a list of variable or re ning it, if the variables already have one.
An atom built on h P ; FP ; Vi (resp. h C ; FC ; Vi) is said to be a program (resp. constraint) atom. Any constraint atom and any subterm based on hFC ; Vi is interpreted in a constraint domain, namely, ful lling the intended semantics of its symbols (in this case, the arithmetical properties on integer numbers). The same happens to constraint atoms. To this aim, each variable X used in constraint atoms is associated with a domain DX . We will use the functions min and max that return the smallest (resp., largest) value of a domain.
A primitive constraint is a constraint atom or its negation and a constraint is a conjunction of primitive constraints. We denote the empty conjunction by true. This syntactic notion of constraint has a semantic counterpart: a constraint C on n variables X1; : : : ; Xn with domains D1; : : : ; Dn, respectively, is a relation on D1 Dn. A solution for C is a mapping [X1=d1; : : : ; Xn=dn] such that hd1; : : : ; dni 2 C. If there are no solutions, then C is inconsistent.
A goal CLP is of the form B, where B is a conjunction of program atoms and primitive constraints. A CLP rule is of the form A B where A is a program atom and B is a CLP goal. A CLP program is a set of CLP rules.
The operational semantics of CLP is parametric on the function solve that given a constraint C should detect whether C is satis able (consistent) in the constraint domain chosen (in this paper nite domains). During its computation, solve(C) might rewrite C to an equivalent simpli ed constraint. In practice, for complexity reasons, solve is an incomplete procedure, in the sense that instead of verifying consistency of the (entire) constraints, acts locally in each primitive constraint, removing some values in domains that cannot belong to any solution until a local property is satis ed. Typical local properties are (hyper)arc consistency and (hyper)bounds consistency (see below for details). This operation is called constraint propagation and is required to be as fast as possible. During this computation, inconsistency of C can be detected. In this case solve(C) returns false. But, even if solve(C) 6= false we cannot be sure of the consistency of the constraint. As we will see below, the user might require the search for a solution using the labeling predicate.
As an example, let us consider the constraint X 6= Y; X 6= W; X 6= Z; Y 6= W; Y 6= Z; W 6= Z, where DX = DY = DZ = DW = f0; 1; 2g. Although it is inconsistent, default options in Prolog implementations are such that it is left unaltered by solve and, therefore, inconsistency is not detected. This constraint is the encoding of the 3-coloring problem of a graph (in this case, of four nodes, fX; Y; W; Zg, disequations are added for each edge). Checking consistency of this class of constraints is therefore NP-complete and a fast propagation algorithm can not check it (unless P=NP).
Operational semantics of CLP is based on the notion of state. Some variants are possible. The one presented here is the one we believe is the closest to standard SLD resolution.
A state is a pair hG j Ci where G is a CLP goal and C is a constraint (also known as the constraint store). A state hG j Ci is said to be: { successful if G = true and solve(C) 6= false. { failing if either solve(C) = false or there are no clauses in P with the same predicate of the head of the selected atom in G. { unsolved if G 6= true and it is not failing.
Let hG1 j C1i be an unsolved state, where G1 = L1; : : : ; Lm, and P a program. A CLP-derivation step hG1 j C1i ) hG2 j C2i is de ned as follows: { Let Li be the selected literal in G1 (for simplicity, let us assume it is L1). { Then hG2 j C2i is obtained from S and P in one of the following ways: L1 is a primitive constraint, C2 = L1 ^ C1. If solve(C2) = false, then G2 = false, otherwise G2 = L2; : : : ; Ln.
If L1 = p(t1; : : : ; tn) is a program atom, and p(s1; : : : ; sn) B is a renaming of a clause of P then G2 = t1 = s1; : : : ; tn = sn; B; L2; : : : ; Ln and C2 = C1.
A derivation for a state S0 in P is a maximal sequence of derivations such that S0 ) S1 ) . A derivation for a goal G is a derivation for the state hG j truei.
A nite derivation S0 ) ) Sn is said successful (resp. failing ) if Sn is a successful (resp., failing) state. In the case of a successful derivation the computed answer is the projection of the constraint store of Sn on the variables in S0. Of course, a simpli cation, based on solve, is usually employed to make the output readable.
Although the computed answer is returned in implicit form, explicit enumeration of the solutions can be forced by using the built-in predicate labeling. In this stage inconsistency of a constraint is discovered. The main parameter is a list of variables to be instantiated (labeled). Other optional parameters are related to the search heuristics and are di erent in di erent Prolog implementations. We use here the choice of not allowing extra parameters.
Basically, starting from a successful state htrue j Ci (or equivalently, by a constraint C) the labeling builds a search tree that alternates two stages: a constraint propagation stage followed by a non deterministic assignment of a (selected) variable. During the propagation stage the constraint is simpli ed and, possibly, its inconsistency is detected. In this case, the search backtracks to the last non deterministic choice. If all variables are assigned (labeled) a solution is found. If all possible backtracks are applied and no solution is found, the constraint is inconsistent. The derivation step is extended with: If L1 = labeling([V1; : : : ; Vn]) then G2 = V1 = v1; : : : ; Vn = vn; L2; : : : ; Ln and C2 = C1 if [V1=v1; : : : ; Vn=vn] is an assignment that do not lead C1 to inconsistency. If there are not such assignments, then G2 = false.
Every variable X used in constraint is associated with a domain DX . This is done initially by the built-in predicate domain; domains and later reduced by e ect of the computation. As common in CLP, we denote the interval fa; a + 1; a + 2; : : : ; bg by a::b.
Let us consider a primitive constraint c on the variables X1; : : : ; Xn. c is arc consistent (hyper arc consistent if n > 2) if for all i 2 f1; : : : ; ng and for all di 2 Di exist d1 2 D1; : : : di 1 2 Di 1; di+1 2 Di+1; : : : ; dn 2 Dn such that [X1=d1; : : : ; Xn=dn] is a solution of c.
As explained in [
Let us consider a primitive constraint c on the variables X1; : : : ; Xn. c is bounds consistent (hyper bounds consistent if n > 2) if for all i 2 f1; : : : ; ng and for all di 2 fmin Di; max Dig (the two interval bounds), exist d1 2 min D1:: max D1; : : : ; di 1 2 min Di 1:: max Di 1; di+1 2 min Di+1:: max Di+1; : : : ; dn 2 min Dn:: max Dn such that [X1=d1; : : : ; Xn=dn] is a solution of c.
Going back to the example in the Introduction, the constraint 2X = Y where the domains DX = f0; 1g; DY = f0; 1; 2g is bounds consistent but not arc consistent. 4
This section introduces PrettyCLP: Section 4.1 reports the concrete syntax of the CLP part of PrettyCLP, Section 4.2 describes the procedures implemented for constraint propagation and labeling, and Section 4.3 shows how the output primitives have been modi ed and reports some system screenshots. 4.1
Concrete CLP syntax for PrettyCLP Concretely, the set C contains the constraint predicate symbols #= and #=<; symbols #\=; #>; #>=; #< are accepted as a syntactic sugar for building negated constraint literals. Standard arithmetic functional symbols are allowed as well.
The built-in instruction domain for assigning a nite domain to variables can be used in two ways (lists are usual Prolog lists): { domain(VARS, min, max), where VARS is a list of variables, and the domain is the interval min..max. { domain(VARS, DOMAIN): where VARS is a list of variables, and DOMAIN is a list of integer numbers.
The labeling built-in has a unique argument: labeling(VARS), where VARS is a list of variables assigned to a nite domain. 4.2
Constraint Propagation and Labeling Every nite domain variable is assigned to a domain, namely a set of points that can monotonically decrease during the computation, or increase again due to backtracking. Domains are stored in a vector of integer values (we recall that Java vectors are in fact a dynamic data structures that can be increased and decreased as needed). This is realized by modifying the class Variable within the module Data Types.
More in detail, a Java constructor is changed in order to characterize a variable by a symbol. symbol is a PrettyProlog class, and a symbol can be the string naming a variable or a constant or functional symbol of FC .
Moreover, the class Domain is de ned in the module Engine. This class stores an array (again, a Java dynamic array) with an entry for each of the variables occurring in the derivation and implements the methods for domain manipulation. Among them, we would like to point out the methods: { getDomain(Var X) that returns the (vector storing the) domain of a variable
X. { domainVar(Var X, int min, int max) that initializes the domain of the variable X with the interval min..max. { updateDomain(Var X, Vector D) that replaces the current domain of the variable X with the domain array D. This method simpli es propagation and backtracking operations.
The parser of Pretty Prolog has been slightly modi ed to be able to deal with constraint terms and atoms.
The class Engine is the core of the computation. Since the SLD resolution is now coupled with constraint solving, we need to act on the class Engine. Uni cation is called for standard terms, constraint solving for constraint terms. The constructor that creates a new instance has been modi ed for dealing with the array domains. Then the method ContinueSolving is called. Its role is to either call the Constraint Solver procedure, called SolveConstraint, or the uni cation procedures already developed in PrettyProlog.
The Constraint Solver returns a Boolean value: false can be obtained as e ect of constraint propagation; if constraint propagation ends without failing it returns true. Constraint Propagation operates on both arc and bounds consistency. The procedures called by the Constraint Solver are: { Solve that receives as input a constraint and the domains of the variables in it and elaborates it on the basis of its main predicate symbol. When selected, unary constraints are used to reduce the domain of the corresponding variable and removed. Constraints with two or more variables, instead, are dealt with by:
ArcSolveConstraint, implementing arc consistency, and
BoundSolveConstraint, that implements bounds consistency.
In these two procedures, one variable per time is selected, then every value in its domain is considered and a support for it is looked for in the domains of the remaining variables (but with a di erent rule for arc vs bounds). In the case of bounds, of course, a faster algorithm based on the bounds of the domains is employed. { SolveConstraint repeatedly applies the Solve procedures on all the constraints until a xpoint is reached. { ExprEval computes the various expressions involved in constraints when values are assigned to variables and is used as auxiliary procedure by ArcSolve/ BoundSolveConstraint.
The handling of labeling is made by a homonymous method. Variables in the argument list are selected from left to right (heuristics leftmost of other CLP(FD) systems) and smallest domain values are tried rst (heuristics up).5 5 It it easy to implement other heuristics here. This will be done as future work. This method also deals with backtracking, handling,choice points, and storing and retrieving intermediate constraint stores.
Remark 1. As a nal observation for this section, we would like to underline a typical problem in CLP implementations coming from the weak typing of constraint functional symbols and variables. In theory, terms and variables are sorted, in practice this is not true. If the two terms 1 + 3 and 3 + 1 are found within a uni cation they are assumed to be di erent even if the arguments are integer numbers and the binary symbol + 2 FC . On the contrary the constraint 1 + 3 #= 3 + 1 is true. This is also the behavior of our interpreter, but this may lead a student, the target of PrettyCLP, to confusion.
Similarly, let us assume to nd the constraint atom X #< 3 and the variable X is not yet assigned to a domain. Some Prolog implementations will answer X in -inf..2, thus implicitly assuming a starting domain -inf..+inf for each nite domain variable. We have chosen a more rigid option: if the variable has been not yet associated with a domain, it cannot be used in a constraint atom. An error (a sort of type error) is returned. 4.3
Output rendering After the parametric propagation procedures and the procedures for the labeling have been implemented, we modi ed the graphical applet of PrettyProlog for showing the new information. In particular: { buttons for visualizing and erasing domains have been added to the applet window; { the eld Constraint can be inspected from the Stack Viewer; { two windows for inspecting Arc Consistency and Bounds Consistency based propagation have been made available to PrettyCLP users.
In Figures 2 and 3 we report the rendering of the two alternative executions to a goal p(X,Y) where the predicate p is de ned by the constraint: domain([X],0,2), domain([Y],0,5), Y #= 2 * X.
In the current implementation, we decided to leave an unique SLD tree, while di erent computed answers are returned in the Arc Consistency and Bounds Consistency windows. Since Arc Consistency is more e ective in reducing the domains, it can be the case that an inconsistent branch of the SLD tree is found some steps before than using bounds consistency. However, this case is extremely rare. We have preferred to leave the tree obtained using Bounds Consistency (the same computed by Standard Prolog system) only. However, the user can view what would have happened with the other propagation technique looking at the Arc Consistency window. In particular, all domains computed during the computation are included in those computed with Bounds Consistency. Sometimes they are strictly included and it may happen that one domain becomes empty before arriving at the end of the tree. This choice can be changed as future work, namely, we could leave the user to select in advance (with a button) the propagation choice and report the selected computation only.
In Figures 4{5 we report the execution of PrettyCLP on a Knapsack problem. The explicit labeling is required for variable W only. The computed solution is shown in the main picture (Fig 4). In the labeling case the di erences between Arc and Bounds become evident. An excerpt of the executed constraint propagation is shown in Fig 5. 5
Although visualization and tracing of constraint programs do not constitute a new research area, implemented systems that provide dynamic visualization and control functionalities for CLP(FD) are still few.
Among the oldest ones we may mention the Oz-Explorer system by C. Schulte
[
In [
The integration of explanations in the trace structure and some ideas on how
to implement the trace structure in a high-end system like SICStus are addressed
by [
More recently, F. Fages, S. Soliman, and R. Coolen developed CLPGUI [
Although de nitely simpler than some of the above systems as far as the visualization of variables is concerned, PrettyCLP shows the original feature of allowing the user to select the propagation strategies (e.g. arc consistency vs bound consistency), which { to the best of our knowledge { is not supported by any other tool.
As part of our close future activities we are planning to incorporate some global constraints, such as the alldifferent one, into PrettyCLP. Propagation procedures of global constraints allow to sensibly prune the search tree. This has e ects on the size and on the form of the SLD tree too. Therefore, we will add buttons to enable/disable global consistency vs simple consistency so as to select one or the other search tree.
Because of our teaching mission, from which the development of both PrettyProlog and PrettyCLP stemmed, we are currently facing the problem of guiding the student in his/her CLP learning activity. To this aim, we are designing a set of benchmarks for supporting self-evaluation and for helping students in identifying those aspects of CLP design and programming that they still need to better understand. This benchmark will heavily ground upon PrettyCLP as the tool that the students will be suggested to use in order to appreciate CLP not only on the stage, but also behind the scene.
All the material relevant to PrettyProlog and PrettyCLP can be found at http://code.google.com/p/prettyprolog/.
Acknowledgments This work is partially supported by INdAM-GNCS 2010, INdAM-GNCS 2011, and PRIN 20089M932N. We would like to thank Maurizio Martelli for the precious discussions during the design and implementation of the PrettyProlog visualizer.