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 `A`

to `B`

.

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 `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 \]

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 `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]`

.

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)`

.

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 = [3] ; Dest = 5, Path = [5] ; 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).

The

is numeric equality (like `=:=`

`==`

in other languages), and

expresses equality but can be used to search for the left operand (like a mix of `is`

`=`

and `==`

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

In Prolog, `\+`

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:

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

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:

- python-constraint
- OR-Tools (C++, Python, C#, Java)
- Gecode (C++)
- Choco-solver (Java)