100 Languages Speedrun: Episode 42: Prolog

The computing world had periods of obsession with "Artificial Intelligence" a few times. One such period was during the late 1970s and 1980s when "logic programming" was the big AI idea.

It was so huge and it failed so dismally that by now not only it is largely forgotten, but people rarely even know it ever happened.

Let's take a dive into the history of AI, and check Prolog - the language at the center of those AI attempts, and while it's not any in-depth analysis, we'll bump into a few reasons why it all failed.

Basics

Prolog does logic programming, but it also has some basic ability to do regular programming like I/O and so on. Many Prologs also have builtin constraint solver libraries similar to Z3. I'll stay away from those parts and mostly focus on the core Prolog.

The idea of Prolog is that you define a bunch of formulas. It's not actually possible for computers to handle arbitrary formulas, so Prolog limits it to formulas like A :- B1, B2, B3. meaning A is true if all B are true, notably without negation and quantifiers (like "for all" or "exists"). If you need to do any and / or you can just add extra relations. Everything that fails to prove is treated as false.

Let's start with some basics like Spanish Habsburg family tree:

father(philip3, maria_anna).
father(philip3, philip4).
father(philip4, charles2).

mother(maria_anna, mariana).
mother(mariana, charles2).

parent(A, B) :- father(A, B).
parent(A, B) :- mother(A, B).

grandfather(A, B) :- father(A, X), parent(X, B).
grandmother(A, B) :- mother(A, X), parent(X, B).

grandparent(A, B) :- grandfather(A, B).
grandparent(A, B) :- grandmother(A, B).

greatgrandfather(A, B) :- father(A, X), grandparent(X, B).

Lowercase names are symbols, uppercase names are variables.

Step by step:

• father(A, B) means A is father of B, and is defined by a list of cases
• mother(A, B) means A is mother of B, also by a list of cases
• parent(A, B) is defined with an OR, so it can be true if A is father or mother of B. To do an OR, just list all possibilities.
• grandfather(A, B) is defined with an AND, and also with an internal variable - so A is grandfather of B if A is father of X, and X is parent of B, for some X.
• then grandmother, grandparent, and greandgrandfather are defined similarly.

OK, let's give it a go in interactive session. It's important to note that logical relations these are not functions, so you can go from either direction.

~/langs/episode-xx-prolog(:|✔) % gprolog
| ?- [family].
| ?- father(philip4, X).

X = charles2

yes
| ?- father(X, philip4).

X = philip3 ?

In Prolog all definitions are treated as complete. So if someone's mother is not on the list, they just don't have a mother, like poor Philip 4.

yes
| ?- mother(X, philip4).

no

We can also ask for any combination of relations:

| ?- grandfather(X, Y), greatgrandfather(X, Y).

X = philip3
Y = charles2 ?

yes

Prolog naturally supports multiple answers as well. In interactive use if you're happy with the first one, you can just hit Enter, otherwise press ; for next or a for all:

| ?- father(philip3, X).

X = maria_anna ? ;

X = philip4

yes

Expressions

Relations can be defined not just on "atoms" (or what other languages would generally call "symbols"), but on any expressions. You can define any kind of expression like a(b, c), but we also have a few syntactic sugar, for example, [1, 2, 3] for a list, or a + b * c for math expressions and so on, in the end they're just expressions without any special meaning beyond what we give them.

So let's play with lists and membership and some pattern matching:

list_member(X, [X|_]).
list_member(X, [_|T]) :- list_member(X, T).

member_twice(X, [X|T]) :- list_member(X, T).
member_twice(X, [_|T]) :- member_twice(X, T).

Step by step:

• [X|T] means a list with head (first element) X and tail (rest of the list) T
• if we don't care about some part of the expression, we should mark it as _ - we could just put a variable there, but Prolog warns about unused variables as these are often mistakes, similar to many linters for other languages
• X is list_member if it's first element, or if it's list_member of the rest
• X is member_twice if it's first element and it's list_member of the rest; or if it's member_twice of the rest

As you can see it works both ways:

[member].

| ?- list_member(X, [1,2,3]).

X = 1 ? ;

X = 2 ? ;

X = 3 ? ;

no
| ?- list_member(7, [A, B, C]).

A = 7 ? ;

B = 7 ? ;

C = 7 ? ;

no
| ?- member_twice(X, [1, 2, 3, 1, 2]).

X = 1 ? ;

X = 2 ? ;

no

Prolog does not remember that it returned a given answer already, so it will keep going. As 1 is on the list three times, we get the answer three times:

| ?- list_member(X, [1, 1, 1]).

X = 1 ? ;

X = 1 ? ;

X = 1 ? ;

no

If there are infinitely many answers, it will keep going forever until we tell it to stop:

| ?- member_twice(7, X).

X = [7,7|_] ? ;

X = [7,_,7|_] ? ;

X = [7,_,_,7|_] ? ;

X = [7,_,_,_,7|_] ? ;

X = [7,_,_,_,_,7|_] ? ;

X = [7,_,_,_,_,_,7|_] ?

yes

Prolog Fails

OK, that was enough for an introduction, let's get ot Prolog fails.

For example let's get back to Spanish Habsburg family tree and define what it means to be an ancestor in two ways:

father(philip3, maria_anna).
father(philip3, philip4).
father(philip4, charles2).

mother(maria_anna, mariana).
mother(mariana, charles2).

parent(A, B) :- father(A, B).
parent(A, B) :- mother(A, B).

ancestor1(A, B) :- parent(A, B).
ancestor1(A, B) :- parent(A, X), ancestor1(X, B).

ancestor2(A, B) :- parent(A, B).
ancestor2(A, B) :- ancestor2(X, B), parent(A, X).

They're logically totally equivalent A and B is exactly the same thing as B and A. So do they work the same?

$ gprolog
| ?- [family2].
| ?- ancestor1(X, charles2).

X = philip4 ? ;

X = mariana ? ;

X = philip3 ? ;

X = philip3 ? ;

X = maria_anna ? ;

no
| ?- ancestor2(X, charles2).

X = philip4 ? ;

X = mariana ? ;

X = philip3 ? ;

X = maria_anna ? ;

X = philip3 ? ;

Fatal Error: local stack overflow (size: 16384 Kb, reached: 16384 Kb, environment variable used: LOCALSZ)

The first definition works just fine. The second crashes with infinite recursion. Even more often you accidentally write something that's pathologically slow.

With some experience you can learn to avoid and debug such issues of course. I've intentionally chosen a super simple example so you can see why it crashes. In real code, it won't be so easy.

The point is - at first Prolog pretends it's all about declarative programming and you just define the "what" and let it handle the "how". In reality you need to be constantly thinking about "how" Prolog would execute your code. And if you have to think about the "how", and structure your programs carefully by reordering, cuts, and all other techniques to manage tho "how", you might just as well use a regular programming language.

It might seem like I'm expecting too much, but with something like Z3, you can really be declarative.

Math

OK, let's do some arithmetic. We can start with the obvious, length of the list:

len(0, []).
len(L, [_|T]) :- len(LT, T), L=1+LT.

Empty list has length of 0, any other list has length of 1 plus length of the rest.

| ?- [len].
| ?- len(L, [1,2,3]).

L = 1+(1+(1+0)) ?

yes

What just happened? Prolog doesn't do math, it just matches expressions by shape. Prolog has is operator that does the math, but it's quite limited.

len(0, []).
len(L, [_|T]) :- len(LT, T), L is 1+LT.

That works a bit better:

| ?- [len2].
| ?- len(X, [1,2,3]).

X = 3 ?

yes
| ?- len(3, X).

X = [_,_,_] ?

yes

Let's define sum of a list of numbers:

sum(0, []).
sum(S, [H|T]) :- sum(ST, T), S is H+ST.

Unfortunately it works only one way, you can do variable is expression, but only if every variable on the right side is resolved to a number:

| ?- [sum].
| ?- sum(X, [1,2,3]).

X = 6 ?

yes
| ?- sum(6, [A, B, C]).
uncaught exception: error(instantiation_error,(is)/2)

Even if the answer is completely unambiguous, it still fails:

| ?- sum(6, [A]).
uncaught exception: error(instantiation_error,(is)/2)

Unary Math

Let's avoid is, and use "unary" mathematics. All numbers will be either z or s(something) which means. So z is 0, s(z) is 1, s(s(z)) is 2, and so on:

add(A, z, A).
add(A, s(B), s(C)) :- add(A, B, C).

This is really hard to read, especially for big numbers, but at least it works both directions:

| ?- [unary_math].
| ?- add(s(s(z)), s(s(s(z))), N).

N = s(s(s(s(s(z))))) ?

yes
| ?- add(s(s(z)), N, s(s(s(z)))).

N = s(z) ?

yes

Because it uses pure Prolog only we can now define a list sum that works both ways:

sum(z, []).
sum(S, [H|T]) :- sum(ST, T), add(H, ST, S).

That works forwards and backwards:

| ?- sum(S, [s(z), s(s(z))]).

S = s(s(s(z))) ?

yes
| ?- sum(s(s(s(s(s(s(z)))))), [A, B]).

A = s(s(s(s(s(s(z))))))
B = z ? ;

A = s(s(s(s(s(z)))))
B = s(z) ? ;

A = s(s(s(s(z))))
B = s(s(z)) ? ;

A = s(s(s(z)))
B = s(s(s(z))) ? ;

A = s(s(z))
B = s(s(s(s(z)))) ? ;

A = s(z)
B = s(s(s(s(s(z))))) ? ;

A = z
B = s(s(s(s(s(s(z)))))) ? ;

no

Awesome! Let's try to ask Prolog if there's any N, such that N+1=N. The answer as you can probably guess should be no.

| ?- add(N, s(z), N).

cannot display cyclic term for N ?

yes
| ?- add(s(z), N, N).

Fatal Error: global stack overflow (size: 32768 Kb, reached: 32765 Kb, environment variable used: GLOBALSZ)

What the hell just happened? One way we asked we got a yes, with infinitely defined N = s(N). The other way we got a crash. There are workarounds, but so far every "logic" we tried, no matter how simple, runs into needing workarounds almost immediately. Which is the total opposite of the Z3 experience where you can declare some formulas, and things Just Work.

FizzBuzz

Let's do a FizzBuzz with fairly conventional programming:

divisible(N, D) :- 0 is N mod D.
not_divisible(N, D) :- \+ divisible(N, D).

fizzbuzz(N, 'FizzBuzz') :- divisible(N, 15).
fizzbuzz(N, 'Fizz') :- divisible(N, 3), not_divisible(N, 5).
fizzbuzz(N, 'Buzz') :- divisible(N, 5), not_divisible(N, 3).
fizzbuzz(N, N) :- not_divisible(N, 3), not_divisible(N, 5).

num_between(A, A, B) :- A =< B.
num_between(X, A, B) :- A1 is A+1, num_between(X, A1, B).

write_fizzbuzz(X) :- fizzbuzz(X, W), write(W), nl.

fizzbuzzloop :-
  num_between(1, 100, X),
  write_fizzbuzz(X),
  fail.

Step by step:

• divisible is a predicate that checks if a number is divisible by another
• not_divisible uses \+ which means "not provable". \+ divisible(N, D) checks if divisible(N, D) is provable. If not, then \+ divisible(N, D) is provable. This is not quite the same thing as negation, but in many context it's close enough.
• fizzbuzz(N, W) is a relationship saying that for number N FizzBuzz output value should be W. We need to add all the not clauses, as Prolog is totally fine with multiple matches. For example if we didn't add not checks, fizzbuzz(15, W) would match W being equal to all four possibilities.
• num_between(X, A, B) is true for every X between A and B and we can use it as a loop
• write_fizzbuzz(X) figures out what's the correct FizzBuzz output for X, writes that out, and writes newline.
• fizzbuzz loop is where we pretty much exit logic programming. It gets a number between 1 and 100 as X, uses write_fizzbuzz(X) to write it out, and then fails, causing it to retry with another number. The whole thing technically "fails" but it prints the FizzBuzz output anyway.

| ?- [fizzbuzz].
| ?- fizzbuzzloop.
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
[...]
Buzz
Fizz
97
98
Fizz
Buzz

no

Well, the I/O code being non-logic is understandable, but we'd like to be able to at least use fizzbuzz(N, W) logically.

It works in forward direction just fine:

| ?- fizzbuzz(14, W).

W = 14

yes
| ?- fizzbuzz(15, W).

W = 'FizzBuzz' ? ;

no

But in backwards direction only for some numbers (the non-Fizz non-Buzz ones):

| ?- fizzbuzz(N, 29).

N = 29

yes
| ?- fizzbuzz(N, 20).

no
| ?- fizzbuzz(N, 'Fizz').
uncaught exception: error(instantiation_error,(is)/2)
| ?- fizzbuzz(N, 'FizzBuzz').
uncaught exception: error(instantiation_error,(is)/2)

FizzBuzz with Unary Math

This isn't quite pure Prolog, as I turn unary numbers to regular integers for I/O and readability, but the FizzBuzz core is pure Prolog at least:

not_zero(s(_)).

% A + B = C
add(A, z, A).
add(A, s(B), s(C)) :- add(A, B, C).

% A - B = C
sub(A, B, C) :- add(C, B, A).

% N divides D if:
% - N is zero
% - N-D divides D
% (there are no negative numbers in our representation, so no infinite loops)
divisible(z, D) :- not_zero(D).
divisible(N, D) :- not_zero(D), sub(N, D, NminusD), divisible(NminusD, D).
not_divisible(N, D) :- \+ divisible(N, D).

% We just use this for I/O and testing
tonum(z, 0).
tonum(s(N), Num) :- tonum(N, Num1), Num is Num1+1.

fromnum(0, z).
fromnum(Num, s(N)) :- Num > 0, Num1 is Num-1, fromnum(Num1, N).

% Just to make fizzbuzz more readable
divisible_by_three(N) :- divisible(N, s(s(s(z)))).
not_divisible_by_three(N) :- \+ divisible_by_three(N).
divisible_by_five(N) :- divisible(N, s(s(s(s(s(z)))))).
not_divisible_by_five(N) :- \+ divisible_by_five(N).

fizzbuzz(N, 'FizzBuzz') :- divisible_by_three(N), divisible_by_five(N).
fizzbuzz(N, 'Fizz') :- divisible_by_three(N), not_divisible_by_five(N).
fizzbuzz(N, 'Buzz') :- divisible_by_five(N), not_divisible_by_three(N).
fizzbuzz(N, W) :- not_divisible_by_three(N), not_divisible_by_five(N), tonum(N, W).

% We could define this without the tonum/fromnum, but it's a bit more readable
num_between(X, A, B) :- A =< B, fromnum(A, X).
num_between(X, A, B) :- A < B, A1 is A+1, num_between(X, A1, B).

write_fizzbuzz(X) :- fizzbuzz(X, W), write(W), nl.

fizzbuzzloop :-
  num_between(X, 1, 100),
  write_fizzbuzz(X),
  fail.

Step by step:

• unary numbers are z for 0, or s(N) for 1+N
• add, sub, and divisible are defined for unary numbers
• tonum and fromnum convert between unary numbers and regular integers. Logically we should have one predicate that can handle both convert(Unary, Num) depending on which one is variable, but that doesn't work without some serious hacks as is only allows data to flow one way.
• divisible_by_three etc. are just trivial convenience predicates
• fizzbuzz is defined as before, except we use tonum for printing, as we want fizzbuzz(s(z), 1) not fizzbuzz(s(z), s(z))
• I reused num_between and just added fromnum so it generates unary numbers - but it still takes integers as arguments, as I really didn't want to express 100 as s(s(s(...))) 100 times nested
• and the loop itself is the same

The result is of course the same:

| ?- [fizzbuzz2].
| ?- fizzbuzzloop.
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
...
Buzz
Fizz
97
98
Fizz
Buzz

no

However this time fizzbuzz predicate works both ways, we can do some proper logic, and ask questions like "which numbers convert to Fizz or Buzz"!

| ?- fizzbuzz(N, 'Fizz').

N = s(s(s(z))) ? ;

N = s(s(s(s(s(s(z)))))) ? ;

N = s(s(s(s(s(s(s(s(s(z))))))))) ? ;

N = s(s(s(s(s(s(s(s(s(s(s(s(z)))))))))))) ?

yes
| ?- fizzbuzz(N, 'Buzz'), tonum(N, W).

N = s(s(s(s(s(z)))))
W = 5 ? ;

N = s(s(s(s(s(s(s(s(s(s(z))))))))))
W = 10 ? ;

N = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(z))))))))))))))))))))
W = 20 ? ;

N = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(z)))))))))))))))))))))))))
W = 25 ?

yes

Oh by the way, if we reversed the definiton of fizzbuzz and instead declared:

fizzbuzz(N, 'FizzBuzz') :- divisible_by_three(N), divisible_by_five(N).
fizzbuzz(N, 'Fizz') :- not_divisible_by_five(N), divisible_by_three(N).
fizzbuzz(N, 'Buzz') :- not_divisible_by_three(N), divisible_by_five(N).
fizzbuzz(N, W) :- not_divisible_by_three(N), not_divisible_by_five(N), tonum(N, W).

We'd have a fail. I'll let you figure out why if you want, but it just adds up to show what a damn minefield Prolog programming is.

Should you use Prolog?

No.

Logic programming was tried, hundreds of billions of yen were spent to make it happen between Japanese government and industry, and it was decisively shown to be a miserable failure. There weren't even any real lessons to be learned here, it was a total dead end and utter failure.

Meanwhile, using general purpose programming language like Ruby or Python with a constraint solver library like Z3 does everything logic programming promised, except it actually works.

Pretty much the only way to get any value out of Prolog is to use the bundled constraint solver library (different for every Prolog, but usually there is one, as Prolog is barely usable otherwise). But then you don't even need Prolog. Just use Z3.

Prolog is also fine as an esoteric language. Its computation model is very different from regular programming and also very painful, both great esoteric language features.

Code

All code examples for the series will be in this repository.

Code for the Prolog episode is available here.