egraphs-good / extraction-gym

benchmarking e-graph extraction
MIT License
27 stars 16 forks source link

ExtractionResult is not flexible enough for some extractors #36

Open oflatt opened 5 months ago

oflatt commented 5 months ago

Some extractors are non-local: for different root eclasses, they extract different sub-terms for the same eclass. However, the current extraction gym does not allow picking two different nodes for the same eclass.

As a result, the global_greedy_dag extractor sometimes extracts cycles because it chooses conflicting nodes when extracting different roots.

oflatt commented 5 months ago

I have a simple solution: let's just allow a single root per benchmark. If you want to benchmark something with multiple roots, just create multiple benchmarks

oflatt commented 5 months ago

Perhaps there's a more general problem with cycles and DAG extractors- if you allow them to extract a particular term, the problem goes away. However, if they must pick a single term per eclass cycles can occur