1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/rt_equivalence/cpcs_cprs.ma".
16 include "basic_2/dynamic/cnv_preserve.ma".
17 include "basic_2/dynamic/nta.ma".
19 (* NATIVE TYPE ASSIGNMENT FOR TERMS *****************************************)
21 (* Properties based on preservation *****************************************)
23 lemma cnv_cpms_nta (a) (h) (G) (L):
24 ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[a,h] U.
25 /3 width=4 by cnv_cast, cnv_cpms_trans/ qed.
27 lemma cnv_nta_sn (a) (h) (G) (L):
28 ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∃U. ⦃G,L⦄ ⊢ T :[a,h] U.
30 elim (cnv_fwd_cpm_SO … HT) #U #HTU
31 /4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/
34 (* Basic_1: was: ty3_typecheck *)
35 lemma nta_typecheck (a) (h) (G) (L):
36 ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] T0.
37 /3 width=1 by cnv_cast, cnv_nta_sn/ qed-.
39 (* Basic_1: was: ty3_correct *)
40 (* Basic_2A1: was: ntaa_fwd_correct *)
41 lemma nta_fwd_correct (a) (h) (G) (L):
42 ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ U :[a,h] T0.
43 /3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-.
45 lemma nta_pure_cnv (h) (G) (L):
46 ∀T,U. ⦃G,L⦄ ⊢ T :*[h] U →
47 ∀V. ⦃G,L⦄ ⊢ ⓐV.U !*[h] → ⦃G,L⦄ ⊢ ⓐV.T :*[h] ⓐV.U.
48 #h #G #L #T #U #H1 #V #H2
49 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
50 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
51 elim (cnv_cpms_conf … HU … HUX0 … HUX2) -HU -HUX2
52 <minus_O_n <minus_n_O #X #HX0 #H
53 elim (cpms_inv_abst_sn … H) -H #X3 #X4 #HX13 #HX24 #H destruct
54 @(cnv_cast … (ⓐV.X0)) [2:|*: /2 width=1 by cpms_appl_dx/ ]
55 @(cnv_appl … X3) [4: |*: /2 width=7 by cpms_trans, cpms_cprs_trans/ ]
59 (* Inversion lemmas based on preservation ***********************************)
61 lemma nta_inv_bind_sn_cnv (a) (h) (p) (I) (G) (K) (X2):
62 ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[a,h] X2 →
63 ∃∃U. ⦃G,K⦄ ⊢ V ![a,h] & ⦃G,K.ⓑ{I}V⦄ ⊢ T :[a,h] U & ⦃G,K⦄ ⊢ ⓑ{p,I}V.U ⬌*[h] X2 & ⦃G,K⦄ ⊢ X2 ![a,h].
64 #a #h #p * #G #K #X2 #V #T #H
65 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
66 elim (cnv_inv_bind … H1) -H1 #HV #HT
67 [ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
68 [ #V0 #U #HV0 #HTU #H destruct
69 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
70 | #U #HTU #HX1U #H destruct
71 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_zeta, ex4_intro/
73 | elim (cpms_inv_abst_sn … H2) -H2 #V0 #U #HV0 #HTU #H destruct
74 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
78 (* Basic_1: uses: ty3_gen_appl *)
79 lemma nta_inv_appl_sn (h) (G) (L) (X2):
80 ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h] X2 →
81 ∃∃p,W,U. ⦃G,L⦄ ⊢ V :[h] W & ⦃G,L⦄ ⊢ T :[h] ⓛ{p}W.U & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h].
83 elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
84 elim (cnv_inv_appl … H1) * [ | #n ] #p #W #U #Hn #HV #HT #HVW #HTU
85 [ lapply (cnv_cpms_trans … HT … HTU) #H
86 elim (cnv_inv_bind … H) -H #_ #HU
87 elim (cnv_fwd_cpm_SO … HU) #U0 #HU0 -HU
88 lapply (cpms_step_dx … HTU 1 (ⓛ{p}W.U0) ?) -HTU [ /2 width=1 by cpm_bind/ ] #HTU
89 | lapply (le_n_O_to_eq n ?) [ /3 width=1 by le_S_S_to_le/ ] -Hn #H destruct
91 lapply (cpms_appl_dx … V V … HTU) [1,3: // ] #HVTU
92 elim (cnv_cpms_conf … H1 … H2 … HVTU) -H1 -H2 -HVTU <minus_n_n #X0 #HX0 #HUX0
93 @ex4_3_intro [6,13: |*: /2 width=5 by cnv_cpms_nta/ ]
94 /3 width=5 by cprs_div, cprs_trans/
97 lemma nta_inv_pure_sn_cnv (h) (G) (L) (X2):
98 ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :*[h] X2 →
99 ∨∨ ∃∃p,W,T0,U0. ⦃G,L⦄ ⊢ V :*[h] W & ⦃G,L⦄ ⊢ ⓛ{p}W.T0 :*[h] ⓛ{p}W.U0 & ⦃G,L⦄ ⊢ T ➡*[h] ⓛ{p}W.T0 & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U0 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h]
100 | ∃∃U. ⦃G,L⦄ ⊢ T :*[h] U & ⦃G,L⦄ ⊢ ⓐV.U !*[h] & ⦃G,L⦄ ⊢ ⓐV.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h].
101 #h #G #L #X2 #V #T #H
102 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H
103 elim (cnv_inv_appl … H1) -H1 * [| #n ] #p #W0 #T0 #_ #HV #HT #HW0 #HT0
104 lapply (cnv_cpms_trans … HT … HT0) #H
105 elim (cnv_inv_bind … H) -H #_ #H1T0
106 [ elim (cpms_inv_appl_sn_decompose … H) -H #U #HTU #HUX1
109 [ #V0 #U0 #HV0 #HU0 #H destruct
110 elim (cnv_cpms_conf … HT … HT0 … HU0)
111 <minus_O_n <minus_n_O #X #H #HU0X
112 elim (cpms_inv_abst_sn … H) -H #W1 #U1 #HW01 #HU01 #H destruct
114 @(ex5_4_intro … U1 … HT0 … HX2) -HX2
115 [ /2 width=1 by cnv_cpms_nta/
116 | @nta_bind_cnv /2 width=4 by cnv_cpms_trans/ /2 width=3 by cnv_cpms_nta/
117 | @(cpcs_cprs_div … HX21) -HX21
118 @(cprs_div … (ⓐV0.ⓛ{p}W1.U1))
119 /3 width=1 by cpms_appl, cpms_appl_dx, cpms_bind/
122 (* Basic_2A1: uses: nta_inv_cast1 *)
123 lemma nta_inv_cast_sn (a) (h) (G) (L) (X2):
124 ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] X2 →
125 ∧∧ ⦃G,L⦄ ⊢ T :[a,h] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
126 #a #h #G #L #X2 #U #T #H
127 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
128 elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
129 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
130 [ #U0 #T0 #HU0 #HT0 #H destruct -HU -HU0
131 elim (cnv_cpms_conf … HT … HTX … HT0) -HT -HTX -HT0
132 <minus_n_n #T1 #HXT1 #HT01
133 @and3_intro // @(cprs_div … T1) /3 width=4 by cprs_trans, cpms_eps/ (**) (* full auto too slow *)
135 elim (cnv_cpms_conf … HT … HTX … HTX0) -HT -HTX -HTX0
136 <minus_n_n #T1 #HXT1 #HXT01
137 @and3_intro // @(cprs_div … T1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
138 | #m #HUX0 #H destruct -HT -HTX
139 elim (cnv_cpms_conf … HU … HUX … HUX0) -HU -HUX0
140 <minus_n_n #U1 #HXU1 #HXU01
141 @and3_intro // @(cprs_div … U1) /2 width=3 by cprs_trans/ (**) (* full auto too slow *)
145 (* Basic_1: uses: ty3_gen_cast *)
146 lemma nta_inv_cast_sn_old (a) (h) (G) (L) (X2):
147 ∀T0,T1. ⦃G,L⦄ ⊢ ⓝT1.T0 :[a,h] X2 →
148 ∃∃T2. ⦃G,L⦄ ⊢ T0 :[a,h] T1 & ⦃G,L⦄ ⊢ T1 :[a,h] T2 & ⦃G,L⦄ ⊢ ⓝT2.T1 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
149 #a #h #G #L #X2 #T0 #T1 #H
150 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
151 elim (cnv_inv_cast … H1) #X #HT1 #HT0 #HT1X #HT0X
152 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
153 [ #U1 #U0 #HTU1 #HTU0 #H destruct
154 elim (cnv_cpms_conf … HT0 … HT0X … HTU0) -HT0 -HT0X -HTU0
155 <minus_n_n #X0 #HX0 #HUX0
156 lapply (cprs_trans … HT1X … HX0) -X #HT1X0
157 /5 width=7 by cnv_cpms_nta, cpcs_cprs_div, cprs_div, cpms_cast, ex4_intro/
159 elim (cnv_cpms_conf … HT0 … HT0X … HTX0) -HT0 -HT0X -HTX0
160 <minus_n_n #X1 #HX1 #HX01
161 elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
162 lapply (cprs_trans … HT1X … HX1) -X #HTX1
163 lapply (cprs_trans … HX20 … HX01) -X0 #HX21
164 /4 width=5 by cprs_div, cpms_eps, ex4_intro/
165 | #n #HT1X0 #H destruct -X -HT0
166 elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
167 /4 width=5 by cprs_div, cpms_eps, ex4_intro/
171 (* Forward lemmas based on preservation *************************************)
173 (* Basic_1: was: ty3_unique *)
174 theorem nta_mono (a) (h) (G) (L) (T):
175 ∀U1. ⦃G,L⦄ ⊢ T :[a,h] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[a,h] U2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
176 #a #h #G #L #T #U1 #H1 #U2 #H2
177 elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
178 elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
179 elim (cnv_cpms_conf … HT … HTX1 … HTX2) -T <minus_n_n #X #HX1 #HX2
180 /3 width=5 by cprs_div, cprs_trans/