| 1 |
; *********************************************************** |
| 2 |
; ; Adapt path if necessary: |
| 3 |
; (define path "~/minlog/examples/tait/diplomarbeit_schlenker/") |
| 4 |
|
| 5 |
; ; Defines the function "pload" to load files |
| 6 |
; ; from the path defined above |
| 7 |
; (define pload (lambda (x) (load (string-append path x)))) |
| 8 |
|
| 9 |
; ; Used Modules: |
| 10 |
; (pload "./initiate.scm") |
| 11 |
; (pload "./defsLamCalc.scm") |
| 12 |
; (pload "./defsSubst.scm") |
| 13 |
; |
| 14 |
; NOTICE: Uncomment modules only when file is run on its own |
| 15 |
; *********************************************************** |
| 16 |
|
| 17 |
|
| 18 |
; ============================== |
| 19 |
; Section: Substitution Lemmas |
| 20 |
; ============================== |
| 21 |
; Substitution in Joachimski style |
| 22 |
|
| 23 |
; Definition: "Subcompose" |
| 24 |
; ------------------------ |
| 25 |
; Composition on substitutions |
| 26 |
|
| 27 |
(add-program-constant "Subcompose" (py "Sublist=>Sublist=>Sublist") 1 'const 2) |
| 28 |
|
| 29 |
; ________________________ INTERNAL ________________________ |
| 30 |
; Allows the infix notation with "circ" instead of "Subcompose" |
| 31 |
|
| 32 |
(add-token |
| 33 |
"circ" |
| 34 |
'mul-op |
| 35 |
(lambda (x y) |
| 36 |
(let* ((type1 (term-to-type x)) |
| 37 |
(type2 (term-to-type y)) |
| 38 |
(type (types-lub type1 type2))) |
| 39 |
(mk-term-in-app-form |
| 40 |
(make-term-in-const-form (pconst-name-to-pconst "Subcompose")) |
| 41 |
x y)))) |
| 42 |
|
| 43 |
(add-display |
| 44 |
(py "Sublist") |
| 45 |
(lambda (x) |
| 46 |
(let ((op (term-in-app-form-to-final-op x)) |
| 47 |
(args (term-in-app-form-to-args x))) |
| 48 |
(if (and (term-in-const-form? op) |
| 49 |
(string=? "Subcompose" |
| 50 |
(const-to-name (term-in-const-form-to-const op))) |
| 51 |
(= 2 (length args))) |
| 52 |
(list 'mul-op "circ" |
| 53 |
(term-to-token-tree (car args)) |
| 54 |
(term-to-token-tree (cadr args))) |
| 55 |
#f)))) |
| 56 |
; _________________________________________________________ |
| 57 |
|
| 58 |
|
| 59 |
(add-computation-rule (pt "Up 0 circ theta") (pt "theta")) |
| 60 |
(add-computation-rule (pt "Up(Succ n) circ Dot r theta") |
| 61 |
(pt "Up n circ theta")) |
| 62 |
(add-computation-rule (pt "Up(Succ n)circ Up m") (pt "Up(Succ n+m)")) |
| 63 |
(add-computation-rule (pt "Dot r theta circ theta1") |
| 64 |
(pt "Dot(Sub r theta1)(theta circ theta1)")) |
| 65 |
|
| 66 |
; Lemma: "LiftId" |
| 67 |
; -------------- |
| 68 |
; lifting with value 0 is identity |
| 69 |
|
| 70 |
(add-rewrite-rule (pt "Lift r k 0") (pt "r")) |
| 71 |
|
| 72 |
; Lemma: "LiftTwiceMod" |
| 73 |
; --------------------- |
| 74 |
; lifting with k and then with k1 is the same as lifting |
| 75 |
; with (k+k1) at one step |
| 76 |
|
| 77 |
(add-rewrite-rule (pt "Lift(Lift r l k)l k1") (pt "Lift r l(k+k1)")) |
| 78 |
|
| 79 |
; Lemma: "SubliftId" |
| 80 |
; ------------------ |
| 81 |
; lifting of a substitutionlist with value 0 is identity |
| 82 |
|
| 83 |
(add-rewrite-rule (pt "Sublift theta 0") (pt "theta")) |
| 84 |
|
| 85 |
; Definition: Spare |
| 86 |
; ----------------- |
| 87 |
; adds 0 1 ... (m-1) to a substitution list |
| 88 |
|
| 89 |
(add-program-constant "Spare" (py "nat=>Sublist=>Sublist") 1 'const 2) |
| 90 |
|
| 91 |
(add-computation-rule (pt "Spare 0 theta") (pt "theta")) |
| 92 |
(add-computation-rule (pt "Spare(Succ m)theta") |
| 93 |
(pt "Spare m(Dot(Var m)theta)")) |
| 94 |
|
| 95 |
; Lemma: "SubVarSpare" |
| 96 |
; -------------------- |
| 97 |
(add-global-assumption "SubVarSpare" |
| 98 |
(pf "all m,k,theta.Sub(Var(k+m))(Spare m theta)=Sub(Var k)theta")) |
| 99 |
|
| 100 |
; Lemma: "SubVarSpareLt" |
| 101 |
; ---------------------- |
| 102 |
(add-global-assumption "SubVarSpareLt" |
| 103 |
(pf "all m,k,theta.k<m -> Sub(Var k)(Spare m theta)=Var k")) |
| 104 |
|
| 105 |
; Lemma: "DotVarSubliftSpare" |
| 106 |
; ---------------------------- |
| 107 |
(add-global-assumption "DotVarSubliftSpare" |
| 108 |
(pf "all m,theta.Dot(Var 0)(Sublift(Spare m theta)1)= |
| 109 |
Spare(Succ m)(Sublift theta 1)")) |
| 110 |
|
| 111 |
; Lemma: "CircUpUp" |
| 112 |
; ----------------- |
| 113 |
|
| 114 |
(add-rewrite-rule (pt "Up m circ Up n") (pt "Up(m+n)")) |
| 115 |
|
| 116 |
; Lemma: "CircUp" |
| 117 |
; --------------- |
| 118 |
; Joachimski's (3) |
| 119 |
|
| 120 |
(add-rewrite-rule (pt "theta circ Up n") (pt "Sublift theta n")) |
| 121 |
|
| 122 |
; Definition: "Pushlist" |
| 123 |
; --------------------- |
| 124 |
; adds the elements of a list to a substitution list |
| 125 |
|
| 126 |
(add-program-constant "Pushlist" (py "list term=>Sublist=>Sublist") 1 'const 2) |
| 127 |
|
| 128 |
(add-var-name "rs" "ss" (py "list term")) |
| 129 |
|
| 130 |
(add-computation-rule (pt "Pushlist(Nil term)theta") (pt "theta")) |
| 131 |
(add-computation-rule (pt "Pushlist(r::rs)theta") |
| 132 |
(pt "Dot r(Pushlist rs theta)")) |
| 133 |
|
| 134 |
; Lemma: "PushlistEq" |
| 135 |
; ------------------ |
| 136 |
(add-rewrite-rule (pt "Sub(Var(k+Lh rs))(Pushlist rs theta)") |
| 137 |
(pt "Sub(Var k)theta")) |
| 138 |
|
| 139 |
; Lemma: "SubLiftSpare" |
| 140 |
; --------------------- |
| 141 |
; Joachimski's (6) |
| 142 |
|
| 143 |
(add-global-assumption "SubLiftSpare" |
| 144 |
(pf "all r,m,rs,theta. |
| 145 |
Sub(Lift r m Lh rs)(Spare m(Pushlist rs theta))=Sub r(Spare m theta)")) |
| 146 |
|
| 147 |
; Theorem: "SubSub" |
| 148 |
; ----------------- |
| 149 |
; Joachimski's (7) |
| 150 |
(add-global-assumption "SubSub" |
| 151 |
(pf "all r,theta,theta1. |
| 152 |
Sub(Sub r theta)theta1=Sub r(theta circ theta1)")) |
| 153 |
|