<p>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.</p>
<p>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?</p>

<data-structures><abstract-syntax-tree>
Representing multiple alternative ASTs in one structure
CC BY-SA 4.0
2024-05-27T06:58:56.033Z
Is it possible that you’re thinking of [equality saturation](https://langdev.stackexchange.com/a/2817/861)?
Alexis King
CC BY-SA 4.0
2024-05-27T07:02:28.500Z
Yes, it was exactly that. Do you think my question is a useful pointer to that answer, or should I just delete it?
Mankka
CC BY-SA 4.0
2024-05-27T07:04:57.653Z
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.
Alexis King
<p><a href="https://people.csail.mit.edu/asolar/SynthesisCourse/Lecture6.htm" rel="nofollow noreferrer">Version space algebra</a> 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.</p>

CC BY-SA 4.0
2024-05-30T05:08:55.060Z
2024-05-30T05:08:55.060Z
Jay Lee
<p>Perhaps you’re thinking of <a href="https://langdev.stackexchange.com/a/2817/861">equality saturation</a>?</p>
<p>It doesn’t <em>quite</em> match the description in your question—it isn’t really about multiple AST “representations” <em>per se</em>, 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”.</p>

CC BY-SA 4.0
2024-05-27T07:08:17.043Z
2024-05-27T07:08:17.043Z
Alexis King
# Representing multiple alternative ASTs in one structure
Posted by: username_0 on 2024-05-27
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?
**Tags:** data-structures abstract-syntax-tree
> **Comments:**
> **username_1**: Is it possible that you’re thinking of [equality saturation](https://langdev.stackexchange.com/a/2817/861)?  
> **username_0**: Yes, it was exactly that. Do you think my question is a useful pointer to that answer, or should I just delete it?  
> **username_1**: 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.  
---
## 2 answers
### Answer by username_1 on 2024-05-27. Score: 4 | Accepted answer
Perhaps you’re thinking of [equality saturation](https://langdev.stackexchange.com/a/2817/861)?

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”.
---
### Answer by username_2 on 2024-05-30. Score: 0
[Version space algebra](https://people.csail.mit.edu/asolar/SynthesisCourse/Lecture6.htm) 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.
---
