src/HOL/MiniML/W.thy
author nipkow
Mon, 11 Dec 1995 11:24:51 +0100
changeset 1402 b72ccd1cff02
parent 1400 5d909faf0e04
child 1476 608483c2122a
permissions -rw-r--r--
layout

(* Title:     HOL/MiniML/W.thy
   ID:        $Id$
   Author:    Dieter Nazareth and Tobias Nipkow
   Copyright  1995 TU Muenchen

Type inference algorithm W
*)

W = MiniML + 

types 
        result_W = "(subst * typ * nat)maybe"

(* type inference algorithm W *)
consts
	W :: [expr, typ list, nat] => result_W

primrec W expr
  W_Var	"W (Var i) a n = (if i < length a then Ok(id_subst, nth i a, n)
		          else Fail)"
  W_Abs	"W (Abs e) a n = ( (s,t,m) := W e ((TVar n)#a) (Suc n);
		           Ok(s, (s n) -> t, m) )"
  W_App	"W (App e1 e2) a n =
 		 ( (s1,t1,m1) := W e1 a n;
		   (s2,t2,m2) := W e2 ($s1 a) m1;
		   u := mgu ($s2 t1) (t2 -> (TVar m2));
		   Ok( $u o $s2 o s1, $u (TVar m2), Suc m2) )"
end