Best way to collapse nested language

[genos]

Hello all!

First off, thanks very much for egg, it's really interesting.

I'm trying to use egg to, among other things, flatten out a potentially nested structure, but I'm having trouble figuring out the best way to do it. Simplifying greatly from my intended application, suppose we've got the following language.

define_language! {
    pub enum Nested {
        One(Symbol),
        "many" = Many(Vec<Id>),
    }
}

What's the best way to flatten a potential multi-layered Many?¹ Would it go in an Analysis, or in rewrite rules? For example, I'd ultimately like something like

(many (many (many 0)) 1 2 (many 3) (many (many 4) 5 (many 6 7 8)))  ⇒ (many 0 1 2 3 4 5 6 7 8)

But I'm having trouble figuring out how to pull this off:

• I'd imagine the ideal place to do this would be in an Analysis::make, but I can't see how to do that without cloning a bunch?
• I haven't been able to do it via rewrite!, as I'm not sure how to match on the vector of Ids instead of pattern matching on a singleton

Any guidance would be greatly appreciated. Thanks again!

Footnotes

1. I'm thinking of something similar to the Foldable instance for rose trees in Haskell if that's familiar to anyone. ↩

[mwillsey]

Hi there!

Yes, that is definitely one of the downsides of the variadic patterns: you can't write a pattern than captures all of them. You could maybe try refactoring to a sort of "cons list" approach, but I'm not sure if that would work in your domain. I think you could definitely do it in an analysis. I wouldn't fear cloning tooooo much, after all, you have to materialize the list somewhere. Perhaps a clever use of Rc or something a persistent vector could help.

[genos]

Thanks for getting back to me so quickly! The cons list and immutable structures are nice ideas, thanks.

What I'm actually trying to do (which the above example grossly oversimplifies) is rewrite programs of Quantum gates, something like:

egg::define_language! {
    pub enum GateSet {
        Angle(OrderedFloat(f32)),
        "+" = Add([Id; 2]),
        "RX" = RX([Id; 2]),
        "RZ" = RZ([Id; 2]),
        "H" = H(Id),
        "circuit" = Circuit(Vec<Id>),
        Symbol(egg::Symbol),
    }
}

Here a single gate might first be expanded to a collection of multiple gates applied in a row; for example, the hardware involved might decompose a Hadamard gate as a series of rotations:

rw!("h"; "(H ?q)" => "(circuit (RZ pi/2 ?q) (RX pi/2 ?q) (RZ pi/2 ?q))")

I'd also like the entire collection gets reduced by a number of rules, like "two consecutive RZs on the same qubit can be simplified to a single RZ with the sum of their angles." like

rw!("rz-repeated"; "(circuit (RZ ?a1 ?q) (RZ ?a2 ?q))" => "(circuit (RZ (+ ?a1 ?a2) ?q))")

Rubber-ducking it a bit, would it make sense to split the stages in two? Handle the expansion to a native gate set separately, then use egg to simplify the larger chain, perhaps in a cons list structure; the former is a bit finicky/hardware specific, while the latter bit is essentially just group theory.

[mwillsey]

Hmm, I'm not sure, potentially! I'm not really sure what a "circuit" is in this context; this is definitely outside my wheelhouse. If it really is just a list of things, and you only need to match on adjacent neighbors, I think cons list might really be helpful here.

[genos]

Oh! Since “circuits” here are lists of instructions to be applied in sequential order and gate operations form a group (sweeping details under the rug), I could have a language entry

“seq” = Seq([Id; 2])

and add associativity as part of the rewrite rules.

…or was that what you had in mind when mentioning cons lists 😅

Thanks so much again for your help and for the library!

[mwillsey]

Sure thing! One note: I would watch out for associativity, as it can quickly explode the e-graph if you aren't careful. Maybe your usecase will just work; but it's something to watch out for!

…

On Thu, May 18, 2023 at 5:36 PM Graham ***@***.***> wrote: Oh! Since “circuits” are lists of instructions to be applied in order and gate operations form a group (sweeping details under the rug), I could have a language entry “seq” = Seq([Id; 2]) and add associativity as part of the rewrite rules. Thanks so much again for your help and for the library! — Reply to this email directly, view it on GitHub <#260 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AANTPTGAV6YAYERB4XYR25TXG26A5ANCNFSM6AAAAAAYG6UBGU> . You are receiving this because you commented.Message ID: ***@***.***>