| 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")) |