DeepSpec / InteractionTrees

A Library for Representing Recursive and Impure Programs in Coq
MIT License
198 stars 50 forks source link

Remove uses of axioms #194

Closed Lysxia closed 3 years ago

Lysxia commented 3 years ago

Closes #72

There is one inversion lemma left which necessitates UIP, which is eqit_Vis_inv. It's actually not as useful as it seems (the tutorial example doesn't use it), but when you do run into it, it's very hard to do without (one can try using eqit_Vis_inv_weak instead).

There may be some way of strengthening eqitF so that eqit_Vis_inv is provable. That's Future Work™.


JMeq_eq/UIP is the main axiom we use. It is used by pcofix/etc. and more directly in various places.

Lysxia commented 3 years ago

The tutorial is now CLOSED UNDER THE GLOBAL CONTEXT, i.e., it does not use any axiom anymore.

The library still contains lemmas that depend on axioms (most notably eqit_Vis_inv). I'll leave it there because doing some stuff without it seems hard (using eqit_Vis_inv_weak instead). The library itself makes no use of that particular lemma at the moment though.

There may be some way of strengthening eqitF so that eqit_Vis_inv is provable.