Logic Programming & Prolog

Logic Programming & Prolog

Since we have time, let's take a quick tour of one more programming paradigm: logic programming. It's another example of declarative programming.

The idea: we give logical expressions that describe our results. That is, when the expression is true, we have found a correct result. The language searches for results that make our expressions true and tells us what they are.

Logic Programming & Prolog

The most prominent logic programming language is Prolog.

It has been around since 1972 but has never really been used outside of specific areas. My conclusion: it's good at a few things, but only those.

Predicates

Suppose we want to find paths in a directed graph like this:

We will create a predicate to represent the fact that there is an edge from one node to another: edge(A, B) indicates an edge from A to B.

Predicates

Then we can represent our graph by declaring some facts where edge is true (others are implicitly false): [full code for these examples]

edge(1, 3).
edge(1, 5).
edge(2, 4).
edge(3, 2).
edge(3, 5).
edge(4, 3).
edge(6, 1).
edge(6, 5).

Predicates

When interacting with Prolog code (with SWI-Prolog here), the language is trying to prove that facts are correct. If it can, you can ask it to stop (enter) or try to prove a different way (space).

Here, keep pressing space and learn that edge(1, 3) can be proved one way; edge(1, 6) can't be proven.

?- [graph].
true.

?- edge(1, 3).
true ;
false.

?- edge(1, 6).
false.

Rules

A rule is a way to express a logical implication. This expresses A is true if both B and C are true, or if D is true:

A :- B, C
A :- D

Or in math notation: \[ (B \wedge C \rightarrow A) \wedge (D \rightarrow A) \\ \equiv ((B \wedge C) \vee D) \rightarrow A \]

Rules

This predicate is true when it is possible to get from one node to another in the graph:

connected(X, Y) :- edge(X, Y).
connected(X, Y) :- edge(X, Z), connected(Z, Y).

The graph has a loop, so this can be proved an infinite number of ways (and I pressed enter to stop searching).

?- connected(1, 3).
true ;
true ;
true .

?- connected(1, 4).
true ;
true ;
true .

Searching

Or search for both arguments:

?- connected(A, B).
A = 1,
B = 3 ;
A = 1,
B = 5 ;
A = 2,
B = 4 ;
A = 3,
B = 2 ;
A = 3,
B = 5 .

Searching

Some better logic: we don't just want to know if vertices are connected, but what the path between them is. We will say path(A, B, Path) is true if there is a path from A to B and Path is a list representing the path.

path(X, Y, [X,Y]) :- edge(X, Y).
path(X, Y, [X|Path]) :-
    edge(X, Z),
    path(Z, Y, Path).

The base case is the first line: if there is an edge then there is a path from X to Y consisting of just [X,Y].

Searching

The recursive case:

path(X, Y, [X|Path]) :-
    edge(X, Z),
    path(Z, Y, Path).

There is a path from X to Y if there's an edge X to Z and a path Z to Y. The path is X followed by the Z to Y path.

In Prolog, [H|T] is a cons match, like Haskell's (h:t).

Searching

Now we can search paths in the graph, and the language will find all lists that make the predicate true:

?- path(1, 5, Path).
Path = [1, 5] ;
Path = [1, 3, 5] ;
Path = [1, 3, 2, 4, 3, 5] ;
Path = [1, 3, 2, 4, 3, 2, 4, 3, 5] ;
Path = [1, 3, 2, 4, 3, 2, 4, 3, 2|...] .

Searching

Prolog's search is surprisingly flexible: where can we get, starting at 6, then going to 1?

?- path(6, Dest, [6,1|Path]).
Dest = 1,
Path = [] ;
Dest = 3,
Path = [3] ;
Dest = 5,
Path = [5] ;
Dest = 2,
Path = [3, 2] ;
Dest = 5,
Path = [3, 5] .

Search Limits

We can have Prolog find the hailstone sequence:

hailstone(1, []).
hailstone(N, [H|Tail]) :-
    N > 1,
    mod(N, 2) =:= 0,
    H is div(N, 2),
    hailstone(H, Tail).
hailstone(N, [H|Tail]) :-
    N > 1,
    mod(N, 2) =:= 1,
    H is 3*N + 1,
    hailstone(H, Tail).

The =:= is numeric equality (like == in other languages), and is expresses equality but can be used to search for the left operand (like a mix of = and == in other languages).

Search Limits

It finds the sequence and then (correctly) can't find any other solutions.

?- hailstone(6, HS).
HS = [3, 10, 5, 16, 8, 4, 2, 1] ;
false.

?- hailstone(11, HS).
HS = [34, 17, 52, 26, 13, 40, 20, 10, 5|...] ;
false.

Search Limits

But some expressions can only be searched in one-way. We can't find the answers (N could be 5 or 32) here because the search won't go that direction.

?- hailstone(N, [16, 8, 4, 2, 1]).
ERROR: Arguments are not sufficiently instantiated

Search Limits

The problem is that Prolog tries to satisfy the terms in order.

hailstone(N, [H|Tail]) :-
    N > 1,
    mod(N, 2) =:= 0,
    H is div(N, 2),
    hailstone(H, Tail).

The first thing it would have to do: look at all numbers that satisfy N > 1 and then try all of them to see if mod(N, 2) =:= 0, etc. It refuses.

Search Limits

We can define a predicate for path in the graph without loops:

noloop(X, Y, [X,Y]) :- edge(X, Y).
noloop(X, Y, [X|Path]) :-
    edge(X, Z),
    \+ member(X, Path),
    noloop(Z, Y, Path).

In Prolog, \+ is negation: the expression can not be proved true. Here, X is not already in the path taken.

Search Limits

Again, we find that Prolog can't search past the negation: it can only prove things are true, not that they are false. Thus it can check with this rule but not search:

?- noloop(1, 4, [1,3,2,4]).
true .

?- noloop(1, 4, Path).
false.

[I'm sure there is a way to work around all of these limitations. If I was a better Prolog programmer, I'd know them.]

Conclusion

My takeaway lessons:

  • Programming languages can be weird.
  • Prolog lets you express yourself in a way you probably never would have imagined as programming.
  • For problems it's good at, it's a very expressive and compact way to solve the problem.
  • Its limits show very quickly.

Conclusion

But there's a more general category of constraint programming tools. If you have a problem where I know these facts about the world, please find a solution is a useful way to look at it, they might save you. A few constraint programming libraries: