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