src/HOL/MiniML/W.thy
author nipkow
Wed, 22 May 1996 17:11:54 +0200
changeset 1757 f7a573c46611
parent 1476 608483c2122a
child 1900 c7a869229091
permissions -rw-r--r--
Added the second half of the W/I correspondence.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1300
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     1
(* Title:     HOL/MiniML/W.thy
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     2
   ID:        $Id$
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     3
   Author:    Dieter Nazareth and Tobias Nipkow
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     4
   Copyright  1995 TU Muenchen
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     5
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     6
Type inference algorithm W
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     7
*)
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     8
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
     9
W = MiniML + 
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    10
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    11
types 
1400
5d909faf0e04 Introduced Monad syntax Pat := Val; Cont
nipkow
parents: 1376
diff changeset
    12
        result_W = "(subst * typ * nat)maybe"
1300
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    13
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    14
(* type inference algorithm W *)
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    15
consts
1476
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    16
        W :: [expr, typ list, nat] => result_W
1300
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    17
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    18
primrec W expr
1476
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    19
  W_Var "W (Var i) a n = (if i < length a then Ok(id_subst, nth i a, n)
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    20
                          else Fail)"
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    21
  W_Abs "W (Abs e) a n = ( (s,t,m) := W e ((TVar n)#a) (Suc n);
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    22
                           Ok(s, (s n) -> t, m) )"
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    23
  W_App "W (App e1 e2) a n =
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    24
                 ( (s1,t1,m1) := W e1 a n;
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    25
                   (s2,t2,m2) := W e2 ($s1 a) m1;
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    26
                   u := mgu ($s2 t1) (t2 -> (TVar m2));
608483c2122a expanded tabs; incorporated Konrad's changes
clasohm
parents: 1402
diff changeset
    27
                   Ok( $u o $s2 o s1, $u (TVar m2), Suc m2) )"
1300
c7a8f374339b New theory: type inference for let-free MiniML
nipkow
parents:
diff changeset
    28
end