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 "labelled_hap_computation.ma".
17 (* KASHIMA'S "ST" COMPUTATION ***********************************************)
19 (* Note: this is the "standard" computation of:
20 R. Kashima: "A proof of the Standization Theorem in λ-Calculus". Typescript note, (2000).
22 inductive st: relation term ≝
23 | st_vref: ∀s,M,i. M ⓗ⇀*[s] #i → st M (#i)
24 | st_abst: ∀s,M,A1,A2. M ⓗ⇀*[s] 𝛌.A1 → st A1 A2 → st M (𝛌.A2)
25 | st_appl: ∀s,M,B1,B2,A1,A2. M ⓗ⇀*[s] @B1.A1 → st B1 B2 → st A1 A2 → st M (@B2.A2)
28 interpretation "'st' computation"
31 notation "hvbox( M ⓢ⥤* break term 46 N )"
32 non associative with precedence 45
35 lemma st_inv_lref: ∀M,N. M ⓢ⥤* N → ∀j. #j = N →
39 | #s #M #A1 #A2 #_ #_ #j #H destruct
40 | #s #M #B1 #B2 #A1 #A2 #_ #_ #_ #j #H destruct
44 lemma st_inv_abst: ∀M,N. M ⓢ⥤* N → ∀C2. 𝛌.C2 = N →
45 ∃∃s,C1. M ⓗ⇀*[s] 𝛌.C1 & C1 ⓢ⥤* C2.
47 [ #s #M #i #_ #C2 #H destruct
48 | #s #M #A1 #A2 #HM #A12 #C2 #H destruct /2 width=4/
49 | #s #M #B1 #B2 #A1 #A2 #_ #_ #_ #C2 #H destruct
53 lemma st_inv_appl: ∀M,N. M ⓢ⥤* N → ∀D2,C2. @D2.C2 = N →
54 ∃∃s,D1,C1. M ⓗ⇀*[s] @D1.C1 & D1 ⓢ⥤* D2 & C1 ⓢ⥤* C2.
56 [ #s #M #i #_ #D2 #C2 #H destruct
57 | #s #M #A1 #A2 #_ #_ #D2 #C2 #H destruct
58 | #s #M #B1 #B2 #A1 #A2 #HM #HB12 #HA12 #D2 #C2 #H destruct /2 width=6/
62 lemma st_refl: reflexive … st.
63 #M elim M -M /2 width=2/ /2 width=4/ /2 width=6/
66 lemma st_step_sn: ∀N1,N2. N1 ⓢ⥤* N2 → ∀s,M. M ⓗ⇀*[s] N1 → M ⓢ⥤* N2.
67 #N1 #N2 #H elim H -N1 -N2
68 [ #r #N #i #HN #s #M #HMN
69 lapply (lhap_trans … HMN … HN) -N /2 width=2/
70 | #r #N #C1 #C2 #HN #_ #IHC12 #s #M #HMN
71 lapply (lhap_trans … HMN … HN) -N /3 width=5/
72 | #r #N #D1 #D2 #C1 #C2 #HN #_ #_ #IHD12 #IHC12 #s #M #HMN
73 lapply (lhap_trans … HMN … HN) -N /3 width=7/
77 lemma st_step_rc: ∀s,M1,M2. M1 ⓗ⇀*[s] M2 → M1 ⓢ⥤* M2.
78 /3 width=4 by st_step_sn/
81 lemma st_lift: liftable st.
82 #h #M1 #M2 #H elim H -M1 -M2
84 | #s #M #A1 #A2 #HM #_ #IHA12 #d
85 @st_abst [3: @(lhap_lift … HM) |1,2: skip ] -M // (**) (* auto fails here *)
86 | #s #M #B1 #B2 #A1 #A2 #HM #_ #_ #IHB12 #IHA12 #d
87 @st_appl [4: @(lhap_lift … HM) |1,2,3: skip ] -M // (**) (* auto fails here *)
91 lemma st_inv_lift: deliftable_sn st.
92 #h #N1 #N2 #H elim H -N1 -N2
93 [ #s #N1 #i #HN1 #d #M1 #HMN1
94 elim (lhap_inv_lift … HN1 … HMN1) -N1 /3 width=3/
95 | #s #N1 #C1 #C2 #HN1 #_ #IHC12 #d #M1 #HMN1
96 elim (lhap_inv_lift … HN1 … HMN1) -N1 #M2 #HM12 #HM2
97 elim (lift_inv_abst … HM2) -HM2 #A1 #HAC1 #HM2 destruct
98 elim (IHC12 ???) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #HAC2 destruct (**) (* simplify line *)
99 @(ex2_intro … (𝛌.A2)) // /2 width=4/
100 | #s #N1 #D1 #D2 #C1 #C2 #HN1 #_ #_ #IHD12 #IHC12 #d #M1 #HMN1
101 elim (lhap_inv_lift … HN1 … HMN1) -N1 #M2 #HM12 #HM2
102 elim (lift_inv_appl … HM2) -HM2 #B1 #A1 #HBD1 #HAC1 #HM2 destruct
103 elim (IHD12 ???) -IHD12 [4: // |2,3: skip ] #B2 #HB12 #HBD2 destruct (**) (* simplify line *)
104 elim (IHC12 ???) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #HAC2 destruct (**) (* simplify line *)
105 @(ex2_intro … (@B2.A2)) // /2 width=6/
109 lemma st_dsubst: dsubstable st.
110 #N1 #N2 #HN12 #M1 #M2 #H elim H -M1 -M2
111 [ #s #M #i #HM #d elim (lt_or_eq_or_gt i d) #Hid
112 [ lapply (lhap_dsubst … N1 … HM d) -HM
113 >(dsubst_vref_lt … Hid) >(dsubst_vref_lt … Hid) /2 width=2/
114 | destruct >dsubst_vref_eq
115 @(st_step_sn (↑[0,i]N1) … s) /2 width=1/
116 | lapply (lhap_dsubst … N1 … HM d) -HM
117 >(dsubst_vref_gt … Hid) >(dsubst_vref_gt … Hid) /2 width=2/
119 | #s #M #A1 #A2 #HM #_ #IHA12 #d
120 lapply (lhap_dsubst … N1 … HM d) -HM /2 width=4/ (**) (* auto needs some help here *)
121 | #s #M #B1 #B2 #A1 #A2 #HM #_ #_ #IHB12 #IHA12 #d
122 lapply (lhap_dsubst … N1 … HM d) -HM /2 width=6/ (**) (* auto needs some help here *)
126 lemma st_inv_lsreds_is_le: ∀M,N. M ⓢ⥤* N →
127 ∃∃r. M ⇀*[r] N & is_le r.
128 #M #N #H elim H -M -N
130 lapply (lhap_inv_lsreds … H)
131 lapply (lhap_inv_head … H) -H #H
132 lapply (is_head_is_le … H) -H /2 width=3/
133 | #s #M #A1 #A2 #H #_ * #r #HA12 #Hr
134 lapply (lhap_inv_lsreds … H) #HM
135 lapply (lhap_inv_head … H) -H #Hs
136 lapply (lsreds_trans … HM (sn:::r) (𝛌.A2) ?) /2 width=1/ -A1 #HM
137 @(ex2_intro … HM) -M -A2 /3 width=1/
138 | #s #M #B1 #B2 #A1 #A2 #H #_ #_ * #rb #HB12 #Hrb * #ra #HA12 #Hra
139 lapply (lhap_inv_lsreds … H) #HM
140 lapply (lhap_inv_head … H) -H #Hs
141 lapply (lsreds_trans … HM (dx:::ra) (@B1.A2) ?) /2 width=1/ -A1 #HM
142 lapply (lsreds_trans … HM (sn:::rb) (@B2.A2) ?) /2 width=1/ -B1 #HM
143 @(ex2_intro … HM) -M -B2 -A2 >associative_append /3 width=1/
147 lemma st_step_dx: ∀p,M,M2. M ⇀[p] M2 → ∀M1. M1 ⓢ⥤* M → M1 ⓢ⥤* M2.
148 #p #M #M2 #H elim H -p -M -M2
150 elim (st_inv_appl … H ???) -H [4: // |2,3: skip ] #s #B1 #M #HM1 #HB1 #H (**) (* simplify line *)
151 elim (st_inv_abst … H ??) -H [3: // |2: skip ] #r #A1 #HM #HA1 (**) (* simplify line *)
152 lapply (lhap_trans … HM1 … (dx:::r) (@B1.𝛌.A1) ?) /2 width=1/ -M #HM1
153 lapply (lhap_step_dx … HM1 (◊) ([⬐B1]A1) ?) -HM1 // #HM1
154 @(st_step_sn … HM1) /2 width=1/
155 | #p #A #A2 #_ #IHA2 #M1 #H
156 elim (st_inv_abst … H ??) -H [3: // |2: skip ] /3 width=4/ (**) (* simplify line *)
157 | #p #B #B2 #A #_ #IHB2 #M1 #H
158 elim (st_inv_appl … H ???) -H [4: // |2,3: skip ] /3 width=6/ (**) (* simplify line *)
159 | #p #B #A #A2 #_ #IHA2 #M1 #H
160 elim (st_inv_appl … H ???) -H [4: // |2,3: skip ] /3 width=6/ (**) (* simplify line *)
164 lemma st_lhap1_swap: ∀p,N1,N2. N1 ⓗ⇀[p] N2 → ∀M1. M1 ⓢ⥤* N1 →
165 ∃∃q,M2. M1 ⓗ⇀[q] M2 & M2 ⓢ⥤* N2.
166 #p #N1 #N2 #H elim H -p -N1 -N2
168 elim (st_inv_appl … H ???) -H [4: // |2,3: skip ] #s #D1 #N #HM1 #HD1 #H (**) (* simplify line *)
169 elim (st_inv_abst … H ??) -H [3: // |2: skip ] #r #C1 #HN #HC1 (**) (* simplify line *)
170 lapply (lhap_trans … HM1 … (dx:::r) (@D1.𝛌.C1) ?) /2 width=1/ -N #HM1
171 lapply (lhap_step_dx … HM1 (◊) ([⬐D1]C1) ?) -HM1 // #HM1
172 elim (lhap_inv_pos … HM1 ?) -HM1
173 [2: >length_append normalize in ⊢ (??(??%)); // ]
174 #q #r #M #_ #HM1 #HM -s
175 @(ex2_2_intro … HM1) -M1
176 @(st_step_sn … HM) /2 width=1/
177 | #p #D #C1 #C2 #_ #IHC12 #M1 #H -p
178 elim (st_inv_appl … H ???) -H [4: // |2,3: skip ] #s #B #A1 #HM1 #HBD #HAC1 (**) (* simplify line *)
179 elim (IHC12 … HAC1) -C1 #p #C1 #HAC1 #HC12
180 lapply (lhap_step_dx … HM1 (dx::p) (@B.C1) ?) -HM1 /2 width=1/ -A1 #HM1
181 elim (lhap_inv_pos … HM1 ?) -HM1
182 [2: >length_append normalize in ⊢ (??(??%)); // ]
183 #q #r #M #_ #HM1 #HM -p -s
184 @(ex2_2_intro … HM1) -M1 /2 width=6/
188 lemma st_lsreds: ∀s,M1,M2. M1 ⇀*[s] M2 → M1 ⓢ⥤* M2.
189 #s #M1 #M2 #H @(lstar_ind_r ????????? H) -s -M2 // /2 width=4 by st_step_dx/
192 theorem st_trans: transitive … st.
194 elim (st_inv_lsreds_is_le … HM1) -HM1 #s1 #HM1 #_
195 elim (st_inv_lsreds_is_le … HM2) -HM2 #s2 #HM2 #_
196 lapply (lsreds_trans … HM1 … HM2) -M /2 width=2/
199 theorem lsreds_standard: ∀s,M,N. M ⇀*[s] N →
200 ∃∃r. M ⇀*[r] N & is_le r.
202 @st_inv_lsreds_is_le /2 width=2/
205 theorem lsreds_lhap1_swap: ∀s,M1,N1. M1 ⇀*[s] N1 → ∀p,N2. N1 ⓗ⇀[p] N2 →
206 ∃∃q,r,M2. M1 ⓗ⇀[q] M2 & M2 ⇀*[r] N2 & is_le (q::r).
207 #s #M1 #N1 #HMN1 #p #N2 #HN12
208 lapply (st_lsreds … HMN1) -s #HMN1
209 elim (st_lhap1_swap … HN12 … HMN1) -p -N1 #q #M2 #HM12 #HMN2
210 elim (st_inv_lsreds_is_le … HMN2) -HMN2 #r #HMN2 #Hr
211 lapply (lhap1_inv_head … HM12) /3 width=7/