Re: [isabelle] Code generation for reverse sorting
Here are my thoughts about List.sort & friends:
a) The first problem with List.sort and friends is that they are defined in the type class
linorder, although their definitions could be made as well in the type class ord. Three
years ago (2ada2be850cb), I have moved all the operations for red-black trees (RBT) into
the linorder type class, precisely because I wanted to use them with other ordering
relations. Ideally, the same should be done for List.sort and friends.
For the time being, you can still avoid some of the overheads by using the foundational
constant linorder.sort_key, which takes the order as an additional argument. So, you can
pass in the dual order. With a single interpretation for the dual order, you should get
all the theorems you need. You can even define an abbreviation for it:
interpretation dual!: linorder "op â" "op > :: _ :: linorder â _" by(rule dual_linorder)
abbreviation "rsort == linorder.sort_key op â (Îx. x)"
Unfortunately, code generation does not work out of the box, because the code setup has
only been done for the type-class based instance. If List.sort was defined in the type
class ord, one could simply re-declare the code equations (as I did for the RBT operations
in my AFP entry Containers). Alternatively, you can prove that sort & friends are
parametric (as Peter did for RBT operations in his AFP entry Collections) and exploit
parametricity like he does, but my feeling is that this again requires unconditional
equations, i.e., a definition in ord.
b) The second problem is that we want to implement List.sort with different algorithms
during code generation. For linear orders, this is no problem, because the result is
unique. However, if we pass in a non-linear order, the outcome might depend on the
algorithm. Thus, we can only do program refinement for linear orders. In that view, even
if we move List.sort to the type class ord, we still have problems, because we cannot
prove the code equations for arbitrary ordering relations any more.
Ideally, we should separate the proving part from the code generation part. AFAICS, the
following should work.
1. Move List.sort and friends to type class ord. For ease of use and compatibility, we can
add sign constraints such that type inference infers the linorder sort constraints for
2. Define a type 'a linorder of linear orders using typedef and an embedding
linorder_of :: "'a :: linorder itself => 'a linorder"
3. Define operations for sorting lists that are parametrised with the order from the type
'a linorder. Prove equations like "List.sort_key == sort_key_impl TYPE('a)".
4. Adapt all the implementations for sorting such that they refine sort_key_impl rather
Apart from sorting, such a setup could be used for further improvements to the generated
code. For example, one could refine the type 'a linorder to provide a comparator instead
of a comparison operation.
I guess such a change requires quite a lot of work to be carried out on the whole
repository. At the moment, I do not have the time to carry all this out, but if the issue
is pressing for you, you might want to try it yourself. But before you start, we should
also ask Florian on his opinion.
On 03/10/15 21:59, Christian Sternagel wrote:
for those of you who do not regularly check stackoverflow but might have
an answer to my question there (yes I am looking at you Florian ;) ) I'm
brazenly posting the link to my question here
In short, my question is: What is the easiest way to generate code for a
sorting algorithm that sorts its argument in reverse order, while
building on top of the existing List.sort?
This archive was generated by a fusion of
Pipermail (Mailman edition) and