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