[imp-dev] Another design issue: annotations

[Jurgen Vinju <Jurgen.Vinju@xxxxxx>]

Hi imps,

People, i.e. Paul Klint and Tijs van der Storm, are starting to use the annotations feature of pdb.values and
found a design issue. After discussing with them it is logical to change one important thing. Here's the rationale.
It's an FYI, so don't bother if you're not interested in the nitty gritty details of the semantics of pdb.values. 

Pre-notes: 
  * annotations were recently restricted to trees (constructors) for lack of use case on the other value types
    and for lack of a proper semantics that prevents implicit loss of annotations. I.e. when two annotated sets
    are unioned, where do the annotations go? Same for addition on annotated integers etc. So, no annotations
    on anything but structured adt's (trees).
  * having annotations introduces two notations of equality: ignoring and not ignoring annotations. These two
    notions necessarily infect all other data-types since trees can be nested in sets, tuples, etc.
  * We are not talking about the Object.equals() method now which is an implementation detail, rather about
    IValue.isEqual() which implements logical equality between two values.
 
The issue on the table is that one needs to choose which form of equality is default (in particular for the semantics of set
union and set intersection). The current implementation(s) of pdb.values use the not-ignoring version of equality.
This is good for efficiency in some ways (but this is not a general fact) and it makes set union and intersection
commutative as they should be. 

But: using not-ignoring equality is not good! Since annotations are designed to be ignorable, now sets
don't ignore them and so you as a user of the API can't ignore them at all - if you catch my drift. 
As Paul Klint noticed: this directly contradicts the rationale for having annotations. If equality does
not ignore annotations, they just can't be ignored altogether and they are useless.

Ergo, equality in general (the IValue.isEqual()) should ignore annotations. We need to change this in the (already two!) 
implementations of pdb.values. It will only affect clients that actually make use of annotations already. As far
as I know this is the implementation of the Rascal interpreter and nothing else. Please correct me if I'm wrong.

It's trivial to see what is good about this decision, but it has a slight side-effect. Suppose we write equals ignoring annotations as ==
and equals not ignoring annotations as =@=, then:
  - For every set A and B: A union B == B union A
  - But *not* for every set A and B: A union B =@= B union A
  - Similarly for intersection.

The question is, if two elements have different annotations but are otherwise equal, which element ends up in the result of a union/intersection?

Therefore, the plan is to:
  * rename the current isEqual() method to isEqualIncludingAnnotations()
  * copy this method to isEqual() and remove the check for annotation equality.
  * in the computation of intersection and union, always the element from the "right" set is entered in the result.
    So, for A union B (read A.union(B), the elements of B will override the elements in A.
    This is just a documented convention, which is arbitrary from an abstract point of view, but is the most practical on the implementation level.

* The new isEqual method will make annotations ignorable
* The isEqualIncludingAnnotations provides a method of not ignoring annotations, next to getAllAnnotations() and {get,set}Annotation() of course.
* The right biased union/intersection documents exactly how annotations might be lost in sets when they are ignored.

Cheers,

Jurgen