Notes on Relational Programming and miniKanren

Relational programming is a different way of writing computation. I want to compare two ways to describe the same problem: the functional way and the relational way.

The problem is simple. Take two lists and combine them into one.

The ordinary function version

With an ordinary Scheme function, append takes two lists and returns a third:

(append '(1 2) '(3 4))
; => (1 2 3 4)

The first two arguments are inputs. The result is the output. The caller decides which values go in and which value comes out.

This append interface is written for that direction. If you want every way to split a list, you use a different operation. The direction is part of this function's interface.

This is the ordinary function-call model: supply arguments, evaluate the function body, and receive a result.

The relational version

Now look at the same problem as a relationship instead of a procedure.

The relationship is: out is what you get when you put l and s together. Those are just names for the three positions.

Notice what it does not say. It does not say that l and s are inputs. It does not say that out is the output. It only says how the three values are connected.

Imagine a form with three blanks:

l: ______    s: ______    out: ______

You can fill in any of the blanks and ask for the rest.

Fill in l and s, and the relation gives you out. That is append.

Fill in out, leave l and s blank, and the relation gives you every way to split that list. That is the same relationship, used in a different direction.

Fill in all three, and the relation tells you whether they fit.

This is the difference the example is highlighting. The problem has not changed. We are still connecting two lists to their concatenation. Only the description has changed.

A conventional function call fixes which positions are inputs. A relational query lets the query decide which positions are known.

This function call asks: given these inputs, what is the output?

Relational programming asks: what values make this relationship true?

How the relationship is represented

There is no single picture that is “the” relation. There are layers.

At the level of the interface, the relation is a box with three ports. The function version has two inputs and one output. The relational version has three ports and no fixed direction.

At the level of values, the relation is a table. A few rows for the append relationship:

Each row is a fact. The table illustrates the relation extensionally. It is infinite because lists can be any length, but any finite slice looks like this.

A conventional function call reads the last column from the first two. A relation can be read along any column.

Mathematically, the same relation is written:

{ (l, s, out) | out = l ++ s }

That is shorthand for “all triples where out is l followed by s.”

A miniKanren program defines the relation intensionally: it states the rule and answers particular queries. The table is one extensional view of that relation.

What makes the relational version work

To fill in the blanks, the language cannot rely only on a deterministic, one-way procedure. It has to treat the blanks as unknown values and solve for them.

Three pieces make that possible.

Logic variables. A logic variable is a placeholder that may stay unbound or be bound later. It can also be bound to a term that contains other logic variables.

Unification. Unification is how the language fills in blanks. It takes two terms and finds bindings for the logic variables that make the terms identical.

For example, unify (1 x 3) with (1 2 y). The first elements match. The second elements give x = 2. The third elements give y = 3.

It walks both terms at the same time. When it reaches an unbound variable, it records a binding. When it reaches two unbound variables, it links them together. Bind one later, and the other resolves to the same value. When it reaches two concrete values, they must be equal.

This is more than equality checking. Equality asks whether two complete values are the same. Unification solves for bindings that would make them the same.

It is also more than pattern matching. Pattern matching binds variables on one side. Unification can bind variables on either side. Unify (x 2) with (1 y) and you get x = 1, y = 2.

If the terms cannot be made identical, unification fails. Unify (1 2) with (1 3), and the second elements conflict. There is no assignment that makes them the same.

The result is a substitution: the current set of bindings among logic variables and terms. As unification proceeds, the substitution grows.

Back in the append relationship, the split query leaves the first two positions blank. Unification is what lets the system bind those positions to concrete lists, one consistent answer at a time.

Search. When more than one answer fits, the language tries the alternatives and keeps the ones that work. That is how one relationship can produce several splits or several matches.

Together, these turn a description into a search for values that satisfy it.

That is the shift. A function is a recipe. A relation is a rule, and the language searches for values that fit the rule.

Relational programming is narrower than logic programming

Logic programming is the broader family. Relational programming is a style within it: every goal is written as a pure relation, and each relation produces meaningful answers even when all of its arguments are unbound logic variables ^[1].

Pure means the relation's logical meaning does not depend on which arguments are ground, and it does not rely on hidden state. Termination and answer order can still depend on the query.

Prolog is a logic programming language, but not every Prolog program is relational. Cut and modes are useful, but they tie a program to a particular direction. Relational programming tries to avoid that ^[4].

Relational programming is a style, not a single language. miniKanren is one family designed for it.

The same problem in miniKanren

Here is the relational version of append in miniKanren. The code is short because the relationship is short:

(define (appendo l s out)
  (conde
    [(== l '()) (== s out)]
    [(fresh (a d res)
       (== l (cons a d))
       (== out (cons a res))
       (appendo d s res))]))

This is miniKanren embedded in Scheme. appendo has two clauses. The first is the base case: if l is empty, out is s. The second is the recursive case: it moves the head of l onto the front of out and recurses on the tail. == is unification, fresh introduces local logic variables, and cons builds a pair. The trailing o is just a naming convention for relations.

Ask it to append:

(run* (q)
  (appendo '(1 2) '(3 4) q))
; => ((1 2 3 4))

Ask it to split:

(run* (q)
  (fresh (x y)
    (appendo x y '(1 2 3))
    (== q (list x y))))
; => ((() (1 2 3))
;     ((1) (2 3))
;     ((1 2) (3))
;     ((1 2 3) ()))

run* returns a list of answers. In the first query, there is one answer, and that answer is the list (1 2 3 4). In the second, q is bound to a two-element list, so each answer is a two-element list.

These are the append and split cases from above, now expressed in code.

Where miniKanren comes in

miniKanren is a family of logic programming languages designed for relational programming. The name comes from the Japanese word for relation. It has been implemented in Scheme, Racket, Clojure, Haskell, Python, JavaScript, and other host languages ^[4].

Core miniKanren adds three logical operators to its host language: ==, fresh, and conde. There is also run, which is the interface between the host language and the miniKanren program ^[3].

How search works

Search is the part that turns a relation into answers. It has three moving pieces: states, goals, and streams.

State

A state holds the current substitution and whatever bookkeeping the implementation needs for fresh variables and constraints. In a minimal implementation, that bookkeeping can be just a counter.

The substitution records bindings. If you unify x with 1, x resolves to 1. If you then unify y with x, y resolves to 1 as well. Implementations may store that as y -> x or as y -> 1; the observable result is the same.

Goal

A goal is a function from a state to a stream of states. An expression such as (== x 1) is a goal. fresh and conde build goals out of other goals.

A goal can return no states, one state, or many states. == returns one state when unification succeeds and none when it fails. If three conde clauses each succeed exactly once, their merged stream contains three states.

A stream is lazy. It can be finite or infinite because the next state is produced only when something asks for it.

Conjunction and disjunction

Conjunction is sequencing: run the first goal, then run the second goal on every state the first produces. Disjunction is choice: run both goals on the same input state and merge their streams.

In the code, the goals inside a conde clause are a conjunction. The clauses themselves are a disjunction. That is why one clause can fail while another succeeds.

Merging streams

When a goal produces several states, the next goal runs on each one. The results are merged into a single stream.

The order of that merge matters. A depth-first merge takes all of the first stream before touching the second. If the first stream is infinite, the second is never reached.

miniKanren interleaves the streams. It gives each branch a bounded turn once that branch has produced a stream, so an infinite branch does not monopolize the merge. That is why it can find answers where depth-first search would loop forever ^[2][4].

Interleaving is fairness at the merge point. It does not guarantee that every relation terminates, and it cannot rescue a branch that diverges before it produces a stream.

Each conde clause is a branch. Recursion adds another level. The search walks the resulting tree.

At each node, the split query has two branches: one for the empty list and one for a non-empty list. The empty-list branch produces an answer. The recursive branch produces the rest of the tree. The tree shows that structure. The merge diagram above illustrates the scheduling strategy, not this tree's exact traversal order.

What is relational programming good at?

Relational programming is a good fit when the relation is the specification, and when you need to ask more than one question of it.

Multiple directions

The same relation can append, split, or check a list. A relational type inferencer can infer a type, check a type, or perform type inhabitation. A relational interpreter can evaluate a program, generate a program, or check that a program produces a value.

This is the strongest case. One specification answers several kinds of question, instead of requiring a separate function for each direction.

Search and constraints

Relational programming fits problems where you need to find values that satisfy conditions: scheduling, configuration, planning, graph and path problems, and resource assignment.

miniKanren is good for small, symbolic versions of these, especially when the problem is embedded in a larger application. For large optimization problems, SAT, SMT, and constraint solvers are usually better.

Synthesis and generation

Relational programming fits problems where you want many candidates, not one answer: generating programs that satisfy a specification, generating proofs or theorems, generating test inputs, or generating examples from a grammar.

Byrd's examples include a theorem prover that generates proofs and theorems, and a relational interpreter that can run forward, generate programs, and produce quines from the same definition ^[1][4].

Checking and verification

Once a relation exists, checking is often just running it with all arguments known: type checking, proof checking, validating a configuration, or checking whether a transformation preserves a property.

The useful part is that the checker and the generator can share one specification.

Symbolic interpreters and transformations

Relational programming is comfortable with recursive symbolic structure: interpreters and evaluators, type systems, parsers and grammars, and AST transformations. Some compiler and refactoring tasks can be expressed as relations, though the search cost may not be worth it.

Lists, trees, terms, and substitutions are natural fits for unification and search. This is where miniKanren's heritage in Scheme and symbolic computation shows.

Embedded tools and prototypes

miniKanren is small and embeddable. It fits when you want to add search or logic to an existing application without adopting a full Prolog system. That is also its practical niche: a small relational engine inside a larger host program.

Where it is a poor fit

• One-direction, deterministic transforms. If a function is enough, a relation adds search overhead for no benefit.
• Large ground datasets or knowledge bases. miniKanren has no global fact database. Datalog or Prolog is often a better fit.
• Heavy numeric computation. Relational arithmetic exists, but it is usually not the fast path.
• Performance-critical or latency-sensitive code. Search order, memory use, and nondeterminism work against predictable performance.
• Large branching search spaces. Without constraints or heuristics, the search explodes.
• Effects and mutable state. The core is pure. I/O and mutation belong to the host and can undermine the relational properties.

A rule of thumb

Use relational programming when:

1. The relation is the specification, not just the implementation.
2. More than one mode of use matters.
3. The search space is small enough, or constraints prune it enough.
4. Generation, checking, and solving can share one definition.

Otherwise, use a function, a database, or a specialized solver.

What the style costs

Relational programming does not remove the need to think about direction. It moves the decision from the interface to the query. appendo terminates for finite lists in the forward and split directions. A less careful relation can diverge when a variable is left unbound.

Byrd calls the desired property finite failure: if no answer exists, the query should fail in a finite amount of time ^[1]. That is not guaranteed for every relation, and it is one of the hard parts of the style.

The hard parts are still yours. Writing a relational program is mostly a question of representation. A relation that is natural in one direction can be awkward in another. Termination is not automatic. Search order matters. Constraints can prune the space, but they also complicate the relation. Tabling can improve termination, but it is an extension. The small core is small because these features are not free.

miniKanren is also not itself a theorem prover. It searches for substitutions that satisfy goals. If you want proof search, you encode it as a relation.

That boundary is what makes miniKanren useful to study. It does not hide the cost of search behind a large system. It gives you a small core and makes you decide what to do with it.

Summary

Relational programming changes the question from “given these inputs, what is the output?” to “what values make this relation true?” A function call fixes a direction. A relation leaves the direction to the query. The engine fills the gaps with logic variables, unification, and search.

miniKanren is a small implementation of that idea. Its core is a handful of operators, and its search interleaves branches so one infinite path does not monopolize the merge. That is enough to make the same relation append, split, or check, depending on what the query supplies.

The cost is search. A relation can have no answer, one answer, or many. It can also fail to terminate. Writing relational programs is mostly about choosing a representation and an order of search that makes the queries you care about tractable.

References

1. Byrd, W. E. (2009). Relational Programming in miniKanren: Techniques, Applications, and Implementations. PhD dissertation, Indiana University.
2. Hemann, J., and Friedman, D. P. (2013). μKanren: A Minimal Functional Core for Relational Programming. Scheme and Functional Programming Workshop.
3. Friedman, D. P., Byrd, W. E., Kiselyov, O., and Hemann, J. (2018). The Reasoned Schemer, Second Edition. MIT Press.
4. miniKanren.org. “What is miniKanren?” and “Differences between miniKanren and Prolog.”