Defining a language with AST

[LegNeato]

Hello! Cool lib. I'm looking to use egg to transform some source code I have. I have the AST parsed in Rust. How do I take the AST and use it with egg? Will it be easier parse the source with egg instead?

Sorry, I am a bit lost even after looking at the examples.

[mwillsey]

Thanks! egg requires pretty much total control over your AST, since it needs to be able to put stuff in the e-graph. So it's pretty common to have an "algebraic" version of your AST that you'll work with and and egg version that's flatter.

So yours might look like

enum Expr {
  Add(Box<Self>, Box<Self>),
  Num(i32),
}

But the egg version will look like

define_language! {
    enum SimpleLanguage {
        "+" = Add([Id; 2]),
        Num(i32),
    }
}

where basically every instance of recursion in the AST is replaced with an Id.

[LegNeato]

Ah ok, that's what I suspected but thought there might be a trait or conversion I could implement on my ast

[mwillsey]

I would love to have such a trait, but I have tried and failed to design one that does what you describe. I think we need higher kinded types or something.