src/HOLCF/Tools/Domain/domain_library.ML
author huffman
Tue Mar 02 15:06:02 2010 -0800 (2010-03-02)
changeset 35519 abf45a91d24d
parent 35497 979706bd5c16
child 35521 47eec4da124a
permissions -rw-r--r--
remove unused selector field from type arg
     1 (*  Title:      HOLCF/Tools/Domain/domain_library.ML
     2     Author:     David von Oheimb
     3 
     4 Library for domain command.
     5 *)
     6 
     7 
     8 (* infix syntax *)
     9 
    10 infixr 5 -->;
    11 infixr 6 ->>;
    12 infixr 0 ===>;
    13 infixr 0 ==>;
    14 infix 0 ==;
    15 infix 1 ===;
    16 infix 1 ~=;
    17 
    18 infix 9 `  ;
    19 infix 9 `% ;
    20 infix 9 `%%;
    21 
    22 
    23 (* ----- specific support for domain ---------------------------------------- *)
    24 
    25 signature DOMAIN_LIBRARY =
    26 sig
    27   val first  : 'a * 'b * 'c -> 'a
    28   val second : 'a * 'b * 'c -> 'b
    29   val third  : 'a * 'b * 'c -> 'c
    30   val upd_second : ('b -> 'd) -> 'a * 'b * 'c -> 'a * 'd * 'c
    31   val upd_third  : ('c -> 'd) -> 'a * 'b * 'c -> 'a * 'b * 'd
    32   val mapn : (int -> 'a -> 'b) -> int -> 'a list -> 'b list
    33   val atomize : Proof.context -> thm -> thm list
    34 
    35   val Imposs : string -> 'a;
    36   val cpo_type : theory -> typ -> bool;
    37   val pcpo_type : theory -> typ -> bool;
    38   val string_of_typ : theory -> typ -> string;
    39 
    40   (* Creating HOLCF types *)
    41   val ->> : typ * typ -> typ;
    42   val mk_ssumT : typ * typ -> typ;
    43   val mk_sprodT : typ * typ -> typ;
    44   val mk_uT : typ -> typ;
    45   val oneT : typ;
    46   val mk_maybeT : typ -> typ;
    47   val mk_ctupleT : typ list -> typ;
    48   val mk_TFree : string -> typ;
    49   val pcpoS : sort;
    50 
    51   (* Creating HOLCF terms *)
    52   val %: : string -> term;
    53   val %%: : string -> term;
    54   val ` : term * term -> term;
    55   val `% : term * string -> term;
    56   val /\ : string -> term -> term;
    57   val UU : term;
    58   val ID : term;
    59   val oo : term * term -> term;
    60   val mk_ctuple : term list -> term;
    61   val mk_fix : term -> term;
    62   val mk_iterate : term * term * term -> term;
    63   val mk_fail : term;
    64   val mk_return : term -> term;
    65   val list_ccomb : term * term list -> term;
    66   val con_app2 : string -> ('a -> term) -> 'a list -> term;
    67   val prj : ('a -> 'b -> 'a) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> int -> 'a
    68   val proj : term -> 'a list -> int -> term;
    69   val mk_ctuple_pat : term list -> term;
    70   val mk_branch : term -> term;
    71 
    72   (* Creating propositions *)
    73   val mk_conj : term * term -> term;
    74   val mk_disj : term * term -> term;
    75   val mk_imp : term * term -> term;
    76   val mk_lam : string * term -> term;
    77   val mk_all : string * term -> term;
    78   val mk_ex : string * term -> term;
    79   val mk_constrainall : string * typ * term -> term;
    80   val === : term * term -> term;
    81   val strict : term -> term;
    82   val defined : term -> term;
    83   val mk_adm : term -> term;
    84   val lift : ('a -> term) -> 'a list * term -> term;
    85   val lift_defined : ('a -> term) -> 'a list * term -> term;
    86 
    87   (* Creating meta-propositions *)
    88   val mk_trp : term -> term; (* HOLogic.mk_Trueprop *)
    89   val == : term * term -> term;
    90   val ===> : term * term -> term;
    91   val ==> : term * term -> term;
    92   val mk_All : string * term -> term;
    93 
    94       (* Domain specifications *)
    95       eqtype arg;
    96   type cons = string * mixfix * arg list;
    97   type eq = (string * typ list) * cons list;
    98   val mk_arg : (bool * Datatype.dtyp) * string -> arg;
    99   val is_lazy : arg -> bool;
   100   val rec_of : arg -> int;
   101   val dtyp_of : arg -> Datatype.dtyp;
   102   val vname : arg -> string;
   103   val upd_vname : (string -> string) -> arg -> arg;
   104   val is_rec : arg -> bool;
   105   val is_nonlazy_rec : arg -> bool;
   106   val nonlazy : arg list -> string list;
   107   val nonlazy_rec : arg list -> string list;
   108   val %# : arg -> term;
   109   val /\# : arg * term -> term;
   110   val when_body : cons list -> (int * int -> term) -> term;
   111   val when_funs : 'a list -> string list;
   112   val bound_arg : ''a list -> ''a -> term; (* ''a = arg or string *)
   113   val idx_name : 'a list -> string -> int -> string;
   114   val app_rec_arg : (int -> term) -> arg -> term;
   115   val con_app : string -> arg list -> term;
   116   val dtyp_of_eq : eq -> Datatype.dtyp;
   117 
   118 
   119   (* Name mangling *)
   120   val strip_esc : string -> string;
   121   val extern_name : string -> string;
   122   val dis_name : string -> string;
   123   val mat_name : string -> string;
   124   val pat_name : string -> string;
   125 end;
   126 
   127 structure Domain_Library :> DOMAIN_LIBRARY =
   128 struct
   129 
   130 fun first  (x,_,_) = x;
   131 fun second (_,x,_) = x;
   132 fun third  (_,_,x) = x;
   133 
   134 fun upd_first  f (x,y,z) = (f x,   y,   z);
   135 fun upd_second f (x,y,z) = (  x, f y,   z);
   136 fun upd_third  f (x,y,z) = (  x,   y, f z);
   137 
   138 fun mapn f n []      = []
   139   | mapn f n (x::xs) = (f n x) :: mapn f (n+1) xs;
   140 
   141 fun foldr'' f (l,f2) =
   142     let fun itr []  = raise Fail "foldr''" 
   143           | itr [a] = f2 a
   144           | itr (a::l) = f(a, itr l)
   145     in  itr l  end;
   146 
   147 fun atomize ctxt thm =
   148     let
   149       val r_inst = read_instantiate ctxt;
   150       fun at thm =
   151           case concl_of thm of
   152             _$(Const("op &",_)$_$_)       => at(thm RS conjunct1)@at(thm RS conjunct2)
   153           | _$(Const("All" ,_)$Abs(s,_,_))=> at(thm RS (r_inst [(("x", 0), "?" ^ s)] spec))
   154           | _                             => [thm];
   155     in map zero_var_indexes (at thm) end;
   156 
   157 exception Impossible of string;
   158 fun Imposs msg = raise Impossible ("Domain:"^msg);
   159 
   160 (* ----- name handling ----- *)
   161 
   162 val strip_esc =
   163     let fun strip ("'" :: c :: cs) = c :: strip cs
   164           | strip ["'"] = []
   165           | strip (c :: cs) = c :: strip cs
   166           | strip [] = [];
   167     in implode o strip o Symbol.explode end;
   168 
   169 fun extern_name con =
   170     case Symbol.explode con of 
   171       ("o"::"p"::" "::rest) => implode rest
   172     | _ => con;
   173 fun dis_name  con = "is_"^ (extern_name con);
   174 fun dis_name_ con = "is_"^ (strip_esc   con);
   175 fun mat_name  con = "match_"^ (extern_name con);
   176 fun mat_name_ con = "match_"^ (strip_esc   con);
   177 fun pat_name  con = (extern_name con) ^ "_pat";
   178 fun pat_name_ con = (strip_esc   con) ^ "_pat";
   179 
   180 fun cpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort cpo});
   181 fun pcpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort pcpo});
   182 fun string_of_typ sg = Syntax.string_of_typ_global sg o Sign.certify_typ sg;
   183 
   184 (* ----- constructor list handling ----- *)
   185 
   186 type arg =
   187      (bool * Datatype.dtyp) *   (*  (lazy, recursive element) *)
   188      string;                       (*   argument name    *)
   189 
   190 type cons =
   191      string *         (* operator name of constr *)
   192      mixfix *         (* mixfix syntax of constructor *)
   193      arg list;        (* argument list      *)
   194 
   195 type eq =
   196      (string *        (* name      of abstracted type *)
   197       typ list) *     (* arguments of abstracted type *)
   198      cons list;       (* represented type, as a constructor list *)
   199 
   200 val mk_arg = I;
   201 
   202 fun rec_of ((_,dtyp),_) =
   203     case dtyp of Datatype_Aux.DtRec i => i | _ => ~1;
   204 (* FIXME: what about indirect recursion? *)
   205 
   206 fun is_lazy arg = fst (fst arg);
   207 fun dtyp_of arg = snd (fst arg);
   208 val     vname =       snd;
   209 val upd_vname =   apsnd;
   210 fun is_rec         arg = rec_of arg >=0;
   211 fun is_nonlazy_rec arg = is_rec arg andalso not (is_lazy arg);
   212 fun nonlazy     args   = map vname (filter_out is_lazy args);
   213 fun nonlazy_rec args   = map vname (filter is_nonlazy_rec args);
   214 
   215 
   216 (* ----- combinators for making dtyps ----- *)
   217 
   218 fun mk_uD T = Datatype_Aux.DtType(@{type_name "u"}, [T]);
   219 fun mk_sprodD (T, U) = Datatype_Aux.DtType(@{type_name "**"}, [T, U]);
   220 fun mk_ssumD (T, U) = Datatype_Aux.DtType(@{type_name "++"}, [T, U]);
   221 fun mk_liftD T = Datatype_Aux.DtType(@{type_name "lift"}, [T]);
   222 val unitD = Datatype_Aux.DtType(@{type_name "unit"}, []);
   223 val boolD = Datatype_Aux.DtType(@{type_name "bool"}, []);
   224 val oneD = mk_liftD unitD;
   225 val trD = mk_liftD boolD;
   226 fun big_sprodD ds = case ds of [] => oneD | _ => foldr1 mk_sprodD ds;
   227 fun big_ssumD ds = case ds of [] => unitD | _ => foldr1 mk_ssumD ds;
   228 
   229 fun dtyp_of_arg ((lazy, D), _) = if lazy then mk_uD D else D;
   230 fun dtyp_of_cons (_, _, args) = big_sprodD (map dtyp_of_arg args);
   231 fun dtyp_of_eq (_, cons) = big_ssumD (map dtyp_of_cons cons);
   232 
   233 
   234 (* ----- support for type and mixfix expressions ----- *)
   235 
   236 fun mk_uT T = Type(@{type_name "u"}, [T]);
   237 fun mk_cfunT (T, U) = Type(@{type_name "->"}, [T, U]);
   238 fun mk_sprodT (T, U) = Type(@{type_name "**"}, [T, U]);
   239 fun mk_ssumT (T, U) = Type(@{type_name "++"}, [T, U]);
   240 val oneT = @{typ one};
   241 
   242 val op ->> = mk_cfunT;
   243 
   244 fun mk_TFree s = TFree ("'" ^ s, @{sort pcpo});
   245 
   246 (* ----- support for term expressions ----- *)
   247 
   248 fun %: s = Free(s,dummyT);
   249 fun %# arg = %:(vname arg);
   250 fun %%: s = Const(s,dummyT);
   251 
   252 local open HOLogic in
   253 val mk_trp = mk_Trueprop;
   254 fun mk_conj (S,T) = conj $ S $ T;
   255 fun mk_disj (S,T) = disj $ S $ T;
   256 fun mk_imp  (S,T) = imp  $ S $ T;
   257 fun mk_lam  (x,T) = Abs(x,dummyT,T);
   258 fun mk_all  (x,P) = HOLogic.mk_all (x,dummyT,P);
   259 fun mk_ex   (x,P) = mk_exists (x,dummyT,P);
   260 fun mk_constrainall (x,typ,P) = %%:"All" $ (TypeInfer.constrain (typ --> boolT) (mk_lam(x,P)));
   261 end
   262 
   263 fun mk_All  (x,P) = %%:"all" $ mk_lam(x,P); (* meta universal quantification *)
   264 
   265 infixr 0 ===>;  fun S ===> T = %%:"==>" $ S $ T;
   266 infixr 0 ==>;   fun S ==> T = mk_trp S ===> mk_trp T;
   267 infix 0 ==;     fun S ==  T = %%:"==" $ S $ T;
   268 infix 1 ===;    fun S === T = %%:"op =" $ S $ T;
   269 infix 1 ~=;     fun S ~=  T = HOLogic.mk_not (S === T);
   270 
   271 infix 9 `  ; fun f ` x = %%: @{const_name Rep_CFun} $ f $ x;
   272 infix 9 `% ; fun f`% s = f` %: s;
   273 infix 9 `%%; fun f`%%s = f` %%:s;
   274 
   275 fun mk_adm t = %%: @{const_name adm} $ t;
   276 val ID = %%: @{const_name ID};
   277 fun mk_strictify t = %%: @{const_name strictify}`t;
   278 fun mk_ssplit t = %%: @{const_name ssplit}`t;
   279 fun mk_sscase (x, y) = %%: @{const_name sscase}`x`y;
   280 fun mk_fup (t,u) = %%: @{const_name fup} ` t ` u;
   281 val ONE = @{term ONE};
   282 fun mk_iterate (n,f,z) = %%: @{const_name iterate} $ n ` f ` z;
   283 fun mk_fix t = %%: @{const_name fix}`t;
   284 fun mk_return t = %%: @{const_name Fixrec.return}`t;
   285 val mk_fail = %%: @{const_name Fixrec.fail};
   286 
   287 fun mk_branch t = %%: @{const_name Fixrec.branch} $ t;
   288 
   289 val pcpoS = @{sort pcpo};
   290 
   291 val list_ccomb = Library.foldl (op `); (* continuous version of list_comb *)
   292 fun con_app2 con f args = list_ccomb(%%:con,map f args);
   293 fun con_app con = con_app2 con %#;
   294 fun if_rec  arg f y   = if is_rec arg then f (rec_of arg) else y;
   295 fun app_rec_arg p arg = if_rec arg (fn n => fn x => (p n)`x) I (%# arg);
   296 fun prj _  _  x (   _::[]) _ = x
   297   | prj f1 _  x (_::y::ys) 0 = f1 x y
   298   | prj f1 f2 x (y::   ys) j = prj f1 f2 (f2 x y) ys (j-1);
   299 fun  proj x      = prj (fn S => K(%%:"fst" $S)) (fn S => K(%%:"snd" $S)) x;
   300 fun lift tfn = Library.foldr (fn (x,t)=> (mk_trp(tfn x) ===> t));
   301 
   302 fun /\ v T = %%: @{const_name Abs_CFun} $ mk_lam(v,T);
   303 fun /\# (arg,T) = /\ (vname arg) T;
   304 infixr 9 oo; fun S oo T = %%: @{const_name cfcomp}`S`T;
   305 val UU = %%: @{const_name UU};
   306 fun strict f = f`UU === UU;
   307 fun defined t = t ~= UU;
   308 fun cpair (t,u) = %%: @{const_name Pair} $ t $ u;
   309 fun spair (t,u) = %%: @{const_name spair}`t`u;
   310 fun mk_ctuple [] = HOLogic.unit (* used in match_defs *)
   311   | mk_ctuple ts = foldr1 cpair ts;
   312 fun mk_ctupleT [] = HOLogic.unitT   (* used in match_defs *)
   313   | mk_ctupleT Ts = foldr1 HOLogic.mk_prodT Ts;
   314 fun mk_maybeT T = Type ("Fixrec.maybe",[T]);
   315 fun cpair_pat (p1,p2) = %%: @{const_name cpair_pat} $ p1 $ p2;
   316 val mk_ctuple_pat = foldr1 cpair_pat;
   317 fun lift_defined f = lift (fn x => defined (f x));
   318 fun bound_arg vns v = Bound (length vns - find_index (fn v' => v' = v) vns - 1);
   319 
   320 fun cont_eta_contract (Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body)) = 
   321     (case cont_eta_contract body  of
   322        body' as (Const("Cfun.Rep_CFun",Ta) $ f $ Bound 0) => 
   323        if not (0 mem loose_bnos f) then incr_boundvars ~1 f 
   324        else   Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body')
   325      | body' => Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body'))
   326   | cont_eta_contract(f$t) = cont_eta_contract f $ cont_eta_contract t
   327   | cont_eta_contract t    = t;
   328 
   329 fun idx_name dnames s n = s^(if length dnames = 1 then "" else string_of_int n);
   330 fun when_funs cons = if length cons = 1 then ["f"] 
   331                      else mapn (fn n => K("f"^(string_of_int n))) 1 cons;
   332 fun when_body cons funarg =
   333     let
   334       fun one_fun n (_,_,[]  ) = /\ "dummy" (funarg(1,n))
   335         | one_fun n (_,_,args) = let
   336             val l2 = length args;
   337             fun idxs m arg = (if is_lazy arg then (fn t => mk_fup (ID, t))
   338                               else I) (Bound(l2-m));
   339           in cont_eta_contract
   340                (foldr'' 
   341                   (fn (a,t) => mk_ssplit (/\# (a,t)))
   342                   (args,
   343                 fn a=> /\#(a,(list_ccomb(funarg(l2,n),mapn idxs 1 args))))
   344                ) end;
   345     in (if length cons = 1 andalso length(third(hd cons)) <= 1
   346         then mk_strictify else I)
   347          (foldr1 mk_sscase (mapn one_fun 1 cons)) end;
   348 
   349 end; (* struct *)