Adding optimisations to case classes / extractors and structural equality

I'll make a guess here and assume your optimisations are the pruning
of the Boolean expression tree - that's what I can see in the
extractor apply() for Not.

As a suggestion, why not go back to the original case class design and
add an abstract method to Expr that tidies up 'this', returning a new
Expr. You can implement this method in each case class, which would
keep the logic distributed in each kind of expression (which I think
is what you want). Each implementation would contain the same code as
you would have in each of your current extractors.

You can go a step further and define an additional single extractor
object that calls this method on its input and returns the result.

That way, you go back to having the compiler-generated equality
implementation.

Would this work for you?

Gerard

On 1/6/2012 15:28, GerardMurphy wrote:
> I'll make a guess here and assume your optimisations are the pruning
> of the Boolean expression tree - that's what I can see in the
> extractor apply() for Not.
Indeed, and with "small" optimisations I meant sort of local
simplifications that only consider the current node and its direct
children, as in the case of Not.

> As a suggestion, why not go back to the original case class design and
> add an abstract method to Expr that tidies up 'this', returning a new
> Expr. You can implement this method in each case class, which would
> keep the logic distributed in each kind of expression (which I think
> is what you want). Each implementation would contain the same code as
> you would have in each of your current extractors.

Is this what you have in mind?

trait Expr { def simplify: Expr }

case class Not(e: Expr) extends Expr {
def simplify = { /* match on e */ }

Here the simplification has to be triggered manually, which is what I'd
like to avoid because it implies changes at client side.

> You can go a step further and define an additional single extractor
> object that calls this method on its input and returns the result.
I don't quite understand, could you give an illustrating example?

Thanks,
Malte

> > As a suggestion, why not go back to the original case class design and
> > add an abstract method to Expr that tidies up 'this', returning a new
> > Expr. You can implement this method in each case class, which would
> > keep the logic distributed in each kind of expression (which I think
> > is what you want). Each implementation would contain the same code as
> > you would have in each of your current extractors.
>
> Is this what you have in mind?
>
>   trait Expr { def simplify: Expr }
>
>   case class Not(e: Expr) extends Expr {
>     def simplify = { /* match on e */ }
>
> Here the simplification has to be triggered manually, which is what I'd
> like to avoid because it implies changes at client side.

Yes, we're on the same page.

>
> > You can go a step further and define an additional single extractor
> > object that calls this method on its input and returns the result.
>
> I don't quite understand, could you give an illustrating example?
>

Hmm - I was hoping that something along the lines of:

  object Simplified { 
    def apply(e: Expr) = e simplify
    }
Would help, but this would still involve cutover of client code - but
at least it could sit more naturally inline within any existing
pattern matching in the client code.

So:
e match {
case Simplified(And(Not(e1), e2)) => blah
case Simplified(Or(e1, _)) => whatever
}
On reflection, this is daft - why not use:

e simplify match {
case And(Not(e1), e2) => blah
case Or(e1, _) => whatever
}
… which is back to square one.
Musing a bit more ….

If you've got to keep client code the same (including the type
signatures), then maybe you can mix and match.
Expr itself would follow the same design as what you started with -
based on extractors that do simplification. The twist is to define
these extractors only for the 'compound' expressions - Not, And, Or.
True and False are leaf values and remain as case classes - note that
I'm fudging around any true variable terms and assuming for now that
it's just constants that you make your expressions out of.
Then your compound extractors can simplify on the fly down to the
basic leaf values, which keep their compiler-generated equality.
As for the extractors, you can delegate their equality down to the
simplified versions which are guaranteed to be leaf values.

As an aside, I remember something very much like this in Expert F# -
this also deals with variable leaf terms and hash-consing. It used
active patterns which you probably know are the F# equivalent of
extractors - might be worth taking a look.
Regards,
Gerard