2 (c) Walther Neuper 2000
7 val assoc_thm': theory -> ThmC.thm' -> thm
8 val assoc_thm'': theory -> ThmC.thmID -> thm
9 val calculate_: theory -> string * Exec_Def.eval_fn -> term -> (term * (string * thm)) option
10 val eval__true: theory -> int -> term list -> (term * term) list -> Rule_Set.T -> term list * bool
11 val eval_prog_expr: theory -> Rule_Set.T -> term -> term
12 val eval_true_: theory -> Rule_Set.T -> term -> bool
13 val eval_true: theory -> term list -> Rule_Set.T -> bool
14 val rew_sub: theory -> int -> (term * term) list -> ((term * term) list -> term * term -> bool)
15 -> Rule_Set.T -> bool -> TermC.path -> term -> term -> term * term list * TermC.path * bool
16 val rewrite_: theory -> ((term * term) list -> term * term -> bool) -> Rule_Set.T -> bool -> thm ->
17 term -> (term * term list) option
18 val rewrite_inst_: theory -> ((term * term) list -> term * term -> bool) -> Rule_Set.T -> bool
19 -> (term * term) list -> thm -> term -> (term * term list) option
20 val rewrite_set_: theory -> bool -> Rule_Set.T -> term -> (term * term list) option
21 val rewrite_set_inst_: theory -> bool -> (term * term) list -> Rule_Set.T -> term -> (term * term list) option
22 val rewrite_terms_: theory -> ((term * term) list -> term * term -> bool) -> Rule_Set.T -> term list
23 -> term -> (term * term list) option
24 (* ---- for tests only: shifted from below to remove the Warning "unused" at fun.def. --------- *)
26 (*/-------------------------------------------------------- ! aktivate for Test_Isac BEGIN ---\* )
27 val rewrite__: theory -> int -> (term * term) list -> ((term * term) list -> term * term -> bool) ->
28 Rule_Set.T -> bool -> thm -> term -> (term * term list) option
29 val rewrite__set_: theory -> int -> bool -> (term * term) list -> Rule_Set.T -> term -> (term * term list) option
30 val app_rev: theory -> int -> Rule_Set.T -> term -> term * term list * bool
31 val app_sub: theory -> int -> Rule_Set.T -> term -> term * term list * bool
32 val mk_thm: theory -> string -> thm
33 val trace1: int -> string -> unit
34 ( *\--- ! aktivate for Test_Isac END ----------------------------------------------------------/*)
38 structure Rewrite(**): REWRITE(**) =
43 exception STOP_REW_SUB; (*WN050820 quick and dirty*)
46 if ! Celem.trace_rewrite andalso i < ! Celem.depth then tracing (idt "#" i ^ str) else ()
48 if ! Celem.trace_rewrite andalso i < ! Celem.depth then tracing (idt "#" (i + 1) ^ str) else ()
50 fun rewrite__ thy i bdv tless rls put_asm thm ct =
52 val (t', asms, _ (*lrd*), rew) = rew_sub thy i bdv tless rls put_asm ([(*root of the term*)]: TermC.path)
53 (((TermC.inst_bdv bdv) o Num_Calc.norm o #prop o Thm.rep_thm) thm) ct
54 in if rew then SOME (t', distinct asms) else NONE end
55 (* one rewrite (possibly conditional, ordered) EXOR exn EXOR go into subterms *)
56 and rew_sub thy i bdv tless rls put_asm lrd r t =
58 val (lhs, rhs) = (HOLogic.dest_eq o HOLogic.dest_Trueprop o Logic.strip_imp_concl) r
59 (*?alternative Unify.matchers:
60 http://isabelle.in.tum.de/repos/isabelle/file/Isabelle2017/src/Pure/more_unify.ML*)
61 val r' = Envir.subst_term (Pattern.match thy (lhs, t) (Vartab.empty, Vartab.empty)) r
62 val p' = map HOLogic.dest_Trueprop ((fst o Logic.strip_prems) (Logic.count_prems r', [], r'))
63 val t' = (snd o HOLogic.dest_eq o HOLogic.dest_Trueprop o Logic.strip_imp_concl) r'
64 val _ = if ! Celem.trace_rewrite andalso i < ! Celem.depth andalso p' <> []
65 then tracing (idt "#" (i + 1) ^ " eval asms: " ^ UnparseC.t2str thy r') else ()
66 val (t'', p'') = (*conditional rewriting*)
68 val (simpl_p', nofalse) = eval__true thy (i + 1) p' bdv rls
72 (if ! Celem.trace_rewrite andalso i < ! Celem.depth andalso p' <> []
73 then tracing (idt "#" (i + 1) ^ " asms accepted: " ^ UnparseC.ts2str thy p' ^
74 " stored: " ^ UnparseC.ts2str thy simpl_p')
76 (t',simpl_p')) (* uncond.rew. from above*)
78 (if ! Celem.trace_rewrite andalso i < ! Celem.depth
79 then tracing (idt "#" (i + 1) ^ " asms false: " ^ UnparseC.ts2str thy p')
81 raise STOP_REW_SUB (* don't go into subterms of cond *))
84 if TermC.perm lhs rhs andalso not (tless bdv (t', t)) (*ordered rewriting*)
85 then (if ! Celem.trace_rewrite andalso i < ! Celem.depth
86 then tracing (idt"#"i ^ " not: \"" ^ UnparseC.t2str thy t ^ "\" > \"" ^ UnparseC.t2str thy t' ^ "\"")
89 else (t'', p'', [], true)
91 ) handle _ (*TODO Pattern.MATCH when tests are ready: ERROR 364ce4699452 *) =>
93 Const(s,T) => (Const(s,T),[],lrd,false)
94 | Free(s,T) => (Free(s,T),[],lrd,false)
95 | Var(n,T) => (Var(n,T),[],lrd,false)
96 | Bound i => (Bound i,[],lrd,false)
98 let val (t', asms, _ (*lrd*), rew) = rew_sub thy i bdv tless rls put_asm (lrd @ [TermC.D]) r body
99 in (Abs(s, T, t'), asms, [], rew) end
101 let val (t2', asm2, lrd, rew2) = rew_sub thy i bdv tless rls put_asm (lrd @ [TermC.R]) r t2
103 if rew2 then (t1 $ t2', asm2, lrd, true)
105 let val (t1', asm1, lrd, rew1) = rew_sub thy i bdv tless rls put_asm (lrd @ [TermC.L]) r t1
106 in if rew1 then (t1' $ t2, asm1, lrd, true) else (t1 $ t2,[], lrd, false) end
108 and eval__true thy i asms bdv rls = (* simplify asumptions until one evaluates to false *)
109 if asms = [@{term True}] orelse asms = [] then ([], true)
110 else (* this allows to check Rrls with prepat = ([@{term True}], pat) *)
111 if asms = [@{term False}] then ([], false)
114 fun chk indets [] = (indets, true) (*return asms<>True until false*)
115 | chk indets (a :: asms) =
116 (case rewrite__set_ thy (i + 1) false bdv rls a of
117 NONE => (chk (indets @ [a]) asms)
119 if t = @{term True} then (chk (indets @ a') asms)
120 else if t = @{term False} then ([], false)
121 (*asm false .. thm not applied ^^^; continue until False vvv*)
122 else chk (indets @ [t] @ a') asms);
124 and rewrite__set_ thy _ __ Rule_Set.Empty t = (* rewrite with a rule set *)
125 error ("rewrite__set_ called with 'Erls' for '" ^ UnparseC.t2str thy t ^ "'")
126 | rewrite__set_ thy i _ _ (rrls as Rule_Set.Rrls _) t = (* rewrite with a 'reverse rule set' *)
128 val _= trace i (" rls: " ^ Rule_Set.rls2str rrls ^ " on: " ^ UnparseC.t2str thy t)
129 val (t', asm, rew) = app_rev thy (i + 1) rrls t
130 in if rew then SOME (t', distinct asm) else NONE end
131 | rewrite__set_ thy i put_asm bdv rls ct = (* Rls, Seq containing Thms or Num_Calc, Cal1 *)
133 (* attention with cp to test/..: unbound thy, i, bdv, rls; TODO1803? pull out to rewrite__*)
134 datatype switch = Appl | Noap;
135 fun rew_once _ asm ct Noap [] = (ct, asm) (* ?TODO unify with Prog_Expr.rew_once? *)
136 | rew_once ruls asm ct Appl [] =
137 (case rls of Rule_Def.Repeat _ => rew_once ruls asm ct Noap ruls
138 | Rule_Set.Seqence _ => (ct, asm)
139 | rls => raise ERROR ("rew_once not appl. to \"" ^ Rule_Set.rls2str rls ^ "\""))
140 | rew_once ruls asm ct apno (rul :: thms) =
142 Rule.Thm (thmid, thm) =>
143 (trace1 i (" try thm: \"" ^ thmid ^ "\"");
144 case rewrite__ thy (i + 1) bdv ((snd o #rew_ord o Rule_Set.rep) rls)
145 ((#erls o Rule_Set.rep) rls) put_asm thm ct of
146 NONE => rew_once ruls asm ct apno thms
147 | SOME (ct', asm') =>
148 (trace1 i (" rewrites to: \"" ^ UnparseC.t2str thy ct' ^ "\"");
149 rew_once ruls (union (op =) asm asm') ct' Appl (rul :: thms)))
150 (* once again try the same rule, e.g. associativity against "()"*)
151 | Rule.Num_Calc (cc as (op_, _)) =>
152 let val _= trace1 i (" try calc: \"" ^ op_ ^ "\"")
153 val ct = TermC.uminus_to_string ct (*WN190312: superfluous?*)
154 in case Num_Calc.adhoc_thm thy cc ct of
155 NONE => rew_once ruls asm ct apno thms
158 val pairopt = rewrite__ thy (i + 1) bdv ((snd o #rew_ord o Rule_Set.rep) rls)
159 ((#erls o Rule_Set.rep) rls) put_asm thm' ct;
160 val _ = if pairopt <> NONE then () else error ("rewrite_set_, rewrite_ \"" ^
161 ThmC.string_of_thmI thm' ^ "\" " ^ UnparseC.t2str thy ct ^ " = NONE")
162 val _ = trace1 i (" calc. to: " ^ UnparseC.t2str thy ((fst o the) pairopt))
163 in rew_once ruls asm ((fst o the) pairopt) Appl (rul :: thms) end
165 | Rule.Cal1 (cc as (op_, _)) =>
166 let val _= trace1 i (" try cal1: " ^ op_ ^ "'");
167 val ct = TermC.uminus_to_string ct
168 in case Num_Calc.adhoc_thm1_ thy cc ct of
172 val pairopt = rewrite__ thy (i + 1) bdv ((snd o #rew_ord o Rule_Set.rep) rls)
173 ((#erls o Rule_Set.rep) rls) put_asm thm' ct;
174 val _ = if pairopt <> NONE then () else error ("rewrite_set_, rewrite_ \"" ^
175 ThmC.string_of_thmI thm' ^ "\" " ^ UnparseC.t2str thy ct ^ " = NONE")
176 val _ = trace1 i (" cal1. to: " ^ UnparseC.t2str thy ((fst o the) pairopt))
180 (case rewrite__set_ thy (i + 1) put_asm bdv rls' ct of
181 SOME (t', asm') => rew_once ruls (union (op =) asm asm') t' Appl thms
182 | NONE => rew_once ruls asm ct apno thms)
183 | r => raise ERROR ("rew_once not appl. to \"" ^ Rule.rule2str r ^ "\"");
184 val ruls = (#rules o Rule_Set.rep) rls;
185 val _ = trace i (" rls: " ^ Rule_Set.rls2str rls ^ " on: " ^ UnparseC.t2str thy ct)
186 val (ct', asm') = rew_once ruls [] ct Noap ruls;
187 in if ct = ct' then NONE else SOME (ct', distinct asm') end
188 (*------------------------
189 -------------------------------------*)
190 and app_rev thy i rrls t = (* apply an Rrls; if not applicable proceed with subterms *)
191 let (* check a (precond, pattern) of a rev-set; stops with 1st true *)
192 fun chk_prepat _ _ [] _ = true
193 | chk_prepat thy erls prepat t =
195 fun chk (pres, pat) =
197 val subst: Type.tyenv * Envir.tenv =
198 Pattern.match thy (pat, t) (Vartab.empty, Vartab.empty)
200 snd (eval__true thy (i + 1) (map (Envir.subst_term subst) pres) [] erls)
201 end) handle _ (*TODO Pattern.MATCH*) => false
202 fun scan_ _ [] = false
203 | scan_ f (pp :: pps) =
204 if f pp then true else scan_ f pps;
205 in scan_ chk prepat end;
206 (* apply the normal_form of a rev-set *)
207 fun app_rev' thy (Rule_Set.Rrls {erls, prepat, scr = Rule.Rfuns {normal_form, ...}, ...}) t =
208 if chk_prepat thy erls prepat t then normal_form t else NONE
209 | app_rev' _ r _ = raise ERROR ("app_rev' not appl. to \"" ^ Rule_Set.rls2str r ^ "\"");
210 val opt = app_rev' thy rrls t
213 SOME (t', asm) => (t', asm, true)
214 | NONE => app_sub thy i rrls t
216 and app_sub thy i rrls t = (* apply an Rrls to subterms *)
218 Const (s, T) => (Const(s, T), [], false)
219 | Free (s, T) => (Free(s, T), [], false)
220 | Var (n, T) => (Var(n, T), [], false)
221 | Bound i => (Bound i, [], false)
222 | Abs (s, T, body) =>
223 let val (t', asm, rew) = app_rev thy i rrls body
224 in (Abs(s, T, t'), asm, rew) end
226 let val (t2', asm2, rew2) = app_rev thy i rrls t2
228 if rew2 then (t1 $ t2', asm2, true)
230 let val (t1', asm1, rew1) = app_rev thy i rrls t1
231 in if rew1 then (t1' $ t2, asm1, true)
232 else (t1 $ t2, [], false)
236 (* rewriting without argument [] for rew_ord; WN110603: shouldnt asm<>[] lead to false? *)
237 fun eval_true thy terms rls = (snd o (eval__true thy 1 terms [])) rls;
239 (* rewriting without internal argument [] *)
240 fun rewrite_ thy rew_ord erls bool thm term = rewrite__ thy 1 [] rew_ord erls bool thm term;
241 fun rewrite_set_ thy bool rls term = rewrite__set_ thy 1 bool [] rls term;
243 (* variants of rewrite; TODO del. put_asm *)
244 fun rewrite_inst_ thy rew_ord rls put_asm subst thm ct =
245 rewrite__ thy 1 subst rew_ord rls put_asm thm ct;
246 fun rewrite_set_inst_ thy put_asm subst rls ct = rewrite__set_ thy 1 put_asm subst rls ct;
248 (* given a list of equalities (lhs = rhs) and a term,
249 replace all occurrences of lhs in the term with rhs;
250 thus the order or equalities matters: put variables in lhs first. *)
251 fun rewrite_terms_ thy ord erls equs t =
253 fun rew_ (t', asm') [] _ = (t', asm')
254 | rew_ (t', asm') (rules as r::rs) t =
256 val (t'', asm'', _(*lrd*), rew) = rew_sub thy 1 [] ord erls false [] (HOLogic.Trueprop $ r) t
259 then rew_ (t'', asm' @ asm'') rules t''
260 else rew_ (t', asm') rs t'
262 val (t'', asm'') = rew_ (TermC.empty, []) equs t
263 in if t'' = TermC.empty then NONE else SOME (t'', asm'')
266 (* search ct for adjacent numerals and calculate them by operator isa_fn *)
267 fun calculate_ thy isa_fn ct =
268 let val ct = TermC.uminus_to_string ct
269 in case Num_Calc.adhoc_thm thy isa_fn ct of
271 | SOME (thmID, thm) =>
272 (let val rew = case rewrite_ thy Rewrite_Ord.dummy_ord Rule_Set.empty false thm ct of
274 | NONE => raise ERROR ""
275 in SOME (rew, (thmID, thm)) end)
276 handle _ (*TODO Pattern.MATCH ?del?*)=> error ("calculate_: " ^ thmID ^ " does not rewrite")
279 (* Thm.make_thm added to Pure/thm.ML *)
282 val t = (Thm.term_of o the o (TermC.parse thy)) str
284 Const ("Pure.imp", _) $ _ $ _ => t
285 | _ => HOLogic.Trueprop $ t
286 in Thm.make_thm (Thm.global_cterm_of thy t') end;
288 (* "metaview" as seen from programs and from user input (both are parsed like terms presently) *)
289 fun convert_metaview_to_thmid thy thmid =
290 let val thmid' = case thmid of
291 "add_commute" => "add.commute"
292 | "mult_commute" => "mult.commute"
293 | "add_left_commute" => "add.left_commute"
294 | "mult_left_commute" => "mult.left_commute"
295 | "add_assoc" => "add.assoc"
296 | "mult_assoc" => "mult.assoc"
298 in (Global_Theory.get_thm thy) thmid' end;
300 (* get the theorem associated with the xstring-identifier;
301 if the identifier starts with "sym_" then swap lhs = rhs around =
302 (ATTENTION: "RS sym" attaches a [.] -- remove it with ThmC.string_of_thmI);
303 identifiers starting with "#" come from Num_Calc and
304 get a hand-made theorem (containing numerals only) *)
305 fun assoc_thm'' thy thmid =
306 case Symbol.explode thmid of
307 "s"::"y"::"m"::"_"::"#"::_ => error ("assoc_thm'' not impl.for " ^ thmid)
308 | "s"::"y"::"m"::"_"::id => ((TermC.num_str o (Global_Theory.get_thm thy)) (implode id)) RS sym
309 | "#"::_ => error ("assoc_thm'' not impl.for " ^ thmid)
310 | _ => thmid |> convert_metaview_to_thmid thy |> TermC.num_str
311 fun assoc_thm' thy (thmid, ct') =
312 (case Symbol.explode thmid of
313 "s"::"y"::"m"::"_"::id =>
316 else ((TermC.num_str o (Global_Theory.get_thm thy)) (implode id)) RS sym
320 else thmid |> convert_metaview_to_thmid thy |> TermC.num_str
321 ) handle _ (*TODO: find exn behind ERROR: Undefined fact: "add_commute"*) =>
322 error ("assoc_thm': \"" ^ thmid ^ "\" not in \"" ^ ThyC.theory2domID thy ^ "\" (and parents)")
324 fun eval_prog_expr thy srls t =
325 let val rew = rewrite_set_ thy false srls t;
326 in case rew of SOME (res,_) => res | NONE => t end;
328 fun eval_true_ _ _ (Const ("HOL.True",_)) = true
329 | eval_true_ thy rls t =
330 case rewrite_set_ thy false rls t of
331 SOME (Const ("HOL.True",_),_) => true