src/HOL/MiniML/W.thy
changeset 1900 c7a869229091
parent 1476 608483c2122a
child 2525 477c05586286
equal deleted inserted replaced
1899:0075a8d26a80 1900:c7a869229091
    14 (* type inference algorithm W *)
    14 (* type inference algorithm W *)
    15 consts
    15 consts
    16         W :: [expr, typ list, nat] => result_W
    16         W :: [expr, typ list, nat] => result_W
    17 
    17 
    18 primrec W expr
    18 primrec W expr
    19   W_Var "W (Var i) a n = (if i < length a then Ok(id_subst, nth i a, n)
    19   "W (Var i) a n = (if i < length a then Ok(id_subst, nth i a, n)
    20                           else Fail)"
    20                           else Fail)"
    21   W_Abs "W (Abs e) a n = ( (s,t,m) := W e ((TVar n)#a) (Suc n);
    21   "W (Abs e) a n = ( (s,t,m) := W e ((TVar n)#a) (Suc n);
    22                            Ok(s, (s n) -> t, m) )"
    22                            Ok(s, (s n) -> t, m) )"
    23   W_App "W (App e1 e2) a n =
    23   "W (App e1 e2) a n =
    24                  ( (s1,t1,m1) := W e1 a n;
    24                  ( (s1,t1,m1) := W e1 a n;
    25                    (s2,t2,m2) := W e2 ($s1 a) m1;
    25                    (s2,t2,m2) := W e2 ($s1 a) m1;
    26                    u := mgu ($s2 t1) (t2 -> (TVar m2));
    26                    u := mgu ($s2 t1) (t2 -> (TVar m2));
    27                    Ok( $u o $s2 o s1, $u (TVar m2), Suc m2) )"
    27                    Ok( $u o $s2 o s1, $u (TVar m2), Suc m2) )"
    28 end
    28 end