Thinking In Prolog - for procedural programmers

Help!
1

I just finished a recent war with Prolog. As a veteran procedural programmer of many years I wanted to put down my thoughts while they are still fresh and by fresh I mean I just got my code working minutes ago.

If you are having a war with Prolog it is usually because you are still trying to write your code using procedural logic. Rather than hit you with the canon “think declaratively” and run away as you will find many articles and books on the Web do, I’ll say “think in Prolog’s execution model” and explain what that means. “Think declaratively” has always been a problem for me for two reasons:

  • The answers to the question “What does that really mean?” that I have read have always been unsatisfying to me. In other words, I could never use those answers to change my programming habits
  • That assertion completely ignores Prolog’s execution model where the order of clauses is critically important

So what do I mean by saying “Think in Prolog’s execution model”?

Rather than express my opinion, a dubious exercise considering my troublesome path with Prolog and the fact that I am certainly not an expert Prolog programmer, I will simply recount the symptoms that manifested during my recent war with Prolog and how I solved the problems with my code that created those symptoms. Note, the problems I had with Prolog were all my fault and were all due to my incorrect thinking that stemmed from my long history of procedural programming.

SYMPTOMS OF PROCEDURAL POISONING IN PROLOG

  • You are in a war with Prolog to begin with
  • You are trying to do too much in one clause, especially if you find yourself using the disjunction operator (";") to create multiple code paths in the same predicate clause
  • You are trying to accumulate solutions for the same goal in too many directions (i.e. – breadth and depth at the same time, etc.)

That last one deserves further expansion because that should have been a warning sign to me that I was coding my logic in a procedural manner and thereby causing myself many hours of pain.

I was trying to accumulate solutions as I iterated a list an elements, one element at a time while using recursion. At the same time I (i.e. – in the same predicate clause) I was also accumulating them by descending down a tree of nodes to also pick up solutions via recursive descent of a node tree. Worse, some of the control path logic was handled by a disjunction in a bloated predicate that was doing way too much. In the middle of this procedural disaster I found myself fighting conflicting unification problems with difference lists and wishing I had chose a different way to earn a living than programming.

I ended up giving up late last night, frustrated and having failed. When I woke in the morning the answer on how to code the logic in harmony with Prolog’s amazing execution model came to me effortlessly. Apparently during sleep I finally decided to stop trying to code the logic my way and do it the Prolog way

THINKING IN HARMONY WITH PROLOG’S POWERFUL EXECUTION MODEL

The main “enlightenment” I had was to stop thinking of my current objective as the accumulation of solutions and to understand that I was actually creating a generator. As soon as I did this I could start shaping my current objective in harmony with Prolog’s execution model. This simple reframing of the problem radically simplified the problem I was trying to solve.

Instead of suffering the burden of trying to build a list of solutions in a painfully complex set of ways all at the same time, I just had to figure out how to create (i.e - "generate) one solution at a time and let findall do the rest of the work. That allowed me to immediately unravel the spaghetti logic that existed in one bloated clause into multiple clauses that were much simpler, with the side benefit of the code being much easier to read and understand now.

This led me to some useful principles in breaking the hold of procedural thinking when refactoring a failed complex logic attempt:

  • Turn over as much of the task to Prolog’s backtracking and recursion model. This is very hard for procedural programmers, at least like myself, because we want micro-control over every step in the control flow.

  • Keep simplifying your code in an iterative manner into smaller pieces of logic. The most common tools here are: recursive descent, backtracking, more clauses for a complex predicate, and more predicates too.

  • Learn to stop worrying and love findall(). Turn your logic into a generator wherever possible and let findall() do all the busy work. If you are iterating a list argument “horizontally” just to get at each element, that frequently indicates you should be using findall() and a generator instead.

SYMPTOMS OF A SUCCESSFUL REFACTORING FROM PROCEDURAL TO PROLOG

  • You are shocked at how much of your old code you are deleting and how little code it takes to express the same logic with one notable difference. Now your code works beautifully
  • You feel your thoughts changing from “Why the hell doesn’t this code work the way I want it to?” to “How do I restructure my thoughts and code to the way Prolog works?”
  • You learn to trust Prolog and let it do all the work. You also find Prolog beautiful.

CONCLUSION

I’ve said this in other places and many times. Prolog is very hard for most veteran procedural programmers to adapt to but it is worth the effort many, many times over. The breathtaking experience you have when you finally succeed is unique and indescribable. I hope this helps some of my fellow veteran procedural programmers out there.

6 Likes
2

You could generalize that more and say

Learn to stop worrying and love aggregation

2 Likes
3

Yes, one simple and productive way to use Prolog is to define simple logical statements that generate or filter solutions and then use aggregation (including findall/3) to get the result you want.

There are some buts though, notably if you use this to transform Prolog terms (including lists) as opposed to extracting data from the Prolog database.

  • When (for example) converting a list using findall with some generator, any element for which the conversion fails is simply ignored. This causes you to easily miss omissions in your definitions.
  • The aggregation predicates causes the data to be copied. That can be slow (although that is not a very common problem), but it also looses bindings between variables. That is notably a problem as you start working with constraints.

So, yes, generate+filter+aggregate is nice. But, there are other areas that are worthwhile. Notably the high order list predicates (maplist, foldl, etc.) and constraints can solve many (search) problems elegantly.

3 Likes
4

So does findall do a copy of each solution to the aggregating term? I was hoping it just attaches it to the end of the aggregating term (list) without copying, akin to the matter a difference list tacks on new elements to the end without doing any copying.

5

It must. It doesn’t need to do such if it could prove that the term is not being created or further instantiated during the execution of the findall/3 goal. This is rather expensive to figure out though and I’m not aware of any Prolog system that does this.

3 Likes
6

Someday I’d like to read a treatise on why there is not equivalent operator for Prolog lists to append an element at the end of a list like you can using the pipe operator “|” to place an element at the front of a list. I know you can use difference lists but they do require more thinking than not. I continually wonder why there isn’t something like this in some version of Prolog:

?- L = [ a | [b, c] ? x ].
L = [ a,b,c,x]
?-

Note, I used “?” character here as a mythical “Tail Element” operator.

7

This is not a topic specific to Prolog. Any programming language using immutable list and the concept of head and tail, e.g CAR and CDR, are in the same boat.

See: append/2

?- append([[a,b,c],[d]],X).
X = [a, b, c, d].

Without going into the details if you rememeber that list are immutable in Prolog, and the difference between adding to the head and adding to the tail, it makes sense.

?- time(X=[a|[b,c]]).
% 2 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = [a, b, c].

?- time(append([[a,b],[c]],X)).
% 12 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = [a, b, c].

Notice that adding the head is a lot cheaper in terms of number of inferences than adding to the tail.

3 Likes
8

Yes. Only, Prolog has the notion of partial terms that lead to difference lists that allow you to add terms to the end at constant cost. If you want to use that you typically use DCGs or one of its extensions. You can of course also define an abstract data type for difference lists. You may get something like below. Not tested. I don’t think I ever felt the need for it. DCGs are simply more convenient.

:- op(700, xfx, \).

el_dl(E, [E|T]\T).
dl_append(L1\T1, T1\T2, L1\T2).

dl_member(E, L\DT) :-
    L = [H|T],
    dl_member_(T, E, H, DT).

dl_member_(T, _, _, DT) :-
    T == DT,
    !,
    fail.
dl_member(_, E, E, _).
dl_member([H|T], _, E, DT) :-
    dl_member(T, H, E, DT).
3 Likes
10

5 posts were split to a new topic: How would you parallelize between(1,20,N), prime(N)?

11

Better to use bagof/3 or setof/3. As Lee Naish and Richard O’Keefe have pointed out, findall is unsound if the Template doesn’t capture all the free variables in the Goal.

bagof and setof allow you to mark variables as existentially qualified (although you might want to define an auxiliary predicate for clarity), and also allow backtracking over the other free variables. The downside of using bagof and setof is that if you want “no solutions” to result in [], you need to wrap it: (bagof(X, pred(X), Results) -> true ; Results=[]).

1 Like
12

I know bagof/3 and setof/3 make more sense from a logical perspective. Unfortunately only few users understand these predicates. In many cases intended existential quantification is omitted and what is actually intended is findall/3. In the solution_sequences library I have tried to remedy this issue to some extend by introducing a more familiar notion of group by. See group_by/4. This basically inverts the notion of the existential variables, i.e., variables are existential unless specified otherwise. Paulo’s library(yall) can be used to achieve a similar effect in a comfortable way.

It is seen as an advantage that bagof/3 and setof/3 preserve variables, but one should be aware that this comes at a rather high price. Data is still copied, but enough of the environment is copied along with the data to unify the variables in the copy with the original values.

Bagof/3 and setof/3 are beautiful constructs, but unfortunately require mastering Prolog at level 2.0 :frowning: So, not for this topic :slight_smile:

2 Likes
13

Like so many things in ComputerScience, it’s tempting to skip the nuances until the nuances cause trouble.
For example, nesting findalls can be an unhappy experience (as opposed to nesting setofs).

I’ve never observed the “high price” of bagof/setof being a problem, but no doubt there are situations where it could become an issue.

14

From a combinatorial explosion perspective, or due to program crashes? If the latter, can you give an example you experienced?

15

Here’s an example from The Craft of Prolog for converting a predicate of node pairs into an adjacency list:

    bagof(T1-T2s,
          bagof(T2, edge_pair(T1, T2), T2s),
          AdjancyGraph).

If you replace the bagofs with findall, this won’t work.

Minor note 1: the book uses setof rather than bagof; I think that this is only needed if there are duplicate facts in edge_pair/2.

Minor note 2: the book claims that this suffices for creating an adjacency graph for library(ugraph) top_sort/2 (topological sort). However, it seems that top_sort/2 requires more entries:

edge_pair(a,b).
edge_pair(a,c).
edge_pair(b,c).
edge_pair(b,d).

no_succ(T) :-
    edge_pair(_, T),
    \+ edge_pair(T, _).


adj(TaskGraph) :-
    bagof(T1-T2s,
          bagof(T2, edge_pair(T1, T2), T2s),
          TaskGraph1),
    setof(T-[], no_succ(T), TaskGraph2),
    append(TaskGraph1, TaskGraph2, TaskGraph).

tasks(TaskList) :-
    adj(TaskGraph),
    top_sort(TaskGraph, TaskList).
1 Like
17

Sure. Just, not that many people will understand what is going on here :frowning: We can also write

findall(T1-T2s,
        group_by([T1], T1-T2, edge_pair(T1,T2), T2s),
        AdjancyGraph)

I’m not saying this is better. In fact, there are logical purity reasons to consider this worse. I think I would be willing to defend that this is easier for many Prolog programmers. Even seasoned Prolog programmers can be surprised by the effect of sharing compound terms with a goal such as bagof(T2, edge_pair(T1, T2), T2s) though.

18

I think you mean:

findall(T1-T2s,
        group_by([T1], T2, edge_pair(T1,T2), T2s),
        AdjancyGraph).

which is essentially the same as

findall(T1-T2s, 
        bagof(T2, edge_pair(T1,T2), T2s),
        AdjancyGraph).

I suppose group_by version is marginally easier to understand because it explicitly marks the grouping variable, but to understand the code it’s still necessary to realize that group_by backtracks through all values of T1.

19

Yes. Thanks!

Yes. And the name is more familiar. bagof/3 seems to hint at creating a single bag. Note that explicitly marking the variable to group by has the advantage that you get no unforeseen grouping on variables that are not directly visible in the goal but come from outside through the arguments. Even I am sometimes still surprised by this.

Yes. Prolog predicates producing multiple results on backtracking isn’t really anything novel except for the real beginner.

In my contacts with not-so-experienced Prolog programmers that use Prolog for data refactoring, the primitives provided by library(solution_sequences) are highly appreciated. I think that is in part due to the familiar naming. Another reason is that they allow you to stay in the same paradigm, producing answers on backtracking. Notably distinct/1,2 is popular.

20

To add my 2 cents.

I found Markus (online) book, and discussions with Markus on relational programming enlightening.

To think relationally during program solving – to define predicates that indicate what relations hold.

I think this is a paradigm shift from functional (and procedural) thinking – which is (essentially) input-output oriented.

https://www.metalevel.at/prolog

Dan

21

One way i am thinking about optimizing is to creating an adjacency graph incrementially, say, held within an assoc, instead of asserting the edge pair.

Do you think this could make a significant different over searching for adjacencies, based on asserted edges?