It's been a while since I've studied Prolog, but it's good to see it getting some press. I learned Prolog before ever dabbling in Scheme or ML, and it was just as much of a paradigm shift from imperative style. It's kind of like FP-style pattern matching, but taken to a whole new level, such that the pattern matching itself is pretty much the entire computational engine.

Rather than using functions, which take a number of arguments and return a result, you use predicates on a number arguments. You build your program out of clauses, which are conjunctions of predicates. A process called unification [1] finds the argument values (if any) that satisfy an entire clause. By sharing constants and variables between predicates, the valid results that unification can produce are restricted to what the logic of your program allows.

So your algorithms end up being, in many ways, description of what a valid results look like, and the Prolog engine goes out and finds them. This paradigm clearly maps nicely to domains with lots of rules, like decision engines, parsers, and such. Sounds awesome, right? One caveat is that, in practice, you as a programmer have to have a pretty good understanding of how unification works in order to write performant algorithms.

This is all from several years-old recollections and a little bit of Wikipedia to refresh my memory, so someone please chime in if I'm incorrect someplace or leaving out key concepts.

[1] http://en.wikipedia.org/wiki/Unification_%28computer_science...