Prolog Taolu

The workshop sample solutions are available here

What is Prolog?

Prolog is shit.

Why Prolog is shit?

The Closed World Assumption

Prolog assumes all true things can be derived from the program. This is called the closed world assumtion. So use negation carefully when the predicates are not complete (The query might give False Positive results).

Negation as failure

Prolog executes \+ G by first try to prove G. If it fails, then \+ G succeeds; If it succeeds then \+ G fails. This is called negation as failure. In prolog, failing goals never bind variables, so any variable bindings made in solving G are thrown away when \+ G fails. Therefore, \+ G cannot solve for any variables and gols such as these cannot work properly.

Terms

In Prolog, all data structures are terms, which can be atomic or compound. Atomic terms include integer, float, and atoms. An atom begins with lower case letter or quoted with single quote, for example both prolog_shit and 'Prolog Shit\n' are atoms.

A compound term is a functor followed by zero or more arguments. Functors are Prolog’s equivalent of data constructor, and have the same syntax as atoms, for example

node(leaf, 1, node(leaf, 2, leaf))

represents a tree.

A variable is a single unknown term. Variable names begin with uppercase letters or underscores.、

Ground terms, Substitution, Unification

A term is ground if it contains no variables. A ground term has only one instance, while a non-ground term has an infinite number of instances.

A substitution is a mapping from variables to terms. Applying a substitution to a term means consistently replacing all occurrences of each variable in the map with the term it is mapped to. Substitution only replaces variables.

A substitution unifies two terms if the terms are identical after the substitution.

Prolog debugger, Infinite backtracing loop

Prolog has a shitty debugger. There’s something called Byrd box, like following:

Unlike conventional languages which have only one way to enter and one way to exit, Prolog has two of each. Thing about the following code

/*
    rev1/2
    rev1(A, B) holds if B is reversed version of A
*/
rev1([], []).
rev1([A|BC], CBA) :- 
    rev1(BC, CB),
    append(CB, [A], CBA).

Why the fuck does it enter infinite backtracking loop? for example we have a query

rev1(X, [a])

is was resolved to

rev1(BC, CB),
append(CB, [A], [a]).

The call rev1(BC, CB) produces an infinite backtracking sequesce of solutions, for wach one we call append. append([],[A], [A]) succeeds but the following ones all fail.

In order to make it work in all modes, we need to add samelength(ABC, CBA) in the front.

See? This is why Prolog is shit.

Choicepoints

When a clause succeeds but there are later clauses that could possibly succeed, Prolog will leave a choicepoint so it can later backtrack and try the later clause.

Think about following clauses which computes factorial

fact(0, 1).
fact(N, F) :- 
    N > 0,
    N1 is N - 1,
    fact(N, F1),
    F is F1 * N.

After finding 0!=1, prolog will continue trying -1!, -2!, ..., so we need to add N > 0 at the beginning in order to ensure correctness.

Semantics of logic program

A logic program P consists of a set of predicate definitions. The semantic of this program is the set of its logical consequences as ground atomic formulas

Ground atomic formula is a logical consequence of program P if P makes a true.

How to find semantics? We’re gonna work backwards. We can reason fro mthe program to figure out what ground queries makes it true. Immediate consequence operator TP takes a set of ground unit clauses C and produce the set of ground unit clauses implies by C and P.

For example:


P = {q(X,Z) :- p(X,Y), p(Y,Z)}.
C = {p(a,b), p(b,c), p(c,d)}.

TP = {q(a,c), q(b,d)}.

SLD Resolution

Consequences of logic program are determined through SLD resolution, which is simple? and powerful? and shitty (That’s true). It all about: Given a program, show this goal is true. It works like following:

Backtracking

When there are multiple clauses matching a goal, Prolog remembers which one to go back to if necessary. It must be able to return the computation to the state it was in when the first matching clause was selected, so that it can return to that state and try next matching claise, which called choicepoint.

When a goal fails, Prolog backtracks to the most recent choicepoint, removing all variable bindings made since the choicepoint was created, returning those variables to their unbound state. Then prolog begins to resolution the next matching clause, repeating the process until Prolog detects no more matching clauses. It then removes the checkpoint. The subsequent failures still backtrack to nearest checkpoint.

Index

Index improves Prolog performance because it allows the Prolog to jump to match clauses directly by creating indexes for clauses with distinct constant or functors. SWI Prolog makes indices for arguments other than the first one. For example, parent/2, SWIpl index on both args, so finding the children of a parent or parent of a child both speeds up.

Tail Recursion, TRO and choicepoint

A predicate is tail recursive if and only if the recursive call on any execution of that predicate is the last code executed before returning to the caller. Prolog applied tail recursion optimization (TRO) to prevent recursions from eating up stack. For example, a called b, b called c, there will be three frames on stack storing all the variables so that the routine can be restored after the sub routine returned. TRO is made such that if returning the result of c is the last execution of b, then the variables in be can be released in advance, so the stack can be saved. But if there’s a choice point in b, the program isn’t tail recursive because Prolog need to backtrack to the choicepoint later on.

Write tail recursive code by adding accumulate

Look at this example.

{-
    fact/2 
    fact(N, F) holds if F is the factorial of N
-}

fact(N, F) :- 
    (
        N =:= 0 -> 
        F=1;
        N>0,
        N1 is N - 1,
        fact(N1, F1),
        F is F1 * N
    ).

This is not tail recursive because the last excution is multiplication and substitution. But however we can make it tail recursive by introducing an accumulator, just like this


fact(N, F, C) :- 
    (
        N =:= 0 -> 
        F = C;
        N > 0,
        N1 is N - 1,
        C1 is C * N,
        fact(N1, F, C1)
    ).

Then this is tail recursive.

All solution

If we wanna bring together all solutions to a goal, Prolog’s all solution predicates do exactly this. The definition is

setof(Template, Goal, List).

The Template is like how you wanna present the result. For example, if you wanna display the parent relation of two people, you could use

setof(P-C, parent(P,C), List).
bagof(P-C, parent(P,C), List). % This is for unsorted solutions

Existential quantification can be used with ^. Like following predicate

setof(P, C^parent(P,C), Parents)

This predicate means, put all the solutions in list Parents. The solutions satisfy that “There exist C such that P is the parent of C”, which means find parent of any children.