pipette
ESEspañol

Associativity and Commutativity in Equality Saturation

Tarik Rosin, Marcel Ullrich, Sebastian Hack

Preprint

In the authors' words

Equality saturation is a promising technique for program optimization which sidesteps the phase ordering problem. However, current e-graph implementations grow exponentially large, even for simple examples. Many practical applications involve associative and commutative (AC) operators. We present an extension of relational e-matching that handles AC operators natively by storing terms as multisets. Preliminary results show that equality saturation modulo AC uses asymptotically less memory in certain cases.

Main resultLimitation the authors admit

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.