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 i

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.