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!):
- Describe the base case, i.e. the smallest form of the problem.
- 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!
- 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.
3
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.