Choice Point Sequencing and Control Patterns -- list ordering, interpreting, resolving -- and the quest for A*.

[jjtolton]

As these things tend to do, researching the article for I/O and side-effect handling best practices in Prolog has sent me down a bit of a rabbit hole.

It is clear that side-effects should be partitioned, where possible, to the start and end of the program -- this is true for most languages, anyway, but is particularly true for Prolog. But specifically how to do that is not always evident.

Motivating example:

Let's look at this incredibly boring but extremely common resource request pattern:

The $${\color{red}RED}$$ boxes indicate extra-logical, side-effecting interactions with external systems. The $${\color{blue}BLUE}$$ boxes indicate things that are either logical or I/O that happens at the beginning or end of program. In this case, there really is no way to avoid interleaving side-effects with pure-logic -- at least, operationally.

In procedural languages where I feel particularly motivated and somehow have a little extra time, sometimes I will create a Finite State Machine that will transition between states, receiving and emitting signals. It is easy to logically test the FSM, and the integration test of the external systems with the FSM can be a separate concern.

In the real world, the situation becomes trickier when the control flow needs to be multithreaded, asyncronous, or non-blocking (as is often the case with single-threaded GUI applications such as JavaScript web apps), and those typically require synchronization structures. There are a number of ways to handle this, and when I have time I create a thread-safe queue of data or control structures and a stack machine to consume them, creating an "architecture" something like this:

Do I always do this? Hell no. There are plenty of non-functional requirements that are not even addressed by this implementation, but very frequently it just seems to be the case that trying to explain "we can do it this way, it will be better but take longer" vs "sure, we can interleave I/O and it will be quicker at first but harder to maintain and test, and harder to reason about in the event we need to make changes down the road"... well I can tell you 100% of the time, option 2 is chosen.

Even in situations where you do get to implement a nice architecture like this, sometimes I choose not to, because very often you end up writing code that is not idiomatic to the language you are working in. Writing declarative, logical code with a DSL and custom architecture in Python is often very frustrating to Python users when interleaving I/O in a 10 page long function is "easier" to read. Even in Clojure and other lisps, you can find yourself be very unpopular if you write some "clever macros" to wrap your opaque machinery. In JavaScript, "why aren't you just using X or Y frameworks?". Increasingly, "can't you just have ChatGPT to do that?" (whatever that means).

The beautiful thing about Prolog is that writing up such a declarative pattern can be incredibly concise, and finding a way to do something declaratively is often easier than trying to find a way to do something by interleaving side-effects.

Problems with DFS in large state spaces

However, we can imagine much larger FSMs than the one pictured above...

...and more complex control structures where hand-written state transitions become impractical, impossible, or innumerable, such as behavior trees, goal oriented action planning, or more concretely the [water filling problem](https://en.wikipedia.org/wiki/Water_pouring_puzzle) [discussed by](https://www.youtube.com/watch?v=vdabv9EkYrY) @triska [and by](https://www.youtube.com/watch?v=q6M_pco_5Vo&t=2s) Peter Norvig.

These could potentially result in very large state spaces where iterative deepening could take prohibitively long, such as in shortest path algorithms, when known greedy algorithms such as A* exist to make these types of problems tractable.

To achieve A*, it seems like we would need fine-grained control over backtracking strategy.

Control Strategies

When it comes to doing this sort of work in Prolog, I have seen so far four approaches to control that seem to essentially amount to converting Prolog's DFS backtracking to another type of control sequence such as iterative DFS (i.e., ?- length(Sequence, _), phrase(algorithm(InitialState), Sequence)).

-1. 🚫 ⛔ 🙅 (I'm labeling this -1 because from everything I've read it should probably be considered a non-approach) is manually mixing logic and control together. Yes, we still have to do this to some extent to ensure in certain situations that variables are instantiated -- something experienced Prolog developers do naturally without even thinking about it -- but I'm talking about interleaving side-effects and using one of the various rainbow colored (blue, green, red, yellow, purple) cut ! operators. Everything I've read so far about this control strategy is that it is "sometimes necessary, best avoided".

0. List ordering. @triska effectively demonstrated exceptional speedups on complicated constraint problems using effective list ordering techniques in his Faster labeling for N-queens video.

1. Interpreting. Prolog has been shown to be a great language for crafting interpreters where you can have more control over the resolution strategies [1], [2].

2. Different resolution strategies. This is the one I know the least about, but I understand that SLG resolution and the tabling library provide alternative methods to DFS.

---

Edit: thanks @aarroyoc for pointing out the magical labeling/2 as a possible option #3.

---

Takeaways and Questions

I have listed these in the order in which I believe they are most often used. Aside from mixing logic and control, which I see frequently (ab)used but am often told is 🚫 ⛔ 🙅, these are also listed in the order in which I assume is the most practical approach to control.

Are these observations correct? Does anyone know of any other strategies I haven't listed here? Does anyone have any "go to" favorites? Does anyone have any resources on implementing different resolution strategies, such as SLG? Does anyone disagree with any of these?

Most importantly, which strategy, listed or unlisted, would be most suitable for implementing the A* algorithm over large state spaces with Scryer?

[jjtolton]

OK, so my first observation is that the tabling module is pretty amazing. I was really surprised to find out that they have trie data structures as well as doubly linked lists. I wasn't even sure these were possible in Prolog. Beyond that, it was really impressive to discover that the assoc module has a ready made AVL tree data structure! WOW!

There is a LOT to unpack here. The combination of built in backtracking with just these powerful persistent data structures could be the subject of many years of joyful study.

I have to say that this was enough to make me already change and even reverse my stance on preferred control sequencing methods. Even on something like a "shortest path" graph algorithm, it would be so much more enjoyable to program it descriptively and not worry at all about the control sequencing at all. It would be far preferable to simply switch out the resolution strategies without having to change the logic.

Until I saw these modules, I wasn't sure how practical writing your own resolution strategy might be, because it seems like you would need things like associative data structures, queues, and other things in order to potentially build your own index or manage other bookkeeping data while implementing a resolution strategy.

But now I'm convinced this the best way to do it, so you can reuse the resolution mechanism while keeping your logic unaware of the control strategy.

[aarroyoc]

Yes, that should be ideal. Describe your problem in a generic way, and in other part of the program, have a solver. This is also how clpz is supposed to work. You define your constraints, the constraints get attached to the variables, but how the search space is explored is defined by the strategy in labeling/2 options, and there are multiple ones predefined.

[jjtolton]

That's a great point, I forgot about labeling/2. I think labeling/2 is actually a strategy that I have not yet mentioned, because unless I am mistaken it is neither an interpreter nor is it a directive like table/2. And in the N-queens video, @triska did list ordering before labeling. CLPZ has many secrets to explore!

This is me looking at all things I wish I knew 🤣

I have a feeling all the strategies I just mentioned are, at best, intermediate Prolog topics -- but where does one go to learn such things?? Information on them seems to be quite scarce. Source code still seems to be the best learning resource!

[jjtolton]

Alright so quick update.

First of all, it turns out that I was setting my sights too low, A* is just the beginning! Partial order planning, GRAPHPLAN, and Simulation and Control with CLP are exciting search applications with Prolog I've only recently learned about!

I'm currently working my way through the relevant chapters in Prolog Programming for Artificial Intelligence. This is not a book review, but I will say that while the ideas are very good, the code does not seem to be available online AND the example code does not conform to best practices (very procedural, heavy use of the cut operator, etc). Through various discussions I am slowly attempting to rewrite the code as closely as I can to high quality Prolog code.

The techniques focus heavily on generating a sequence of actions, such as in Zurg and the jug pouring problem, which @triska has demonstrated that DCGs seem to be really ideal for this sort of work.

I've noticed that with DCGs, the inputs could even be sorted according to priority before being passed to the next DCG rule, which should be enough to accomplish most if not all of the tasks related to searching.

[ocharles]

Please do keep sharing your findings! Interestingly, I find myself at a very similar point with learning Prolog - wanting to use it but not yet knowledgeable enough, striving to stay in the pure monotonic fragment, etc. Also I'm very interested in AI search too! At work we do all sorts of planning. We've done A*, landmark search, and SMT solving (to name but a few techniques). We also have allocation/scheduling/optimisation problems, all of which I think Prolog might be able to solve. This is a bit rambley but I just wanted to share a bit of support for your learning, and express thanks for sharing it all so publicly. If you ever want to collaborate on anything in particular, drop me a message - maybe we can find some time to learn together!

[jjtolton]

This is a bit rambley

We can't start being judgemental about being rambley or I'd never be able to post anything again 🤣

maybe we can find some time to learn together!

I'd LOVE that! I'll send you an email, and I'll also be at the Scryer meetup in Vienna, if you can make it! Search and planning have to be the most magical parts of coding for me. I too have a feeling that Prolog will be explosively useful for this sort of work once a few of the versatile techniques are well understood. In particular, the fact that constraint propagation is a first class concern (and something you get almost for "free" thanks to clp(z) and clp(b)) dramatically increases the ratio of power to expressiveness you can get.

For instance I have been studying Peter Norvig's Sudoku Solver for a long time, and I've never really been able to "generalize" the principles -- he uses unorthdox data structures and some really tricky but fascinating mutual recursion, along with backtracking search over mutable data that make it hard for me to hold all the principles in my head at once (but hey, that's why he's Peter Norvig!). It's perhaps not a "fair" comparison, but compare that to @triska's sudoku solver:

sudoku(Rows) :-
        length(Rows, 9),
        maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs),
        blocks(Ds, Es, Fs),
        blocks(Gs, Hs, Is).

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

WOW!

I think one of the major differences is that in Python (or Clojure, or ...), for instance, you need to either use a framework or write a bespoke/custom constraint propagation and search algorithm for every new problem.

Being able to focus on just the relationships really unlocks a lot of mental capacity to focus on even bigger problems.

From my industry experience I can say for certain that the performance would scale very effectively to most web development tasks, I will be interested to see where scaling limits are hit, if any!

[jjtolton]

Ok, first serious effort towards search algorithm best practices in a good discussion over here.

Rewrote some code from a book, then reimplemented it with DCG notation. Lots of good distilled information if you are trying to get started with search in Scryer based on applying the work and theory from some prominent community members.

[jjtolton]

I wrote up an example of a very simple monotonic scheduler that works in Scryer. @UWN helped me figure out how to find a lower bound on it! I also was reminded of an important lesson that constraint propagation, search, and optimization are not necessarily the same thing.

[jjtolton]

Full circle, finally managed to cludge together a working A* demonstration.