Video: Describing Domino Tilings with Prolog

[triska]

Dear all,

today I uploaded a short video about describing domino tilings of a chessboard with Prolog:

https://www.metalevel.at/prolog/videos/domino_tiling

Thank you all for motivating me to make this! This time, many thanks especially to you @jjtolton, and to one undisclosed interested party, since your question about this task motivated me to start.

The solution uses CLP(B), Constraint Logic Programming over Boolean variables, which Scryer Prolog provides via library(clpb). Personally, I find CLP(B) to be the coolest and most mystic of the current constraint solvers. The fact that there is a data structure that lets us, in so many interesting cases, efficiently count all solutions without enumerating them has always been extremely fascinating to me, and still is.

I first learned about CLP(B) in 2004, when I saw that cTI uses CLP(B) for termination inference. As a student of @UWN, I used to look in awe at the Overview of Prolog Systems, seeing that only SICStus Prolog and IF/Prolog had a "yes" entry for CLP(B). Seeing this, I wanted more systems to provide such an interesting component, and began to study Binary Decision Diagrams (BDDs) which are used by the SICStus Prolog implementation explained in a Technical Report by Mats Carlsson.

The example is taken from Donald Knuth: The Art of Computer Programming, Vol. 4, Fascicle 1, which contains excellent information and references about BDDs and related data structures.

Conceptually, BDDs are simple data structures. But how would one represent them in Prolog? I thought for years about it without being able to write a single line of code. I managed to find a satisfactory way only ten years later, in 2014, and eventually published a long journal paper about my portable Prolog-based CLP(B) implementation. And only now, another ten years later, is there a free Prolog system that ships with all the features I need to elegantly express this task in a way that is most compatible with SICStus Prolog. Think about this when you get frustrated with Prolog after a few hours, weeks or only months of trying. We can count ourselves lucky if the geost/N family of constraints provided by SICStus Prolog become available in Scryer Prolog in the next 20 years.

It is a privilege to see Scryer Prolog in such a great shape, with so many exciting developments in the year of the dragon. In the year 2025, we shall mix the chips: agua al dominó! May the chaos we find ourselves in motivate us to build what the world cannot give us. May correctness, robustness and elegance be found, if nowhere else, then at least in Scryer Prolog and its applications! May our journey be long and adventurous, with many highs and lows, for the highs are only highs due to the lows!

Enjoy!

All the best,
Markus

[aarroyoc]

Great video! I wonder what's so special about geost/N now, but I don't want to enter into another rabbit hole! I was also surprised to see one of the most complex ways of generating numbers of the Fibonacci sequence in Prolog :)

The year of the tiger is ending right now, but the year of the snake is around the corner and I hope we can finish, with great success the adventures we started, ready to jump into new missions and exploring hic sunt dracones territory!

[UWN]

hit sunt dracones territory!

hic

[jjtolton]

Wow this is a great video. I did not realize there was such a crazy story behind clp(b)!! I'm on my second time watching now and still have more information to extract.

I'm thinking I need to move to Vienna. I'm not even sure TU Wien would accept me but I could sit outside and lick the windows.