Teaching Pure LP with Prolog and a Fair Search Rule
Manuel V. Hermenegildo ¹ ² Jose F. Morales ¹ ² Pedro Lopez-Garcia ² ³ ¹ Universidad Politécnica de Madrid (UPM)
² IMDEA Software Institute
³ Spanish Council for Scientific Research (CSIC)
Thanks to David S. Warren and Daniela Ferreiro for their feedback.
Prolog Education Workshop @ ICLP. October 13, 2024. Dallas
These slides are an Active Logic Document which can be edited using the Ciao Prolog Playground .
Intro Many ideas on how to best teach Prolog in:
(in the "Prolog: The Next 50 Years" book).
Here: expand on one of the main messages: do show the beauty!
That to solve a problem, we can just describe it in logic and ask questions.
That logic programs are both:
logical theories / specifications (with declarative meaning) and procedural programs that can be debugged, followed step by step, etc.
That one can go from executable specifications to efficient algorithms gradually, % and as needed.
The vision is easy to convey at first The first examples - family relations. ? ↗
Next Stop Creep Leap Skip Retry Fail Loading bundles and booting ... ✕ Abort
Students can get answers to questions in different modes:
?- mother_of(susan,Y). ?- mother_of(X,mary). ?- grandmother_of(X,Y). All is good!
The vision is easy to convey at first Some fun examples - circuit topology.
:- module(_,_).
%! \begin{focus}
resistor(power,n1).
resistor(power,n2).
transistor(n2,ground,n1).
transistor(n3,n4,n2).
transistor(n5,ground,n4).
inverter(Input,Output) :-
transistor(Input,ground,Output), resistor(power,Output).
nand_gate(Input1,Input2,Output) :-
transistor(Input1,X,Output), transistor(Input2,ground,X),
resistor(power,Output).
and_gate(Input1,Input2,Output) :-
nand_gate(Input1,Input2,X), inverter(X, Output).
%! \end{focus} ?- and_gate(In1,In2,Out). All still good!
All these queries will return the correct solution and terminate using standard Prolog.
However, things can quickly get more complicated...
Non-termination rears its ugly head
:- module(_,_).
%! \begin{focus}
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).
%! \end{focus} Now, for
any query, standard Prolog hangs:
?- ancestor(X,Y). Non-termination rears its ugly head :- module(_,_).
%! \begin{focus}
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) :- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).
%! \end{focus} Changing the order of the ancestor/2 clauses :
?- ancestor(X,Y). Standard Prolog obtains all the answers and then hangs.
Key point: it is a bit early to face non-termination! It is an inevitable fact that sooner or later students will have to deal with non-termination.
But having to learn how to get around it early on can lead to confusion / disenchantment.
Need to provide early on additional tools and understanding . Tabling to the (partial) rescue Tabling to the (partial) rescue table ancestor/2. ?- ancestor(X,Y). Now we not only obtain all answers (even with the first clause order):
X = susan,
Y = mary ? ;
X = susan,
Y = john ? ;
X = mary,
Y = michael ? ;
X = john,
Y = david ? ;
X = susan,
Y = michael ? ;
X = susan,
Y = david ? ;
no but the program also terminates.
We can get this result also with standard Prolog, but need to switch order of goals in the body:
:- module(_,_).
%! \begin{focus}
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) :- parent(X,Y).
ancestor(X,Y) :- parent(Z,Y), ancestor(X,Z).
%! \end{focus} ?- ancestor(X,Y). However, this is not always the case and tabling offers a more powerful mechanism.
Some relevant issues in tabling:
Which predicates to declare as tabled
Does not cover cases outside the bounded term-size property.
More complex cases :- module(_,_).
%! \begin{focus}
natural(0).
natural(s(X)) :- natural(X).
add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mult(0,Y,0) :- natural(Y).
mult(s(X),Y,Z) :- add(W,Y,Z), mult(X,Y,W).
nat_square(X,Y) :- natural(X), natural(Y), mult(X,X,Y).
%! \end{focus} In class, we develop each of predicate with the students reasoning about the (infinite) set of (ground) facts we want to capture (declarative semantics). More complex cases :- module(_,_).
%! \begin{focus}
natural(0).
natural(s(X)) :- natural(X).
add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mult(0,Y,0) :- natural(Y).
mult(s(X),Y,Z) :- add(W,Y,Z), mult(X,Y,W).
nat_square(X,Y) :- natural(X), natural(Y), mult(X,X,Y).
%! \end{focus} Standard Prolog execution provides useful answers for, e.g., mode
nat_square(+,-) .
?- nat_square(s(s(0)), X). and even for mode
nat_square(-,+) which nicely surprises students:
?- nat_square(X,s(s(s(s(0))))). The next obvious temptation is to try: ?- nat_square(X,Y). but only the first, trivial answer is generated and then execution hangs. Cannot be avoided with just tabling. Fairness to the (partial) rescue To deal with these more complex cases we have found it useful to provide a means for selectively switching to other (fair) search rules such as breadth-first or iterative deepening: :- use_package (sr/bfall). Comes with Ciao Prolog, but can be implemented in any Prolog with meta-programming. Of course, with a fair rule everything "works well" for all possible queries .
In the sense that all valid solutions will be found, even if possibly inefficiently. Fairness to the (partial) rescue For example, our problematic query will now enumerate the infinite set of correct answers.
:- module(_,_).
%! \begin{focus}
natural(0).
natural(s(X)) :- natural(X).
add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mult(0,Y,0) :- natural(Y).
mult(s(X),Y,Z) :- add(W,Y,Z), mult(X,Y,W).
nat_square(X,Y) :- natural(X), natural(Y), mult(X,X,Y).
%! \end{focus} ?- nat_square(X,Y). Other benefits of the fair search rules Even for the cases in which depth-first works, in bf:
The ``quality'' in the solution enumeration greatly improves! For example, for the Peano example, in depth-first search: :- module(_,_).
%! \begin{focus}
natural(0).
natural(s(X)) :- natural(X).
add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mult(0,Y,0) :- natural(Y).
mult(s(X),Y,Z) :- add(W,Y,Z), mult(X,Y,W).
%! \end{focus} ?- mult(X,Y,Z). It is clear that some answers will never be generated. Would be a bad trainer for a learning system! Other benefits of the fair search rules Even for the cases in which depth-first works
the ``quality'' in the solution enumeration greatly improves! While in breadth-first search: :- module(_,_).
%! \begin{focus}
:- use_package(sr/bfall).
natural(0).
natural(s(X)) :- natural(X).
add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mult(0,Y,0) :- natural(Y).
mult(s(X),Y,Z) :- add(W,Y,Z), mult(X,Y,W).
%! \end{focus} ?- mult(X,Y,Z). Clearly more informative, satisfying, and useful for subsequent predicates.
Other benefits of the fair search rules In Ciao Prolog marking predicates as types (or in general as properties) allows them to be used in assertions. However, remain regular predicates can be:
called as any other, used as run-time tests (dynamic checking), "run backwards" to generate examples or test cases (property-based testing), etc. Other benefits of the fair search rules In Ciao Prolog marking predicates as types (or in general as properties) allows them to be used in assertions. However, remain regular predicates can be:
called as any other, used as run-time tests (dynamic checking), "run backwards" to generate examples or test cases (property-based testing), etc. For example:
:- module(_,_).
%! \begin{focus}
:- use_package([assertions,regtypes]).
% :- use_package(sr/bfall).
:- regtype color/1.
color(red).
color(green).
color(blue).
:- regtype colorlist/1.
colorlist([]).
colorlist([H|T]) :- color(H), colorlist(T).
%! \end{focus} ?- colorlist(L). Depth-first correct answers, but not very satisfying. Breadth-first much better! Other benefits of the fair search rules In Ciao Prolog marking predicates as types (or in general as properties) allows them to be used in assertions. However, remain regular predicates can be:
called as any other, used as run-time tests (dynamic checking), "run backwards" to generate examples or test cases (property-based testing), etc. For example (in Ciao's
functional notation ):
:- module(_,_).
%! \begin{focus}
:- use_package([fsyntax,assertions,regtypes]).
% :- use_package(sr/bfall).
:- regtype color/1.
color := red | green | blue.
:- regtype colorlist/1.
colorlist := [] | [~color|~colorlist].
%! \end{focus} ?- colorlist(L). Depth-first correct answers, but not very satisfying. Breadth-first much better! Fair search rules are great, but they cannot do the impossible After playing with a fair search rule, students will observe that it does provide all the expected answers, but sometimes hangs after that. Ah, that pesky semi-decidability (a.k.a, halting problem)...
We cannot completely solve non-termination! It is important thus to explain better what is going on.
Characterization of the search tree
All solutions are at finite depth in the tree. Failures can be at finite depth or, in some cases, be an infinite branch. Depth-First Search
Incomplete: may fall through an infinite branch before finding all solutions. But very efficient: it can be implemented with a call stack, very similar to a traditional programming language. Breadth-First Search
Will find all solutions before falling through an infinite branch. But costly in terms of time and memory. Used in all the following examples (via Ciao's bf package).
From specifications to efficient programs OK, so can we have executable specifications.
Are they efficient?
Sometimes, efficiency not even needed... If not, do we then need to go to an imperative language?
No, we can gradually optimize the performance-sensitive parts within Prolog From Specifications to Efficient Programs :- module(_,_).
%! \begin{focus}
:- use_package(sr/bfall).
mod(X,Y,Z) :- less(Z, Y), mult(Y,_Q,W), add(W,Z,X).
%! \end{focus} Program clearly correct (it is the specification!). And with bf all the infinite solutions are enumerated. ?- op(500,fy,s).
?- mod(X,Y, s 0). But it can of course be quite inefficient. However, we can write a much more efficient version, also within (pure) Prolog:
Works well in depth-first for several modes. However, enumeration of solutions is again biased. Again, we can also show the constraints version. And we can discuss modes and how they affect determinism, cost, termination, etc.
Depth-first / Breadth-first / Iterative Deepening
Just the Ciao naive implementations: no claim of optimality! Only one program, no claim of generality! %! \begin{jseval}
async (pg) => {
let e = pg.preview_el;
e.innerHTML = `
<br>
<br>
<br>
<br>
<br>
<center>
<h1>Thanks!</h1>
</center>
`;
pg.show_preview(true);
pg.update_inner_layout();
}
%! \end{jseval} %! \begin{jseval}
async (pg) => {
let e = pg.preview_el;
e.innerHTML = `
<br>
<br>
<br>
<br>
<br>
<center>
<h1>Additional slides</h1>
</center>
`;
pg.show_preview(true);
pg.update_inner_layout();
}
%! \end{jseval} Polynomials Recognizing (and generating!) polynomials in some term X: X is a polynomial in X a constant is a polynomial in X sums, differences and products of polynomials in X are polynomials also polynomials raised to the power of a natural number and the quotient of a polynomial by a constant
polynomial (X ,X ).
polynomial (Term ,X ) :- pconstant(Term ).
polynomial (Term1 +Term2 ,X ) :- polynomial(Term1 ,X ), polynomial(Term2 ,X ).
polynomial (Term1 -Term2 ,X ) :- polynomial(Term1 ,X ), polynomial(Term2 ,X ).
polynomial (Term1 *Term2 ,X ) :- polynomial(Term1 ,X ), polynomial(Term2 ,X ).
polynomial (Term1 /Term2 ,X ) :- polynomial(Term1 ,X ), pconstant(Term2 ).
polynomial (Term1 ^N ,X ) :- polynomial(Term1 ,X ), nat(N ). Derivative (and Integrals!) deriv(Expression, X, Derivative)
deriv (X ,X ,s(0)).
deriv (C ,X ,0) :- pconstant(C ).
deriv (U +V ,X ,DU +DV ) :- deriv(U ,X ,DU ), deriv(V ,X ,DV ).
deriv (U -V ,X ,DU -DV ) :- deriv(U ,X ,DU ), deriv(V ,X ,DV ).
deriv (U *V ,X ,DU *V +U *DV ) :- deriv(U ,X ,DU ), deriv(V ,X ,DV ).
deriv (U /V ,X ,(DU *V -U *DV )/V ^s(s(0))) :- deriv(U ,X ,DU ), deriv(V ,X ,DV ).
deriv (U ^s(N ),X ,s(N )*U ^N *DU ) :- deriv(U ,X ,DU ), nat(N ).
deriv (log(U ),X ,DU /U ) :- deriv(U ,X ,DU ).
... ?- deriv(s(s(s(0)))*x+s(s(0)),x,Y). A simplification step can be added. Recursive Programming: Automata (Graphs) Recognizing the sequence of characters accepted by the following non-deterministic, finite automaton (NDFA): where q0 is both the initial and the final state.
Strings are represented as lists of constants (e.g., [a,b,b] ). Program: initial (q0). delta (q0,a,q1).
delta (q1,b,q0).
final (q0). delta (q1,b,q1).
accept (S ) :- initial(Q ), accept_from(S ,Q ).
accept_from ([],Q ) :- final(Q ).
accept_from ([X |Xs ],Q ) :- delta(Q ,X ,NewQ ), accept_from(Xs ,NewQ ). Recursive Programming: Automata (Graphs) (Contd.) A nondeterministic, stack, finite automaton (NDSFA): accept (S ) :- initial(Q ), accept_from(S ,Q ,[]).
accept_from ([],Q ,[]) :- final(Q ).
accept_from ([X |Xs ],Q ,S ) :- delta(Q ,X ,S ,NewQ ,NewS ),
accept_from(Xs ,NewQ ,NewS ).
initial (q0).
final (q1).
delta (q0,X ,Xs ,q0,[X |Xs ]).
delta (q0,X ,Xs ,q1,[X |Xs ]).
delta (q0,X ,Xs ,q1,Xs ).
delta (q1,X ,[X |Xs ],q1,Xs ). What sequence does it recognize? Recursive Programming: Towers of Hanoi Objective: Move tower of N disks from peg a to peg b , with the help of peg c . Rules: Only one disk can be moved at a time. A larger disk can never be placed on top of a smaller disk.
Recursive Programming: Towers of Hanoi (Contd.) We will call the main predicate hanoi_moves(N,Moves) N is the number of disks and Moves the corresponding list of ''moves''. Each move move(A, B) represents that the top disk in A should be moved to B. Example:
is represented by:
hanoi_moves ( s(s(s(0))),
[ move(a,b), move(a,c), move(b,c), move(a,b),
move(c,a), move(c,b), move(a,b) ]) Recursive Programming: Towers of Hanoi (Contd.) A general rule:
We capture this in a predicate hanoi(N,Orig,Dest,Help,Moves) where ''Moves contains the moves needed to move a tower of N disks from peg Orig to peg Dest , with the help of peg Help .''
hanoi (s(0),Orig ,Dest ,_Help ,[move(Orig , Dest )]).
hanoi (s(N ),Orig ,Dest ,Help ,Moves ) :-
hanoi(N ,Orig ,Help ,Dest ,Moves1 ),
hanoi(N ,Help ,Dest ,Orig ,Moves2 ),
append(Moves1 ,[move(Orig , Dest )|Moves2 ],Moves ). And we simply call this predicate: hanoi_moves (N ,Moves ) :-
hanoi (N ,a,b,c,Moves ). Recursive Programming: Arithmetic/Functions The Ackermann function: ackermann (0,N ) = N +1
ackermann (M ,0) = ackermann(M -1,1)
ackermann (M ,N ) = ackermann(M -1,ackermann(M ,N -1)) In Peano arithmetic: ackermann (0,N ) = s(N )
ackermann (s(M1 ),0) = ackermann(M1 ,s(0))
ackermann (s(M1 ),s(N1 )) = ackermann(M1 ,ackermann(s(M1 ),N1 )) Can be defined as: ackermann (0,N ,s(N )).
ackermann (s(M1 ),0,Val ) :- ackermann(M1 ,s(0),Val ).
ackermann (s(M1 ),s(N1 ),Val ) :- ackermann(s(M1 ),N1 ,Val1 ),
ackermann(M1 ,Val1 ,Val ). In general, functions can be coded as a predicate with one more argument, which represents the output (and additional syntactic sugar often available). Recursive Programming: Arithmetic/Functions (Functional Syntax) Syntactic support available (see, e.g., the Ciao fsyntax and functional packages). The Ackermann function (Peano) in Ciao's functional Syntax and defining s as a prefix operator: :- use_package (functional).
:- op (500,fy,s).
ackermann ( 0, N ) := s N .
ackermann (s M , 0) := ackermann(M , s 0).
ackermann (s M , s N ) := ackermann(M , ackermann(s M , N ) ). Convenient in other cases -- e.g. for defining types: nat (0).
nat (s(X )) :- nat(X ). Using special := notation for the ''return'' (last) argument: nat := 0.
nat := s(X ) :- nat(X ). Recursive Programming: Arithmetic/Functions (Funct. Syntax, Contd.) Moving body call to head using the
~ notation (''evaluate and replace with result''):
nat := 0.
nat := s(~nat ).''
~ '' not needed with
functional package if inside its own definition:
nat := 0.
nat := s(nat).Using an
:- op(500,fy,s). declaration to define
s as a
prefix operator :
nat := 0.
nat := s nat.Using ''
| '' (disjunction):
nat := 0 | s nat.Which is exactly equivalent to:
nat (0).
nat (s(X )) :- nat(X ). On system types System types:
Classical installation: most appropriate for more advanced students / "real" use. Show serious, competitive language. Playgrounds and notebooks --see PL50 Book papers! (e.g., Ciao Playground/Active Logic Documents, SWISH, -Prolog, SICStus+Jupyter).
Can be attractive for beginners, young students. Some places (e.g., schools) may not have personnel/machines for installation, but will have a tablet. Server-based vs. browser-based. Very useful for executable examples in manuals and tutorials. Offer both types to students! Block-based versions can be useful starters for youngest (cf. Laura Cecchi's paper in PL50 Book)
Also, nice tool for kids developed by J.F.Morales and S. Abreu for the Prolog Year (see PL50 Book). Ideally the system should allow covering:
pure LP (with several search rules, tabling), ISO-Prolog, higher-order support and functional syntax, constraints, ASP/s(CASP), etc. Much more in the related
PL50 book papers and our
teaching materials page .