Make sure the equality comparison only depends on things that affect functionality -- i.e. it will declare any functionally equivalent programs equal even they use a different nameset for variables or something.

(Yes, I know that's reducible to the halting problem; in practice, you'll use a computable, polynomial time approximation for it that will inevitably have to throw out equivalent programs that are too complex or otherwise be too 'clever'.)