| 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 |
; *************************************************************** |