Sometime during the past year I read (possibly on SO/SE) about a topic that sounded interesting. Now I would like to pick it up but I can't find it again. My memory is somewhat vague, I'm afraid.

I think it was about compilation, how to represent multiple possible ASTs in one data structure. In this way one does not have to commit to a single representation, but can perform operations on all possible representations. Or something similar. Does that sound familiar?

  • 1
    $\begingroup$ Is it possible that you’re thinking of equality saturation? $\endgroup$
    – Alexis King
    Commented May 27 at 6:58
  • $\begingroup$ Yes, it was exactly that. Do you think my question is a useful pointer to that answer, or should I just delete it? $\endgroup$
    – Mankka
    Commented May 27 at 7:02
  • $\begingroup$ I think it’s a little ambiguous based on the question text alone, but I think it could probably be a useful signpost question for people coming from Google. I’ll write a short answer. $\endgroup$
    – Alexis King
    Commented May 27 at 7:04

2 Answers 2


Perhaps you’re thinking of equality saturation?

It doesn’t quite match the description in your question—it isn’t really about multiple AST “representations” per se, but rather multiple terms with equivalent denotations—but it is very much in the spirit of your description. In particular, techniques that use equality saturation do effectively “perform operations on all possible representations”.


Version space algebra might also be what you were looking for. It is used to efficiently represent program spaces, and primarily used in the field of program synthesis AFAIK.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .