174 |
174 |
175 (*Indexnames can be quickly renamed by adding an offset to the integer part, |
175 (*Indexnames can be quickly renamed by adding an offset to the integer part, |
176 for resolution.*) |
176 for resolution.*) |
177 type indexname = string*int; |
177 type indexname = string*int; |
178 |
178 |
179 (* Types are classified by classes. *) |
179 (* Types are classified by sorts. *) |
180 type class = string; |
180 type class = string; |
181 type sort = class list; |
181 type sort = class list; |
182 |
182 |
183 (* The sorts attached to TFrees and TVars specify the sort of that variable *) |
183 (* The sorts attached to TFrees and TVars specify the sort of that variable *) |
184 datatype typ = Type of string * typ list |
184 datatype typ = Type of string * typ list |
191 val op ---> = foldr (op -->); |
191 val op ---> = foldr (op -->); |
192 |
192 |
193 |
193 |
194 (*terms. Bound variables are indicated by depth number. |
194 (*terms. Bound variables are indicated by depth number. |
195 Free variables, (scheme) variables and constants have names. |
195 Free variables, (scheme) variables and constants have names. |
196 An term is "closed" if there every bound variable of level "lev" |
196 An term is "closed" if every bound variable of level "lev" |
197 is enclosed by at least "lev" abstractions. |
197 is enclosed by at least "lev" abstractions. |
198 |
198 |
199 It is possible to create meaningless terms containing loose bound vars |
199 It is possible to create meaningless terms containing loose bound vars |
200 or type mismatches. But such terms are not allowed in rules. *) |
200 or type mismatches. But such terms are not allowed in rules. *) |
201 |
201 |
444 | loose_bvar1(Abs(_,_,t),k) = loose_bvar1(t,k+1) |
444 | loose_bvar1(Abs(_,_,t),k) = loose_bvar1(t,k+1) |
445 | loose_bvar1 _ = false; |
445 | loose_bvar1 _ = false; |
446 |
446 |
447 (*Substitute arguments for loose bound variables. |
447 (*Substitute arguments for loose bound variables. |
448 Beta-reduction of arg(n-1)...arg0 into t replacing (Bound i) with (argi). |
448 Beta-reduction of arg(n-1)...arg0 into t replacing (Bound i) with (argi). |
449 Note that for ((x,y)c)(a,b), the bound vars in c are x=1 and y=0 |
449 Note that for ((%x y. c) a b), the bound vars in c are x=1 and y=0 |
450 and the appropriate call is subst_bounds([b,a], c) . |
450 and the appropriate call is subst_bounds([b,a], c) . |
451 Loose bound variables >=n are reduced by "n" to |
451 Loose bound variables >=n are reduced by "n" to |
452 compensate for the disappearance of lambdas. |
452 compensate for the disappearance of lambdas. |
453 *) |
453 *) |
454 fun subst_bounds (args: term list, t) : term = |
454 fun subst_bounds (args: term list, t) : term = |
488 |
488 |
489 (*insertion into list, optimized version for indexnames*) |
489 (*insertion into list, optimized version for indexnames*) |
490 fun ins_ix (x,xs) = if mem_ix (x, xs) then xs else x :: xs; |
490 fun ins_ix (x,xs) = if mem_ix (x, xs) then xs else x :: xs; |
491 |
491 |
492 (*Tests whether 2 terms are alpha-convertible and have same type. |
492 (*Tests whether 2 terms are alpha-convertible and have same type. |
493 Note that constants and Vars may have more than one type.*) |
493 Note that constants may have more than one type.*) |
494 fun (Const(a,T)) aconv (Const(b,U)) = a=b andalso T=U |
494 fun (Const(a,T)) aconv (Const(b,U)) = a=b andalso T=U |
495 | (Free(a,T)) aconv (Free(b,U)) = a=b andalso T=U |
495 | (Free(a,T)) aconv (Free(b,U)) = a=b andalso T=U |
496 | (Var(v,T)) aconv (Var(w,U)) = eq_ix(v,w) andalso T=U |
496 | (Var(v,T)) aconv (Var(w,U)) = eq_ix(v,w) andalso T=U |
497 | (Bound i) aconv (Bound j) = i=j |
497 | (Bound i) aconv (Bound j) = i=j |
498 | (Abs(_,T,t)) aconv (Abs(_,U,u)) = t aconv u andalso T=U |
498 | (Abs(_,T,t)) aconv (Abs(_,U,u)) = t aconv u andalso T=U |
668 |
668 |
669 |
669 |
670 (**** Syntax-related declarations ****) |
670 (**** Syntax-related declarations ****) |
671 |
671 |
672 |
672 |
673 (*Dummy type for parsing. Will be replaced during type inference. *) |
673 (*Dummy type for parsing and printing. Will be replaced during type inference. *) |
674 val dummyT = Type("dummy",[]); |
674 val dummyT = Type("dummy",[]); |
675 |
675 |
676 (*scan a numeral of the given radix, normally 10*) |
676 (*scan a numeral of the given radix, normally 10*) |
677 fun scan_radixint (radix: int, cs) : int * string list = |
677 fun scan_radixint (radix: int, cs) : int * string list = |
678 let val zero = ord"0" |
678 let val zero = ord"0" |