Re: [isabelle] Code generation for reverse sorting

Hi Florian,

I think there is one misperception concerning sort_key â it is not
parametrized by an order, but by a morphism:

"sort_key" :: "('a â 'b) â 'a list â 'a list"

The morphism is not the parametrisation I was referring to. I meant the implicit parametrisation with the order coming from the type class linorder. Obviously, this parameter can only be seen by looking at the foundational constant for sort_key.

IMHO the best way to continue from here is to develope a *algorithmic*
theory on sorting, which is specifically designed for executability.  I
guess this should follow the spirit of the Isabelle collection
framework.  The sort in List.thy then could stand as it is.
I am also in favour of separating reasoning and code generation. But ultimately, you want to connect the two kinds of sorting.


Am 05.10.2015 um 09:17 schrieb Andreas Lochbihler:
Hi Christian,

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

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

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 List.sort.

2. Define a type 'a linorder of linear orders using typedef and an

   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 than List.sort_key.

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:
Dear all,

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 MHonArc.