The Prolog Debugger and Declarative Programming. Examples

This paper contains examples for a companion paper “The Prolog Debugger and Declarative Programming”, which discusses (in)adequacy of the Prolog debugger for declarative programming. Logic programming is a declarative programming paradigm. Programming language Prolog makes logic programming possible, at least to a substantial extent. However the Prolog debugger works solely in terms of the operational semantics. So it is incompatible with declarative programming. The companion paper tries to find methods of using it from the declarative point of view. Here we provide examples of applying them.


Introduction
This report contains examples for "The Prolog Debugger and Declarative Programming" [Dra19]. The examples present diagnosis of (i.e. locating errors in) logic programs using the Prolog debugger, following the methods (algorithms) described in [Dra19]. Erroneous versions of an insertion sort program are used (based on those from [Sha83]). For a comparison, we show how the same incorrectness error is dealt with by declarative diagnosis. This turns out much simpler than that using the Prolog debugger.
Our specification for completeness [Dra16] is insert(n, l, l ) ∈ HB l is an ordered list of numbers, n is a number, l is l with n added and is ordered where HB is the Herbrand base (the set of all ground atoms), and S 1 is a specification (for both correctness and completeness) of isort, > and =< , l is a sorted permutation of a list l of numbers ∪ i 1 > i 2 ∈ HB j 1 =< j 2 ∈ HB i 1 , i 2 , j 1 , j 2 are integers, The specification for correctness is if n is a number and l is an ordered list of numbers then l is l with n added and is ordered    So Sp 0 ⊆ Sp, and the difference is the set of ground atoms insert(n, l, l ) in which n is not a number or l is not an ordered list of numbers. Such atoms may (but do not have to) be answers of a "right" program.

Diagnosing incorrectness
Here we deal with this program (inc.isort.pl)      Whenever an incorrect answer is encountered, command jc is issued to go to the corresponding Call item. So recursive invocations of the algorithm were performed for isort([1, 3], 2249) and insert(1, [3], 2249). Note that the resulting trace is an abbreviation of that of Algorithm 4. The located incorrect clause is the same as in the previous example. Figure 4 shows that in this particular case the search of Algorithm 5 is not made shorter by beginning from the incorrect answer to the considered query (instead of beginning from the query itself).
Note that, in the top-level trace for isort([1, 3], 2249), we could not jump over the fragment leading to the first, correct answer. If we do so, the Prolog debugger misses crucial fragments of the computation leading the the second, wrong answer. See Figure 5. After the jc command leading to Call: isort([1,3], 2239), command s was issued, to immediately obtain the first answer. As a result, insert(1, [3], 2249) was not traced at all.

Declarative diagnosis of incorrectness
For a comparison, Figure 6 presents declarative incorrectness diagnosis of the program used above, with the same initial query.
Note that declarative diagnosis is substantially simpler and more efficient than that using the Prolog debugger, exemplified above. In particular, its log is shorter and much simpler to understand.
Some explanations are due. The tool used is a prototype browser for proof trees. It displays the current tree node (an atom) and asks for a command. For non-root nodes it displays (in green) the applicable navigation commands. These commands are: v -go to the child, < -go to the left sibling, > -go to the right sibling, So we know if the current node is a leaf, a leftmost sibling, or a rightmost one. (A command moving to the parent is not displayed and is not used here.) Declarative incorrectness diagnosis is performed by navigating the tree looking for an incorrect child of the last found incorrect node. Eventually we arrive at one without incorrect children. In our case such correct children are 3 > 1 and insert (1, [ ], [1]). This means finding an incorrectness error (an instance of an incorrect clause). Command s displays (in red) the error. (Technically, it displays the parent of the current node with all its children.) It is important that the user does not face a strict declarative diagnosis algorithm, which only asks questions. Instead, the user decides, what to do. For instance, when correctness of a given atom is not obvious (say the atom is big), one may look at its siblings first. One may explore a subtree, and then move back; etc. and insert(1, [ ], 3851) is a symptom, it is also an incorrectness error (as it fails immediately, so its top-level trace is empty, by Algorithm 2). Procedure insert has been found to be the reason of incompleteness.