Bug: Standardization issues

[casey-c]

P ↔ Q

 ┌─────────┐ ┌─────────┐ 
 │   ┌───┐ │ │   ┌───┐ │ 
 │ P │ Q │ │ │ Q │ P │ │ 
 │   └───┘ │ │   └───┘ │ 
 └─────────┘ └─────────┘ 

...has some issues with the auto-formatting. Specifically, it isn't outputting the exact same format that egg-parser wants (which is supposed to be the de-facto standard).

egg is giving the following output string:
2 21PQ 21QP

while egg-parser has the two main cuts swapped:
2 21QP 21PQ.

I think in this case I might agree with egg's output over egg-parser. The above graph to me looks better than what egg-parser wants, which is:

 ┌─────────┐ ┌─────────┐ 
 │   ┌───┐ │ │   ┌───┐ │ 
 │ Q │ P │ │ │ P │ Q │ │ 
 │   └───┘ │ │   └───┘ │ 
 └─────────┘ └─────────┘ 

In that case, I think this is more of a bug for egg-parser. I'll try and see what's going on and will return when I've come up with a fix to coordinate the two applications.

[casey-c]

I wasted about 7 hours on this today by rewriting egg-parser from scratch using some of the techniques I developed when working with egg. However, I'm come to the realization that perhaps the original egg-parser was correct all along.

Consider the following input:

31A1C1B

When "sorted" by the standardization process, we really come down to a list of three child cuts, and we have to decide an ordering for them. This is what egg parser creates, based on it's alphabetization process:

1A
1B
1C

Clearly, "1A" comes before "1B" in alphabetical order, and both come before "1C". So when egg-parser then prints out its output, it (by design) reverses this ordering so that it can be parsed easily later. Its output then is the following string:

31C1B1A

When we look at the original issue, the two strings we are comparing are

21PQ
21QP

This above ordering (which is what egg prints out as the final string) is actually the proper alphabetization. However, we must reverse the order for the final string, as required by the standardization process. In this case, 221QP21PQ was correct all along, and EGG was wrong.

Looking at it further broken down, we can sort of identify the key issue. This lies in the construction of the sub components. For example, 21PQ is constructed of two parts:

Q
1P

The standardization algorithm will sort all the letters (in this case it's the single-item set {Q} ), and then independently sort all the cuts (again, a single-item set {1P} ). Then we list the letters first, and the cuts last. So the ordering is as shown above, Q then 1P. Finally, to get the output string we reverse the order again.

This is all well and good at this lower level, but things get sketchy when this propagates up the tree. At the parent level, the third letter in each string is really where the alphabetization fires:

  v
21PQ
21QP
  ^

We're not comparing the outer letters (like we probably should), but we end up comparing the contents of the cuts first!

So the solution? Read right to left! This is a relatively simple change. I'll update egg-parser first to see how it fares and then go from there.

UPDATE: (this is like 5 minutes later after starting to write this)

• I just updated the code for the comparator to read from right to left instead. I also found another issue involving sizes. So I made it such that smaller cuts are given higher priority (i.e. closer to "A" if you think alphabetically). With this update, I think egg-parser might be finally okay.

• I now need to port the changes back into EGG (doing so will close this issue), but after that standardization should be cross app compatible and we should really be cooking.