Reactive and dataflow programs using SQLite — Part 1: A bit of background

The topic of relational and logic programming showed up on my radar in late 2018 when I discovered minikanren and Prolog. At the time, I was focused on programming languages for chemical automation and ideas the most concise robust possible implementations. Five years later, I am still hooked, and as I set up a lab where combining automation and languages is the bread and butter, “can it run a robot” has become my litmus test for any new idea

Prolog (from programming + logic) is the oldest and probably best-known example of a logic programming language where programs are expressed in terms of logical relationships between statements known as predicates. Execution generally begins with a query, where you ask the. To grossly oversimplify the process, Prolog responds by working backwards from the question to facts. A little example to demonstrate this (and whet your appetite!).

% Hint: Identifiers starting with a small letter are symbols
% those starting with a capital letter are variables.
% Also :- is meant to show a backwards arrow ← meaning if
% e.g. "A :- B, C" is read: "A holds if B and C are true".
% A is called the head and "B, C" the body of the clause.

% Facts (i.e. relations that unconditionally true).
language(prolog, 1972).
language(python, 1991).

% Relations: Language 1 precedes Language 2 if it was created in an earlier year
precedes(Lang1, Lang2) :- language(Lang1, Year1),
                          language(Lang2, Year2),
                          Year1 < Year2.

% Query: Is there a language L older than Python (and if so, what is it)?
?- precedes(L, python).
% Answer (yes, and it is Prolog)
L = prolog.

When posting the query precedes(L, python), Prolog simply does the following:

1. Asks “what are all the ways in which precedes(L, python) could hold?”, i.e. “what are the clauses whose head could be precedes(L, python)?”. Looks up the precedes relation and finds precedes(Lang1, Lang2)
2. Binds Lang1 to L (still a variable) and Lang2 to python (constrained). This operation is called unifying. Generally a free variable can be unified with any constant or free variable, but a constant like a symbol can only be unified with itself.
3. Substitutes every unified variable with what it has been unified with in the body of the clause, so the looks something like this now
   language(L, Year1), language(python, Year2), Year1 < Year2
   Note that L is still unbound.
4. From this point the process is recursive (it is beautifully simple!). Every predicate is queried in the same way until we fail or everything is rooted in facts. Let’s follow the steps …
5. The first predicate in the body post-unification is language(L, Year1), which can either be unified with language(prolog, 1972) or language(python, 1991). This is called a choice point and Prolog always tries all possibilities unless told otherwise. We’ll try both:
   • We unify L = prolog and Year1 = 1972 and move on to the next clause: language(python, Year2).
   • language(python, Year2) can only be unified with language(python, 1991), i.e. Year2 = 1991.
   • The last clause (Year1 < Year2) becomes 1972 < 1991, which is true.
   • Success: Add bindings L = prolog, Year1 = 1972, Year2 = 1991 to possible answers.
     We then try to unify language(L, Year1) with language(python, 1991).
   • We unify L = python and Year1 = 1991 and move on to the next clause: language(python, Year2).
   • language(python, Year2) can only be unified with language(python, 1991), i.e. Year2 = 1991.
   • The last clause (Year1 < Year2) becomes 1991 < 1991, which is false.
   • Failure
6. Once all possible paths have ended in success or failure, print the possible bindings (only those contained in the query are displayed, in this case L):
   L = Prolog

To summarise: Prolog’s default way of answering queries is by recursively looking up the clause it’s trying to prove and finding its body (i.e. condition or pre-requisites). This method is called backward chaining. In the next post, we’ll look at the opposite of this approach, called forward chaining and how it starts to approximate the operation of a database.