Semirings -- Brief ☧
Deep version -> | Back to E-Graphs ->
Q: Let's start with something concrete. Think about a road map.
If I ask "Can I get from Jerusalem to Bethlehem?" the answer is
yes or no. Simple. But what if I ask a different question about
the same map: "What's the shortest route?" or "How many different
routes are there?" or "What's the probability I arrive safely?"
A: Those are very different questions! The first is yes/no, the
second is about distance, the third is counting, and the fourth is
probability.
Q: Right. But here's what's surprising: the structure of the
computation is the same in every case. You're always doing two things --
combining constraints along a path, and choosing among alternatives.
It's just that the "combine" and "choose" operations change:
Question Combine (along path) Choose (among paths) Name "Can I get there?" AND (both legs must work) OR (either route suffices) Boolean "How likely?" multiply (joint probability) add (total probability) Probability "Shortest route?" add (sum the distances) min (pick the shorter) Tropical "How many routes?" multiply (combinations) add (total count) Counting This shared two-operation structure is called a semiring.
Q: So the algorithm stays the same, but you swap in different
arithmetic?
A: Exactly. Think of a semiring as a plug-in. Your constraint solver
or graph algorithm is the engine, and the semiring is the fuel. Change
the fuel and the engine answers a different question -- without rewriting
any of the logic.
Q: How does this apply to the FPGA hardware we've been learning about?
A: Our hardware does AND and OR on bitmasks -- that's the Boolean
semiring. But the same hardware structure can be reused with different
operations:
# Boolean semiring: does a solution exist? result_chirho = domain_a_chirho & domain_b_chirho # AND exists_chirho = result_chirho != 0 # OR (any bit set) # Probability semiring: how likely is each value? result_chirho = prob_a_chirho * prob_b_chirho # multiply total_chirho = sum(result_chirho) # add # Same structure, different arithmetic.Q: Can we go further? Like, could the FPGA learn -- adjust weights
like a neural network?
A: Yes! Replace Boolean AND/OR with differentiable multiply/add
(the probability semiring with gradients). Now constraints can have
learned weights that update during training. This is the bridge
between hard logic and machine learning -- same structure, richer
arithmetic.
The Four Semirings
Now here is the payoff. The same hardware structure -- the same pipeline of
operations -- can answer four completely different questions just by swapping
which operations you plug in for "combine" and "choose." Our FPGA currently
uses the Boolean semiring (AND/OR), but the architecture is ready for any
of these:
graph TD
S[Semiring Abstraction] --> B[Boolean<br/>AND / OR]
S --> P[Probability<br/>multiply / add]
S --> T[Tropical<br/>add / min]
S --> C[Counting<br/>multiply / add]
B -->|"hard logic"| HW[FPGA Hardware]
P -->|"soft logic"| ML[Machine Learning]
T -->|"optimization"| OPT[Shortest Path]
C -->|"enumeration"| CNT[Solution Count]Learn more about semirings, provenance, and differentiable logic
Soli Deo Gloria