binius_m3/builder/
expr.rs

1// Copyright 2025 Irreducible Inc.
2
3use binius_field::{ExtensionField, Field, TowerField};
4use binius_math::ArithExpr;
5use getset::{CopyGetters, Getters};
6
7use super::{column::Col, table::TableId};
8
9/// A constraint that the evaluation of an expression over a table is zero at every row.
10#[derive(Debug)]
11pub struct ZeroConstraint<F: Field> {
12	pub name: String,
13	pub expr: ArithExpr<F>,
14}
15
16/// A type representing an arithmetic expression composed over some table columns.
17///
18/// If the expression degree is 1, then it is a linear expression.
19#[derive(Debug, Clone, Getters, CopyGetters)]
20pub struct Expr<F: TowerField, const V: usize> {
21	#[get_copy = "pub"]
22	table_id: TableId,
23	#[get = "pub"]
24	expr: ArithExpr<F>,
25}
26
27impl<F: TowerField, const V: usize> Expr<F, V> {
28	/// Polynomial degree of the arithmetic expression.
29	pub fn degree(&self) -> usize {
30		self.expr.degree()
31	}
32
33	/// Exponentiate the expression by a constant power.
34	pub fn pow(self, exp: u64) -> Self {
35		Self {
36			table_id: self.table_id,
37			expr: self.expr.pow(exp),
38		}
39	}
40}
41
42impl<F: TowerField, const V: usize> From<Col<F, V>> for Expr<F, V> {
43	fn from(value: Col<F, V>) -> Self {
44		Expr {
45			table_id: value.table_id,
46			expr: ArithExpr::Var(value.partition_index),
47		}
48	}
49}
50
51impl<F: TowerField, const V: usize> std::ops::Add<Self> for Col<F, V> {
52	type Output = Expr<F, V>;
53
54	fn add(self, rhs: Self) -> Self::Output {
55		assert_eq!(self.table_id, rhs.table_id);
56
57		let lhs_expr = ArithExpr::Var(self.partition_index);
58		let rhs_expr = ArithExpr::Var(rhs.partition_index);
59
60		Expr {
61			table_id: self.table_id,
62			expr: lhs_expr + rhs_expr,
63		}
64	}
65}
66
67impl<F: TowerField, const V: usize> std::ops::Add<Col<F, V>> for Expr<F, V> {
68	type Output = Expr<F, V>;
69
70	fn add(self, rhs: Col<F, V>) -> Self::Output {
71		assert_eq!(self.table_id, rhs.table_id);
72
73		let rhs_expr = ArithExpr::Var(rhs.partition_index);
74		Expr {
75			table_id: self.table_id,
76			expr: self.expr + rhs_expr,
77		}
78	}
79}
80
81impl<F: TowerField, const V: usize> std::ops::Add<Expr<F, V>> for Expr<F, V> {
82	type Output = Expr<F, V>;
83
84	fn add(self, rhs: Expr<F, V>) -> Self::Output {
85		assert_eq!(self.table_id, rhs.table_id);
86		Expr {
87			table_id: self.table_id,
88			expr: self.expr + rhs.expr,
89		}
90	}
91}
92
93impl<F: TowerField, const V: usize> std::ops::Add<F> for Expr<F, V> {
94	type Output = Expr<F, V>;
95
96	fn add(self, rhs: F) -> Self::Output {
97		Expr {
98			table_id: self.table_id,
99			expr: self.expr + ArithExpr::Const(rhs),
100		}
101	}
102}
103
104impl<F: TowerField, const V: usize> std::ops::Add<Expr<F, V>> for Col<F, V> {
105	type Output = Expr<F, V>;
106
107	fn add(self, rhs: Expr<F, V>) -> Self::Output {
108		Expr::from(self) + rhs
109	}
110}
111
112impl<F: TowerField, const V: usize> std::ops::Add<F> for Col<F, V> {
113	type Output = Expr<F, V>;
114
115	fn add(self, rhs: F) -> Self::Output {
116		Expr::from(self) + rhs
117	}
118}
119
120impl<F: TowerField, const V: usize> std::ops::Sub<Self> for Col<F, V> {
121	type Output = Expr<F, V>;
122
123	fn sub(self, rhs: Self) -> Self::Output {
124		assert_eq!(self.table_id, rhs.table_id);
125		let lhs_expr = ArithExpr::Var(self.partition_index);
126		let rhs_expr = ArithExpr::Var(rhs.partition_index);
127
128		Expr {
129			table_id: self.table_id,
130			expr: lhs_expr - rhs_expr,
131		}
132	}
133}
134
135impl<F: TowerField, const V: usize> std::ops::Sub<Col<F, V>> for Expr<F, V> {
136	type Output = Expr<F, V>;
137
138	fn sub(self, rhs: Col<F, V>) -> Self::Output {
139		self - Expr::from(rhs)
140	}
141}
142
143impl<F: TowerField, const V: usize> std::ops::Sub<Expr<F, V>> for Expr<F, V> {
144	type Output = Expr<F, V>;
145
146	fn sub(self, rhs: Expr<F, V>) -> Self::Output {
147		assert_eq!(self.table_id, rhs.table_id);
148		Expr {
149			table_id: self.table_id,
150			expr: self.expr - rhs.expr,
151		}
152	}
153}
154
155impl<F: TowerField, const V: usize> std::ops::Sub<F> for Expr<F, V> {
156	type Output = Expr<F, V>;
157
158	fn sub(self, rhs: F) -> Self::Output {
159		Expr {
160			table_id: self.table_id,
161			expr: self.expr - ArithExpr::Const(rhs),
162		}
163	}
164}
165
166impl<F: TowerField, const V: usize> std::ops::Sub<Expr<F, V>> for Col<F, V> {
167	type Output = Expr<F, V>;
168
169	fn sub(self, rhs: Expr<F, V>) -> Self::Output {
170		Expr::from(self) - rhs
171	}
172}
173
174impl<F: TowerField, const V: usize> std::ops::Sub<F> for Col<F, V> {
175	type Output = Expr<F, V>;
176
177	fn sub(self, rhs: F) -> Self::Output {
178		Expr::from(self) - rhs
179	}
180}
181
182impl<F: TowerField, const V: usize> std::ops::Mul<Self> for Col<F, V> {
183	type Output = Expr<F, V>;
184
185	fn mul(self, rhs: Self) -> Self::Output {
186		Expr::from(self) * Expr::from(rhs)
187	}
188}
189
190impl<F: TowerField, const V: usize> std::ops::Mul<Col<F, V>> for Expr<F, V> {
191	type Output = Expr<F, V>;
192
193	fn mul(self, rhs: Col<F, V>) -> Self::Output {
194		self * Expr::from(rhs)
195	}
196}
197
198impl<F: TowerField, const V: usize> std::ops::Mul<Expr<F, V>> for Expr<F, V> {
199	type Output = Expr<F, V>;
200
201	fn mul(self, rhs: Expr<F, V>) -> Self::Output {
202		assert_eq!(self.table_id, rhs.table_id);
203		Expr {
204			table_id: self.table_id,
205			expr: self.expr * rhs.expr,
206		}
207	}
208}
209
210impl<F: TowerField, const V: usize> std::ops::Mul<F> for Expr<F, V> {
211	type Output = Expr<F, V>;
212
213	fn mul(self, rhs: F) -> Self::Output {
214		Expr {
215			table_id: self.table_id,
216			expr: self.expr * ArithExpr::Const(rhs),
217		}
218	}
219}
220
221impl<F: TowerField, const V: usize> std::ops::Mul<Expr<F, V>> for Col<F, V> {
222	type Output = Expr<F, V>;
223
224	fn mul(self, rhs: Expr<F, V>) -> Self::Output {
225		Expr::from(self) * rhs
226	}
227}
228
229impl<F: TowerField, const V: usize> std::ops::Mul<F> for Col<F, V> {
230	type Output = Expr<F, V>;
231
232	fn mul(self, rhs: F) -> Self::Output {
233		Expr::from(self) * rhs
234	}
235}
236
237/// Upcast an expression from a subfield to an extension field.
238pub fn upcast_expr<F, FSub, const V: usize>(expr: Expr<FSub, V>) -> Expr<F, V>
239where
240	FSub: TowerField,
241	F: TowerField + ExtensionField<FSub>,
242{
243	let Expr { table_id, expr } = expr;
244	Expr {
245		table_id,
246		expr: expr.convert_field(),
247	}
248}
249
250/// This exists only to implement Display for ArithExpr with named variables.
251pub struct ArithExprNamedVars<'a, F: TowerField>(pub &'a ArithExpr<F>, pub &'a [String]);
252
253impl<F: TowerField> std::fmt::Display for ArithExprNamedVars<'_, F> {
254	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
255		let Self(expr, names) = self;
256		match expr {
257			ArithExpr::Const(v) => write!(f, "{v}"),
258			ArithExpr::Var(i) => write!(f, "{}", names[*i]),
259			ArithExpr::Add(x, y) => {
260				write!(f, "{} + {}", self.expr(x), self.expr(y))
261			}
262			ArithExpr::Mul(x, y) => {
263				write!(f, "({}) * ({})", self.expr(x), self.expr(y))
264			}
265			ArithExpr::Pow(x, p) => {
266				write!(f, "({})^{p}", self.expr(x))
267			}
268		}
269	}
270}
271
272impl<'a, F: TowerField> ArithExprNamedVars<'a, F> {
273	fn expr(&self, expr: &'a ArithExpr<F>) -> Self {
274		Self(expr, self.1)
275	}
276}
binius_m3/builder/expr.rs

binius_m3/builder/
expr.rs
