An arithmetic circuit is a directed acyclic graph (DAG) comprised of gates (vertices) and wires (edges). There are three types of gates:
For the purposes of this article, I'll refer to the latter two types of gate as operator gates. Also observe that our operator gates here both have an arity of strictly two.
As you may have realised already, this construction of arithmetic circuits permits us to construct a set of expressions which is exactly the set of all polynomials:
$$\left\{p|p\left(x\right)=\sum_{i=0}^{n}{a_ix_i^i}\right\}$$
With our theory out of the way, let's have a crack at modelling these in Rust.
In our construction, operator gates accept exactly two arguments. We can leverage this to greatly simplify our design by restricting our circuits to not just be DAGs but binary trees. Given that arithmetic circuits are both comprised of gates and exhibit fundamentally recursive structure, it seems very natural to model them as such.
use std::boxed::Box;
#[derive(Debug)]
enum Gate<T> {
Input(T),
Add(Box<Self>, Box<Self>),
Multiply(Box<Self>, Box<Self>),
}
Let's break this down line-by-line.
Line 1 imports the Box<T> type provided by the standard library. I won't delve deeply into what Box provides us in this article, but the short end of it is that it's the most straightforward way to allocate to the heap in Rust. This will become significant for our Gate type as we'll see below.
Line 3 instructs the Rust compiler to automatically derive the Debug trait for our Gate<T> type. We might as well get this out of the way early as this is bound to help us in the future and is generally considered well-mannered.
Lines 4-5 handle the start of our Gate<T> type and the definition of an input gate, respectively. In Rust, enumerated types (or simply enums) are much more expressive than in other languages (say C): they allow us to define variants of our type which can be pattern matched against in various, more powerful ways (most prominently via the match keyword). As such, I've decided to make Gate generic and for the first type of gate -- input gates -- our variant will simply accept an instance of our type variable, T.
Lines 6-7 concern our operator gate definitions. For our operator gates, we exploit the same line of reasoning as for input gates, only this time they are self-referential. This introduces a problem for us: how will the Rust compiler know the size of our Gate<T> type at compile time if it contains itself? Consider the following alternative (but flawed) definition:
#[derive(Debug)]
enum Gate<T> {
Input(T),
Add(Self, Self),
Multiply(Self, Self),
}
If we attempt to compile this, rustc will complain accordingly:
$ cargo build
error[E0072]: recursive type `Gate` has infinite size
--> src/main.rs:2:1
|
2 | enum Gate<T> {
| ^^^^^^^^^^^^ recursive type has infinite size
3 | Input(T),
4 | Add(Self, Self),
| ---- ---- recursive without indirection
| |
| recursive without indirection
5 | Multiply(Self, Self),
| ---- ---- recursive without indirection
| |
| recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `Gate` representable
|
4 ~ Add(Box<Self>, Box<Self>),
5 ~ Multiply(Box<Self>, Box<Self>),
|
For more information about this error, try `rustc --explain E0072`.
error: could not compile `bang` due to previous error
Note that we have more than one option for indirection here; I've avoided the use of a reference as I don't want to deal with explicit lifetimes.
Appealing to our use of recursion, it's possible to consider evaluation not just at a circuit level, but at a gate level also. What do we mean by evaluation?
$$ \text{eval}:\text{Gate}\rightarrow S $$
Here, $S$ denotes the set of all elements that our arithmetic circuit operates over1.
This is all well and good, but how do we actually perform such gate evaluation? We take cases:
impl<T: Clone + std::ops::Add<Output = T> + std::ops::Mul<Output = T>> Gate<T> {
pub fn evaluate(&self) -> T {
match self {
Self::Input(t) => (*t).clone(),
Self::Add(a, b) => a.evaluate() + b.evaluate(),
Self::Multiply(a, b) => a.evaluate() * b.evaluate(),
}
}
}
There's a bit going on here, but not that much! The guts of the function involve our aforementioned match expression2.
| Case | Description |
|---|---|
| Input | Simply return the input number, t. We clone here due to not wanting to constrain T to be Copy (although it'd probably be sensible to do so). |
| Addition | We return the sum of the result of evaluating each input gate. |
| Multiplication | We return the product of the result of evaluating each input gate. |
What about the first line, the one that opens the impl block, though? It might look a bit intimidating but it simply imposes some type bounds on our type variable, T. Specifically, we need T to be able to do three things:
Clone)T)T)The type bounds we've specified on T (T: Clone + std::ops::Add<Output = T> + std::ops::Mul<Output = T>) exactly capture these requirements.
It'd be nice if we could print gates canonically (i.e., without having to rely on its Debug representation). Fundamentally, gates themselves represent arithmetic (sub)expressions, so this should be relatively straightforward. We've recursed twice now and we're going to do it again.
impl<T: std::fmt::Display> std::fmt::Display for Gate<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
Self::Input(t) => write!(f, "{}", t),
Self::Add(a, b) => write!(f, "({} + {})", a, b),
Self::Multiply(a, b) => write!(f, "({} * {})", a, b),
}
}
}
This code block is structurally identical to our Gate::evaluate implementation. This time, we only require that T itself be Displayable -- we can handle the rest.
Now that we've constructed a fairly robust gate primitive, it's time to actually compose gates together somehow. It turns out that our existing gate code can already do this rather gracefully due to its recursive design. All we need now is to capture the circuit-level functionality.
#[derive(Debug)]
pub struct Circuit<T> {
root: Box<Gate<T>>,
}
impl<T> Circuit<T> {
pub fn new(root: Gate<T>) -> Self {
Self {
root: Box::new(root),
}
}
}
That's it. Our Circuit<T> type simply holds a Boxed Gate<T>, which is the root vertex of our binary tree. Our constructor simply does the Boxing for us, provided a Gate<T>.
Circuit evaluation proceeds in much the same way as gate evaluation does. We'll need to preserve our existing type bounds on T but otherwise:
impl<T: Clone + std::ops::Add<Output = T> + std::ops::Mul<Output = T>>
Circuit<T>
{
pub fn evaluate(&self) -> T {
self.root.evaluate()
}
}
Even formatting is the same.
impl<T: std::fmt::Display> std::fmt::Display for Circuit<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.root)
}
}
Let's attempt to actually construct and evaluate an arithmetic circuit using the code we've written thus far.
fn main() {
let g: Gate<u64> = Gate::Multiply(
Box::new(Gate::Add(
Box::new(Gate::Input(12u64)),
Box::new(Gate::Input(20u64)),
)),
Box::new(Gate::Input(30u64)),
);
let c: Circuit<u64> = Circuit::new(g);
println!("{} = {}", c, c.evaluate());
}
$ cargo run
((12 + 20) * 30) = 960
$ ghci
Prelude> ((12 + 20) * 30)
960
Checks out!
I leave you, dear reader, with an exercise. Your exercise is to implement expression parsing by completing the following block:
use std::{error::Error, str::FromStr};
impl<T> FromStr for Circuit<T> {
type Err = Box<dyn Error>;
fn from_str(s: &str) -> Result<Self, Self::Err> {
todo!()
}
}
In a future article, I hope to extend this code to operate over arbitrary Galois fields
Did you know that there's a name for the expression we're matching on? In match x {}, x is called the "scrutinee"