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.
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.
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
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).
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.
A rule is a way to express a logical implication. This expresses
A is true if both
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 \]
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 .
We can also search for values that would make the predicate true. (Again, infinite results. Space to search; enter to stop.)
?- connected(1, N). N = 3 ; N = 5 ; N = 2 ; N = 5 ; N = 4 ; N = 3 ; N = 2 .
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 .
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
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
Y consisting of just
The recursive case:
path(X, Y, [X|Path]) :- edge(X, Z), path(Z, Y, Path).
There is a path from
Y if there's an edge
Z and a path
Y. The path is
X followed by the
[H|T] is a cons match, like Haskell's
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|...] .
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 =  ; Dest = 5, Path =  ; Dest = 2, Path = [3, 2] ; Dest = 5, Path = [3, 5] .
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).
is numeric equality (like
== in other languages), and
expresses equality but can be used to search for the left operand (like a mix of
== in other languages).
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.
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
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.
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).
\+ is negation: the expression can not be proved true. Here,
X is not already in the path taken.
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.]
My takeaway lessons: