Lattices -- Brief ☧
Deep version -> | Back to Fixpoint ->
Q: Jacob dreams of a ladder set upon the earth, its top reaching to
heaven, with angels ascending and descending (Genesis 28:12). Let's
borrow that image. If the bottom of the ladder is "I know absolutely
nothing" and the top is "I know everything possible," which direction
does learning go?
A: Upward. Each step up the ladder means we've learned something new --
we've eliminated a possibility. At the bottom, every value is still on the
table. As we climb, the domain shrinks and our knowledge grows.
Q: And we can never step back down? We never "unlearn" something?
A: Right. If we discover "the answer is NOT Dan," then Dan stays
eliminated. Domains only shrink. Knowledge only grows. In math, we say
the process is monotone -- it only moves in one direction.
Q: So what do computer scientists call this ladder structure?
A: A lattice -- specifically a meet-semilattice. Let's unpack
those terms with our concrete example:
- The meet of two domains is their intersection. If one constraint says "could be {gold, silver, copper}" and another says "could be {silver, copper, tin}," the meet is {silver, copper} -- what they agree on. With bitmasks, the meet is just AND.
- Moving up the lattice means knowing more (smaller domain, fewer bits set).
- The bottom is "know nothing" (all bits = 1, every value possible).
- The top is "contradiction" (all bits = 0, nothing is possible).
TOP (contradiction): 000000 -- impossible, nothing works | | {gold}: 000001 -- fully refined, one answer | {gold, silver}: 000011 -- almost there | ... | BOTTOM (everything): 111111 -- know nothing, all possibleQ: Wait -- the "bottom" has the most bits set? That feels upside down.
A: It does feel counterintuitive at first! Think of it this way:
information flows upward. "Everything is possible" sounds like a lot, but
it actually tells you very little -- it's the least informative state.
"Only gold remains" is far more informative. And "nothing is possible"
(contradiction) is the most extreme conclusion you can reach. So the
ordering is by how much you know, not by how many bits are set.
Key Properties
These four properties are the reason the entire constraint-solving machinery
works. They are not just abstract math -- each one directly impacts how our
hardware operates and why we can trust its results.
| Property | Meaning | Why It Matters |
|---|---|---|
| Monotone | Domains only shrink | Guarantees termination -- see Fixpoint |
| Meet = AND | Combining knowledge = intersection | Single instruction on FPGA |
| Finite height | 64 bits = at most 64 steps down | Bounded computation |
| Convergence | Must reach fixpoint | The refiner always finishes |
Let us walk through what each of these means in practice. Monotonicity is
the guarantee that we never go backward -- once we learn that Dan is not the
answer, we never have to reconsider Dan. This is why our FPGA does not need
an "undo" mechanism during propagation (backtracking is a separate matter,
handled by evaluating parallel "worlds"). Meet = AND means that combining
two pieces of knowledge is a single bitwise instruction -- on our FPGA, this
happens in one clock cycle, which is why the hardware is so fast. **Finite
height** gives us a hard upper bound: with 64-bit domains, the lattice can
have at most 64 levels, so the absolute worst case is 64 narrowing steps per
variable before convergence. And convergence is the punchline -- because
the lattice is finite and the operation is monotone, the process must
terminate. The refiner always finishes his work.
Because the lattice has finite height, we know the algorithm will
terminate. Each step either removes at least one bit (moves up the lattice)
or changes nothing (fixpoint reached). With 64-bit domains, that means
at most 64 narrowing steps per variable -- a strong guarantee that
translates directly into bounded hardware execution time.
Soli Deo Gloria