Change condenser to normalize algebraic expressions

powdr-labs / powdr

A modular stack for zkVMs, with a focus on productivity, security and performance.

Apache License 2.0

387 stars 80 forks source link

Change condenser to normalize algebraic expressions #1110

Open chriseth opened 7 months ago

chriseth commented 7 months ago

The condenser should "normalize" algebraic expressions:

It should perform computations on constants (done in the evaluator in a pending PR)
It should pull ' operators across linear operators to the inside until they reach a column It should also be the responsibility of this component to detect double applications of ' and so on.

chriseth commented 5 months ago

Just a quick thought: If we implement elements of an extension field as a user-defined type, then maybe this normalization could be a trait on the extension field type which then returns an expr (or a pair of exprs).

We could also implement the whole normalization described in the issue here inside pil.

So maybe in the end, the type we want to have at constraint / statement level is anything that implements

trait ToConstraint<T> {
  to_constraint: T -> constr[],
}