What are the design heuristics one has to master to write good Prolog? I've heard it takes an experienced programmer about two years to become proficient in Prolog. Using recursion effectively is part of it, but that seems to be a relatively minor hurdle. What exactly is it that gives programmers so much trouble? What should I be looking for in sample code to judge its quality?
The major difficulty in writing good Prolog code lies in not only understanding but also adequately transmitting the intention or purpose of a program. In contrast to other programming languages there are several quite different kinds of Prolog code often within the same program. By confusing such levels bugs and problems ensue:
Pure, monotonic code.
This code lies at the heart of Prolog. In such code a lot of algebraic properties hold, and the actual problems are described in the pure, ideal manner which Prolog is often advertised with. Yet, even in such parts certain procedural properties may surface, such as non-termination. Take as an example the commutativity of conjunction. In pure, monotonic code, ( A, B ) and ( B, A ) describe the same relation. The only differences may lie in different termination behavior and the sequence how answers appear. Ideally, the names of pure predicates communicate that the predicates are relations. Imperatives are definitely not a good choice here.
Side-effectful code. The other extreme is code that can only be understood by effectively executing it, either by machine or in the mind. There are no simple invariants in the program. But even in such parts, there might still be certain properties observed like steadfastness. Effectively such code is not much different to other programming languages.
Often, the side-effectful part "eats up" the pure side since programmers are used to an imperative, command-oriented do-this do-that thinking. To lean into the other direction, think of which properties you will lose or gain. Think how easy it will be to test your program: The purer a program the easier it is to test without any extra sandbox around. A simple toplevel query is good enough.
Some examples, how the pure side can be expanded at the expense of seemingly necessary side-effects:
Or simply these answers.
Edit: In your comment, you ask for "advice for learning". So here is some:
Stick to writing pure, monotonic code only. You can only judge to choose one or the other side if you know both. I assume you have some previous experience producing side effects in some command-oriented language, but none with pure code. As a consequence this will mean that you will refrain from writing inherently non-monotonic code.
Play with the toplevel. Imagine, the toplevel is the only way to access your programs. How would you formulate a problem such that it fits into this format? The SWI, Scryer and Trealla toplevel have been specifically designed to permit such light-weight interaction.
Use clpfd for arithmetics. Don't use (is)/2, it makes your code much too moded.
Enjoy the algebraic properties of pure, monotonic code. Think of it: You add a goal, no matter where, and still you can predict that this goal will specialize your program (and at best leaves it as is). You can - blindly - remove a goal, and still you know (part of) its effect.
Study the notion of a failure-slice to master non-termination.
Do not use a step-by-step tracer/debugger, as it is offered in many Prologs. It only shows you the precise steps Prolog takes. It does not show you anything directly related to the meaning of the program. It reinforces a step-by-step thinking.
Watch your language. The way how you talk about a program influences the way you think about it. So, if you use a lot of operationalizing language (like: This does this etc), chances are you reinforce the command-oriented view. There is a cleaner way of talking about things, but you need to find it. This is probably the hardest part.