Debian Codegraph @

examples/tait/diplomarbeit_schlenker/defsPred.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 ; (pload "./subst_Joachimski_SHORT.scm")
14 ; (pload "./omega.scm")
15 ; (pload "./defsNT.scm")
16 ; (pload "./trivial.scm")
17 ; (pload "./auxGlobal_SHORT.scm")
18 ;
19 ; NOTICE: Uncomment modules only when file is run on its own
20 ; ***********************************************************
21
22
23 ; ===================================
24 ; Section: Definition of Predicates
25 ; ===================================
26 ; contains the definitions of N, A, H
27
28 ; Subsection: Global Definitions
29 ; ==============================
30
31 ; Definition: "--->"
32 ; ------------------
33 ; folds a list of types with the last type
34
35 (add-program-constant "--->" (py "list type => type => type") 1)
36
37 (add-computation-rule (pt " ---> (Nil type) rho") (pt "rho"))
38 (add-computation-rule (pt " ---> (sig::rhos) rho")
39 (pt "sig to (---> rhos rho)"))
40
41
42 ; Subsection: Definition of N
43 ; ===========================
44
45 ; Subsubsection: BN
46 ; :::::::::::::::::
47
48 ; Definition: FoldApp
49 ; -------------------
50 (add-program-constant "FoldApp" (py "term => list term => term") 1)
51
52 (add-computation-rule (pt "FoldApp r (Nil term)")
53 (pt "r"))
54 (add-computation-rule (pt "FoldApp r (s::ss)")
55 (pt "FoldApp (r s) ss"))
56
57 (pp (nt (pt "FoldApp (r) (s::t:)")))
58 ; => r s t
59
60 ; Definition: "BN", "BNs"
61 ; -----------------------
62 ; simultaneous inductive definition of "BN" and "BNs"
63
64 (add-ids (list
65 (list "BN" (make-arity (py "term") (py "term")) )
66 (list "BNs" (make-arity (py "list term") (py "list term")) ))
67 '("all n, rs, ss. BNs rs ss ->
68 BN (FoldApp (Var n) rs) (FoldApp (Var n) ss)" "BNVar")
69 '("all rho, r,s. BN r s -> BN (Abs rho r) (Abs rho s)" "BNAbs")
70 '("all rho, r,s,t,rs. BN (FoldApp (Sub r (Wrap 0 (s:))) rs) t ->
71 BN (FoldApp (Abs rho r) (s::rs)) t" "BNBeta")
72 '("BNs (Nil term) (Nil term)" "BNsNil")
73 '("all r,s,rs,ss. BN r s -> BNs rs ss -> BNs (r::rs) (s::ss)"
74 "BNsCons"))
75
76
77 ; Subsubsection: Exp
78 ; ::::::::::::::::::
79
80 ; Definition: "Eta"
81 ; -----------------
82 ; recursive definition of Eta (=outside/brute force expansion)
83 ; which is used for the definition of Exp
84
85 (add-program-constant "Eta" (py "type => term => term") 1)
86
87 (add-computation-rule (pt "Eta Iota r")
88 (pt "r"))
89 (add-computation-rule (pt "Eta (rho to sig) r")
90 (pt "Abs rho (Eta sig ((Lift r 0 1) (Eta rho (Var 0))))"))
91
92 (pp (nt (pt "Eta ((Iota to Iota) to Iota) ((Var 3))")))
93
94 ; Notice that the "1" (i.e., the totality) of Eta must be proved.
95 ; This is easy, by induction on types.
96
97
98 ; Definition: "Exp", "Exps"
99 ; -------------------------
100 ; "Exp" and "Exps" are defined simultaneously
101 ; Exp t s means s is the eta-expanded form of t
102 ; (since we only need t to be in beta-reduced form
103 ; t is restricted to this form to keep proofs shorter)
104
105 (add-ids (list
106 (list "Exp" (make-arity (py "list type") (py "type")
107 (py "term") (py "term")) )
108 (list "Exps" (make-arity (py "list type") (py "list type")
109 (py "list term") (py "list term")) ))
110 '("all rhos, sigs, rs, ss, k, t, rho.
111 TypJ rhos (Var k) (---> sigs rho) ->
112 Exps rhos sigs rs ss ->
113 t = Eta rho (FoldApp (Var k) ss) ->
114 Exp rhos rho (FoldApp (Var k) rs) t"
115 "ExpVar")
116 '("all rhos1,rhos2,sigs,taus,rho,sig,r,s,k.
117 TypJ ((rhos1:+:rhos2):+:sigs) (Var k) rho ->
118 Exp (rhos1:+:rhos2) sig r s ->
119 TypJ rhos1 (ABS k rho r) (rho to sig) ->
120 Exp (rhos1 :+: taus)(rho to sig)
121 (ABS k rho r) (ABS k rho s)" "ExpAbs")
122 '("all rhos. Exps rhos (Nil type) (Nil term)
123 (Nil term)" "ExpsNil")
124 '("all rhos,sigs,r,s,rs,ss.
125 Exp rhos rho r s -> Exps rhos sigs rs ss ->
126 Exps rhos (rho::sigs) (r::rs) (s::ss)" "ExpsCons"))
127
128
129 ; SubSubsection: Definition of NInd
130 ; :::::::::::::::::::::::::::::::::
131 ; N r s means s is the long normal form of r
132 ; i.e. the beta-reduced and eta-expanded form of r
133
134 ; Definition: NInd
135 ; ----------------
136 (add-ids (list (list
137 "NInd" (make-arity (py "list type")(py "type")
138 (py "term") (py "term")) ))
139 '("all rhos,rho,r,s,t.
140 TypJ rhos r rho -> BN r t -> Exp rhos rho t s ->
141 NInd rhos rho r s" "NIntro"))
142
143 ; Definition: "N"
144 ; ---------------
145 (add-global-assumption "NDef"
146 (pf "all rhos,rho,r^,s^. N rhos rho r^ s^ ->
147 NInd rhos rho r^ s^"))
148
149 (add-global-assumption "NDefRev"
150 (pf "all rhos,rho,r^,s^.NInd rhos rho r^ s^ ->
151 N rhos rho r^ s^ "))
152
153
154 ; SubSubsection: Definition of Head
155 ; :::::::::::::::::::::::::::::::::
156
157 ; Definition: "HeadInd"
158 ; ---------------------
159 (add-ids (list (list
160 "HeadInd" (make-arity (py "term") (py "term")) ))
161 '("all rho,r,s,rs.HeadInd (FoldApp ((Abs rho r)s) rs)
162 (FoldApp (Sub r(Dot s (Up 0))) rs)" "HeadCon"))
163
164 ; Definition: "HeadDef" "HeadDefRev"
165 ; ----------------------------------
166 (add-global-assumption "HeadDef"
167 (pf "all r,s. Head r s -> HeadInd r s"))
168
169 (add-global-assumption "HeadDefRev"
170 (pf "all r,s.HeadInd r s -> Head r s"))
171
172
173 ; SubSubsection: Definition of A
174 ; ::::::::::::::::::::::::::::::
175
176 ; Definition: "AInd"
177 ; ------------------
178 (add-ids (list (list "AInd" (make-arity (py "list type")(py "type")
179 (py "term") (py "term")) ))
180 '("all rhos,rho, k. TypJ rhos (Var k) rho ->
181 AInd rhos rho (Var k) (Var k)" "AIndVar")
182 '("all rhos,rho,sig,r,s,r1,s1.
183 AInd rhos (rho to sig) r s ->
184 TypJ rhos r1 rho -> NInd rhos rho r1 s1 ->
185 AInd rhos sig (r r1) (s s1)" "AIndApp"))
186
187 ; Definition: "A"
188 ; ---------------
189 (add-global-assumption "ADef"
190 (pf "all rhos,rho,r,s. A rhos rho r s -> AInd rhos rho r s"))
191
192 (add-global-assumption "ADefRev"
193 (pf "all rhos,rho,r,s. AInd rhos rho r s -> A rhos rho r s"))