Debian Codegraph @

examples/tait/diplomarbeit_schlenker/defsLamCalc.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 ;
12 ; NOTICE: Uncomment modules only when file is run on its own
13 ; ***********************************************************
14
15
16 ; ============================================
17 ; Section: Definition of the Lambda Calculus
18 ; ============================================
19 ; contains the basic definition for the simply typed lambda calculus
20 ; in de Bruijn style
21
22
23 ; Subsection: Definition of the Types and the Lambda-Terms
24 ; ========================================================
25
26 ; Definition: "type"
27 ; ------------------
28 ; the types of the lambda terms
29
30 (add-alg "type"
31 '("Iota" "type")
32 '("Arrow" "type=>type=>type"))
33
34 (add-var-name "rho" "sig" "tau" (py "type"))
35
36
37 ; ________________________ INTERNAL ________________________
38 ; Allows the infix notation with "to" instead of "Arrow"
39
40 (add-token
41 "to"
42 'pair-op
43 (lambda (x y)
44 (let* ((type1 (term-to-type x))
45 (type2 (term-to-type y))
46 (type (types-lub type1 type2)))
47 (mk-term-in-app-form
48 (make-term-in-const-form (constr-name-to-constr "Arrow"))
49 x y))))
50
51 (add-display
52 (py "type")
53 (lambda (x)
54 (let ((op (term-in-app-form-to-final-op x))
55 (args (term-in-app-form-to-args x)))
56 (if (and (term-in-const-form? op)
57 (string=? "Arrow"
58 (const-to-name
59 (term-in-const-form-to-const op)))
60 (= 2 (length args)))
61 (list 'pair-op "to"
62 (term-to-token-tree (car args))
63 (term-to-token-tree (cadr args)))
64 #f))))
65 ; _________________________________________________________
66
67
68 ; Definition: "term"
69 ; ------------------
70 ; represents lambda terms in "de Bruijn" style
71
72 (add-alg "term"
73 '("Var" "nat=>term")
74 '("App" "term=>term=>term")
75 '("Abs" "type=>term=>term"))
76
77 (add-var-name "r" "s" "t" (py "term"))
78
79 ; Definition: Lists of Terms
80 ; --------------------------
81 (add-var-name "rs" "ss" "ts" (py "list term"))
82
83
84 ; ________________________ INTERNAL ________________________
85 ; Allows the simplier notation for application without constructor
86
87 (add-new-application
88 (lambda (type) (equal? type (py "term")))
89 (lambda (term1 term2)
90 (mk-term-in-app-form (pt "App") term1 term2)))
91
92 (add-new-application-syntax
93 ; predicate
94 (lambda (term)
95 (and (term-in-app-form? term)
96 (let ((op (term-in-app-form-to-op term)))
97 (term-in-app-form? op)
98 (term=? (pt "App") (term-in-app-form-to-op op)))))
99 ; to arg
100 (lambda (term)
101 (term-in-app-form-to-arg term))
102 ; to op
103 (lambda (term)
104 (term-in-app-form-to-arg
105 (term-in-app-form-to-op term))))
106
107 ; Example
108 (define term1 (pt "Var 0(Abs tau(Var 3(Var 2)(Var 0)))"))
109 (pp term1)
110
111 (define rhos1
112 (pt "(rho to tau to sig)::rho::((tau to sig)to rho):"))
113 (pp rhos1)
114
115 (define revrhos1
116 (pt "((tau to sig)to rho)::rho::(rho to tau to sig):"))
117 (pp revrhos1)
118 ; _________________________________________________________
119
120
121 ; Subsection: Typechecking
122 ; ========================
123
124 ; Definition: "contexts"
125 ; ----------------------
126 ; contexts are used as simple (predefined) lists of elements
127 ; of type "type".
128
129 (add-var-name "rhos" "sigs" "taus" (py "list type"))
130
131 ; Definition: "Arrowtyp"
132 ; ----------------------
133 ; checks, if a type is an arrow type
134
135 (add-program-constant "Arrowtyp" (py "type=>boole") 1)
136 (add-computation-rule (pt "Arrowtyp Iota") (pt "False"))
137 (add-computation-rule (pt "Arrowtyp(rho to sig)") (pt "True"))
138
139 ; Definition: "Argtyp"
140 ; --------------------
141 ; returns the first part of an arrow type
142
143 (add-program-constant "Argtyp" (py "type=>type") 1)
144 (add-computation-rule (pt "Argtyp Iota") (pt "Iota"))
145 (add-computation-rule (pt "Argtyp(rho to sig)") (pt "rho"))
146
147 ; Definition: "Valtyp"
148 ; --------------------
149 ; returns the second part of an arrow type
150
151 (add-program-constant "Valtyp" (py "type=>type") 1)
152 (add-computation-rule (pt "Valtyp Iota") (pt "Iota"))
153 (add-computation-rule (pt "Valtyp(rho to sig)") (pt "sig"))
154
155 ; ________________________ INTERNAL ________________________
156 ; Numeral
157
158 (define (typealg-numeral-to-type typealg-numeral)
159 (let* ((op (term-in-app-form-to-final-op typealg-numeral))
160 (args (term-in-app-form-to-args typealg-numeral)))
161 (if (not (and (term-in-const-form? op)
162 (eq? 'constr (const-to-kind
163 (term-in-const-form-to-const op)))))
164 (myerror
165 "typealg-numeral-to-type" "constructor expected" op))
166 (let ((name (const-to-name (term-in-const-form-to-const op))))
167 (cond
168 ((string=? "Iota" name) (py "nat=>term"))
169 ((string=? "Arrow" name)
170 (if (= 2 (length args))
171 (make-arrow (typealg-numeral-to-type (car args))
172 (typealg-numeral-to-type (cadr args)))
173 (myerror
174 "typealg-numeral-to-type" "2 arguments expected"
175 typealg-numeral)))
176 (else (myerror "typealg-numeral-to-type"
177 "typealg numeral expected"
178 typealg-numeral))))))
179
180 (define (typealg-numeral? term)
181 ;should be done generally for algebras
182 (or
183 (and (term-in-const-form? term)
184 (string=? "Iota"
185 (const-to-name (term-in-const-form-to-const term))))
186 (and (term-in-app-form? term)
187 (let ((op (term-in-app-form-to-final-op term))
188 (args (term-in-app-form-to-args term)))
189 (and
190 (string=? "Arrow" (const-to-name
191 (term-in-const-form-to-const op)))
192 (= 2 (length args))
193 (typealg-numeral? (car args))
194 (typealg-numeral? (cadr args)))))))
195
196 (define (type-to-typealg-numeral type)
197 (if (not (arrow-form? type))
198 (myerror "type-to-typealg-numeral" "arrow form expected" type))
199 (let ((arg-type (arrow-form-to-arg-type type))
200 (val-type (arrow-form-to-val-type type)))
201 (if ;(equal? (py "nat=>term") type), that is
202 (and (alg-form? arg-type)
203 (alg-form? val-type)
204 (string=? "nat" (alg-form-to-name arg-type))
205 (string=? "term" (alg-form-to-name val-type)))
206 (make-term-in-const-form (constr-name-to-constr "Iota"))
207 (mk-term-in-app-form
208 (make-term-in-const-form (constr-name-to-constr "Arrow"))
209 (type-to-typealg-numeral arg-type)
210 (type-to-typealg-numeral val-type)))))
211 ; _________________________________________________________
212
213
214 ; Definition: "Typ"
215 ; -----------------
216 (add-program-constant "Typ" (py "list type=>term=>type") 1)
217
218 (add-computation-rule (pt "Typ(Nil type)(Var n)") (pt "Iota"))
219 (add-computation-rule (pt "Typ(rho::rhos)(Var 0)") (pt "rho"))
220 (add-computation-rule (pt "Typ(rho::rhos)(Var(Succ n))")
221 (pt "Typ rhos(Var n)"))
222 (add-computation-rule (pt "Typ rhos(r s)")
223 (pt "Valtyp(Typ rhos r)"))
224 (add-computation-rule (pt "Typ rhos(Abs rho r)")
225 (pt "rho to Typ(rho::rhos)r"))
226
227 ; Definition: "Cor"
228 ; -----------------
229 ; checks, if a term is correctly typed
230 ; with respect to a given context
231
232 (add-program-constant "Cor" (py "list type=>term=>boole") 1)
233
234 (add-computation-rule (pt "Cor rhos(Var n)") (pt "n<Lh rhos"))
235 (add-computation-rule (pt "Cor rhos(r s)")
236 (pt "Cor rhos r and Cor rhos s and
237 Typ rhos r=(Typ rhos s to Valtyp(Typ rhos r))"))
238 (add-computation-rule (pt "Cor rhos(Abs rho r)")
239 (pt "Cor(rho::rhos)r"))
240
241
242 ; Definition: "TypJ"
243 ; ------------------
244 ; Checks if a term has a given type with respect to a given context
245 ; (and if the term is correctly typed at all)
246
247 (add-program-constant "TypJ" (py "list type=>term=>type=>boole") 1)
248
249 (add-computation-rule (pt "TypJ rhos r rho")
250 (pt "Cor rhos r and Typ rhos r=rho"))