Prolog vs miniKanren — Brief ☧
Deep version → | Back to appendo →
Q: Two scribes are searching the Scriptures for a particular prophecy. They know it might be in Genesis or in Isaiah, but they are not sure which. How should they search?
A: Scribe A picks Genesis and reads it cover to cover — page by page, never skipping ahead. If the prophecy happens to be in Isaiah, he may spend a very long time in Genesis before he ever gets there. If the book were infinitely long, he would never reach Isaiah.
Q: That sounds risky. What does the second scribe do?
A: Scribe B takes a different approach. He reads Genesis chapter 1, then Isaiah chapter 1, then Genesis chapter 2, then Isaiah chapter 2 — alternating back and forth. He makes slower progress through each book, but he is guaranteed to eventually cover every chapter of both books.
Q: So Scribe A goes deep into one path, and Scribe B spreads his attention evenly. Which strategy is better?
A: That depends on where the answer is hiding:
- Scribe A's strategy (depth-first search) is faster when the answer happens to be on the path he is already reading. No overhead from switching between books.
- Scribe B's strategy (interleaving search) is complete — he will find every finite answer eventually, no matter which book it is in.
This is the fundamental difference between Prolog and miniKanren. Prolog searches like Scribe A. miniKanren searches like Scribe B.
Q: Are there other differences beyond the search strategy?
A: Several important ones:
Side-by-Side
| Feature | Prolog | miniKanren |
|---|---|---|
| Search strategy | Depth-first (may miss answers) | Interleaving (complete for finite answers) |
| Control flow | cut (!), if-then-else | Pure: only conde branching |
| Negation | \+ (negation as failure) | =/= (disequality constraint) |
| State | Mutable (assert/retract) | Immutable substitutions |
| Hosting | Standalone language | Embedded in a host language (Python, Scheme, etc.) |
| Best for | Deterministic, goal-directed programs | Relational exploration, generating all solutions |
| Hardware mapping | Hard to parallelize (cut kills branches) | Natural parallelism (all branches independent) |
The Cut Problem
Prolog has an operator called cut (!) that prunes the search tree — once a branch is chosen, all alternatives are discarded. This can be efficient, but it can also hide valid answers:
% Prolog: once you find a Levite priest, stop looking
priest(X) :- levite(X), !.
priest(melchizedek). % This is NEVER reached!Melchizedek — a priest not from the tribe of Levi (Genesis 14:18) — is lost because the cut told Prolog to stop searching after the first match.
miniKanren has no cut. Every branch of conde is explored:
# miniKanren: finds ALL priests
def priest_chirho(x_chirho):
return conde_chirho(
[levite_chirho(x_chirho)], # Levite priests
[eq_chirho(x_chirho, "Melchizedek")] # AND Melchizedek
)
# Both branches explored — no information lostThis relates back to the idea of search completeness: miniKanren's interleaving algorithm ensures that every conde branch gets a turn, so no valid answer is silently dropped.
For Hardware
Prolog's cut makes parallelism difficult — one branch needs to signal others to stop, which requires coordination between processing lanes. In hardware terms, this means you would need inter-lane communication wires, arbitration logic, and pipeline stalls. Every time one lane finds a result and triggers a cut, the other seven lanes would need to be notified, flush their in-progress work, and reset. The overhead of this coordination would eat into the performance gains from parallelism.
miniKanren's pure conde maps directly to parallel FPGA lanes: each lane processes one branch independently, with no need to communicate "stop" signals. Each lane reads its own search state, applies constraints with bitmask AND, and writes results — all without ever looking at what the other lanes are doing. That independence is what makes hardware acceleration practical: the lanes can run at full speed with zero coordination overhead.
Soli Deo Gloria