I think of Prolog programs as collections of constraints.

Now, a lot of people, when they hear the term "constraints", think of arithmetic inequalities. And indeed, there are "Constraint Logic Programming" extensions to Prolog that support such constraints. But that's not what I'm referring to. Even in the absence of such extensions, Prolog is a constraint language, but the constraints are structural rather than numerical.

Let's take a simple example, the Prolog code that defines list appending:

  append([], X, X).
  append([X|Y], Z, [X|W]) :- append(Y, Z, W).

This says, first, that 'append' is satisfied if its first argument is empty and the second and third are equal; and secondly, that it's also satisfied if the first and third argument have the same head, and 'append' is satisfied recursively on the tail of the first argument, the second argument, and the tail of the third.

Prolog allows any of those arguments to be inputs, and any to be outputs. The way this works is that variables in structures function as named holes to be filled in. So while you can use 'append' as a function to append two lists, like this:

  ? append([3], [7], X).
  X = [3, 7]

you can also use it as a predicate:

  ? append([3], [7], [4]).
  no

Here "no" means Prolog couldn't find any way to satisfy the constraint. Or, you can use it "backwards":

  ? append(X, [7], [4, 7]).
  X = 4

Prolog doesn't even know what's normally an "input" and what's an "output"; it just searches for a solution to the constraints. It can even construct multiple solutions:

  ? append(X, Y, [4, 7]).
  X = [], Y = [4, 7];
  X = [4], Y = [7];
  X = [4, 7], Y = []

Here's the really powerful part. These solutions are produced one at a time. Some larger goal can be consuming them, such that if it fails, Prolog will try the next one automatically. Thus it's very easy to put together a large, complex constraint and have Prolog search for a solution.

The catch, as others have mentioned, is that it does that using a rather naive depth-first search. Even though, at the lowest level, it tries each alternative very quickly, there can easily be a combinatorial explosion of alternatives. To use the language effectively requires the programmer to learn strategies to avoid these explosions. So while in small examples the language seems very declarative, and indeed a lot of code can be written without too much attention to its procedural behavior, eventually this breaks down and you have to think about it procedurally as well.

This is something that unfortunately doesn't have a straightforward answer. Prolog ended up being very influential, but its very nature meant it was never going to become mainstream.

Prolog was intended to be a way to program using logic. It did this in a way by encoding facts in a manner not dissimilar to a relational database; logical statements about the world that resembled functions using Horn clauses (which you can think of as mathematical functions, but applied to logic); and unification, which is what links all this together. Unification is computation via the idea that you have a set of data, a bunch of logical statements, and you want to find everything in the data that satisfies those logical statement.

If you know SQL, Horn clauses should sound a lot like materialised views.

As to why it never really went mainstream, it's a matter of wrong place, wrong time. It didn't help that the language needed a checkpointing mechanism (referred to as 'cuts', and represented by '!') because the unification mechanism could get confused and do much more work than it needed to, so developers needed to put cuts in place to tell the interpreter where it could avoid backtracking to try more solutions within a Horn clause.

If you want to get a taste for it, maybe give this a try: https://github.com/norswap/prolog-dry

Prolog is one of a small number of languages that people should learn even if they never use it in a practical way.

Here's a 60s attempt:

Prolog was (theoretically) a practical declarative programming language. You describe what you want done, and it "figures out" what to do, as opposed to imperative, where you simply tell the computer each step to do.

That's something of an exaggeration in practice, but yet, there was something to it. A typical program was actually doing depth-first search behind the scenes, so "try this, or else try this, or else try this" algorithms were very easy to express in the language.

As an aid to that, it had unification, which you can think of as pattern matching on steroids. You could write a rule like

something([A, [1, X]]) :- yada(A, X)

which would only match if the argument to 'something' was a list the second element of which was another list that started with 1, and so on. It's far more powerful than this, but it's been many years, and I've forgotten most of it.

As for the cons, implementations of the day were relatively inefficient, although Quintus was fairly good.

The killer problem, in my mind, though is that it didn't really deal well with backtracking through huge data structures. If you were trying to write a bit-blitting algorithm on large arrays, for example, and expecting to backtrack a lot, it just plain wasn't going to work well.

Not sure that helps much. I miss Prolog a lot, but it's hard to see a path forward for it. Even somewhat similar languages like Haskell will probably never get any real traction. Or even Ocaml/F#, which are far more practical.

I suppose the closest we have today are really good Makefiles. Done well, this captures just a bit of Prolog, in a very limited domain.

While turing complete, it is essentially a DSL for doing logical deductions in a system of predicate logic. This makes it quite natural for certain classes of search and constraint satisfaction problems, but less natural for day-to-day procedural programming.

Further more, it is missing many things that you come to expect in a modern programming language - arrays, good numerical performance, etc.

The way it works though allows you to do some things quite beautifully. For example, since every function you right can be run either forwards or backwards (solving for any one unknown amongst the arguments or result), you can often write one single piece of logic for parsing that can just be run in reverse to do serialization (or vice versa).

The main reason, though, that it (or it's progeny like Mercury) is not mainstream is really the same as the reason that Haskell and its derivatives are not. It's just too different from the more widely known algol/simula langages, and the library ecosystem is comparatively poor.

Say you want to calculate the area of a triangle, in a Python-style language you would write:

    def area(base, height):
        return (base * height) / 2

This is a function which takes the base and height as inputs, and returns the area as an output, and that is all it can do. You'd never think that's "all" because what else would you expect it to do, but what you wrote down in code? In Prolog, instead you can write this:

    :-use_module(library(clpfd)).

    triangle_area_sides(Area, Base, Height) :-
        Area #= (Base * Height)//2.

This is not a function, it doesn't take any parameters or return anything. It's a rule which says how the Area, Base and Height values are related, and an import for a module which handles numeric calculations. Now you can ask the Prolog rules engine to solve for any missing value(s):

- Given a base and a height, what is the missing Area value? (Same as the Python version)

- Given an Area and a Base, what is the missing Height?

- Given an Area and a Height, what is the missing Base length?

- Given an area, a base and a height, is that a valid triangle?

- Given an Area, generate some / many Base and Height combinations which make a triangle of that area.

- Given a Base, generate some / many Area and Height combinations which make a triangle of that base length.

- Given a Height, generate some / many Area and Base combinations which make a triangle of that height.

- Given nothing, generate some valid triangle sizes.

- Given some values but not others, can it be solved at all (true/false)?

Pros: that's much more capable than the Python function of roughly the same code length. Multiple logic statements like this can make a lot happen in a little code.

Cons: it's very different from imperative programming, it makes IO and state interactions a bit more difficult, it's easy to get the Prolog engine stuck generating infinite combinations or searching enormous search spaces and never finishing, debugging what it's actually doing and what is going wrong is a very different skill from imperative languages.

And years of college courses using Prolog as a "force them to deal with recursion", leaving people with the impression that Prolog is incapable of anything good, and what it can do is slow and needlessly difficult.