Prolog is a vibe

Start with a base sets of facts. Combine those facts to produce more facts. Then combine those facts, original or combined, to produce even more facts, the newly combined facts being just as elemental as the ones we started with. Keep combining until we end up with the fact that we need. Voila, problem solved.

Prolog is tailored for this sort of an approach, which is important because at some point, efficiency becomes qualitative. And not just the efficiency of runtime, but also the efficiency of the programmer who is writing the solver (usually us programmers write solvers, not solutions). Everything is Turing complete, and we can use most languages to do most things, but the absence of the proper combinators severely limits the set of problems that can efficiently expressed, and solved in that language.

This is like my Sapir-Whorf hypotheses, but for programming. And it is not about high level or low level – it is about affinity to the problem's domain. Don't use a hammer to cut cheese.

So the idea here is not to emulate or simulate Prolog in a shell script. It is slightly more abstract - to capture the vibe.

To demonstrate what I'm talking about, I wrote a solver for a recent Advent of Code puzzle in a way to capture this vibe, this process of the computer program "thinking" in its thought space, interospecting on its own previous thoughts, until it links them together into a solution.

The resultant shell script is not structured as functions or subroutines or steps. It is instead structured as a set of passes over a database of facts. What database do we use? It’s own log file!

It is just a simple text file. Many people are unaware of the joy, and capabilities, of manipulating lines of text in the unix universe that came to K&R in a fever dream.

The first pass reads the input, line by line, and if it finds something interesting, it notes it down in its log file. Very basic deductions, and emitted in a very simple way, like

echo "The number on line 7 looks interesting" | \
  tee -a /my/log

The next pass reads the log file (and the input file again if needed), and emits deductions that combine previous deductions. Say something like "Looks like both line 7 and line 8 have interesting numbers". It writes these back to the same log file.

We keep doing this, passing over this "database of facts" as many times as we like, building higher and higher level deductions, until we’ve combined our way to the solution, say "The longest run of lines each with an interesting number is of size 23".

If it sounds abstract, have a look at the source code. Even if you don’t talk shell script or awk, you should be able to get the basic flow that I’m hinting at.

Manav Rathi
Dec 2023