src/HOL/Tools/SMT/smt_translate.ML
changeset 36891 bcd6fce5bf06
parent 36890 8e55aa1306c5
child 37123 fe22fc54b876
equal deleted inserted replaced
36890:8e55aa1306c5 36891:bcd6fce5bf06
    15     SLet of string * sterm * sterm |
    15     SLet of string * sterm * sterm |
    16     SQua of squant * string list * sterm spattern list * sterm
    16     SQua of squant * string list * sterm spattern list * sterm
    17 
    17 
    18   (* configuration options *)
    18   (* configuration options *)
    19   type prefixes = {sort_prefix: string, func_prefix: string}
    19   type prefixes = {sort_prefix: string, func_prefix: string}
       
    20   type header = Proof.context -> term list -> string list
    20   type strict = {
    21   type strict = {
    21     is_builtin_conn: string * typ -> bool,
    22     is_builtin_conn: string * typ -> bool,
    22     is_builtin_pred: string * typ -> bool,
    23     is_builtin_pred: Proof.context -> string * typ -> bool,
    23     is_builtin_distinct: bool}
    24     is_builtin_distinct: bool}
    24   type builtins = {
    25   type builtins = {
    25     builtin_typ: typ -> string option,
    26     builtin_typ: Proof.context -> typ -> string option,
    26     builtin_num: typ -> int -> string option,
    27     builtin_num: Proof.context -> typ -> int -> string option,
    27     builtin_fun: string * typ -> term list -> (string * term list) option }
    28     builtin_fun: Proof.context -> string * typ -> term list ->
    28   datatype smt_theory = Integer | Real | Bitvector
    29       (string * term list) option }
    29   type sign = {
    30   type sign = {
    30     theories: smt_theory list,
    31     header: string list,
    31     sorts: string list,
    32     sorts: string list,
    32     funcs: (string * (string list * string)) list }
    33     funcs: (string * (string list * string)) list }
    33   type config = {
    34   type config = {
    34     prefixes: prefixes,
    35     prefixes: prefixes,
       
    36     header: header,
    35     strict: strict option,
    37     strict: strict option,
    36     builtins: builtins,
    38     builtins: builtins,
    37     serialize: string list -> sign -> sterm list -> string }
    39     serialize: string list -> sign -> sterm list -> string }
    38   type recon = {
    40   type recon = {
    39     typs: typ Symtab.table,
    41     typs: typ Symtab.table,
    40     terms: term Symtab.table,
    42     terms: term Symtab.table,
    41     unfolds: thm list,
    43     unfolds: thm list,
    42     assms: thm list option }
    44     assms: thm list }
    43 
    45 
    44   val translate: config -> Proof.context -> string list -> thm list ->
    46   val translate: config -> Proof.context -> string list -> thm list ->
    45     string * recon
    47     string * recon
    46 end
    48 end
    47 
    49 
    64 
    66 
    65 (* configuration options *)
    67 (* configuration options *)
    66 
    68 
    67 type prefixes = {sort_prefix: string, func_prefix: string}
    69 type prefixes = {sort_prefix: string, func_prefix: string}
    68 
    70 
       
    71 type header = Proof.context -> term list -> string list
       
    72 
    69 type strict = {
    73 type strict = {
    70   is_builtin_conn: string * typ -> bool,
    74   is_builtin_conn: string * typ -> bool,
    71   is_builtin_pred: string * typ -> bool,
    75   is_builtin_pred: Proof.context -> string * typ -> bool,
    72   is_builtin_distinct: bool}
    76   is_builtin_distinct: bool}
    73 
    77 
    74 type builtins = {
    78 type builtins = {
    75   builtin_typ: typ -> string option,
    79   builtin_typ: Proof.context -> typ -> string option,
    76   builtin_num: typ -> int -> string option,
    80   builtin_num: Proof.context -> typ -> int -> string option,
    77   builtin_fun: string * typ -> term list -> (string * term list) option }
    81   builtin_fun: Proof.context -> string * typ -> term list ->
    78 
    82     (string * term list) option }
    79 datatype smt_theory = Integer | Real | Bitvector
       
    80 
    83 
    81 type sign = {
    84 type sign = {
    82   theories: smt_theory list,
    85   header: string list,
    83   sorts: string list,
    86   sorts: string list,
    84   funcs: (string * (string list * string)) list }
    87   funcs: (string * (string list * string)) list }
    85 
    88 
    86 type config = {
    89 type config = {
    87   prefixes: prefixes,
    90   prefixes: prefixes,
       
    91   header: header,
    88   strict: strict option,
    92   strict: strict option,
    89   builtins: builtins,
    93   builtins: builtins,
    90   serialize: string list -> sign -> sterm list -> string }
    94   serialize: string list -> sign -> sterm list -> string }
    91 
    95 
    92 type recon = {
    96 type recon = {
    93   typs: typ Symtab.table,
    97   typs: typ Symtab.table,
    94   terms: term Symtab.table,
    98   terms: term Symtab.table,
    95   unfolds: thm list,
    99   unfolds: thm list,
    96   assms: thm list option }
   100   assms: thm list }
    97 
   101 
    98 
   102 
    99 
   103 
   100 (* utility functions *)
   104 (* utility functions *)
   101 
   105 
   173   in Term.map_types revert end
   177   in Term.map_types revert end
   174 
   178 
   175 
   179 
   176 fun strictify {is_builtin_conn, is_builtin_pred, is_builtin_distinct} ctxt =
   180 fun strictify {is_builtin_conn, is_builtin_pred, is_builtin_distinct} ctxt =
   177   let
   181   let
   178 
       
   179     fun is_builtin_conn' (@{const_name True}, _) = false
   182     fun is_builtin_conn' (@{const_name True}, _) = false
   180       | is_builtin_conn' (@{const_name False}, _) = false
   183       | is_builtin_conn' (@{const_name False}, _) = false
   181       | is_builtin_conn' c = is_builtin_conn c
   184       | is_builtin_conn' c = is_builtin_conn c
   182 
   185 
   183     val propT = @{typ prop} and boolT = @{typ bool}
   186     val propT = @{typ prop} and boolT = @{typ bool}
   197     fun in_term t =
   200     fun in_term t =
   198       (case Term.strip_comb t of
   201       (case Term.strip_comb t of
   199         (c as Const (@{const_name If}, _), [t1, t2, t3]) =>
   202         (c as Const (@{const_name If}, _), [t1, t2, t3]) =>
   200           c $ in_form t1 $ in_term t2 $ in_term t3
   203           c $ in_form t1 $ in_term t2 $ in_term t3
   201       | (h as Const c, ts) =>
   204       | (h as Const c, ts) =>
   202           if is_builtin_conn' (conn c) orelse is_builtin_pred (pred c)
   205           if is_builtin_conn' (conn c) orelse is_builtin_pred ctxt (pred c)
   203           then wrap_in_if (in_form t)
   206           then wrap_in_if (in_form t)
   204           else Term.list_comb (h, map in_term ts)
   207           else Term.list_comb (h, map in_term ts)
   205       | (h as Free _, ts) => Term.list_comb (h, map in_term ts)
   208       | (h as Free _, ts) => Term.list_comb (h, map in_term ts)
   206       | _ => t)
   209       | _ => t)
   207 
   210 
   225           if is_builtin_distinct then Const (pred c) $ in_list T in_term t'
   228           if is_builtin_distinct then Const (pred c) $ in_list T in_term t'
   226           else as_term (in_term t)
   229           else as_term (in_term t)
   227       | (Const c, ts) =>
   230       | (Const c, ts) =>
   228           if is_builtin_conn (conn c)
   231           if is_builtin_conn (conn c)
   229           then Term.list_comb (Const (conn c), map in_form ts)
   232           then Term.list_comb (Const (conn c), map in_form ts)
   230           else if is_builtin_pred (pred c)
   233           else if is_builtin_pred ctxt (pred c)
   231           then Term.list_comb (Const (pred c), map in_term ts)
   234           then Term.list_comb (Const (pred c), map in_term ts)
   232           else as_term (in_term t)
   235           else as_term (in_term t)
   233       | _ => as_term (in_term t))
   236       | _ => as_term (in_term t))
   234   in
   237   in
   235     map (normalize ctxt) #> (fn thms => ((unfold_rules, term_bool' :: thms),
   238     map (normalize ctxt) #> (fn thms => ((unfold_rules, term_bool' :: thms),
   238 
   241 
   239 
   242 
   240 
   243 
   241 (* translation from Isabelle terms into SMT intermediate terms *)
   244 (* translation from Isabelle terms into SMT intermediate terms *)
   242 
   245 
   243 val empty_context = (1, Typtab.empty, 1, Termtab.empty, [])
   246 val empty_context = (1, Typtab.empty, 1, Termtab.empty)
   244 
   247 
   245 fun make_sign (_, typs, _, terms, thys) = {
   248 fun make_sign header (_, typs, _, terms) = {
   246   theories = thys,
   249   header = header,
   247   sorts = Typtab.fold (cons o snd) typs [],
   250   sorts = Typtab.fold (cons o snd) typs [],
   248   funcs = Termtab.fold (cons o snd) terms [] }
   251   funcs = Termtab.fold (cons o snd) terms [] }
   249 
   252 
   250 fun make_recon (unfolds, assms) (_, typs, _, terms, _) = {
   253 fun make_recon (unfolds, assms) (_, typs, _, terms) = {
   251   typs = Symtab.make (map swap (Typtab.dest typs)),
   254   typs = Symtab.make (map swap (Typtab.dest typs)),
   252   terms = Symtab.make (map (fn (t, (n, _)) => (n, t)) (Termtab.dest terms)),
   255   terms = Symtab.make (map (fn (t, (n, _)) => (n, t)) (Termtab.dest terms)),
   253   unfolds = unfolds,
   256   unfolds = unfolds,
   254   assms = SOME assms }
   257   assms = assms }
   255 
   258 
   256 fun string_of_index pre i = pre ^ string_of_int i
   259 fun string_of_index pre i = pre ^ string_of_int i
   257 
   260 
   258 fun add_theory T (Tidx, typs, idx, terms, thys) =
   261 fun fresh_typ sort_prefix T (cx as (Tidx, typs, idx, terms)) =
   259   let
       
   260     fun add @{typ int} = insert (op =) Integer
       
   261       | add @{typ real} = insert (op =) Real
       
   262       | add (Type (@{type_name word}, _)) = insert (op =) Bitvector
       
   263       | add (Type (_, Ts)) = fold add Ts
       
   264       | add _ = I
       
   265   in (Tidx, typs, idx, terms, add T thys) end
       
   266 
       
   267 fun fresh_typ sort_prefix T (cx as (Tidx, typs, idx, terms, thys)) =
       
   268   (case Typtab.lookup typs T of
   262   (case Typtab.lookup typs T of
   269     SOME s => (s, cx)
   263     SOME s => (s, cx)
   270   | NONE =>
   264   | NONE =>
   271       let
   265       let
   272         val s = string_of_index sort_prefix Tidx
   266         val s = string_of_index sort_prefix Tidx
   273         val typs' = Typtab.update (T, s) typs
   267         val typs' = Typtab.update (T, s) typs
   274       in (s, (Tidx+1, typs', idx, terms, thys)) end)
   268       in (s, (Tidx+1, typs', idx, terms)) end)
   275 
   269 
   276 fun fresh_fun func_prefix t ss (cx as (Tidx, typs, idx, terms, thys)) =
   270 fun fresh_fun func_prefix t ss (cx as (Tidx, typs, idx, terms)) =
   277   (case Termtab.lookup terms t of
   271   (case Termtab.lookup terms t of
   278     SOME (f, _) => (f, cx)
   272     SOME (f, _) => (f, cx)
   279   | NONE =>
   273   | NONE =>
   280       let
   274       let
   281         val f = string_of_index func_prefix idx
   275         val f = string_of_index func_prefix idx
   282         val terms' = Termtab.update (revert_types t, (f, ss)) terms
   276         val terms' = Termtab.update (revert_types t, (f, ss)) terms
   283       in (f, (Tidx, typs, idx+1, terms', thys)) end)
   277       in (f, (Tidx, typs, idx+1, terms')) end)
   284 
   278 
   285 fun relaxed thms = (([], thms), map prop_of thms)
   279 fun relaxed thms = (([], thms), map prop_of thms)
   286 
   280 
   287 fun with_context f (ths, ts) =
   281 fun with_context header f (ths, ts) =
   288   let val (us, context) = fold_map f ts empty_context
   282   let val (us, context) = fold_map f ts empty_context
   289   in ((make_sign context, us), make_recon ths context) end
   283   in ((make_sign (header ts) context, us), make_recon ths context) end
   290 
   284 
   291 
   285 
   292 fun translate {prefixes, strict, builtins, serialize} ctxt comments =
   286 fun translate {prefixes, strict, header, builtins, serialize} ctxt comments =
   293   let
   287   let
   294     val {sort_prefix, func_prefix} = prefixes
   288     val {sort_prefix, func_prefix} = prefixes
   295     val {builtin_typ, builtin_num, builtin_fun} = builtins
   289     val {builtin_typ, builtin_num, builtin_fun} = builtins
   296 
   290 
   297     fun transT T = add_theory T #>
   291     fun transT T =
   298       (case builtin_typ T of
   292       (case builtin_typ ctxt T of
   299         SOME n => pair n
   293         SOME n => pair n
   300       | NONE => fresh_typ sort_prefix T)
   294       | NONE => fresh_typ sort_prefix T)
   301 
   295 
   302     fun app n ts = SApp (n, ts)
   296     fun app n ts = SApp (n, ts)
   303 
   297 
   311           | NONE => raise TERM ("intermediate", [t]))
   305           | NONE => raise TERM ("intermediate", [t]))
   312       | (Const (@{const_name Let}, _), [t1, Abs (_, T, t2)]) =>
   306       | (Const (@{const_name Let}, _), [t1, Abs (_, T, t2)]) =>
   313           transT T ##>> trans t1 ##>> trans t2 #>>
   307           transT T ##>> trans t1 ##>> trans t2 #>>
   314           (fn ((U, u1), u2) => SLet (U, u1, u2))
   308           (fn ((U, u1), u2) => SLet (U, u1, u2))
   315       | (h as Const (c as (@{const_name distinct}, T)), [t1]) =>
   309       | (h as Const (c as (@{const_name distinct}, T)), [t1]) =>
   316           (case builtin_fun c (HOLogic.dest_list t1) of
   310           (case builtin_fun ctxt c (HOLogic.dest_list t1) of
   317             SOME (n, ts) => add_theory T #> fold_map trans ts #>> app n
   311             SOME (n, ts) => fold_map trans ts #>> app n
   318           | NONE => transs h T [t1])
   312           | NONE => transs h T [t1])
   319       | (h as Const (c as (_, T)), ts) =>
   313       | (h as Const (c as (_, T)), ts) =>
   320           (case try HOLogic.dest_number t of
   314           (case try HOLogic.dest_number t of
   321             SOME (T, i) =>
   315             SOME (T, i) =>
   322               (case builtin_num T i of
   316               (case builtin_num ctxt T i of
   323                 SOME n => add_theory T #> pair (SApp (n, []))
   317                 SOME n => pair (SApp (n, []))
   324               | NONE => transs t T [])
   318               | NONE => transs t T [])
   325           | NONE =>
   319           | NONE =>
   326               (case builtin_fun c ts of
   320               (case builtin_fun ctxt c ts of
   327                 SOME (n, ts') => add_theory T #> fold_map trans ts' #>> app n
   321                 SOME (n, ts') => fold_map trans ts' #>> app n
   328               | NONE => transs h T ts))
   322               | NONE => transs h T ts))
   329       | (h as Free (_, T), ts) => transs h T ts
   323       | (h as Free (_, T), ts) => transs h T ts
   330       | (Bound i, []) => pair (SVar i)
   324       | (Bound i, []) => pair (SVar i)
   331       | _ => raise TERM ("intermediate", [t]))
   325       | _ => raise TERM ("intermediate", [t]))
   332 
   326 
   335       in
   329       in
   336         fold_map transT Us ##>> transT U #-> (fn Up =>
   330         fold_map transT Us ##>> transT U #-> (fn Up =>
   337         fresh_fun func_prefix t Up ##>> fold_map trans ts #>> SApp)
   331         fresh_fun func_prefix t Up ##>> fold_map trans ts #>> SApp)
   338       end
   332       end
   339   in
   333   in
   340     (if is_some strict then strictify (the strict) ctxt else relaxed) #>
   334     (case strict of SOME strct => strictify strct ctxt | NONE => relaxed) #>
   341     with_context trans #>> uncurry (serialize comments)
   335     with_context (header ctxt) trans #>> uncurry (serialize comments)
   342   end
   336   end
   343 
   337 
   344 end
   338 end