I absolutely love programming in Prolog. I've never needed to write anything large in it at all (which is where most prolog interpreters fail), but when it comes together so beautifully at the end, its quite amazing.
I thoroughly recommend "The Art of Prolog" which is an engaging and fun read.
In non-declarative languages like Java, you have to build up the different pieces of computations, while you keep maintaining a mental picture of how the various pieces fit together.
In Prolog, you declare the entities and the relationships/constraints between them, and the system will build the solution for you through inference.
David Nolen has done some awesome work writing the core.logic[1] library, which makes those Prolog gooodies accessible to Clojure programmers.