1300

1 
(* Title: HOL/MiniML/W.thy


2 
ID: $Id$


3 
Author: Dieter Nazareth and Tobias Nipkow


4 
Copyright 1995 TU Muenchen


5 


6 
Type inference algorithm W


7 
*)


8 


9 
W = MiniML +


10 


11 
types


12 
result_W = "(subst * type_expr * nat)maybe"


13 


14 
(* type inference algorithm W *)


15 
consts


16 
W :: "[expr, type_expr list, nat] => result_W"


17 


18 
primrec W expr


19 
W_Var "W (Var i) a n = (if i < length a then Ok(id_subst, nth i a, n)


20 
else Fail)"


21 
W_Abs "W (Abs e) a n = W e ((TVar n)#a) (Suc n) bind


22 
(%(s,t,m). Ok(s, Fun (s n) t, m) )"


23 
W_App "W (App e1 e2) a n =


24 
W e1 a n bind


25 
(%(s1,t1,m1). W e2 ($ s1 a) m1 bind


26 
(%(s2,t2,m2). mgu ($ s2 t1) (Fun t2 (TVar m2)) bind


27 
(%u. Ok( ($ u) o (($ s2) o s1), $ u (TVar m2), Suc m2) )))"


28 
end
