src/HOL/Tools/Quickcheck/narrowing_generators.ML
author wenzelm
Mon Mar 21 16:38:28 2011 +0100 (2011-03-21)
changeset 42039 cef738d55348
parent 42028 bd6515e113b2
child 42090 ef566ce50170
permissions -rw-r--r--
another attempt to exec ISABELLE_GHC robustly (cf. d8c3b26b3da4, 994d088fbfbc);
     1 (*  Title:      HOL/Tools/Quickcheck/narrowing_generators.ML
     2     Author:     Lukas Bulwahn, TU Muenchen
     3 
     4 Narrowing-based counterexample generation.
     5 *)
     6 
     7 signature NARROWING_GENERATORS =
     8 sig
     9   val compile_generator_expr:
    10     Proof.context -> term * term list -> int -> term list option * Quickcheck.report option
    11   val put_counterexample: (unit -> term list option) -> Proof.context -> Proof.context
    12   val finite_functions : bool Config.T
    13   val setup: theory -> theory
    14 end;
    15 
    16 structure Narrowing_Generators : NARROWING_GENERATORS =
    17 struct
    18 
    19 (* configurations *)
    20 
    21 val (finite_functions, setup_finite_functions) =
    22   Attrib.config_bool "quickcheck_finite_functions" (K true)
    23 
    24 
    25 fun mk_undefined T = Const(@{const_name undefined}, T)
    26 
    27 (* narrowing specific names and types *)
    28 
    29 exception FUNCTION_TYPE;
    30 
    31 val narrowingN = "narrowing";
    32 
    33 fun narrowingT T =
    34   @{typ Quickcheck_Narrowing.code_int} --> Type (@{type_name Quickcheck_Narrowing.cons}, [T])
    35 
    36 fun mk_empty T = Const (@{const_name Quickcheck_Narrowing.empty}, narrowingT T)
    37 
    38 fun mk_cons c T = Const (@{const_name Quickcheck_Narrowing.cons}, T --> narrowingT T) $ Const (c, T)
    39 
    40 fun mk_apply (T, t) (U, u) =
    41   let
    42     val (_, U') = dest_funT U
    43   in
    44     (U', Const (@{const_name Quickcheck_Narrowing.apply},
    45       narrowingT U --> narrowingT T --> narrowingT U') $ u $ t)
    46   end
    47   
    48 fun mk_sum (t, u) =
    49   let
    50     val T = fastype_of t
    51   in
    52     Const (@{const_name Quickcheck_Narrowing.sum}, T --> T --> T) $ t $ u
    53   end
    54 
    55 (* creating narrowing instances *)
    56 
    57 fun mk_equations descr vs tycos narrowings (Ts, Us) =
    58   let
    59     fun mk_call T =
    60       let
    61         val narrowing =
    62           Const (@{const_name "Quickcheck_Narrowing.narrowing_class.narrowing"}, narrowingT T)
    63       in
    64         (T, narrowing)
    65       end
    66     fun mk_aux_call fTs (k, _) (tyco, Ts) =
    67       let
    68         val T = Type (tyco, Ts)
    69         val _ = if not (null fTs) then raise FUNCTION_TYPE else ()
    70       in
    71         (T, nth narrowings k)
    72       end
    73     fun mk_consexpr simpleT (c, xs) =
    74       let
    75         val Ts = map fst xs
    76       in snd (fold mk_apply xs (Ts ---> simpleT, mk_cons c (Ts ---> simpleT))) end
    77     fun mk_rhs exprs = foldr1 mk_sum exprs
    78     val rhss =
    79       Datatype_Aux.interpret_construction descr vs
    80         { atyp = mk_call, dtyp = mk_aux_call }
    81       |> (map o apfst) Type
    82       |> map (fn (T, cs) => map (mk_consexpr T) cs)
    83       |> map mk_rhs
    84     val lhss = narrowings
    85     val eqs = map (HOLogic.mk_Trueprop o HOLogic.mk_eq) (lhss ~~ rhss)
    86   in
    87     eqs
    88   end
    89 
    90 
    91 fun instantiate_narrowing_datatype config descr vs tycos prfx (names, auxnames) (Ts, Us) thy =
    92   let
    93     val _ = Datatype_Aux.message config "Creating narrowing generators ...";
    94     val narrowingsN = map (prefix (narrowingN ^ "_")) (names @ auxnames);
    95   in
    96     thy
    97     |> Class.instantiation (tycos, vs, @{sort narrowing})
    98     |> (fold_map (fn (name, T) => Local_Theory.define
    99           ((Binding.conceal (Binding.name name), NoSyn),
   100             (apfst Binding.conceal Attrib.empty_binding, mk_undefined (narrowingT T)))
   101         #> apfst fst) (narrowingsN ~~ (Ts @ Us))
   102       #> (fn (narrowings, lthy) =>
   103         let
   104           val eqs_t = mk_equations descr vs tycos narrowings (Ts, Us)
   105           val eqs = map (fn eq => Goal.prove lthy ["f", "i"] [] eq
   106             (fn _ => Skip_Proof.cheat_tac (ProofContext.theory_of lthy))) eqs_t
   107         in
   108           fold (fn (name, eq) => Local_Theory.note
   109           ((Binding.conceal (Binding.qualify true prfx
   110              (Binding.qualify true name (Binding.name "simps"))),
   111              Code.add_default_eqn_attrib :: map (Attrib.internal o K)
   112                [Simplifier.simp_add, Nitpick_Simps.add]), [eq]) #> snd) (narrowingsN ~~ eqs) lthy
   113         end))
   114     |> Class.prove_instantiation_exit (K (Class.intro_classes_tac []))
   115   end;
   116 
   117 (* testing framework *)
   118 
   119 val target = "Haskell"
   120 
   121 (* invocation of Haskell interpreter *)
   122 
   123 val narrowing_engine = File.read (Path.explode "~~/src/HOL/Tools/Quickcheck/Narrowing_Engine.hs")
   124 
   125 fun exec verbose code =
   126   ML_Context.exec (fn () => Secure.use_text ML_Env.local_context (0, "generated code") verbose code)
   127 
   128 fun value ctxt (get, put, put_ml) (code, value) size =
   129   let
   130     val tmp_prefix = "Quickcheck_Narrowing"
   131     fun run in_path = 
   132       let
   133         val code_file = Path.append in_path (Path.basic "Code.hs")
   134         val narrowing_engine_file = Path.append in_path (Path.basic "Narrowing_Engine.hs")
   135         val main_file = Path.append in_path (Path.basic "Main.hs")
   136         val main = "module Main where {\n\n" ^
   137           "import Narrowing_Engine;\n" ^
   138           "import Code;\n\n" ^
   139           "main = Narrowing_Engine.smallCheck " ^ string_of_int size ^ " (Code.value ())\n\n" ^
   140           "}\n"
   141         val code' = prefix "module Code where {\n\ndata Typerep = Typerep String [Typerep];\n"
   142           (unprefix "module Code where {" code)
   143         val _ = File.write code_file code'
   144         val _ = File.write narrowing_engine_file narrowing_engine
   145         val _ = File.write main_file main
   146         val executable = File.shell_path (Path.append in_path (Path.basic "isa_lsc"))
   147         val cmd = "( exec \"$ISABELLE_GHC\" -fglasgow-exts " ^
   148           (space_implode " " (map File.shell_path [code_file, narrowing_engine_file, main_file])) ^
   149           " -o " ^ executable ^ "; ) && " ^ executable
   150       in
   151         bash_output cmd
   152       end
   153     val result = Isabelle_System.with_tmp_dir tmp_prefix run
   154     val output_value = the_default "NONE"
   155       (try (snd o split_last o filter_out (fn s => s = "") o split_lines o fst) result)
   156       |> translate_string (fn s => if s = "\\" then "\\\\" else s)
   157     val ml_code = "\nval _ = Context.set_thread_data (SOME (Context.map_proof (" ^ put_ml
   158       ^ " (fn () => " ^ output_value ^ ")) (ML_Context.the_generic_context ())))";
   159     val ctxt' = ctxt
   160       |> put (fn () => error ("Bad evaluation for " ^ quote put_ml))
   161       |> Context.proof_map (exec false ml_code);
   162   in get ctxt' () end;
   163 
   164 fun evaluation cookie thy evaluator vs_t args size =
   165   let
   166     val ctxt = ProofContext.init_global thy;
   167     val (program_code, value_name) = evaluator vs_t;
   168     val value_code = space_implode " "
   169       (value_name :: "()" :: map (enclose "(" ")") args);
   170   in Exn.interruptible_capture (value ctxt cookie (program_code, value_code)) size end;
   171 
   172 fun dynamic_value_strict cookie thy postproc t args size =
   173   let
   174     fun evaluator naming program ((_, vs_ty), t) deps =
   175       evaluation cookie thy (Code_Target.evaluator thy target naming program deps) (vs_ty, t) args size;
   176   in Exn.release (Code_Thingol.dynamic_value thy (Exn.map_result o postproc) evaluator t) end;
   177 
   178 (* counterexample generator *)
   179   
   180 structure Counterexample = Proof_Data
   181 (
   182   type T = unit -> term list option
   183   fun init _ () = error "Counterexample"
   184 )
   185 
   186 val put_counterexample = Counterexample.put
   187 
   188 fun finitize_functions t =
   189   let
   190     val ((names, Ts), t') = apfst split_list (strip_abs t)
   191     fun mk_eval_ffun dT rT =
   192       Const (@{const_name "Quickcheck_Narrowing.eval_ffun"}, 
   193         Type (@{type_name "Quickcheck_Narrowing.ffun"}, [dT, rT]) --> dT --> rT)
   194     fun mk_eval_cfun dT rT =
   195       Const (@{const_name "Quickcheck_Narrowing.eval_cfun"}, 
   196         Type (@{type_name "Quickcheck_Narrowing.cfun"}, [rT]) --> dT --> rT)
   197     fun eval_function (T as Type (@{type_name fun}, [dT, rT])) =
   198       let
   199         val (rt', rT') = eval_function rT
   200       in
   201         case dT of
   202           Type (@{type_name fun}, _) =>
   203             (fn t => absdummy (dT, rt' (mk_eval_cfun dT rT' $ incr_boundvars 1 t $ Bound 0)),
   204             Type (@{type_name "Quickcheck_Narrowing.cfun"}, [rT']))
   205         | _ => (fn t => absdummy (dT, rt' (mk_eval_ffun dT rT' $ incr_boundvars 1 t $ Bound 0)),
   206             Type (@{type_name "Quickcheck_Narrowing.ffun"}, [dT, rT']))
   207       end
   208       | eval_function T = (I, T)
   209     val (tt, Ts') = split_list (map eval_function Ts)
   210     val t'' = subst_bounds (map2 (fn f => fn x => f x) (rev tt) (map_index (Bound o fst) Ts), t')
   211   in
   212     list_abs (names ~~ Ts', t'')
   213   end
   214 
   215 fun compile_generator_expr ctxt (t, eval_terms) size =
   216   let
   217     val thy = ProofContext.theory_of ctxt
   218     val t' = list_abs_free (Term.add_frees t [], t)
   219     val t'' = if Config.get ctxt finite_functions then finitize_functions t' else t'
   220     fun ensure_testable t =
   221       Const (@{const_name Quickcheck_Narrowing.ensure_testable}, fastype_of t --> fastype_of t) $ t
   222     val result = dynamic_value_strict
   223       (Counterexample.get, Counterexample.put, "Narrowing_Generators.put_counterexample")
   224       thy (Option.map o map) (ensure_testable t'') [] size
   225   in
   226     (result, NONE)
   227   end;
   228 
   229 
   230 val setup =
   231   Datatype.interpretation
   232     (Quickcheck_Common.ensure_sort_datatype (@{sort narrowing}, instantiate_narrowing_datatype))
   233   #> setup_finite_functions
   234   #> Context.theory_map
   235     (Quickcheck.add_generator ("narrowing", compile_generator_expr))
   236     
   237 end;