Debian Codegraph @

examples/tait/diplomarbeit_schlenker/omega.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: Omega
20 ; ================
21 ; contains definition of omega, OmegaPart, Mod, Hat etc.
22
23 ; Addition of type constants
24 ; --------------------------
25 ; In typ.scm
26
27 ; addition of type constants generally allowed
28
29 (define (add-tconst-name . x)
30 (if (null? x)
31 (myerror "add-tconst-name: arguments expected")
32 (do ((l x (cdr l)))
33 ((null? l))
34 (let ((string (car l)))
35 (if (and (string? string) (not (string=? string "")))
36 (if (is-used? string '() 'type-constant)
37 *the-non-printing-object*
38 (begin
39 (set! TYPE-CONSTANTS
40 (append TYPE-CONSTANTS
41 (list (list string))))
42 (add-token string 'tconst string)
43 (comment "ok, type constant " string " added")))
44 (myerror "add-tconst-name: string expected" string))))))
45
46 (define atc add-tconst-name)
47
48 (define (remove-tconst-name . x)
49 (define (rtc1 tconst-name)
50 (if (assoc tconst-name TYPE-CONSTANTS)
51 (begin (do ((l TYPE-CONSTANTS (cdr l))
52 (res '() (let* ((info (car l))
53 (string (car info)))
54 (if (string=? string tconst-name)
55 res
56 (cons info res)))))
57 ((null? l) (set! TYPE-CONSTANTS (reverse res))))
58 (remove-token tconst-name)
59 (comment
60 "ok, type vonstant " tconst-name " is removed"))
61 (myerror "remove-type-constant: type constant expected"
62 tconst-name)))
63 (do ((l x (cdr l)))
64 ((null? l) *the-non-printing-object*)
65 (rtc1 (car l))))
66
67 (define rtc remove-tconst-name)
68
69 ; Definition: "OmegaIn"
70 ; ---------------------
71 ; In pconst.scm
72
73 ; The treatment of constructors is to be extended to also cover
74 ; constructors for sumtypes.
75
76 ; Notice that we do not have dependent types. Hence we need a
77 ; numeral-string to be part of the name of a constructor. Form
78 ; e.g. "Arrow(Iota)(Iota)", which can be parsed. So
79 ; "OmegaInIota to Iota" would be a constructor name, of type
80 ; ((nat=>term)=>(nat=>term))=>omega.
81
82 ; nbe-reify and nbe-reflect are changed only in that the tag sumtype
83 ; is treated exactly as alg.
84
85 (define (initial-substring? string1 string2)
86 (and (<= (string-length string1) (string-length string2))
87 (string=? string1 (substring string2 0
88 (string-length string1)))))
89
90 ; (initial-substring? "ab" "abc")
91
92 (define (constr-name-to-inst-constructors name)
93 (let ((info (assoc name CONSTRUCTORS)))
94 (cond
95 (info (cadr info))
96 ((initial-substring? "OmegaIn" name)
97 (let* ((typestring
98 (substring name (string-length "OmegaIn")
99 (string-length name)))
100 (typealg-numeral (pt typestring))
101 (type (typealg-numeral-to-type typealg-numeral))
102 (del-constr
103 (eval-once (lambda () (constr-name-to-constr name))))
104 (obj
105 (nbe-make-object
106 (mk-arrow type (py "omega"))
107 (lambda (obj1)
108 (nbe-make-object (py "omega")
109 (nbe-make-constr-value
110 name (list obj1) del-constr)))))
111 (constr (make-const obj name 'constr
112 (mk-arrow type (py "omega"))
113 empty-subst 1 'const)))
114 (list (list empty-subst constr))))
115 (else
116 (myerror
117 "constr-name-to-inst-constructors: constructor name expected"
118 name)))))
119
120 (define (constr-name? string)
121 (or (assoc string CONSTRUCTORS)
122 (and
123 (initial-substring? "OmegaIn" string)
124 (typealg-numeral?
125 (pt (substring
126 string (string-length "OmegaIn")
127 (string-length string)))))))
128
129 (define (constr-name-and-tsubst-to-constr name tsubst)
130 (let ((info (assoc name CONSTRUCTORS)))
131 (cond
132 (info
133 (let ((info1 (assoc-wrt substitution-equal? tsubst
134 (cadr info))))
135 (if info1
136 (cadr info1)
137 (myerror "constr-name-and-tsubst-to-constr: unknown tsubst"
138 tsubst "for constructor" name))))
139 ((initial-substring? "OmegaIn" name)
140 (let* ((typestring
141 (substring name (string-length "OmegaIn")
142 (string-length name)))
143 (typealg-numeral (pt typestring))
144 (type (typealg-numeral-to-type typealg-numeral))
145 (del-constr
146 (eval-once (lambda () (constr-name-to-constr name))))
147 (obj
148 (nbe-make-object
149 (mk-arrow type (py "omega"))
150 (lambda objs
151 (nbe-make-object (py "omega")
152 (nbe-make-constr-value
153 name objs del-constr)))))
154 (constr (make-const obj name 'constr (mk-arrow type
155 (py "omega"))
156 empty-subst 1 'const)))
157 constr))
158 (else
159 (myerror
160 "constr-name-and-tsubst-to-constr: constructor name expected"
161 name)))))
162
163 (define (constr-name-to-constr name . rest)
164 (cond
165 ((string? name)
166 (let ((tsubst (if (null? rest) empty-subst (car rest))))
167 (constr-name-and-tsubst-to-constr name tsubst)))
168 ((and (pair? name) (string=? "Ex-Intro" (car name)))
169 (let ((ex-formula
170 (if (pair? (cdr name))
171 (cadr name)
172 (myerror "constr-name-to-constr: name expected" name)))
173 (opt-pvar-to-tvar (cddr name)))
174 (apply ex-formula-to-ex-intro-const
175 (cons ex-formula opt-pvar-to-tvar))))
176 ((and (pair? name) (string=? "Intro" (car name)))
177 (let ((i (if (pair? (cdr name))
178 (cadr name)
179 (myerror "constr-name-to-constr: name expected" name)))
180 (idpc (if (pair? (cddr name))
181 (caddr name)
182 (myerror "constr-name-to-constr: name expected"
183 name)))
184 (opt-pvar-to-tvar (cdddr name)))
185 (apply number-and-idpredconst-to-intro-const
186 (cons i (cons idpc opt-pvar-to-tvar)))))
187 (else (myerror "constr-name-to-constr: name expected" name))))
188
189 ; Definition: "OmegaOut"
190 ; ----------------------
191 ; The treatment of program constants is to be extended to also allow
192 ; the infinitely many program constants OmegaOut... with ... a
193 ; string denoting a typealg-numeral.
194
195 (define (pconst-name-to-pconst name)
196 (let ((info (assoc name PROGRAM-CONSTANTS)))
197 (cond
198 (info (cadr info))
199 ((initial-substring? "OmegaOut" name)
200 (let* ((typestring
201 (substring name (string-length "OmegaOut")
202 (string-length name)))
203 (typealg-numeral (pt typestring))
204 (type (typealg-numeral-to-type typealg-numeral)))
205 (type-to-omegaout-pconst type)))
206 (else (myerror "pconst-name-to-pconst: pconst name expected"
207 name)))))
208
209 (define (type-to-omegaout-pconst type)
210 (let* ((typealg-numeral (type-to-typealg-numeral type))
211 (string (term-to-string typealg-numeral))
212 (name (string-append "OmegaOut" string)))
213 (make-const
214 (nbe-make-object
215 (mk-arrow (py "omega") type) (type-to-omegaout-value type))
216 name 'pconst (mk-arrow (py "omega") type) empty-subst 1 'const)))
217
218 (define (type-to-omegaout-value type)
219 (lambda (obj)
220 (let ((val (nbe-object-to-value obj)))
221 (cond
222 ((nbe-fam-value? val) ;reproduce
223 (let* ((op-obj (nbe-reflect (nbe-term-to-termfam
224 (make-term-in-const-form
225 (type-to-omegaout-pconst type)))))
226 (op-val (nbe-object-to-value op-obj)))
227 (op-val obj)))
228 ((nbe-constr-value? val)
229 (let* ((name (nbe-constr-value-to-name val))
230 (typestring1
231 (substring
232 name (string-length "OmegaIn")
233 (string-length name)))
234 (typealg-numeral1 (pt typestring1))
235 (type1 (typealg-numeral-to-type typealg-numeral1)))
236 (if (equal? type1 type)
237 (car (nbe-constr-value-to-args val))
238 (nbe-reflect
239 (nbe-make-termfam
240 type (lambda (k)
241 (type-to-canonical-inhabitant type)))))))
242 (else
243 (myerror "type-to-omegaout-value" "unexpected object" obj))))))
244
245 (define (pconst-name-to-comprules name)
246 (let ((info (assoc name PROGRAM-CONSTANTS)))
247 (cond
248 (info (caddr info))
249 ((initial-substring? "OmegaOut" name) '())
250 (else (myerror "pconst-name-to-comprules: pconst name expected"
251 name)))))
252
253 (define (pconst-name-to-rewrules name)
254 (let ((info (assoc name PROGRAM-CONSTANTS)))
255 (cond
256 (info (cadddr info))
257 ((initial-substring? "OmegaOut" name) '())
258 (else (myerror "pconst-name-to-rewrules: pconst name expected"
259 name)))))
260
261 (define (pconst-name-to-inst-objs name)
262 (let ((info (assoc name PROGRAM-CONSTANTS)))
263 (cond
264 (info (car (cddddr info)))
265 ((initial-substring? "OmegaOut" name) '())
266 (else (myerror "pconst-name-to-inst-objs: pconst name expected"
267 name)))))
268
269 (define (pconst-name-and-tsubst-to-object name tsubst)
270 (let ((info (assoc name PROGRAM-CONSTANTS)))
271 (cond
272 (info
273 (let ((info1
274 (assoc-wrt substitution-equal? tsubst
275 (car (cddddr info)))))
276 (if info1
277 (cadr info1)
278 (let ((pconst (pconst-name-to-pconst name)))
279 (const-substitute pconst tsubst #f)
280 ;updates PROGRAM-CONSTANTS
281 (pconst-name-and-tsubst-to-object name tsubst)))))
282 ((initial-substring? "OmegaOut" name)
283 (let* ((typestring
284 (substring name (string-length "OmegaOut")
285 (string-length name)))
286 (typealg-numeral (pt typestring))
287 (type (typealg-numeral-to-type typealg-numeral)))
288 (nbe-make-object
289 (mk-arrow (py "omega") type)
290 (type-to-omegaout-value type))))
291 (else
292 (myerror "pconst-name-and-tsubst-to-object: pconst name expected"
293 name)))))
294
295 (define (pconst-name-to-external-code name)
296 (let ((info (assoc name PROGRAM-CONSTANTS)))
297 (cond
298 (info (let ((info1 (cdr (cddddr info))))
299 (if (pair? info1)
300 (car info1)
301 #f)))
302 ((initial-substring? "OmegaOut" name) #f)
303 (else
304 (myerror "pconst-name-to-external-code: pconst name expected"
305 name)))))
306
307 ; Empty-Test
308 ; ----------
309 ; const-substitute now needs an initial test whether the type
310 ; substitution is empty.
311
312 (define (const-substitute const tsubst
313 update-of-program-constants-done?)
314 (if
315 (null? tsubst)
316 const
317 (let* ((obj-or-arity (const-to-object-or-arity const))
318 (name (const-to-name const))
319 (uninst-type (const-to-uninst-type const))
320 (orig-tsubst (const-to-tsubst const))
321 (t-deg (const-to-t-deg const))
322 (token-type (const-to-token-type const))
323 (type-info-or-repro-formulas
324 (const-to-type-info-or-repro-formulas const))
325 (composed-tsubst
326 (compose-t-substitutions orig-tsubst tsubst))
327 (tvars (const-to-tvars const))
328 (restricted-tsubst
329 (restrict-substitution-to-args composed-tsubst tvars)))
330 (case (const-to-kind const)
331 ((constr)
332 (if
333 (or (string=? "Ex-Intro" (const-to-name const))
334 (string=? "Intro" (const-to-name const)))
335 const
336 ;else form new-constr with restricted-subst. If not yet done,
337 ;update CONSTRUCTORS, via computing for all simalgs and all of
338 ;their constructors the new object, type etc. Return new-constr
339 (let* ((val-type (arrow-form-to-final-val-type uninst-type))
340 (alg-name (alg-form-to-name val-type))
341 (alg-names (alg-name-to-simalg-names alg-name))
342 (alg-names-with-typed-constr-names
343 (map (lambda (x)
344 (cons x (alg-name-to-typed-constr-names x)))
345 alg-names))
346 (assoc-list (constr-name-to-inst-constructors name))
347 (info (assoc-wrt substitution-equal?
348 restricted-tsubst assoc-list)))
349 (if
350 info
351 (cadr info) ;else update CONSTRUCTORS, return new-constr
352 (begin
353 (for-each ;of alg-names-with-typed-constr-names
354 (lambda (item)
355 (let ((typed-constr-names (cdr item)))
356 (for-each
357 ;of typed-constr-names, update CONSTRUCTORS
358 (lambda (y)
359 (let* ((constr-name (car y))
360 (type (cadr y))
361 (token-type1
362 (if (null? (cddr y)) 'const (caddr y)))
363 (argtypes (arrow-form-to-arg-types type))
364 (arity (length argtypes))
365 (new-type
366 (type-substitute type restricted-tsubst))
367 (new-valtype
368 (arrow-form-to-final-val-type new-type))
369 (del-constr
370 (eval-once (lambda ()
371 (constr-name-and-tsubst-to-constr
372 constr-name restricted-tsubst))))
373 (obj
374 (nbe-make-object
375 new-type
376 (if
377 (zero? arity)
378 (nbe-make-constr-value
379 constr-name '() del-constr)
380 (nbe-curry
381 (lambda objs ;as many as argtypes
382 (nbe-make-object
383 new-valtype
384 (nbe-make-constr-value
385 constr-name objs del-constr)))
386 new-type
387 arity))))
388 (constr
389 (make-const obj constr-name 'constr type
390 restricted-tsubst 1 token-type1))
391 (constrs-exept-name
392 (do ((l CONSTRUCTORS (cdr l))
393 (res '() (if (string=? (caar l) constr-name)
394 res
395 (cons (car l) res))))
396 ((null? l) (reverse res))))
397 (prev-alist-for-name
398 (let ((info (assoc constr-name CONSTRUCTORS)))
399 (if info
400 (cadr info)
401 (myerror
402 "const-substitute: constr expected"
403 constr-name))))
404 (new-alist-for-name
405 (cons (list restricted-tsubst constr)
406 prev-alist-for-name)))
407 (set! CONSTRUCTORS
408 (cons (list constr-name new-alist-for-name)
409 constrs-exept-name))))
410 typed-constr-names)))
411 alg-names-with-typed-constr-names)
412 (constr-name-and-tsubst-to-constr name restricted-tsubst))))))
413 ((pconst)
414 ;form new-pconst with restricted-tsubst. If not yet done, update
415 ;PROGRAM-CONSTANTS with new object for restricted-tsubst,
416 ;return new-pconst.
417 (let* ((new-pconst (make-const obj-or-arity
418 name
419 'pconst
420 uninst-type
421 restricted-tsubst
422 t-deg
423 token-type))
424 (assoc-list (pconst-name-to-inst-objs name))
425 (info (assoc-wrt substitution-equal?
426 restricted-tsubst assoc-list)))
427 (if
428 (or update-of-program-constants-done? info)
429 new-pconst ;else update PROGRAM-CONSTANTS, then return new-pconst
430 (let* ((uninst-const (pconst-name-to-pconst name))
431 (comprules (pconst-name-to-comprules name))
432 (rewrules (pconst-name-to-rewrules name))
433 (external-code (pconst-name-to-external-code name))
434 (obj (if external-code
435 (nbe-pconst-and-tsubst-and-rules-to-object
436 const restricted-tsubst comprules rewrules
437 external-code)
438 (nbe-pconst-and-tsubst-and-rules-to-object
439 const restricted-tsubst comprules rewrules)))
440 (pconsts-exept-name
441 (do ((l PROGRAM-CONSTANTS (cdr l))
442 (res '() (if (string=? (caar l) name)
443 res
444 (cons (car l) res))))
445 ((null? l) (reverse res))))
446 (prev-alist-for-name (pconst-name-to-inst-objs name))
447 (new-alist-for-name (cons (list restricted-tsubst obj)
448 prev-alist-for-name)))
449 (set! PROGRAM-CONSTANTS
450 (cons (list name uninst-const comprules rewrules
451 new-alist-for-name)
452 pconsts-exept-name))
453 new-pconst))))
454 ((fixed-rules)
455 (cond
456 ((string=? "Rec" name)
457 (let* ((param-types (rec-const-to-param-types const))
458 (f (length param-types))
459 (arg-types (arrow-form-to-arg-types uninst-type))
460 (step-types-and-alg-type (list-tail arg-types f))
461 (step-types
462 (list-head step-types-and-alg-type
463 (- (length step-types-and-alg-type) 1)))
464 (alg-type (car (last-pair arg-types)))
465 (alg-name (alg-form-to-name alg-type))
466 (uninst-arrow-types (rec-const-to-uninst-arrow-types const))
467 (alg-types (map arrow-form-to-arg-type uninst-arrow-types))
468 (alg-names (map alg-form-to-name alg-types))
469 (uninst-recop-types
470 (map (lambda (x)
471 (apply mk-arrow
472 (append param-types step-types (list x))))
473 uninst-arrow-types))
474 (alg-names-with-uninst-recop-types
475 (map (lambda (x y) (list x y))
476 alg-names uninst-recop-types))
477 (simalg-names (alg-name-to-simalg-names alg-name))
478 (sorted-alg-names (list-transform-positive simalg-names
479 (lambda (x) (member x alg-names))))
480 (typed-constr-names
481 (apply append (map alg-name-to-typed-constr-names
482 sorted-alg-names)))
483 (constr-names (map car typed-constr-names))
484 (uninst-recop-type
485 (cadr (assoc alg-name alg-names-with-uninst-recop-types)))
486 (inst-recop-type (type-substitute uninst-recop-type
487 restricted-tsubst)))
488 (apply alg-name-etc-to-rec-const
489 (append (list alg-name uninst-recop-type restricted-tsubst
490 inst-recop-type f constr-names
491 alg-names-with-uninst-recop-types)
492 type-info-or-repro-formulas))))
493 ((string=? "Cases" name)
494 (let* ((param-types (cases-const-to-param-types const))
495 (f (length param-types))
496 (arg-types (arrow-form-to-arg-types uninst-type))
497 (val-type (arrow-form-to-final-val-type uninst-type))
498 (step-types-and-alg-type (list-tail arg-types f))
499 (step-types
500 (list-head step-types-and-alg-type
501 (- (length step-types-and-alg-type) 1)))
502 (alg-type (car (last-pair arg-types)))
503 (alg-name (alg-form-to-name alg-type))
504 (uninst-arrow-type (make-arrow alg-type val-type))
505 (uninst-casesop-type
506 (apply mk-arrow (append param-types step-types
507 (list uninst-arrow-type))))
508 (typed-constr-names
509 (alg-name-to-typed-constr-names alg-name))
510 (constr-names (map car typed-constr-names)))
511 (apply
512 make-const
513 (append
514 (list (apply
515 cases-at (append (list alg-name restricted-tsubst f
516 constr-names uninst-casesop-type)
517 type-info-or-repro-formulas))
518 "Cases" 'fixed-rules uninst-type restricted-tsubst
519 1 'const)
520 type-info-or-repro-formulas))))
521 ((string=? "=" name) const)
522 ((string=? "E" name) const)
523 ((string=? "Ex-Elim" name) const)
524 (else (myerror "const-substitute: fixed rule name expected"
525 name))))
526 (else (myerror "const-substitute: unknown kind"
527 (const-to-kind const)))))))
528 ; Nbe
529 ; ---
530 ; In term.scm
531
532 (define (nbe-reify obj)
533 (let ((type (nbe-object-to-type obj))
534 (value (nbe-object-to-value obj)))
535 (case (tag type)
536 ((alg)
537 (cond
538 ((nbe-constr-value? value)
539 (let ((args (nbe-constr-value-to-args value)))
540 (nbe-make-termfam
541 type
542 (lambda (k)
543 (apply mk-term-in-app-form
544 (cons (make-term-in-const-form
545 (nbe-constr-value-to-constr value))
546 (map (lambda (obj)
547 (nbe-fam-apply (nbe-reify obj) k))
548 args)))))))
549 ((nbe-fam-value? value) value)
550 (else (myerror "nbe-reify: unexpected value" value
551 "for alg type" type))))
552 ((tvar) (nbe-object-to-value obj))
553 ((tconst)
554 (if (or (string=? "existential" (tconst-to-name type))
555 (string=? "omega" (tconst-to-name type)))
556 (cond
557 ((nbe-constr-value? value)
558 (let ((args (nbe-constr-value-to-args value)))
559 (nbe-make-termfam
560 type
561 (lambda (k)
562 (apply mk-term-in-app-form
563 (cons (make-term-in-const-form
564 (nbe-constr-value-to-constr value))
565 (map (lambda (obj)
566 (nbe-fam-apply (nbe-reify obj) k))
567 args)))))))
568 ((nbe-fam-value? value) value)
569 (else (myerror "nbe-reify: unexpected value for type"
570 (tconst-to-name type)
571 value)))
572 (nbe-object-to-value obj)))
573 ((arrow)
574 (let ((type1 (arrow-form-to-arg-type type)))
575 (nbe-make-termfam
576 type
577 (lambda (k)
578 (let ((var-k (make-var type1 k 1 (default-var-name type1))))
579 (make-term-in-abst-form
580 var-k (nbe-fam-apply
581 (nbe-reify
582 (nbe-object-apply
583 obj
584 (nbe-reflect (nbe-term-to-termfam
585 (make-term-in-var-form var-k)))))
586 (+ k 1))))))))
587 ((star)
588 (nbe-make-termfam
589 type
590 (lambda (k)
591 (make-term-in-pair-form
592 (nbe-fam-apply (nbe-reify (nbe-object-car obj)) k)
593 (nbe-fam-apply (nbe-reify (nbe-object-cdr obj)) k)))))
594 (else (myerror "nbe-reify: type expected" type)))))
595
596 ; Definition: "omega"
597 ; -------------------
598 ; The parser cannot handle these constructor names. However,
599 ; we want that at least "OmegaInIota" is known to the parser.
600
601 (add-tconst-name "omega")
602
603 (add-var-name "a" "b" "c" (py "omega"))
604 (add-var-name "as" "bs" (py "list omega"))
605
606 (add-token "OmegaInIota"
607 'const (const-to-token-value
608 (constr-name-to-constr "OmegaInIota")))
609
610 ; We want to be able to overwrite the value of a pconst, assuming
611 ; that there are no type parameters in pconst,
612
613 (define (overwrite-pconst name val)
614 (let* ((uninst-pconst (pconst-name-to-pconst name))
615 (type (const-to-type uninst-pconst))
616 (obj (nbe-make-object type val))
617 (assoc-list (pconst-name-to-inst-objs name))
618 (external-code (pconst-name-to-external-code name))
619 (pconsts-exept-name
620 (do ((l PROGRAM-CONSTANTS (cdr l))
621 (res '() (if (string=? (caar l) name)
622 res
623 (cons (car l) res))))
624 ((null? l) (reverse res))))
625 (new-alist-for-name
626 (map (lambda (x) (if (equal? empty-subst (car x))
627 (list empty-subst obj) x))
628 assoc-list)))
629 (set! PROGRAM-CONSTANTS
630 (cons (if external-code
631 (list name uninst-pconst '() '()
632 new-alist-for-name external-code)
633 (list name uninst-pconst '() '()
634 new-alist-for-name))
635 pconsts-exept-name))))
636
637 ; Definition: "OmegaPart"
638 ; -----------------------
639 (add-program-constant "OmegaPart" (py "omega=>type") 1)
640
641 ; OmegaPart applied to a constr-value returns the typealg-numeral.
642
643 (define (omegapart-value obj)
644 (let ((val (nbe-object-to-value obj)))
645 (cond
646 ((nbe-fam-value? val) ;reproduce
647 (nbe-reflect
648 (nbe-make-termfam
649 (make-alg "type")
650 (lambda (k)
651 (mk-term-in-app-form
652 (make-term-in-const-form omegapart-pconst)
653 (nbe-fam-apply (nbe-reify obj) k))))))
654 ((nbe-constr-value? val)
655 (let* ((name (nbe-constr-value-to-name val))
656 (typestring
657 (substring name (string-length "OmegaIn")
658 (string-length name)))
659 (typealg-numeral (pt typestring)))
660 (nbe-reflect
661 (nbe-make-termfam
662 (make-alg "type")
663 (lambda (k) typealg-numeral)))))
664 (else (myerror "omegapart-value" "unexpected object" obj)))))
665
666 (define omegapart-pconst
667 (make-const
668 (nbe-make-object (py "omega=>type") omegapart-value)
669 "OmegaPart" 'pconst (py "omega=>type") empty-subst 1 'const))
670
671 (overwrite-pconst "OmegaPart" omegapart-value)
672
673 ; Definition: Hat
674 ; ---------------
675 (add-program-constant "Hat"
676 (py "type=>type=>(omega=>omega)=>omega"))
677
678 ; For (hat-value type-obj1 type-obj2 fct-obj) check whether
679 ; type-obj1 and type-obj2 come from typealg-numerals rho and sig.
680 ; If so, form the object for
681 ; In_{rho=>sig}(Out_sig o fct-term o In_rho)
682
683 (define (hat-value obj1)
684 (nbe-make-object
685 (py "type=>(omega=>omega)=>omega")
686 (lambda (obj2)
687 (nbe-make-object
688 (py "(omega=>omega)=>omega")
689 (lambda (fct-obj)
690 (let* ((reified-obj1 (nbe-reify obj1))
691 (extracted-term1 (nbe-extract reified-obj1))
692 (reified-obj2 (nbe-reify obj2))
693 (extracted-term2 (nbe-extract reified-obj2))
694 (reified-fct-obj (nbe-reify fct-obj))
695 (extracted-fct-term (nbe-extract reified-fct-obj)))
696 (if ;the first two extracted terms are typealg-numerals
697 (and (typealg-numeral? extracted-term1)
698 (typealg-numeral? extracted-term2))
699 (let* ((omegain-constr
700 (typealg-numeral-to-omegain-constr
701 (mk-term-in-app-form
702 (make-term-in-const-form
703 (constr-name-to-constr "Arrow"))
704 extracted-term1 extracted-term2)))
705 (omegain-constr1
706 (typealg-numeral-to-omegain-constr
707 extracted-term1))
708 (omegaout-pconst2
709 (type-to-omegaout-pconst
710 (typealg-numeral-to-type extracted-term2)))
711 (type1 (typealg-numeral-to-type extracted-term1))
712 (new-var (type-to-new-var type1))
713 (free (term-to-free extracted-fct-term))
714 (objs (map (lambda (x) (nbe-reflect
715 (nbe-term-to-termfam
716 (make-term-in-var-form x)))) free))
717 (bindings (nbe-make-bindings free objs))
718 (abst-term
719 (make-term-in-abst-form
720 new-var
721 (make-term-in-app-form
722 (make-term-in-const-form omegaout-pconst2)
723 (make-term-in-app-form
724 extracted-fct-term
725 (make-term-in-app-form
726 (make-term-in-const-form omegain-constr1)
727 (make-term-in-var-form new-var))))))
728 (final-term (make-term-in-app-form
729 (make-term-in-const-form omegain-constr)
730 abst-term)))
731 (nbe-term-to-object final-term bindings))
732 ;else reproduce
733 (let* ((obj (nbe-reflect (nbe-term-to-termfam
734 (make-term-in-const-form hat-pconst))))
735 (val (nbe-object-to-value obj)))
736 (apply (nbe-uncurry val 3)
737 (list obj1 obj2 fct-obj))))))))))
738
739 (define (typealg-numeral-to-omegain-constr typealg-numeral)
740 (constr-name-to-constr (string-append
741 "OmegaIn" (term-to-string typealg-numeral))))
742
743 (define hat-pconst
744 (let ((hat-type (py "type=>type=>(omega=>omega)=>omega")))
745 (make-const (nbe-make-object hat-type hat-value)
746 "Hat" 'pconst hat-type empty-subst 0 'const)))
747
748 (overwrite-pconst "Hat" hat-value)
749
750 ; Definition: Mod
751 ; ---------------
752 (add-program-constant "Mod" (py "omega=>omega=>omega"))
753
754 ; For (mod-value obj) check whether obj is a constr-object of the
755 ; form In_{rho=>sig} s. If so, form the object for
756 ; In_sig o s o Out_rho.
757 ; Else reproduce.
758
759 (define (mod-value obj1)
760 (let ((val1 (nbe-object-to-value obj1)))
761 (if ;obj1 is a constr-object of the form In_{rho=>sig} arg
762 (and (nbe-constr-value? val1)
763 (let* ((args (nbe-constr-value-to-args val1))
764 (arg (if (= 1 (length args))
765 (car args)
766 (myerror "mod-value" "unexpected object" obj1)))
767 (type (nbe-object-to-type arg)))
768 (not (equal? (py "nat=>term") type))))
769 (let* ((constr (nbe-constr-value-to-constr val1))
770 (args (nbe-constr-value-to-args val1))
771 (type (nbe-object-to-type (car args)))
772 (type1 (arrow-form-to-arg-type type))
773 (type2 (arrow-form-to-val-type type))
774 (typealg-numeral1 (type-to-typealg-numeral type1))
775 (typealg-numeral2 (type-to-typealg-numeral type2))
776 (omegaout-pconst1
777 (type-to-omegaout-pconst
778 (typealg-numeral-to-type typealg-numeral1)))
779 (omegain-constr2
780 (typealg-numeral-to-omegain-constr typealg-numeral2))
781 (new-var (type-to-new-var (py "omega")))
782 (arg-term (nbe-extract (nbe-reify (car args))))
783 (free (term-to-free arg-term))
784 (objs (map (lambda (x) (nbe-reflect
785 (nbe-term-to-termfam
786 (make-term-in-var-form x)))) free))
787 (bindings (nbe-make-bindings free objs))
788 (abst-term
789 (make-term-in-abst-form
790 new-var
791 (make-term-in-app-form
792 (make-term-in-const-form omegain-constr2)
793 (make-term-in-app-form
794 arg-term
795 (make-term-in-app-form
796 (make-term-in-const-form omegaout-pconst1)
797 (make-term-in-var-form new-var)))))))
798 (nbe-term-to-object abst-term bindings))
799 ;else reproduce
800 (let* ((obj (nbe-reflect (nbe-term-to-termfam
801 (make-term-in-const-form mod-pconst))))
802 (val (nbe-object-to-value obj)))
803 (val obj1)))))
804
805 (define mod-pconst
806 (make-const
807 (nbe-make-object (py "omega=>omega=>omega") mod-value)
808 "Mod" 'pconst (py "omega=>omega=>omega") empty-subst 0 'const))
809
810 (overwrite-pconst "Mod" mod-value)
811
812 ; Definition: ModIota
813 ; -------------------
814 (add-program-constant "ModIota" (py "omega=>nat=>term"))
815
816 ; (modiota-val obj1) checks whether obj1 is a constructor value of
817 ; type Iota. If so, return its argument. Else reproduce.
818
819 (define (modiota-value obj1)
820 (let ((val1 (nbe-object-to-value obj1)))
821 (if ;constructor values, of type Iota
822 (and (nbe-constr-value? val1)
823 (let* ((args (nbe-constr-value-to-args val1))
824 (arg (if (= 1 (length args))
825 (car args)
826 (myerror "mod-value" "unexpected object" obj1)))
827 (type (nbe-object-to-type arg)))
828 (equal? (py "nat=>term") type)))
829 (car (nbe-constr-value-to-args val1))
830 ;else reproduce
831 (let* ((obj (nbe-reflect (nbe-term-to-termfam
832 (make-term-in-const-form modiota-pconst))))
833 (val (nbe-object-to-value obj)))
834 (val obj1)))))
835
836 (define modiota-pconst
837 (make-const
838 (nbe-make-object (py "omega=>nat=>term") modiota-value)
839 "ModIota" 'pconst (py "omega=>nat=>term") empty-subst 0 'const))
840
841 (overwrite-pconst "ModIota" modiota-value)
842
843 ; Definition: h
844 ; -------------
845 (add-var-name "h" (py "omega=>omega"))
846
847 ; Lemma: "TypeHat"
848 ; ----------------
849 (add-global-assumption "TypeHat"
850 (pf "all rho,sig,h^ OmegaPart(Hat rho sig h^)=(rho to sig)"))
851
852
853 (add-var-name "g" (py "nat=>term"))
854
855 ; Definition: InOut
856 ; -----------------
857 (add-program-constant "InOut" (py "type=>omega=>omega"))
858
859 ; Lemma: "InOutId"
860 ; ----------------
861 (add-global-assumption "InOutId"
862 (pf "all sig,a^.OmegaPart a^ =sig -> Equal(InOut sig a^)a^"))
863
864 ; Lemma: "InOutPart"
865 ; ------------------
866 (add-global-assumption
867 "InOutPart" (pf "all sig,a^ OmegaPart(InOut sig a^)=sig"))
868
869 ; Lemma: "ModHat"
870 ; ---------------
871 (add-global-assumption "ModHat"
872 (pf "all rho,sig,h^,a^ Equal(Mod(Hat rho sig h^)a^)
873 (InOut sig(h^(InOut rho a^)))"))
874
875
876 ; Subsection: STotal
877 ; ==================
878
879 ; Definition: "OmegaOutIota"
880 ; --------------------------
881 (add-token "OmegaOutIota"
882 'const (const-to-token-value
883 (pconst-name-to-pconst "OmegaOutIota")))
884
885 ; Lemma: "OmegaOutIota"
886 ; ---------------------
887 (add-global-assumption
888 "STotalNilOmega" (pf "STotal(Nil omega)"))
889
890 ; Lemma: "OmegaOutIota"
891 ; ---------------------
892 (add-global-assumption
893 "STotalConsOmega" (pf "all a^,as^.STotal as^ -> STotal(a^ ::as^)"))
894