Relations vs Functions — Brief ☧

Deep version → | Back to Bitmasks →

Q: In the book of Ruth, Naomi is Ruth's mother-in-law.

Suppose I write a little program: mother_in_law("Ruth"). It returns "Naomi".

That seems useful — what kind of program is that?

A: That is a function. You give it one input, it gives you one output, and it only works in one direction — you hand it a daughter-in-law and it tells you the mother-in-law.

Q: Alright, but now I want to ask the opposite question: "Who are Naomi's daughters-in-law?"

Can I use the same function?

A: No. A function is like a one-way street. mother_in_law("Ruth") goes forward, but there is no built-in way to go backward and ask "who has Naomi as mother-in-law?" You would have to write a second, separate function.

Q: That feels wasteful. The information is the same — just viewed from a different angle. Is there something that lets me ask the question in any direction?

A: Yes — a relation. Instead of a one-way pipe, think of a table of connections:
mother_in_law_chirho:
  (Ruth, Naomi)       ✓
  (Orpah, Naomi)      ✓
  (Naomi, ???)         (not in the relation)
The data just sits there. You can query it from any side.

Q: How do I actually query a relation?

A: Fix any column you know, and read back the others:

Fix daughter-in-law = "Ruth" → mother-in-law = "Naomi" (forward)

Fix mother-in-law = "Naomi" → daughter-in-law is one of {"Ruth", "Orpah"} (backward)

Fix nothing → get all pairs (enumerate)

Same data. Any direction. That is relational programming.

Functions vs Relations

	Function	Relation
Direction	One way (input → output)	Any way
Results	Exactly one	Zero, one, or many
Example	`len("hello") = 5`	`appendo(?, ?, [1,2,3])` = 4 splits
In Python	`def f(x): return x+1`	Not natural in Python
In miniKanren	Not the paradigm	`(run* (q) (appendo q r '(1 2 3)))`
In your FPGA	Not what it does	Slice tensor on any dimension

The Tensor Connection

A binary relation IS a matrix. A ternary relation IS a 3D tensor.

Think of it this way: if you have ever looked at a spreadsheet, each row is one fact. A relation is that spreadsheet — and you can filter on any column. This is not just an analogy — it is the literal mathematical correspondence that makes our hardware work. When we store a relation as a matrix in memory, querying it forward means reading a row, and querying it backward means reading a column. Both are simple memory access patterns that hardware handles naturally.

graph LR
    subgraph "Function (one-way)"
        A1[Ruth] -->|mother_in_law| B1[Naomi]
    end

    subgraph "Relation (any-way)"
        A2[Ruth] <-->|mother_in_law_chirho| B2[Naomi]
        A3[Orpah] <-->|mother_in_law_chirho| B2
    end

Relation as matrix:
              Naomi  Boaz  Elimelech
    Ruth        1     0      0
    Orpah       1     0      0

Slice on row "Ruth" → {Naomi}       (forward)
Slice on col "Naomi" → {Ruth, Orpah} (backward)

In computer science terms, a function runs in one direction with O(1) lookup time. A relation stored as a hash table can give you fast lookups in multiple directions — or you can think of it as a matrix where slicing on a row or column is the query.

This distinction between functions and relations is the foundation of everything in miniKanren. Traditional programming languages are built around functions: you call a function with inputs and get outputs. Relational programming flips this: you describe relationships, and the system figures out which direction to run them based on what you already know and what you want to find out. The next topic, unification, is the mechanism that makes this bidirectional magic work.

Learn more about relations

→ Next: Unification | Next: appendo

Soli Deo Gloria

Relations vs Functions — Brief ☧

Functions vs Relations

The Tensor Connection

Lab