☰

Teaching Pure LP with Prolog and a Fair Search Rule



%! \begin{jseval}
async(pgcell) => { pgcell.pgset.main_doc.set_slide_mode(true); }
%! \end{jseval}

¹ Universidad Politécnica de Madrid (UPM)

² IMDEA Software Institute

³ Spanish Council for Scientific Research (CSIC)

%! \begin{jseval}
async (pg) => {
  let e = pg.preview_el;
  e.innerHTML = `
Thanks to David S. Warren and Daniela Ferreiro.
<BR>
<h2>Prolog Education Workshop @ ICLP. October 13, 2024. Dallas</h2>
  `;
  pg.show_preview(true);
  pg.update_inner_layout();
}
%! \end{jseval}

Intro

  • 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. 
:- module(_,_).

%! \begin{focus}
mother_of(susan, mary).
mother_of(susan, john).
mother_of(mary, michael).

father_of(john, david).

grandmother_of(X,Y) :-
    mother_of(X,Z), mother_of(Z,Y).
grandmother_of(X,Y) :-
    mother_of(X,Z), father_of(Z,Y).
%! \end{focus}
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

  • Pioneered by XSB and now in B-Prolog, Ciao, SWI, YAP.
  • Ensures termination for programs with the bounded term size property:

    All sizes of subgoals and answers < some fixed number.

    (This is the case for all ``Datalog'' programs.)

  • Mark ancestor/2as a tabled predicate.

Tabling to the (partial) rescue

  • Pioneered by XSB and now in B-Prolog, Ciao, SWI, YAP.
  • Ensures termination for programs with the bounded term size property:

    All sizes of subgoals and answers < some fixed number.

    (This is the case for all ``Datalog'' programs.)

  • Mark ancestor/2as a tabled predicate: 
:- 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

    • cf. XSB's :- auto_table.

  • 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).

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

  • Defining mod(X,Y,Z)

    ''Z is the remainder from dividing X by Y''

  • Can be expressed directly in Prolog: 
:- 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!

Some comments on Peano arithmetic

  • Useful as instructive, reversible substitute for non-reversible is/2, >, etc. for first parts of the course.

    • We also use constraints as alternative [as, e.g., Neumerkel & Triska]

      • But it requires explaining/justifying an extra, complex "black box": the solver.
      • Peano nicely only uses unification, which students need to be introduced to anyway.
      • We do mention that constraints are more efficient, but will use them more later.
  • Peano also allows many elegant examples for the early steps of learning recursion and recursive data structures.

Final remarks

  • Conveying the beauty.
  • Having to deal with Prolog termination early on can work against.
  • How to deal with it all within a Prolog system?
  • Fair search rules and tabling come to the rescue.
  • Also constraints are very useful of course.
  • Expanded here on one of many topics; see Prolog50 papers for more.
  • Se also: 

%! \begin{jseval}
async (pg) => {
  let e = pg.preview_el;
  e.innerHTML = `
<h1>Thanks!</h1>
 `;
  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 Ndisks 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).

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,
    $\tau$-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 PL50 book papers and teaching materials in https://cliplab.org/logalg

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 funcional 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).

Generated with LPdoc using Ciao