Thinking in Prolog

I’ve been having a lot of fun working on a side project written in Prolog, which is a logical programming language. It has been incredibly difficult to wrap my mind around how it works but I’m getting there, and I can see that “there” is a pretty powerful place. It makes me wonder why this paradigm isn’t used for more applications.

It turns out (you may already know this if you write code) that programming languages work very differently depending on which paradigm they use.

From Wikipedia:

Common programming paradigms include:

  • imperative in which the programmer instructs the machine how to change its state,
    • procedural which groups instructions into procedures,
    • object-oriented which groups instructions together with the part of the state they operate on,
  • declarative in which the programmer merely declares properties of the desired result, but not how to compute it
    • functional in which the desired result is declared as the value of a series of function applications,
    • logic in which the desired result is declared as the answer to a question about a system of facts and rules,
    • mathematical in which the desired result is declared as the solution of an optimization problem

I’ve found functional programming to be so intuitive and object-oriented (probably the most common paradigm today) to be so counterintuitive that I almost always write my programs in a functional style.

In a logic program, you write down a set of facts and rules. That’s it. That’s your program. And then you run the program by asking it if it can find a solution to a new query.

Prolog in particular is built around a type of logical statement called a Horn clause that basically reads “X is true if Y and Z are true”. In Prolog that would look like:

X :- Y, Z.

A more complete program (but still tiny) program would look like:

food(sandwich). % declaring a fact that sandwich is a food
drink(water). % declaring that water is a drink

meal(X, Y) :- food(X), drink(Y).
% X and Y (variables) make a meal if X is a food & Y is a drink

When you run this program, you’ll get:

?- meal(X, Y).
X = sandwich,
Y = water.

That’s a toy example, but you can see how quickly the complexity could build up with ever-more relationships and so on. I’m working on writing a program to solve the common wedding-seating problem where you have a set number of tables, people you want to sit next to each other, and people that you want to sit at different tables. It’s fun.