[Agda] An Agda proof of the Church-Rosser theorem

roconnor at theorem.ca roconnor at theorem.ca
Tue Aug 11 21:18:12 CEST 2015


The non-uniform inductive types I use make it more difficult to define 
recursion schemes.  I seem to recall a paper on how to define recursion 
schemes for theses sorts of types (probably written by Bird) in some 
cases.  I haven't reacquanted myself with that paper yet mostly because I 
don't define that many recursive functions.  Most of the work is spent 
doing inductive proofs proving equality of compositions of those few 
recursive functions, and I'm not sure I know any information on to do that 
generically for these sorts of non-uniform inductive types.

On Mon, 10 Aug 2015, Andrea Vezzosi wrote:

> Hi Russel,
>
> I have not read the code fully, but I can see that you also got
> trapped into writing loads of boilerplate code to do proofs that are
> mostly induction + congruence.
>
> I'd be really interested in figuring out how to avoid these parts.
>
> If we are trying to be very structured there would be something like
> generic traversals from "scrap your boilerplate" haskell libraries,
> with provided reasoning principles that allow proofs to only speak
> about the interesting cases.
>
> However it might be more realistic to define a tactic that just tries
> to use congruence and otherwise fails, but still I don't know what the
> interface would be for handling cases where that does not work without
> having to write out the whole proof instead.
>
> Cheers,
> Andrea
>
> On Tue, Aug 4, 2015 at 10:38 PM,  <roconnor at theorem.ca> wrote:
>> URL: http://hub.darcs.net/roconnor/STLC/browse
>>
>> This is my first development in Agda. I'm interested in getting some
>> feedback on this work of any sort, including but not limited to
>>
>>  * Abstractions in the standard library that I could take advantage of.
>>  * Standard naming conventions I should be using.
>>  * Where I should or shouldn't be using implicit arguments.
>>  * Better use of unicode operators.
>>  * Better argument orders.
>>  * Should I be using equational reasoning?
>>  * Ideas on how to use recursion schemes to simplify functions taking Terms.
>> Recursions schemes for dependent families are kinda tricky.
>>
>> --
>> Russell O'Connor                                      <http://r6.ca/>
>> ``All talk about `theft,''' the general counsel of the American Graphophone
>> Company wrote, ``is the merest claptrap, for there exists no property in
>> ideas musical, literary or artistic, except as defined by statute.''
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''


More information about the Agda mailing list