coq-club AT inria.fr
Subject: The Coq mailing list
List archive
- From: Stefan Monnier <monnier AT iro.umontreal.ca>
- To: Benjamin Pierce <bcpierce AT cis.upenn.edu>
- Cc: coq-club AT pauillac.inria.fr, Martin Hofmann <mhofmann AT TCS.IFI.LMU.DE>
- Subject: Re: [Coq-Club] Strengthening the definitional equality on types?
- Date: Wed, 05 Aug 2009 10:38:26 -0400
- List-archive: <http://pauillac.inria.fr/pipermail/coq-club/>
> What to do? We've seen the discussion of John Major equality in
> CoqArt... is this our only hope, or is there a lighter way?
I see other people have already solved your problem, but to get back to
the title of your email, I also wonder: wouldn't it be possible to
strengthen the definitional equality so that your code is accepted
as is.
It seems that what is required here is to extend CIC with the an η-rule
for inductive definitions plus some kind of "match-associativity"
(analogous to the let-associativity rule that says that
let x₁ = let x₂ = e₁ in e₂ in e₃ ≡ let x₂ = e₁ in let x₁ = e₂ in e₃
assuming x₂∉fv(e₁)).
I.e.:
swap (swap d)
≡ match (match d with R => L | L => R end) with R => L | L => R end
≡ match d with R => match L with R => L | L => R end
| L => match R with R => L | L => R end
end
≡ match d with R => R | L => L end
≡ d
the first ≡ is by unfolding the definition, the second is by
match-associativity, the third by the usual reduction rules, the fourth
by η.
Since CIC's consistency is not broken by η applied to the function
space, maybe it can also sustain η applied to the inductive
definitions space (tho you'd probably get into trouble with the issue
of the strong elimination of large inductive definitions).
OTOH, adding a form of match-associativity seems a lot more
far-fetched :-(
Too bad, because it would be handy in various circumstances.
Stefan
- [Coq-Club] Strengthening the definitional equality on types?, Benjamin Pierce
- Re: [Coq-Club] Strengthening the definitional equality on types?, Adam Chlipala
- Re: [Coq-Club] Strengthening the definitional equality on types?, Arnaud Spiwack
- Re: [Coq-Club] Strengthening the definitional equality on types?, Arnaud Spiwack
- Re: [Coq-Club] Strengthening the definitional equality on types?, AUGER Cedric
- Re: [Coq-Club] Strengthening the definitional equality on types?, Stefan Monnier
- Re: [Coq-Club] Strengthening the definitional equality on types?, Conor McBride
- Re: [Coq-Club] Strengthening the definitional equality on types?, Hugo Herbelin
Archive powered by MhonArc 2.6.16.