Question about 10

[Mousaka]

Hi, I'm a prolog beginner and got some question about day 10b. How was your thinking when coming up with this? And what makes this qualify for using tabling? (I know almost nothing about tabling but read that it's another search strategy instead of depth first) https://github.com/aarroyoc/advent-of-code-2020/blob/main/day10/day10.pl#L36-L47

Is it arbitrary that it branches out in 3 subsolutions or is there some smart thing behind that idea?

Thanks for sharing and I hope you don't mind me asking.

[triska]

A key attraction of tabling is that it memoizes logical consequences that have already been computed. This can be used to dramatically speed up computation time without changing the code at all, if the predicate refers to many results that can be automatically reused.

Tabling is also called SLG resolution, it is one of the variants of resolution that we can use to derive logical consequences of our programs. With pure code, we can use the available knowledge in any way we want to derive new consequences, and for example the order in which we consider the clauses will not affect the correctness of computed results. There are variants of tabling that can be implemented particularly efficiently if we know that desirable logical properties such as monotonicity are preserved.

In general, the more we keep to the pure monotonic core of Prolog, the more flexibility and opportunities for automatic optimizations we obtain. In this particular example, the generality of the predicate can be significantly increased, using for example zcompare/3 or if_/3 to distinguish the cases, and this allows us to apply different search strategies to reason about the code and to compute logical consequences. Impure predicates like !/0 severely restrict this generality in that they limit the valid usage modes and also the applicable search strategies we can employ to derive the intended logical consequences of the program.

[Mousaka]

Thanks for clarifying! I see how that could speed things up.

Monotonicity and things like using if_/3 is something I have struggled with a bit but I am somewhat striving for. Been watching some the "Power of Prolog"-videos on that topic and find them very interesting. Are you the one making them @triska? If that is the case, thank you :). With that said it is for me still not that easy to know whether my code is in a pure monotonic state or not but I'm hoping to get better at that.

[aarroyoc]

This puzzle is very easy to solve, but not so easy to understand why (at least on my mind). The thing is that at every transformer in a solution, you can arrive to it from three different transformers (N-1, N-2, and N-3). That's why we check the three previous transformers solutions and we sum them. That means we are combining all the solutions that get to N-3, all the solutions that get to N-2, all the solutions that get to N-1, and we sum them as all the solutions that go through that transformer. It is very important to remember that we do not want to know which solutions are, just how many of them exist. Of course, the base case is 1, just one solution, and 0 if the transformer doesn't exist at all (you can't get any solution on a nonexisting transformer). In an extremely simple network of transformers like this:

We can apply the recursion and see why the number of solutions is 3, because there's one solution going through 2, one solution going through 3, and one solution going through 4, which are the transformers that can be connected to 5 (according to puzzle rules).

Why tabling? Well, the search strategy for this problem is not so important, as both will finish, however this recursion will call the same predicates a lot of time so it's better to store the results in what is called memoization and that's why I used it. You can remove the :- table line and you'll see how much more it takes to give an answer just because it just keeps calculating the same values.

I hope I've solved your question now :)

[Mousaka]

@triska Regarding the "pure monotonic core of Prolog": I was just reading about Datalog

Unlike in Prolog, statements of a Datalog program can be stated in any order. Furthermore, Datalog queries on finite sets are guaranteed to terminate, so Datalog does not have Prolog's cut operator. This makes Datalog a fully declarative language.

That sounds very good - a language that forces me to write good code. But I see it has some restrictions in comparison to Prolog, is that why many still use Prolog?

[triska]

Syntactically, Datalog is essentially the functor-free subset of pure Prolog. Semantically, Datalog and Prolog differ only in that they use different default execution strategies to evaluate programs. However, we can evaluate Datalog programs, and therefore also Prolog programs, in several different ways, and there are execution strategies for Prolog that retain the completeness and termination properties we expect from Datalog.

So, with modern Prolog systems, you can easily run Datalog programs too, possibly with some adjustments if they use negation. Prolog is often preferable over Datalog because Prolog is a full-fledged programming languages, even if you restrict yourself to its pure monotonic subset. For example, in Scryer Prolog, you can use library(tabling) to enable SLG-resolution, a variant of resolution that gives you the nice properties of Datalog.

I have seen people fiercely arguing for Datalog, and rejecting that a Prolog system can achieve the same results. Most of them were implementors of Datalog systems and likely had little knowledge of what modern Prolog systems can do. It is a common misunderstanding that Prolog's default execution strategy is its only execution strategy. The more you keep to the pure subset of Prolog, the more flexible you are regarding your choice of execution strategies. This is a major motivation for keeping as much as possible pure, so that we obtain correct results no matter in which order we consider the clauses and goals.