Debian Codegraph @

examples/tait/diplomarbeit_schlenker/tait.scm

raw
1 ; $Id: tait.scm 2156 2008-01-25 13:25:12Z schimans $
2 ; Based on examples/sn.scm, from 2005-01-08 to NTheorem
3
4 ; ***************************************************************
5 ; This is the central file, which loads all the other modules.
6 ; Running this file requires the head information of all other
7 ; modules to be uncommented (see also the README file).
8 ; ***************************************************************
9
10 ; =======================
11 ; Section: Preparations
12 ; =======================
13
14 ; Subsection: Defining "pload"
15 ; ============================
16 ; Adapt path if necessary:
17 (define path "~/minlog/examples/tait/diplomarbeit_schlenker/")
18
19 ; Defines the function "pload" to load files
20 ; from the path defined above
21 (define pload (lambda (x) (load (string-append path x))))
22
23
24 ; Subsection: Initiation of Minlog
25 ; ================================
26 (pload "./initiate.scm")
27
28
29 ; Subsection: Lambda Calculus
30 ; ===========================
31 ; Subsubsection: Definitions for the Lambda-Calculus
32 ; --------------------------------------------------
33 (pload "./defsLamCalc.scm")
34
35 ; Subsubsection: Substitution
36 ; ---------------------------
37 ; Substitution in "de Bruijn"-style
38
39 ; definitions for substitution
40 (pload "./defsSubst.scm")
41
42 ; Joachimski-Section
43 (pload "./subst_Joachimski.scm")
44 ;(pload "./subst_Joachimski_SHORT.scm")
45
46 ; Subsubsection: Omega
47 ; --------------------
48 (pload "./omega.scm")
49
50
51 ; ================================
52 ; Section: Normalization Theorem
53 ; ================================
54
55 ; Subsection: Specific Definitions
56 ; ================================
57 ; specific definitions for the Normalization Theorem
58
59 ; Subsubsection: General Definitions
60 ; ----------------------------------
61 (pload "./defsNT.scm")
62 (pload "./defsAxiomsSpecial.scm")
63
64
65 ; Subsection: Preceding Lemmas
66 ; ============================
67 ; Trivial Lemmas
68 ; --------------
69 (pload "./trivial.scm")
70
71 ; Global Auxiliaries
72 ; ------------------
73 (pload "./auxGlobal.scm")
74 ;(pload "./auxGlobal_SHORT.scm")
75
76
77 ; Subsection: Axioms
78 ; ===================
79 ; Subsubsection: Proof of the Axioms
80 ; ----------------------------------
81 ; needs to be uncommented when Axioms
82 ; are used without proof (see below)
83 (pload "./defsPred.scm")
84 (pload "./proofAxiomsGlobal.scm")
85 ;(pload "./proofAxiomsGlobal_SHORT.scm")
86 (pload "./proofAxiomsPart1.scm")
87 (pload "./proofAxiomsPart2.scm")
88
89 ; Subsubsection: Definition of the Axioms
90 ; ---------------------------------------
91 ; needs to be uncommented
92 ; if proven Axioms are used (see above)
93 ; (pload "./defsAxioms.scm")
94
95
96 ; Subsection: Proof of original SC-Definition
97 ; ===========================================
98 (pload "./auxSC.scm")
99
100
101 ; Subsection: Lemma 1
102 ; ===================
103 ; Subsubsection: Auxiliaries for Lemma 1
104 ; --------------------------------------
105 (pload "./auxLem1.scm")
106 ;(pload "./auxLem1_SHORT.scm")
107
108 ; Subsubsection: Lemma 1
109 ; ----------------------
110 (pload "./Lem1.scm")
111
112
113 ; Subsection: Lemma 2
114 ; ===================
115 (pload "./Lem2.scm")
116
117
118 ; Subsection: Lemma 3
119 ; ===================
120 ; Subsubsection: Auxiliaries for Lemma 3
121 ; --------------------------------------
122 (pload "./auxLem3.scm")
123 ;(pload "./auxLem3_SHORT.scm")
124
125 ; Subsubsection: Lemma 3
126 ; ----------------------
127 (pload "./Lem3.scm")
128
129
130 ; Subsection: Normalization Theorem
131 ; =================================
132 ; Subsubsection: Auxiliaries for the Normalization Theorem
133 ; --------------------------------------------------------
134 (pload "./auxNT.scm")
135 ;(pload "./auxNT_SHORT.scm")
136
137 ; Subsubsection: Normalization Theorem
138 ; ------------------------------------
139 (pload "./NT.scm")
140
141
142 ; =============================
143 ; Section: Program Extraction
144 ; =============================
145
146 ; Subsection: Preparations
147 ; ========================
148
149 (define SCLemmas
150 '("LemmaSCIotaFold" "LemmaSCIotaUnfold"
151 "LemmaSCFold" "LemmaSCUnfold"))
152
153 (define AllLemmas (append SCLemmas
154 '("LemmaOne" "LemmaTwo" "LemmaThree")))
155
156 (define (theorem-name-to-expanded-proof name names)
157 (expand-theorems (theorem-name-to-proof name)
158 (lambda (x) (member x names))))
159
160 (add-var-name "p" (py "(omega=>nat=>term)@@((nat=>term)=>omega)"))
161 (add-var-name "q" (py "list type=>list omega=>omega"))
162 (add-var-name "d" (py "list type=>list omega"))
163
164
165 ; Subsection: Extraced Programs
166 ; =============================
167 (set! pp-width 68)
168
169 ; Subsubsection: Animating AC, ACL, IP, UNC
170 ; -----------------------------------------
171 (animate "AC" (pt "[alpha1=>alpha2]alpha1=>alpha2"))
172 (animate "ACL" (pt "[g]g"))
173 (animate "IP" (pt "[alpha]alpha"))
174 (animate "UNC" (pt "[alpha2]alpha2"))
175
176 ; Subsubsection: SCLemmas
177 ; -----------------------
178 (pp (nt (proof-to-extracted-term
179 (theorem-name-to-proof "LemmaSCIotaFold"))))
180
181 ; OmegaInIota
182
183 (pp (nt (proof-to-extracted-term
184 (theorem-name-to-proof "LemmaSCIotaUnfold"))))
185
186 ; ModIota
187
188 (pp (nt (proof-to-extracted-term
189 (theorem-name-to-proof "LemmaSCFold"))))
190
191 ; Hat
192
193 (pp (nt (proof-to-extracted-term
194 (theorem-name-to-proof "LemmaSCUnfold"))))
195
196 ; Mod
197
198 ; Subsubsection: LemmaOne
199 ; -----------------------
200 (pp (nt (proof-to-extracted-term
201 (theorem-name-to-expanded-proof "LemmaOne" SCLemmas))))
202
203 ; (Rec type=>(omega=>nat=>term)@@((nat=>term)=>omega))
204 ; (ModIota@OmegaInIota)
205 ; ([rho3,rho4,p5,p6]
206 ; ([a7,n8]
207 ; Abs rho3
208 ; (Sub(left p6(Mod a7(right p5([n9]Var n8)))(Succ n8))
209 ; (Wrap(Succ(Succ n8))((Var map Seq 1 n8):+:(Var 0):))))@
210 ; ([g7]Hat rho3 rho4([a8]right p6([n9]g7 n9(left p5 a8 n9)))))
211
212 ; Subsubsection: LemmaTwo
213 ; -----------------------
214 (pp (nt (proof-to-extracted-term
215 (theorem-name-to-proof "LemmaTwo"))))
216
217 ; [a0]a0
218
219 ; Subsubsection: LemmaThree
220 ; -------------------------
221 (pp (nt (proof-to-extracted-term
222 (theorem-name-to-expanded-proof "LemmaThree" SCLemmas))))
223
224 ; (Rec term=>list type=>list omega=>omega)
225 ; ([n3,rhos4](ListRef omega)n3)
226 ; ([r3,r4,q5,q6,rhos7,as8]Mod(q5 rhos7 as8)(q6 rhos7 as8))
227 ; ([rho3,r4,q5,rhos6,as7]
228 ; Hat rho3(Typ(rho3::rhos6)r4)
229 ; ([a8]cLemmaTwo(q5(rho3::rhos6)(a8::as7))))
230
231 ; Subsubsection: SCrsSeq
232 ; ----------------------
233 (pp (nt (proof-to-extracted-term
234 (theorem-name-to-proof "SCrsSeq"))))
235
236 ; (Rec list type=>list type=>list omega)([rhos2](Nil omega))
237 ; ([rho2,rhos3,d4,rhos5]
238 ; right(cLemmaOne rho2)([n6]Var Lh rhos5)::d4(rhos5:+:rho2:))
239
240 ; Subsubsection: NTheorem
241 ; -----------------------
242 (pp (nt (proof-to-extracted-term
243 (theorem-name-to-proof "NTheorem"))))
244
245 ; [rhos0,r1]
246 ; left(cLemmaOne(Typ rhos0 r1))
247 ; (cLemmaThree r1 rhos0(cSCrsSeq rhos0(Nil type)))
248 ; Lh rhos0
249
250
251 ; Subsection: Animation of Lemmas
252 ; ===============================
253 ; Subsubsection: SC-Lemmas
254 ; ------------------------
255 (animate "LemmaSCFold")
256 (animate "LemmaSCUnfold")
257 (animate "LemmaSCIotaFold")
258 (animate "LemmaSCIotaUnfold")
259
260 ; Subsubsection: Main Lemmas
261 ; --------------------------
262 (animate "LemmaOne")
263 (animate "LemmaTwo")
264 (animate "LemmaThree")
265 (animate "SCrsSeq")
266 (animate "NTheorem")
267
268
269 ; Subsection: Examples
270 ; ====================
271 ; Subsubsection: Example 1
272 ; ------------------------
273 ; Check Term in Context:
274 (pp (nt (pt "Cor ((Iota to Iota):) (Var 0) ")))
275
276 ; Print long NF:
277 (pp (nt (pt "cNTheorem ((Iota to Iota):) (Var 0)" )))
278 ;Abs Iota(Var 1(Var 0))
279
280 ; Subsubsection: Example 2
281 ; ------------------------
282 ; Check Term in Context:
283 (pp (nt (pt "Cor ((Iota to Iota to Iota):) (Var 0) ")))
284
285 ; Print long NF:
286 (pp (nt (pt "cNTheorem ((Iota to Iota to Iota):) (Var 0)" )))
287 ; Abs Iota(Abs Iota(Var 2(Var 1)(Var 0)))
288
289 ; Subsubsection: Example 3
290 ; ------------------------
291 ; Check Term in Context:
292 (pp (nt (pt "Cor (((Iota to Iota) to Iota):) (Var 0) ")))
293
294 ; Print long NF:
295 (pp (nt (pt "cNTheorem (((Iota to Iota) to Iota):) (Var 0)" )))
296 ; Abs(Iota to Iota)(Var 1(Abs Iota(Var 1(Var 0))))
297
298 ; Subsubsection: Example 4
299 ; ------------------------
300 ; Check Term in Context:
301 (pp (nt (pt "Cor ((Iota to Iota):)
302 ((Abs (Iota to Iota) (Var 0)) (Var 0))")))
303
304 ; Print long NF:
305 (pp (nt (pt "cNTheorem ((Iota to Iota):)
306 ((Abs (Iota to Iota) (Var 0)) (Var 0))" )))
307 ; Abs Iota(Var 1(Var 0))
308
309 ; Subsubsection: Example 5
310 ; ------------------------
311 ; Check Term in Context:
312 (pp (nt (pt "Cor
313 ((Iota to Iota) :: (((Iota to Iota) to Iota) :: (Iota to Iota):))
314 ((Abs (Iota to Iota) (Var 2) (Var 0)) (Var 2))")))
315
316 ; Print long NF:
317 (pp (nt (pt "cNTheorem
318 ((Iota to Iota) :: (((Iota to Iota) to Iota) :: (Iota to Iota):))
319 ((Abs (Iota to Iota) (Var 2) (Var 0)) (Var 2))" )))
320 ; Var 1(Abs Iota(Var 3(Var 0)))
321
322 ; ***************************************************************