src/Pure/envir.ML
author paulson
Fri Feb 16 12:19:47 1996 +0100 (1996-02-16)
changeset 1500 b2de3b3277b8
parent 1460 5a6f2aabd538
child 2142 20f208ff085d
permissions -rw-r--r--
Elimination of fully-functorial style.
Type tactic changed to a type abbrevation (from a datatype).
Constructor tactic and function apply deleted.
wenzelm@247
     1
(*  Title:      Pure/envir.ML
clasohm@0
     2
    ID:         $Id$
wenzelm@247
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1988  University of Cambridge
clasohm@0
     5
*)
clasohm@0
     6
clasohm@0
     7
(*Environments
clasohm@0
     8
  Should take account that typ is part of variable name,
clasohm@0
     9
    otherwise two variables with same name and different types
clasohm@0
    10
    will cause errors!
clasohm@0
    11
*)
clasohm@0
    12
clasohm@0
    13
wenzelm@247
    14
signature ENVIR =
clasohm@0
    15
sig
clasohm@0
    16
  type 'a xolist
clasohm@0
    17
  exception ENVIR of string * indexname;
clasohm@0
    18
  datatype env = Envir of {asol: term xolist,
wenzelm@247
    19
                           iTs: (indexname * typ) list,
wenzelm@247
    20
                           maxidx: int}
clasohm@1460
    21
  val alist_of		: env -> (indexname * term) list
clasohm@1460
    22
  val alist_of_olist	: 'a xolist -> (indexname * 'a) list
clasohm@1460
    23
  val empty		: int->env
clasohm@1460
    24
  val is_empty		: env -> bool
clasohm@1460
    25
  val minidx		: env -> int option
clasohm@1460
    26
  val genvar		: string -> env * typ -> env * term
clasohm@1460
    27
  val genvars		: string -> env * typ list -> env * term list
clasohm@1460
    28
  val lookup		: env * indexname -> term option
clasohm@1460
    29
  val norm_term		: env -> term -> term
clasohm@1460
    30
  val null_olist	: 'a xolist
clasohm@1460
    31
  val olist_of_alist	: (indexname * 'a) list -> 'a xolist
clasohm@1460
    32
  val update		: (indexname * term) * env -> env
clasohm@1460
    33
  val vupdate		: (indexname * term) * env -> env
clasohm@0
    34
end;
clasohm@0
    35
paulson@1500
    36
structure Envir : ENVIR =
clasohm@0
    37
struct
clasohm@0
    38
clasohm@0
    39
(*association lists with keys in ascending order, no repeated keys*)
clasohm@0
    40
datatype 'a xolist = Olist of (indexname * 'a) list;
clasohm@0
    41
clasohm@0
    42
clasohm@0
    43
exception ENVIR of string * indexname;
wenzelm@247
    44
wenzelm@247
    45
(*look up key in ordered list*)
clasohm@0
    46
fun xsearch (Olist[], key) = None
clasohm@0
    47
  | xsearch (Olist ((keyi,xi)::pairs), key) =
clasohm@0
    48
      if xless(keyi,key) then xsearch (Olist pairs, key)
wenzelm@247
    49
      else if key=keyi then Some xi
clasohm@0
    50
      else None;
clasohm@0
    51
clasohm@0
    52
(*insert pair in ordered list, reject if key already present*)
clasohm@0
    53
fun xinsert_new (newpr as (key, x), Olist al) =
clasohm@0
    54
  let fun insert [] = [newpr]
wenzelm@247
    55
        | insert ((pair as (keyi,xi)) :: pairs) =
wenzelm@247
    56
            if xless(keyi,key) then pair :: insert pairs
wenzelm@247
    57
            else if key=keyi then
wenzelm@247
    58
                raise ENVIR("xinsert_new: already present",key)
wenzelm@247
    59
            else newpr::pair::pairs
clasohm@0
    60
  in  Olist (insert al)  end;
clasohm@0
    61
clasohm@0
    62
(*insert pair in ordered list, overwrite if key already present*)
clasohm@0
    63
fun xinsert (newpr as (key, x), Olist al) =
clasohm@0
    64
  let fun insert [] = [newpr]
wenzelm@247
    65
        | insert ((pair as (keyi,xi)) :: pairs) =
wenzelm@247
    66
            if xless(keyi,key) then pair :: insert pairs
wenzelm@247
    67
            else if key=keyi then newpr::pairs
wenzelm@247
    68
            else newpr::pair::pairs
clasohm@0
    69
  in  Olist (insert al)  end;
clasohm@0
    70
wenzelm@247
    71
(*apply function to the contents part of each pair*)
clasohm@0
    72
fun xmap f (Olist pairs) =
clasohm@0
    73
  let fun xmp [] = []
wenzelm@247
    74
        | xmp ((key,x)::pairs) = (key, f x) :: xmp pairs
clasohm@0
    75
  in Olist (xmp pairs)  end;
clasohm@0
    76
clasohm@0
    77
(*allows redefinition of a key by "join"ing the contents parts*)
clasohm@0
    78
fun xmerge_olists join (Olist pairsa, Olist pairsb) =
clasohm@0
    79
  let fun xmrg ([],pairsb) = pairsb
wenzelm@247
    80
        | xmrg (pairsa,[]) = pairsa
wenzelm@247
    81
        | xmrg ((keya,x)::pairsa, (keyb,y)::pairsb) =
wenzelm@247
    82
            if xless(keya,keyb) then
wenzelm@247
    83
                (keya,x) :: xmrg (pairsa, (keyb,y)::pairsb)
wenzelm@247
    84
            else if xless(keyb,keya) then
wenzelm@247
    85
                (keyb,y) :: xmrg ((keya,x)::pairsa, pairsb)
wenzelm@247
    86
            else (*equal*)  (keya, join(x,y)) :: xmrg (pairsa, pairsb)
clasohm@0
    87
  in  Olist (xmrg (pairsa,pairsb))  end;
clasohm@0
    88
clasohm@0
    89
val null_olist = Olist[];
clasohm@0
    90
clasohm@0
    91
fun alist_of_olist (Olist pairs) = pairs;
clasohm@0
    92
clasohm@0
    93
fun olist_of_alist pairs = foldr xinsert (pairs, Olist[]);
clasohm@0
    94
clasohm@0
    95
clasohm@0
    96
clasohm@0
    97
(*updating can destroy environment in 2 ways!!
clasohm@0
    98
   (1) variables out of range   (2) circular assignments
clasohm@0
    99
*)
clasohm@0
   100
datatype env = Envir of
wenzelm@247
   101
    {maxidx: int,               (*maximum index of vars*)
wenzelm@247
   102
     asol: term xolist,         (*table of assignments to Vars*)
wenzelm@247
   103
     iTs: (indexname*typ)list}  (*table of assignments to TVars*)
clasohm@0
   104
clasohm@0
   105
clasohm@0
   106
(*Generate a list of distinct variables.
clasohm@0
   107
  Increments index to make them distinct from ALL present variables. *)
clasohm@0
   108
fun genvars name (Envir{maxidx, asol, iTs}, Ts) : env * term list =
clasohm@0
   109
  let fun genvs (_, [] : typ list) : term list = []
clasohm@0
   110
        | genvs (n, [T]) = [ Var((name, maxidx+1), T) ]
clasohm@0
   111
        | genvs (n, T::Ts) =
wenzelm@247
   112
            Var((name ^ radixstring(26,"a",n), maxidx+1), T)
wenzelm@247
   113
            :: genvs(n+1,Ts)
clasohm@0
   114
  in  (Envir{maxidx=maxidx+1, asol=asol, iTs=iTs}, genvs (0,Ts))  end;
clasohm@0
   115
clasohm@0
   116
(*Generate a variable.*)
clasohm@0
   117
fun genvar name (env,T) : env * term =
wenzelm@247
   118
  let val (env',[v]) = genvars name (env,[T])
clasohm@0
   119
  in  (env',v)  end;
clasohm@0
   120
clasohm@0
   121
fun lookup (Envir{asol,...}, xname) : term option = xsearch (asol,xname);
clasohm@0
   122
clasohm@0
   123
fun update ((xname, t), Envir{maxidx, asol, iTs}) =
clasohm@0
   124
  Envir{maxidx=maxidx, asol=xinsert_new ((xname,t), asol), iTs=iTs};
clasohm@0
   125
clasohm@0
   126
(*The empty environment.  New variables will start with the given index.*)
clasohm@0
   127
fun empty m = Envir{maxidx=m, asol=null_olist, iTs=[]};
clasohm@0
   128
wenzelm@247
   129
(*is_empty*)
wenzelm@247
   130
fun is_empty (Envir {asol = Olist [], iTs = [], ...}) = true
wenzelm@247
   131
  | is_empty _ = false;
wenzelm@247
   132
wenzelm@247
   133
(*minidx*)
wenzelm@247
   134
fun minidx (Envir {asol = Olist asns, iTs, ...}) =
wenzelm@247
   135
  (case (asns, iTs) of
wenzelm@247
   136
    ([], []) => None
wenzelm@247
   137
  | (((_, i), _) :: _, _) => Some (min (i :: map (snd o fst) iTs))
wenzelm@247
   138
  | _ => Some (min (map (snd o fst) iTs)));
wenzelm@247
   139
clasohm@0
   140
(*Update, checking Var-Var assignments: try to suppress higher indexes*)
clasohm@0
   141
fun vupdate((a,t), env) = case t of
clasohm@0
   142
      Var(name',T) =>
wenzelm@247
   143
        if a=name' then env     (*cycle!*)
wenzelm@247
   144
        else if xless(a, name')  then
wenzelm@247
   145
           (case lookup(env,name') of  (*if already assigned, chase*)
wenzelm@247
   146
                None => update((name', Var(a,T)), env)
wenzelm@247
   147
              | Some u => vupdate((a,u), env))
wenzelm@247
   148
        else update((a,t), env)
clasohm@0
   149
    | _ => update((a,t), env);
clasohm@0
   150
clasohm@0
   151
clasohm@0
   152
(*Convert environment to alist*)
clasohm@0
   153
fun alist_of (Envir{maxidx,asol,...}) = alist_of_olist asol;
clasohm@0
   154
clasohm@0
   155
paulson@1500
   156
(*** Beta normal form for terms (not eta normal form).
paulson@1500
   157
     Chases variables in env;  Does not exploit sharing of variable bindings
paulson@1500
   158
     Does not check types, so could loop. ***)
paulson@1500
   159
paulson@1500
   160
(*raised when norm has no effect on a term, to do sharing instead of copying*)
paulson@1500
   161
exception SAME;
clasohm@0
   162
paulson@1500
   163
fun norm_term1 (asol,t) : term =
paulson@1500
   164
  let fun norm (Var (w,T)) =
paulson@1500
   165
	    (case xsearch(asol,w) of
paulson@1500
   166
		Some u => normh u
paulson@1500
   167
	      | None   => raise SAME)
paulson@1500
   168
	| norm (Abs(a,T,body)) =  Abs(a, T, norm body)
paulson@1500
   169
	| norm (Abs(_,_,body) $ t) = normh(subst_bounds([t], body))
paulson@1500
   170
	| norm (f $ t) =
paulson@1500
   171
	    ((case norm f of
paulson@1500
   172
	       Abs(_,_,body) => normh(subst_bounds([t], body))
paulson@1500
   173
	     | nf => nf $ normh t)
paulson@1500
   174
	    handle SAME => f $ norm t)
paulson@1500
   175
	| norm _ =  raise SAME
paulson@1500
   176
      and normh t = (norm t) handle SAME => t
paulson@1500
   177
  in normh t end
clasohm@0
   178
paulson@1500
   179
and norm_term2(asol,iTs,t) : term =
paulson@1500
   180
  let fun normT(Type(a,Ts)) = Type(a, normTs Ts)
paulson@1500
   181
	| normT(TFree _) = raise SAME
paulson@1500
   182
	| normT(TVar(v,_)) = (case assoc(iTs,v) of
paulson@1500
   183
		Some(U) => normTh U
paulson@1500
   184
	      | None => raise SAME)
paulson@1500
   185
      and normTh T = ((normT T) handle SAME => T)
paulson@1500
   186
      and normTs([]) = raise SAME
paulson@1500
   187
	| normTs(T::Ts) = ((normT T :: normTsh Ts)
paulson@1500
   188
			   handle SAME => T :: normTs Ts)
paulson@1500
   189
      and normTsh Ts = ((normTs Ts) handle SAME => Ts)
paulson@1500
   190
      and norm(Const(a,T)) = Const(a, normT T)
paulson@1500
   191
	| norm(Free(a,T)) = Free(a, normT T)
paulson@1500
   192
	| norm(Var (w,T)) =
paulson@1500
   193
	    (case xsearch(asol,w) of
paulson@1500
   194
		Some u => normh u
paulson@1500
   195
	      | None   => Var(w,normT T))
paulson@1500
   196
	| norm(Abs(a,T,body)) =
paulson@1500
   197
	      (Abs(a,normT T,normh body) handle SAME => Abs(a, T, norm body))
paulson@1500
   198
	| norm(Abs(_,_,body) $ t) = normh(subst_bounds([t], body))
paulson@1500
   199
	| norm(f $ t) =
paulson@1500
   200
	    ((case norm f of
paulson@1500
   201
	       Abs(_,_,body) => normh(subst_bounds([t], body))
paulson@1500
   202
	     | nf => nf $ normh t)
paulson@1500
   203
	    handle SAME => f $ norm t)
paulson@1500
   204
	| norm _ =  raise SAME
paulson@1500
   205
      and normh t = (norm t) handle SAME => t
paulson@1500
   206
  in normh t end;
clasohm@0
   207
clasohm@0
   208
(*curried version might be slower in recursive calls*)
clasohm@0
   209
fun norm_term (env as Envir{asol,iTs,...}) t : term =
lcp@719
   210
        if null iTs then norm_term1(asol, t) else norm_term2(asol,iTs, t)
lcp@719
   211
clasohm@0
   212
end;
clasohm@0
   213