Classic Prolog has many features, and even more in its modern incarnations. Many of these features are well aligned with the view of pure Logic Programming as both a specification tool and a programming language. However, some other Prolog aspects depart from this view. Classic examples that have received much attention are assert/retract or the cut. Our focus here is however on the depth-first search rule. While well justified by practical concerns, using only depth-first from the start also introduces early on the need to reason about termination, and also possibly a need to use impure features to make different modes produce answers in finite time. Termination of course has to be faced sooner or later by any programmer, but having to do it right at the start can detract from being able to convey early on the vision of Prolog as a declarative language where one can first concentrate on problem specification and/or knowledge representation and only later worry about efficiency. We review a number of ways in which some of these issues can be tackled when teaching Prolog, while still using throughout a Prolog system. The aim is tutorial, in the hope that these ideas can help other instructors that are teaching or plan to teach Prolog. We believe that some of these considerations may also come in handy when combining Prolog with modern, AI-assisted programming methodologies.
In [1,3] we presented some thoughts and lessons learned over time about how to teach (Constraint) Logic Programming -(C)LP-in general and Prolog in particular. We argued that teaching (C)LP and Prolog is necessary because it brings in many useful concepts and characteristics that are not present in other programming paradigms such as imperative, object-oriented, or functional programming. We also addressed different aspects of how to teach Prolog, covering from how to show the beauty and usefulness of the language to how to avoid some common pitfalls, misconceptions, and myths about this unique programming paradigm.
Our aim herein is to expand on the fundamental aspect of transmitting to students the beauty and power of Prolog. The (C)LP paradigm is based on logic and includes search as an intrinsic component, as well as the use of unification, and generalized pattern matching. This brings about interesting and distinctive aspects, such as the reversibility of programs and the ability to represent and reason about knowledge. It also makes it possible to formulate runnable specifications and efficient algorithms within the same formalism, making (C)LP not only a singular programming paradigm, but also a modeling and reasoning tool. We would like to explore how to convey these concepts already in the first steps of teaching (C)LP and Prolog, as well as to provide some ideas on how to do this using the same tool -a modern Prolog system-that will be used in the later, more algorithmically-oriented parts of a Prolog course.
Classic Prolog has many features, with even more in its modern incarnations. Many of these features are well aligned with the view of pure Logic Programming as both a specification tool and a programming language. However, some other Prolog aspects depart from this view. Classic examples that have received much attention are assert/retract and the cut. Our focus here is however on the depth-first search rule: while well-justified by practical concerns, using only depth-first from the start also introduces early on the need to reason about termination, and also possibly a need to use impure features to make different modes produce answers in finite time. Termination of course has to be faced sooner or later by any programmer, but having to do it right at the start can detract from being able to convey early on the vision of Prolog as a declarative language where one can first concentrate on problem specification and/or knowledge representation and only worry later about efficiency.
In the rest of the paper we review a number of ways in which some of these issues can be tackled when teaching Prolog, while still using throughout a Prolog system. The aim is tutorial, in the hope that these ideas can help other instructors that are teaching or plan to teach Prolog.
As we have also argued in [1], perhaps the most important objective during the first steps of teaching Prolog is to succeed in showing the great beauty of the (C)LP paradigm in general and of Prolog in particular. We believe that in order to achieve this, one needs to convey the original inspiration behind the paradigm of being at the same time a specification and knowledge representation language and a practical and highly productive programming language. We find it very useful to explicitly expose students to the ideas put forward by Cordell Green [4]. Green suggested that, provided an effective deduction procedure is available, i.e., a mechanical proof method, inspired at the time by Robinson's recent proposal of the resolution principle [5], a different view of problem solving and computing would be possible (Figure 1, top). In this approach, the automated deduction procedure is programmed once and for all in the computer. Then, for each problem we want to solve, we just need to find a suitable representation for it in logic (i.e., its specification), and, to obtain solutions, we simply ask questions and let the deduction procedure do the rest. Prolog (and (C)LP in general) are the materialization of this idea by Colmerauer and Kowalski [6,7], where (Figure 1, bottom) the problem representation or specification is written in logic using the Prolog language, and the efficient deduction mechanism is Kowalski and Kuhnen's SLD resolution [8,9], combined with the practicality brought about by Warren et al. 's Dec-10 Prolog implementation and compilation techniques [10,11]. Description of the topology of a circuit: resistor (power ,n1). resistor (power ,n2). transistor (n2 ,ground ,n1). transistor (n3 ,n4 ,n2). transistor (n5 ,ground ,n4). run βΆ Figure 3: A simple pure logic program for circuit topology.
The vision that with Prolog one can just represent/specify the problem and then obtain answers automatically is relatively easy to convey with the first simple examples such as, e.g., the classical family relationships (Figure 2), circuit topology (Figure 3), simple puzzles, etc. 2 For example, with the family facts and rules of Figure 2 students can get answers to questions in different modes such as ?-mother_of(susan,Y)., ?-mother_of(X,mary)., ?-grandmother_of(X,Y)., etc. Similarly, with the "digital circuit theory" at the top of Figure 3, which describes how inverters, nand-gates, and and-gates are made up of resistors and transistors connected to ground or power, and the concrete circuit at the bottom, described by enumerating the components to which the circuit nodes are attached, students can also get answers to questions in different modes, such as, e.g.: 3run βΆ ?-and_gate (In1 ,In2 ,Out).
i,e., "is there an and-gate somewhere in this circuit?, " and Prolog finds the answer:
run βΆ mother_of (susan , mary). mother_of (susan , john). mother_of (mary , michael ). father_of (john , david ). parent (X,Y) :-mother_of (X,Y). parent (X,Y) :-father_of (X,Y).
ancestor (X,Y) :ancestor (X,Z), parent (Z,Y). ancestor (X,Y) :parent (X,Y). The issue most relevant to our discussion is that all these queries will return the correct solution and terminate using standard Prolog. I.e., in these examples students can use just the logical reading when writing and reading clauses, and then, assuming that the logic is correct, have confidence that the system will answer correctly any question providing all possible solutions in finite time. However, things can quickly get more complicated.
Returning to the family example of Figure 2, consider adding to it the classical ancestor predicate, as in Figure 4. Now for any query to ancestor/2 the program hangs in standard Prolog without giving any answers:
run βΆ ?ancestor (X,Y).
Of course, we can change the order of the ancestor/2 clauses and the program will now behave better in standard Prolog. E.g., for: run βΆ ?ancestor (X,Y).
We will obtain all the answers:
but the program will still hang at the end. It is an inevitable fact that, sooner or later, students will be confronted with non-termination. It can be hard for them to get around this stumbling block at the early stages of learning the paradigm, and this may lead to disenchantment and/or confusion if no additional tools and understanding of the issues involved are provided.
Fortunately the technique of tabling, pioneered by XSB [12], and now supported by several other modern Prologs [13], including B-Prolog [14], Ciao Prolog [15], SWI Prolog [16], and Yap [17], comes to the rescue for a good number of these cases. Tabling ensures termination of programs for which the "bounded term-size property" holds: programs where all the sizes of subgoals and answers produced during an evaluation are smaller than some fixed number. This is indeed the case for the program of Figure 4, since there are only a finite number of constants in the program and thus any query, subgoal, or answer will be of bounded size. This is also the case for all "Datalog" programs. In order to ensure termination we can declare ancestor/2 as a tabled predicate as follows:4
:table ancestor /2.
Now we not only get all the answers without having to invert the order of the ancestor/2 clauses:
but the program also ends stating in finite time that there are no more solutions. Note that switching the order of the literals in the recursive clause of ancestor/2: run βΆ
ancestor (X,Y) :parent (X,Z), ancestor (Z,Y).
we obtain all the answers and the program also terminates at the end with standard Prolog. However, this is not always the case, and tabling offers in general a more powerful mechanism than just switching the order of clauses and body literals. A relevant issue in tabling is which predicates to declare as tabled, which is a subject onto itself, but beyond the scope of our discussion here. However, in the first stages students can simply be told to try declaring different or all predicates as tabled. 5Overall, tabling can be very useful in our quest to transmit the beauty of the Prolog language. However, it will obviously not cover the cases which fall outside the bounded term-size property. Unfortunately, this can often happen once nested data structures are introduced and combined with recursion.
Consider natural/1 defining the natural numbers in Peano representation: 6run βΆ natural (0). natural (s(X)) :natural (X).
nat_square (X,Y) :natural (X), natural (Y), mult(X,X,Y). and pair/2 defining a pair of natural numbers:
A query such as the following:
run βΆ ?pair(X,Y), X=s(0).
will hang in standard Prolog, because of course the search never progresses beyond X=0, since there are infinite possible solutions for Y that will be explored first. The initially surprised student may eventually realize that in this case it suffices with simply reversing the order of the literals in the query: 7
?-X=s(0) , pair(X,Y).
and see that now all the answers are enumerated:
However, consider the more complex program of Figure 5, defining nat_square(X,Y) that holds if X and Y are both naturals and Y is equal to X multiplied by itself. We have also included the auxiliary predicates defining addition and multiplication. In our classes, we develop each of these predicate definitions with the students by reasoning about the (infinite) set of (ground) facts we want to capture, thereby informally introducing the notion of declarative semantics. We also work with the students on generating the definitions by generalization from tables of facts, thinking inductively, and more. See also [19] for an ample discussion of how to build programs inductively.
Standard Prolog execution provides useful answers for, e.g., mode nat_square(+,-): run βΆ ?-nat_square (s(s(0)), X). X = s(s(s(s(0)))) ?
an even for mode nat_square(-,+):
?-nat_square (X,s(s(s(s(0))))). X = s(s(0)) ?
which invariably nicely surprises students, even if in both cases standard Prolog hangs if one asks for more, non-existent, answers. However, the next obvious temptation is to try:
but this time standard Prolog only produces the first, trivial answer and then hangs: 7 At this point it can also be pointed out that there exist other techniques like delays for changing dynamically the goal order.
X = 0, Y = 0 ? ; <hangs > despite the fact that there are obviously infinitely many additional valid answers.
Unfortunately, these cases of non-termination cannot be avoided with just tabling, since the program is producing continuously growing Peano numbers, i.e., continuously growing terms. Unfortunately, non-termination issues of this sort are often encountered early on by students -basically as soon as recursive data structures are introduced.
In order to address these more complex cases, we have found it useful to provide students with a means for selectively switching between depth-first and other search rule(s), including in particular at least one that is fair. Ciao Prolog, which has incorporated over time a number of features to facilitate teaching Prolog and (C)LP, supports declarations such as:
which students can use to specify alternative search rules and run some or all predicates using breadthfirst, as well as iterative deepening, etc., in addition to depth-first and tabling. Such alternative search rules are in fact relatively straightforward to implement in any Prolog system, for example via metainterpretation and/or code expansions. 8The relevant fact for our discussion is that if students set their predicates to run in, e.g., breadth-first mode, then all examples will "work well" for all possible queries. This, in the sense that all valid solutions will be found, even if possibly inefficiently. For example, our problematic query: run βΆ ?-nat_square (X,Y).
will now enumerate the infinite set of correct answers:
?-nat_square (X,Y). X = 0, Y = 0 ? ; X = s(0) , Y = s(0) ? ; X = s(s(0)), Y = s(s(s(s(0)))) ? ; X = s(s(s(0))), Y = s(s(s(s(s(s(s(s(s(0))))))))) ? ; X = s(s(s(s(0)))), Y = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(0
Another interesting consequence of using a fair search rule, even for the cases where depth-first works, is that the "quality" in the enumeration of solutions also improves with respect to depth-first. For example, the query:
does not hang in standard Prolog. However, it produces the following answers:
It becomes clear that some answers will never be generated by the depth-first search: it will generate infinitely many mult(0,X,0) tuples, with X being any Peano number, without ever having a chance to generate tuples where the first and third arguments are different from 0. In contrast, breadth-first will produce all solutions:
s(s(s(s(s(s(0))))))), Z = 0 ? ; X = s(0) , Y = s(s(0)), Z = s(s(0)) ? ; ... which, in addition, are clearly more informative, satisfying, and useful for subsequent predicates as the solutions obtained using the depth-first search.
In summary, we argue that the use of a fair search rule helps students visualize the true potential of the (C)LP paradigm and Prolog and that it is possible indeed to solve problems by simply thinking logically and/or inductively.
It is interesting to note that this fairness in enumeration also comes in handy in several other areas, such as for example for type definitions. Fig. 6 shows the definition of two types (they are marked as regular types by the regtype directive): color/1, defined as the set of values {red, green, blue}, and colorlist/1, representing the infinite set of lists whose elements are of type color. 9 In Ciao Prolog marking predicates as types (or in general as properties) allows them to be used in assertions. However, they remain regular predicates, and can be called as any other, used as run-time tests (dynamic checking), "run backwards" to generate examples or test cases, etc. See, e.g., [20] for a recent more complete presentation of these aspects.
For example, calling: run βΆ ?colorlist (L).
run βΆ :-use_package ([ assertions , regtypes ]). % :-use_package (sr/ bfall ).
:regtype colorlist /1. colorlist ([]). colorlist ([H|T]) :color (H), colorlist (T).
With all these tools, the student can also be shown with examples (and through benchmarking them) how in Prolog it is possible to go from executable specifications to efficient algorithms gradually, as needed. One of the examples we use is the modulo operation mod(X,Y,Z) , where Z is the remainder from dividing X by Y. A mathematical definition or specification for this operation is:
This can be expressed directly in Prolog as:
This version is clearly correct (since it is directly the specification) and, using, e.g., breadth-first search, works in multiple directions, always finding all solutions:
?-op (500 ,fy ,s). yes ?-mod(X,Y, s 0). X = s 0, Y = s s 0 ? ; X = s 0, Y = s s s 0 ? ; X = s s s 0, Y = s s 0 ? ; X = s 0, Y = s s s s 0 ? ; ... but it can of course be quite inefficient. However, also in Prolog, we can write another version such as this one:
which is much more efficient -one can time some queries or reason about the size of the proof trees to show this. Also, this version works well with the default depth-first search rule for several modes. However, the enumeration of solutions is again biased and thus less elegant and useful than the one obtained using breadth-first search.
We do not mean to imply however that the use of a fair search rule or pure programs are a requirement for traveling the path from executable specifications to efficient algorithms. Figure 8 shows an additional example, where we have a specification and two implementations for computing the maximum of a list of numbers: max/2 on the left is a direct transliteration of the mathematical specification and max2/2 on the right is a much more efficient, algorithmic implementation. Here both programs can only be used in max(+,-) mode because of the use of non-reversible standard Prolog built-ins, but are still quite suitable as an example of writing both the specification and an algorithm in Prolog.
Regarding the examples to show, if only small and simple ones are chosen, sophisticated Prolog implementations running on fast modern computers can also create the misconception that Prolog provides solutions effortlessly. Thus, it is important to eventually also tackle larger and more complex problems and stress that, as a Turing complete language, also Prolog programmers eventually need to care about algorithmic time and memory complexity of both their programs and the libraries/features they utilize, which of course includes, at the limit, termination. Here it is also important to explain at an early stage how to control search, via clause order and literal order, as well as pruning in later stages.
After students have written just a few examples using both depth-first and a fair search rule, they will have observed that the fair search rule does provide all the expected answers, but that execution sometimes hangs after that. It is important thus to explain better what is really happening with their programs, which also implies coming to terms with the realities of non-termination in Turing complete programming languages.
To this end, we have found it very useful to use depictions such as those in Figures 9 and-10 to introduce students in a graphical way to the basic theoretical results at play, i.e., the soundness and (refutation-)completeness of the SLD(NF)-resolution proof procedure used by Prolog.
The idea is to convey that the search tree has in general the shape of Figure 9, i.e., that all solutions and some failures are at finite depth, but that there may be branches leading to failure that are infinite. While techniques such as tabling, as we have seen before, can help detect and avoid traversing some of these infinite failure branches when the bounded term-size property holds, it is not possible to always do so. At this point, it can be interesting to recall or introduce them to the notions of undecidability and the halting problem, and relate these concepts to the graphical depiction of the search tree. The level of discussion will depend of course on the students' level, but it can always be done informally and adapted to their background. At the same time one should underline that this is of course not a particular problem of Prolog or Logic Programming, but rather the essence of computability, and no language (Prolog, logic, nor any other Turing-complete programming language) or proof system can provide a magic formula that guarantees termination in all cases.
This schematic search tree depiction makes it then easy to explain why breadth-first (or iterative deepening, or any other fair search rule) is guaranteed to produce all solutions if they exist (Figure 10, left). If there is a finite number of solutions, such fair search rules find them in finite time, even if perhaps they do not terminate in some cases after producing all the answers. And it is also easy to explain why depth-first search (Figure 10, right) may sometimes hang before producing some of the answers: those that are in the tree to the right of the leftmost infinite branch. This is also a good opportunity for introducing and explaining graphically other alternative fair search rules such as iterative deepening and compare them with the students to depth-first search. One can then discuss the advantages and disadvantages of these search rules in terms of time, memory, etc. E.g., that the price to pay for breadth-first execution's advantages is larger memory consumption and execution time, while depth-first can be implemented very efficiently with a stack, with iterative deepening representing an interesting middle ground. This can be shown very practically by benchmarking actual examples, motivating the practical choices made for Prolog, which bring in great efficiency at the (arguably reasonable) price of having to think about the order of query goals, clauses, and body literals.
As an example, Figure 11 shows some results comparing depth-first (df), breadth-first (bf), and iterative deepening (id) for queries to the nat_square/2 predicate of Figure 5 for two modes: nat_square(+N,-N2) and nat_square(-N,-N2) , i.e., providing a Peano number N and calculating its Peano square, and generating all the pairs of Peano numbers and their squares. For the first mode the graph provides execution times in mS for calls with increasing numbers of N, starting from 0, i.e., ?-nat_square(0,R)., ?-nat_square(s(0),R)., etc. For the second mode, the numbers on the π¦ axis are the timings for each one of the answers to ?-nat_square(N,R)., i.e., the time to get the first values of N and R, then for the second, etc. In this case no curve is given for depth-first, since as we saw it hangs after the first solution.
It is important to note that these numbers are for sub-optimal implementations of the fair rules and that they are for a single problem, so obviously no general conclusions can be drawn and the trade-offs between these search rules are well studied anyway. Here the results are only intended as an illustrative example.
In any case, breadth first search is slower than iterative deepening in most, but not all, cases, and both are slower than depth-first, but obviously only for the cases in which depth-first works. It is also interesting to see that depth-first and iterative deepening are relatively close, as expected.
The important point however is that the fair rules are usable for both (and all) modes, at least for small queries, and can thus be really useful as default rules in the first steps in a teaching environment, which is our concern herein.
Our starting point has been the observation that having to deal with the complexities of termination using Prolog's depth-first rule during the first stages of teaching Prolog often detracts from the objective of conveying to students the beauty and usefulness of the language. Motivated by this observation, we have reviewed some ways of addressing these issues in practice, while still using a Prolog system for all stages, such as the use of tabling and fair search rules. If time permits, it is important to also discuss how the constraint systems built into most current Prolog systems (Q, R, fd, . . . ), can bring about many other improvements to search (e.g., constrain and generate vs. generate and test).
More generally, teaching Prolog and (C)LP is an extremely rich subject and there are of course many other important aspects that we have not been able to address here, including of course all of the traditional subjects of a Prolog course beyond the first steps. For a more complete picture, we have covered previously some of these other issues in [1,3]; here we have expanded on one of the points we raised there. Much of our experience over the years is materialized in a) the courses that we have developed, for which, as pointed out before, all materials such as slides, Active Logic Documents [3], examples, etc. are publicly available, 10 and b) the many teaching-oriented special features that we have incorporated over time in our own Ciao Prolog system. 11 Here we have touched upon some of these features: being able to choose different search rules and use of the playground from documents for the examples, but there are many others.
We hope that at least some of the ideas presented and these materials and systems are helpful and inspiring to both Prolog instructors that are teaching or plan to teach Prolog and students.