Unify and Conquer: Logic Programming in a Strongly-Typed Land

“The computer programmer is a creator of universes for which he alone is the lawgiver. No playwright, no stage director, no emperor, however powerful, has ever exercised such absolute authority to arrange a stage or field of battle and to command such unswervingly dutiful actors or troops.” — Joseph Weizenbaum

In the early 2010’s¹ when I was taking an undergrad course on Logic Programming, there was this professor that was a bit of a legend in the AI community, and a full byte in being a jerk². The course was (and I believe it still is?) taught using Prolog.

In the previous term I had submitted a chess engine as my project for the “Algorithms and Data Structures” course; which was when I learned to hate Java’s inability to elegantly perform pattern matching and term destructuring³. But now… here it was this whole new language with a whole new way of thinking about programming, where pattern matching⁴ was at the core of its semantics.

The Seductive Promise of Logic Programming

So, instead of telling the computer how to solve a problem step-by-step (or asking your favourite LLM and then see it failing in the most hilarious ways), you simply describe what the problem is and let the computer figure out the solution (non-stochastically). Want to find all the ways to arrange a list? In theory, you don’t write a sorting algorithm: you describe what “sorted” means and ask for arrangements that satisfy that property. In theory…

… It sounds almost too good to be true; just like most things that sound too good to be true⁵. But we’ll get there… First, let’s start with the canonical example everyone will show you; something similar to this:

parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Then you ask: “Who are Tom’s grandchildren?” and the system magically responds with ann and pat. It’s elegant, it’s declarative, and it makes you feel like you’re programming at a higher level of abstraction than mere mortals.

This obsession with family members

An unwritten rule of programming languages is to show Fibonnaci as an example of expressiveness and terseness. In the logic programming family of languages, everyone seems to be fixated on family relationships. At some point in my life, I taught Alloy, and one of the canonical examples was to find an inhabitant for something that roughly translated this puzzle:

Can a man be his own grandpa?

Apparently, Alloy preceeded LLM’s ability to immitate art, and personifying Dwilight Latham and Moe Jaffe, it answered in verse⁶:

“Now, many, many years ago when I was twenty-three
I was married to a widow who was pretty as could be
This widow had a grown-up daughter, had hair of red
My father fell in love with her and soon the two were wed
This made my dad my son-in-law and changed my very life
My daughter was my mother ‘cause she was my father’s wife
To complicate the matter, even though it brought me joy
I soon became the father of a bouncing baby boy
My little baby then became the brother-in-law to Dad
And so became my uncle though it made me very sad
For if he was my uncle, that also made him the brother
Of the widow’s grown-up daughter who of course was my step-mother
My father’s wife then had a son that kept him on the run
And he became my grandchild for he was my daughter’s son
My wife is now my mother’s mother and it makes me blue
Because she is my wife, she’s my grandmother too
Now, if my wife is my grandmother, then I’m her grandchild
And every time I think of it, it nearly drives me wild
For now I have become the strangest case you ever saw
As husband of my grandmother, I am my own grandpa”

Thank you. Next…

Personally, not being a huge fan of Beverly Hills-style soap operas, the precise example that I most vividly recall in The-Textbook™ was that of a Symbolic Differentiation Engine, and man… I kid you not when blown away I was by the elegance of the solution. It started with some “facts”:

derivative(X, X, s(0)).
derivative(X^s(N), X, s(N)*S^N).
derivative(sin(X), X, cos(X)).
derivative(cos(X), X, -sin(X)).
derivative(e^X, X, e^X).
derivative(log(X), X, 1/X).

… and proceeded with some rules:

derivative(F+G, X, DF+DG) :- 
  derivative(F, X, DF), derivative(G, X, DG).

...

derivative(F/G, X, (G*DF-F*DG)/(G*G)) :-
  derivative(F, X, DF), derivative(G, X, DF).

You could almost read them as equations:

There it was again! It was elegant, it was declarative, it was beautiful, it was… wait; how the hell did this actually worked?

To be continued…