I have had a hard time learning logic programming thus far, and my request for outside resources on this site was met with some opprobrium, so perhaps this question better addresses both my needs and the requirements of this community:

Is there a step-by-step approach to writing a problem in Prolog or related logic languages? For example, I initially found recursive functions difficult to create myself, though I could more or less understand those that I read, until the I learned the following approach (presented roughly and for example purposes only!):

  1. Describe the base case, i.e. the smallest form of the problem.
  2. Figure out how to combine the results of recursive cases, i.e. add numbers, cons elements, etc. Seeing that there were a few common patterns here helped immensely!
  3. Figure out how to break the results of a larger recursive case up, i.e. cdr down list, subtract, etc. Again, seeing the limited number of common patters was key!

So, a clear description of a related process for tackling a logic problem might be very useful.

  • 1
    Recursive solutions are THE bread and butter of logic programming. What other things do you want to know that would help? (Please do not take this as a rebuke. I used to teach logic programing to freshmen, and I'd love to share tips and strategies with you, but I can't think of any typical problem that doesn't boil down to your steps 1--3.) – Kilian Foth Aug 2 '12 at 15:13
  • @KilianFoth As the ignorant person I am, would you mind posting an answer of why you think this is so? I would have thought if was <em>the</em> bread and butter of logic. – ahodder Aug 2 '12 at 16:17
  • certainly, the recursive solution must be the heart of the game, @KilianFoth. But I ask, clearly, because that alone is not getting me over the hump, since, I can write recursive functions quite handily, but can't write a logic program yet... I imagine the issue is that I understand the evaluation model of functions, but lack one that works in Prolog. My sense is that in prolog, the issue is describing the problem, rather than how to solve it. – Ben Aug 3 '12 at 13:47

Hmmm, let's see. The most fundamental elements of programming languages are state, control flow, and computation. Logic programming subsumes much of this in a single very powerful operation: unification.

Instead of state (global variables) that is changed via assignments, is emphasizes local, single-assignment variables that receive values through unification with other structures. Control flow is expressed through keywords like if or while; but Prolog only has a general unification rule operator (:-) that defines when to attempt unification, and of what. Instead of loops with while, you typically use predicates calling themselves; this gives similar results as loops, and with some care is just as efficient (although more confusing to many learners). Even the most basic control flow - sequencing of operations - is technically not a sequencing construct, but a logical AND operator (,) which just happens to guarantee left-to-right evaluation. Finally, computation is also usually performed by unification rather than by operators, e.g. for list operations or destructuring binds. Even arithmetic can be done through unification if you use Peano numbers, although this is admittedly cumbersome, and Prolog also has an escape hatch into normal arithmetic evaluation with is (but this breaks referential transparency and goes somewhat against the spirit of the system). Most nontrivial Prolog program use many or all of these elements.

Take the simple 'reverse a list' task: almost all solutions you ever see use unification in place of the "if"s you would use in other languages, destructuring bind to manipulate the lists, recursion to generalize from a one-element list to arbitrary lists, and , to sequence the recursive step and the combination step. In the final analysis, they still use the fundamentals of computing such as "IF" or "A, THEN B", but they are all expressed in the medium of terms combined via unification, given arbitrary power through recursion. It is in fact surprisingly difficult to find an instructive predicate that doesn't use recursion in some way. If you have an example of a problem that you can't see how to solve at all, by all means please post it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.