Debian Codegraph @

examples/tait/diplomarbeit_schlenker/subst_Joachimski_SHORT.scm

raw
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