matthewhammer
commented
9 years ago I've looked at the code a little. After first looking at list_to_rope_mergesort as a whole, I started to look at something simpler, using @kyleheadley's new feature to check for uniform output articulation.
I decided to study list_of_rope $$ rope_of_list in isolation. In particular, I wanted to ensure that this composition preserves the uniformity of names and articulations. There was already an experiment written for this test (Rope_iter_name) so I ran it with the debugging flags:
./_build/Source/test/experiments.native --experiment Rope_iter_name --n 100 --debug-flags --num-changes 0
You requested experiment: Rope_iter_name
0: Initial input: 3533; Name; Art => 4775; Name; Art => 501; Name; Art => 10234; Name; Art => 993; Name; Art => 1831; Name; Art => 7019; Name; Art => 11501; Name; Art => 8734; Name; Art => 6024; Name; Art => 10877; Name; Art => 12727; Name; Art => 9533; Name; Art => 114; Name; Art => 11543; Name; Art => 1845; Name; Art => 4721; Name; Art => 12024; Name; Art => 7059; Name; Art => 3792; Name; Art => 3891; Name; Art => 1748; Name; Art => 1994; Name; Art => 10018; Name; Art => 1021; Name; Art => 8450; Name; Art => 8017; Name; Art => 5413; Name; Art => 822; Name; Art => 12154; Name; Art => 5458; Name; Art => 5066; Name; Art => 6334; Name; Art => 3422; Name; Art => 9038; Name; Art => 11594; Name; Art => 3886; Name; Art => 3405; Name; Art => 7184; Name; Art => 1633; Name; Art => 9918; Name; Art => 1418; Name; Art => 2839; Name; Art => 6015; Name; Art => 1232; Name; Art => 11994; Name; Art => 5231; Name; Art => 4348; Name; Art => 9346; Name; Art => 4160; Name; Art => 2971; Name; Art => 8243; Name; Art => 2175; Name; Art => 2680; Name; Art => 5082; Name; Art => 12294; Name; Art => 11256; Name; Art => 10881; Name; Art => 2230; Name; Art => 3209; Name; Art => 11747; Name; Art => 4612; Name; Art => 5325; Name; Art => 7097; Name; Art => 9948; Name; Art => 10464; Name; Art => 10928; Name; Art => 4519; Name; Art => 11711; Name; Art => 550; Name; Art => 9410; Name; Art => 1401; Name; Art => 3681; Name; Art => 3918; Name; Art => 1828; Name; Art => 9498; Name; Art => 12361; Name; Art => 12122; Name; Art => 4940; Name; Art => 1517; Name; Art => 9998; Name; Art => 10956; Name; Art => 4195; Name; Art => 11448; Name; Art => 1438; Name; Art => 1879; Name; Art => 12535; Name; Art => 12038; Name; Art => 6273; Name; Art => 12408; Name; Art => 657; Name; Art => 394; Name; Art => 5522; Name; Art => 7668; Name; Art => 5003; Name; Art => 9562; Name; Art => 10536; Name; Art => 12754; Name; Art => 4190; Name; Art => 5552; Name; Art => Nil
0: Initial output: Name; Art => 3533; Name; Art => 4775; Name; Art => 501; Name; Art => 10234; Name; Art => 993; Name; Art => 1831; Name; Art => 7019; Name; Art => 11501; Name; Art => 8734; Name; Art => 6024; Name; Art => 10877; Name; Art => 12727; Name; Art => 9533; Name; Art => 114; Name; Art => 11543; Name; Art => 1845; Name; Art => 4721; Name; Art => 12024; Name; Art => 7059; Name; Art => 3792; Name; Art => 3891; Name; Art => 1748; Name; Art => 1994; Name; Art => 10018; Name; Art => 1021; Name; Art => 8450; Name; Art => 8017; Name; Art => 5413; Name; Art => 822; Name; Art => 12154; Name; Art => 5458; Name; Art => 5066; Name; Art => 6334; Name; Art => 3422; Name; Art => 9038; Name; Art => 11594; Name; Art => 3886; Name; Art => 3405; Name; Art => 7184; Name; Art => 1633; Name; Art => 9918; Name; Art => 1418; Name; Art => 2839; Name; Art => 6015; Name; Art => 1232; Name; Art => 11994; Name; Art => 5231; Name; Art => 4348; Name; Art => 9346; Name; Art => 4160; Name; Art => 2971; Name; Art => 8243; Name; Art => 2175; Name; Art => 2680; Name; Art => 5082; Name; Art => 12294; Name; Art => 11256; Name; Art => 10881; Name; Art => 2230; Name; Art => 3209; Name; Art => 11747; Name; Art => 4612; Name; Art => 5325; Name; Art => 7097; Name; Art => 9948; Name; Art => 10464; Name; Art => 10928; Name; Art => 4519; Name; Art => 11711; Name; Art => 550; Name; Art => 9410; Name; Art => 1401; Name; Art => 3681; Name; Art => 3918; Name; Art => 1828; Name; Art => 9498; Name; Art => 12361; Name; Art => 12122; Name; Art => 4940; Name; Art => 1517; Name; Art => 9998; Name; Art => 10956; Name; Art => 4195; Name; Art => 11448; Name; Art => 1438; Name; Art => 1879; Name; Art => 12535; Name; Art => 12038; Name; Art => 6273; Name; Art => 12408; Name; Art => 657; Name; Art => 394; Name; Art => 5522; Name; Art => 7668; Name; Art => 5003; Name; Art => 9562; Name; Art => 10536; Name; Art => 12754; Name; Art => 4190; Name; Art => 5552; Nil
----------------------------------------------------------------------------------
0:Rope_iter_name: Initial run: time:0.0033s (unit cost 0)
0:Rope_iter_name: Initial run: {dirty:0; clean:0; eval:301; create:301; tables:0}
--------------------
0:Rope_iter_name: No changes requested; Skipping interaction.As we can see, the output is articulated in (nearly) the same uniform manner as the input. The only difference is that the list begins with a Name and Art, rather than ending with one around the final Nil case. Despite this, the articulations are spaced uniformly, as in the input. Furthermore, this works out even though the code for rope_of_list and list_of_rope shuffles around Names and Arts and data elements into and out of the intermediate tree structure.
What does this mean for rope_mergesort? We can view rope_mergesort as a simpler variation on list_of_rope where we don't perform the logic of the list_merge steps.
Since I've confirmed that this simpler composition works, I suggest that something is going wrong in the list_merge logic, or how it's interacting with the other steps. That seems like the next natural place to focus. If possible, it'd be nice to run list_merge on two small random input lists, in isolation.
kyleheadley
We'd like it if mergesort, when given uniformly named and articulated input, will produce uniformly named and articulated output. Further, we'd like it if it roughly preserved whatever distribution of naming and articulation is found in the input.
As it stands, it doesn't work for uniform (fine-grained) names and articulation points. Instead, the initial output of the sort is articulated, and the later parts are not.
To reproduce this behavior, do this:
You'll see this (notice the two really long lines, and how they look different):
Kyle says: "You'll notice that the order changes from Cons-Name-Art to Name-Cons-Art. That's because of what I wrote in list_merge. I have no idea why I did it, and should probably change it back."
It's not yet clear to me if this discrepancy is related to this issue, or just some other (more minor) one.