Domains and Narrowing -- Brief ☧
Deep version -> | Lab -> | Back to Unification ->
Q: Imagine a goldsmith receives a chunk of raw ore. Inside that ore
there might be gold, silver, copper, tin, lead, or worthless dross. Before
he tests anything, what could be hiding in there?
A: Any of those six substances, right? We just don't know yet. That
set of remaining possibilities is what we call the ore's domain:
{gold, silver, copper, tin, lead, dross}.Q: OK, so the goldsmith heats the ore and skims off the dross. Now
what's left?
A:
{gold, silver, copper, tin, lead}. See what happened? The domaingot smaller -- it narrowed. That's really the heart of constraint
solving: each step removes something that can't be part of the answer.
Q: That makes sense for a goldsmith, but how does a computer do this
kind of refining?
A: Think of each possibility as a single bit in a number. Six substances
means six bits. Removing something is just clearing its bit -- and we can
do that with a simple AND operation using a bitmask:
Raw ore: 111111 (gold=0, silver=1, copper=2, tin=3, lead=4, dross=5) Not dross: 011111 (constraint: bit 5 cleared) AND: 011111 -> dross removed, five remain Not lead: 101111 AND: 001111 -> four remain Pure metals: 000011 (only gold and silver survive all refinement)Each constraint is just a mask, and applying it is a single AND instruction.
That's why this approach is blazingly fast.
Q: What if the domain becomes
000000? All zeros?A: Then nothing survives -- every possibility has been ruled out. The
constraints are unsatisfiable. It's like demanding something that is
both pure gold AND worthless dross at the same time. Contradiction. Failure.
The solver knows to stop and report "no solution exists."
Domain Sizes in Our Hardware
| Domain Type | Capacity | Representation | Use Case |
|---|---|---|---|
BitVec64Chirho | 64 values | Single u64 | Fast, small problems |
Hierarchical4kChirho | 4,096 values | 64 x 64 bits | Medium scale |
Hierarchical256kChirho | 262,144 values | 64 x 64 x 64 | Large (FPGA deployed) |
The takeaway from this table is that domain size is a design choice, and each
level comes with a tradeoff. BitVec64Chirho fits in a single CPU register and
performs intersection in a single clock cycle -- but 64 possible values is only
enough for small problems like the "three tribal leaders" example above. When you
need to represent thousands or hundreds of thousands of possible values (think of
assigning medical codes, scheduling across large datasets, or mapping a complex
graph), you reach for Hierarchical4kChirho or Hierarchical256kChirho. These
use a layered structure -- like a refiner who first checks the broad category of
an ore before examining individual grains -- so they can skip large sections of
empty space efficiently.
On our FPGA, the Hierarchical256kChirho is the workhorse. It lives in HBM
(High Bandwidth Memory) and uses a three-level summary structure that lets the
hardware skip over groups of impossible values without even reading them. This
is the difference between testing every grain of ore one at a time versus first
checking the color of the slag -- the hierarchical structure saves enormous
amounts of work.
The Core Insight
With those details in mind, we can distill the entire domain-narrowing approach
into three simple ideas:
Domain = the set of values a variable might take
Constraint = removes impossible values (AND with a mask)
Solving = refine until each variable has one value or noneEvery topic that follows in this module builds on this foundation. Propagators
(next topic) are the mechanism that applies constraints to domains. Lattices
give us the mathematical guarantee that the narrowing process always terminates.
And fixpoint is the name for the moment when no further narrowing is possible --
the silver is pure.
Soli Deo Gloria