☰

Teaching Pure LP with Prolog and a Fair Search Rule



// Automatic presentation mode (even from playground)
if (main_doc !== pg.pgset.main_doc) main_doc.pgset.cells[0].toggle_presentation();
// Set slideshow mode
pg.pgset.main_doc.set_slide_mode(true);
// Changing some fonts and spacing from lpdoc.css
const cssString = `

/* A bit less space before and after the title */
div.lpdoc-cover-title {
    margin-top: -20px;
    margin-bottom: -20px;
}

/* A bit more space on slides */
.lpdoc-slide-mode .lpdoc-slide {
  width: calc(100% - 32px);
  height: calc(100% - 0px);
  /*        T    R   B    L */
  padding: 0px 16px 0px 16px;
}

/* A bit less space for slide titles */
h2 {
    line-height: 1em;
    margin-bottom: 0.3em;
}

/* A bit less space aroud the notes */
.lpdoc-note {
    /*        T    R   B    L */
    padding: 4px 8px 4px 8px;
}

/* A bit less space above and below the runnables */
.lpdoc-runnable-container {
    position: relative;
    margin-top: 0.5em;
    margin-bottom: 0.5em;
}

.lpdoc-runnable-editor-container,
.lpdoc-runnable-container .comint-editor-container {
  border: 1px solid var(--codeblock-border);
  border-radius: 10px;
  padding-top: 4px;
  padding-bottom: 4px;
  background: var(--codeblock-bg);
}
`;
const style_el = document.createElement("style");
style_el.textContent = cssString;
document.head.appendChild(style_el);

¹ Universidad Politécnica de Madrid (UPM)

² IMDEA Software Institute

³ Spanish Council for Scientific Research (CSIC)

// Injecting arbitrary HTML (needs better interface of course)
let e = pg.preview_el;
e.innerHTML = `
<small>
With thanks to David S. Warren and Daniela Ferreiro for their feedback.
</small>
  `;
pg.show_preview(true);
pg.update_inner_layout();

This presentation corresponds to the paper Teaching Pure LP with Prolog and a Fair Search Rule, in the Prolog Education Group's (PEG 2.0) 2024 Workshop at ICLP 2024.

See also our Course material on logic and constraint logic programming page for more details.

These slides are an Active Logic Document which can be edited using the Ciao Prolog Playground.

Intro

  • Here: we 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, as needed.

The vision is easy to convey at first

  • The first examples - family relations: 
:- module(_,_).

%! \begin{focus}
mother_of(susan, mary).             % To load the program, we click on the '?' --->
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 - all is good!: 
?- mother_of(susan,Y).
?- mother_of(X,mary).
?- grandmother_of(X,Y).

The vision is easy to convey at first

  • Many great examples - e.g., circuit topology: 
:- module(_,_).
:- discontiguous(resistor/2).
:- discontiguous(transistor/3).

%! \begin{focus}
resistor(power,n1).            transistor(n2,ground,n1).
resistor(power,n2).            transistor(n3,n4,n2).
                               transistor(n5,ground,n4). 

inverter(In,Out) :- transistor(In,ground,Out), resistor(power,Out).

nand_gate(In1,In2,Out) :- transistor(In1,X,Out), transistor(In2,ground,X), resistor(power,Out).
   
and_gate(In1,In2,Out) :- nand_gate(In1,In2,X), inverter(X, Out).
%! \end{focus}
?- and_gate(In1,In2,Out).
All still good: all queries will return the correct solution and terminate in standard Prolog!

However, things can quickly get more complicated...

But eventually 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}
  • But now standard Prolog hangs for any query: 
?- ancestor(X,Y).

But eventually 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}
  • We can however change above the order of the ancestor/2 clauses. Now: 
?- ancestor(X,Y).
  • Better: standard Prolog obtains all the answers... but 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 too early how to get around it can lead to confusion / disenchantment.

  • We need to provide early-on:

    • additional tools and
    • additional explanations.

Tabling to the (partial) rescue

  • Pioneered by XSB and now in B-Prolog, Ciao, SWI, YAP.
  • We can mark ancestor/2as a tabled predicate: 
:- table ancestor/2.

Tabling to the (partial) rescue

  • Pioneered by XSB and now in B-Prolog, Ciao, SWI, YAP.
  • We can mark ancestor/2as a tabled predicate: 
:- table ancestor/2.

  • Now we 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
  • and the program also terminates!

Tabling to the (partial) rescue

  • We can get the results also with standard Prolog if we switch the 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).
  • And, we can cover multiple cases using delays, but,

    • this is starting to get too hard for the initial classes, and
    • it does not always work.
  • Tabling is a powerful mechanism!

  • However, it only ensures termination for programs with the bounded term size property:

    • The sizes of all subgoals and answers must be less than some fixed number.

Dealing with terms of unbounded size

  • Often the case with simple programs using lists, trees, etc. E.g., Peano arithmetic: 
natural(0).
natural(s(X)) :- natural(X).

add(0,Y,Y) :- natural(Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
  • In class, we can help students develop predicates like this by:

    • thinking about the (infinite) ground facts to be captured (i.e., the declarative semantics), e.g.: 
natural(0).     natural(s(0)).    natural(s(s(0))).     ...
  • and generalizing by, e.g., thinking inductively (base case + step), to: 
natural(0).
natural(s(X)) :- natural(X).
  • But, will they always work?

Dealing with terms of unbounded size

:- 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.
  • And this cannot be avoided with 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.
We argue that these modes are ideal for the first steps of teaching LP and Prolog.

Fairness to the (partial) rescue

  • For example, our problematic query will now enumerates 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).

Efficiency: depth-first vs. breadth-first vs. iterative deepening

  • This is just for one program, and a naive implementation: no claim of optimality!
  • But can be used to illustrate the overall picture.

From specifications to efficient programs

  • OK, so can we have executable specifications, but:

    • Are they efficient?

      • Sometimes they are,
      • and sometimes efficiency is not even needed (prototyping, smaller problems...)
    • But then, if inefficient or after prototyping, do we then need to recode in an imperative language?

      • No, we can gradually optimize the performance-sensitive parts within Prolog!
  • A (very simple) example: defining mod(X,Y,Z)

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

From specifications to efficient programs

  • The specification:

    can be expressed directly in Prolog: 

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

less(0,s(X)):- natural(X).
less(s(X),s(Y)) :- less(X,Y).

%! \begin{focus}
:- use_package(sr/bfall).
mod(X,Y,Z) :- less(Z, Y), mult(Y,_Q,W), add(W,Z,X).
%! \end{focus}
  • The program is clearly correct (it is the specification!).
  • And (with a fair search rule) all the infinite solutions are enumerated: 
?- op(500,fy,s).
?- mod(X, Y, s 0).
  • But it can of course be inefficient.
  • However, we can write a much more efficient version, also within (pure) Prolog, which:

    • Works well in depth-first for several modes.
    • However, enumeration of solutions is again biased.
  • We can also show the constraints version.
  • And we can discuss modes and how they affect determinism, cost, termination, etc.

Some comments on the use Peano arithmetic

  • Very useful as instructive, reversible substitute for non-reversible is/2, >, etc.

    for the first parts of the course.

  • Enables many elegant examples in the early steps of learning recursion and recursive data structures.

  • We also sometimes use constraints as alternative (as, e.g., [Neumerkel & Triska]), but note that:
  • This 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 we introduce them later.

Final remarks

  • Prolog is beautiful!
  • But:
  • Not dealing with Prolog (non-)termination early on can work against this perception.
  • How to deal with it, staying within a Prolog system?
  • Fair search rules and tabling come to the rescue.
  • Also constraints are very useful of course.

  • We covered here just one of many topics in teaching Prolog; see the Prolog50 papers for more.
  • See also: 

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();

let e = pg.preview_el;
 e.innerHTML = `
<br>
<br>
<br>
<br>
<br>
<center>
<h1>Additional examples and discussion</h1>
</center>
`;
pg.show_preview(true);
pg.update_inner_layout();

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 
    :- module(_,_,[sr/bfall]).

natural(0).
natural(s(X)) :- natural(X).

%! \begin{focus}
:- use_package(sr/bfall).
  
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), natural(N).
  
pconstant(a).    pconstant(b).    pconstant(c). 
%! \end{focus}
    ?- polynomial(P,x).

Derivative (and Integrals!)

  • deriv(Expression, X, Derivative) 

    :- module(_,_,[sr/bfall]).

natural(0).
natural(s(X)) :- natural(X).

%! \begin{focus}
:- use_package(sr/bfall).

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), natural(N).
deriv(log(U),X,DU/U)               :- deriv(U,X,DU).
% ...

pconstant(a).    pconstant(b).    pconstant(c).
pconstant(X) :- natural(X).
%! \end{focus}
    ?- deriv( s(s(s(0)))*x+s(s(0)), x, D).
    ?- deriv(I, x, 0*x+s(s(s(0)))*s(0)+0).
  • A simplification step can of course be added.

Recursive Programming: Automata (Graphs)

  • Recognizing the sequence of characters accepted by a 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]).

    :- module(_,_,[sr/bfall]).

%! \begin{focus}
:- use_package(sr/bfall).

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([C|Cs],Q) :- delta(Q,C,NewQ), accept_from(Cs,NewQ).
%! \end{focus}
  • Check if these sequences accepted: 
    ?- accept([a,b,b]).
    ?- accept([a,b,b,a]).
  • List all sequences of 4 chars: 
    ?- accept([A, B, C, D]).
  • List all accepted sequences: 
    ?- accept(X).

Recursive Programming: Automata (Graphs) (Contd.)

  • A Nondeterministic PushDown Automaton (NPDA):

    :- module(_,_,[sr/bfall]).

%! \begin{focus}
:- use_package(sr/bfall).

accept(S) :- initial(Q), accept_from(S, Q, []).

accept_from([],     Q, []   ) :- final(Q).
accept_from([C|Cs], Q, Stack) :- 
    delta(Q, C, Stack, NewQ, NStack), accept_from(Cs, NewQ, NStack).

initial(q0).   final(q1).

delta(q0, C,     Stack, q0, [C|Stack]).
delta(q0, C,     Stack, q1, [C|Stack]).
delta(q0,_C,     Stack, q1,    Stack ).
delta(q1, C, [C|Stack], q1,    Stack ).
%! \end{focus}
    ?- accept([a,b,b,a]).
    ?- accept([a,b,c,b,a]).
    ?- accept([a,b,c,c,b,a]).
    ?- accept([a,b,X,a]).
    ?- accept([A, B, C, D]).
  • List all accepted sequences: 
    ?- accept(X).
  • 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.'' 

    :- module(_,_).

%! \begin{focus}
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).

hanoi_moves(N,Moves) :- hanoi(N,a,b,c,Moves).
%! \end{focus}
  • And we simply call hanoi_moves/2: 
    ?- hanoi_moves(s(s(s(0))),M).
    ?- hanoi_moves(N,M).

Functional Syntax

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

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

%! \begin{focus}
:- 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) ).
%! \end{focus}
    ?- op(500,fy,s).
    (defines s as a prefix operator to save us writing parenthesis) 
    ?- ackermann(s s 0, s s s 0, X).
    But now it also runs in other modes: 
    ?- ackermann(s s 0, s s s 0, s s s s s s s s s 0).
    ?- ackermann(s s 0, Y, s s s s s s s s s 0).
    ?- ackermann(X, s s s 0, s s s s s s s s s 0).

Functional Syntax

Convenient in other cases -- e.g. for defining types

  • Starting with: 
    nat(0).
nat(s(X)) :- nat(X).
  • Using special := notation for the ''return'' (last) argument: 
    nat := 0.
nat := s(X) :- nat(X).
  • 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).

Some considerations on system types for teaching

  • System types:

    • Classical installation: most appropriate for more advanced students and "real" use.

      Shows 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 but will have a tablet.
      • Server-based vs. browser-based.
      • Very useful for executable examples in manuals and tutorials.
      Offer both types to students!
  • Blocky-style 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 (also in 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.

Generated with LPdoc using Ciao