# Thinking In Prolog - for procedural programmers **URL:** \ **Category:** Help!\ **Created:** [July 15, 2019, 12:27pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954 "2019-07-15T12:27:11Z")\ **Posts on this page:** 19\ **Page:** 1
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [July 15, 2019, 12:27pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/1 "2019-07-15T12:27:11Z")
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. ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [July 15, 2019, 12:59pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/2 "2019-07-15T12:59:11Z")
> [@prodog](#): > > Learn to stop worrying and love **findall()**. You could generalize that more and say Learn to stop worrying and love **[aggregation](https://www.swi-prolog.org/pldoc/man?section=aggregate)** ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 15, 2019, 1:25pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/3 "2019-07-15T13:25:10Z")
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. ---
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [July 15, 2019, 1:30pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/4 "2019-07-15T13:30:26Z")
> [@jan](#): > > The aggregation predicates causes the data to be **copied** 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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 15, 2019, 1:42pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/5 "2019-07-15T13:42:53Z")
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. ---
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [July 15, 2019, 2:00pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/6 "2019-07-15T14:00:43Z")
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. ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [July 15, 2019, 2:26pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/7 "2019-07-15T14:26:20Z")
> [@prodog](#): > > I continually wonder why there isn’t something like this in some version of Prolog: 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](https://en.wikipedia.org/wiki/CAR_and_CDR), are in the same boat. See: [append/2](https://www.swi-prolog.org/pldoc/man?predicate=append/2) ```prolog ?- 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. ```prolog ?- 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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 15, 2019, 3:15pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/8 "2019-07-15T15:15:04Z")
> [@EricGT](#): > > Any programming language using immutable list and the concept of head and tail, e.g [CAR and CDR](https://en.wikipedia.org/wiki/CAR_and_CDR), are in the same boat. 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. ```prolog :- 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). ``` ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [July 15, 2019, 9:57pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/10 "2019-07-15T21:57:56Z")
5 posts were split to a new topic: [How would you parallelize between(1,20,N), prime(N)?](https://swi-prolog.discourse.group/t/how-would-you-parallelize-between-1-20-n-prime-n/957) ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 16, 2019, 7:48pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/11 "2019-07-16T19:48:22Z")
> [@jan](#): > > use aggregation (including findall/3) 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=[])`. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 16, 2019, 8:15pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/12 "2019-07-16T20:15:43Z")
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](https://www.swi-prolog.org/pldoc/doc_for?object=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 ☹ So, not for this topic 🙂 ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 16, 2019, 8:55pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/13 "2019-07-16T20:55:53Z")
Like so many things in ComputerScience, it’s tempting to skip the nuances until the nuances cause trouble. For example, nesting `findall`s can be an unhappy experience (as opposed to nesting `setof`s). 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. ---
**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\ **Post date:** [July 16, 2019, 11:47pm UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/14 "2019-07-16T23:47:23Z")
> [@peter.ludemann](#): > > For example, nesting `findall` s can be an unhappy experience (as opposed to nesting `setof` s). From a combinatorial explosion perspective, or due to program crashes? If the latter, can you give an example you experienced? ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 17, 2019, 12:35am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/15 "2019-07-17T00:35:20Z")
Here’s an example from _The Craft of Prolog_ for converting a predicate of node pairs into an adjacency list: ```prolog bagof(T1-T2s, bagof(T2, edge_pair(T1, T2), T2s), AdjancyGraph). ``` If you replace the `bagof`s 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: ```prolog 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). ``` ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 17, 2019, 7:11am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/17 "2019-07-17T07:11:15Z")
> [@peter.ludemann](#): > > ```prolog > bagof(T1-T2s, > bagof(T2, edge_pair(T1, T2), T2s), > AdjancyGraph). > > ``` Sure. Just, not that many people will understand what is going on here ☹ We can also write ```prolog 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. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 17, 2019, 7:38am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/18 "2019-07-17T07:38:58Z")
> [@jan](#): > > findall(T1-T2s, group\_by([T1], T1-T2, edge\_pair(T1,T2), T2s), AdjancyGraph) I think you mean: ```prolog findall(T1-T2s, group_by([T1], T2, edge_pair(T1,T2), T2s), AdjancyGraph). ``` which is essentially the same as ```prolog 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`. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 17, 2019, 8:05am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/19 "2019-07-17T08:05:01Z")
> [@peter.ludemann](#): > > I think you mean Yes. Thanks! > [@peter.ludemann](#): > > because it explicitly marks the grouping variable 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. > [@peter.ludemann](#): > > still necessary to realize that `group_by` backtracks through all values of `T1` 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. ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [July 21, 2019, 4:27am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/20 "2019-07-21T04:27:49Z")
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](https://www.metalevel.at/prolog) Dan ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [July 21, 2019, 5:01am UTC](https://swi-prolog.discourse.group/t/thinking-in-prolog-for-procedural-programmers/954/21 "2019-07-21T05:01:01Z")
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?