walther@59906
|
1 |
(* Title: Interpret/derive.sml
|
walther@59906
|
2 |
Author: Walther Neuper 2019
|
walther@59906
|
3 |
(c) due to copyright terms
|
walther@59906
|
4 |
|
walther@59906
|
5 |
|
walther@59906
|
6 |
*)
|
walther@59906
|
7 |
|
walther@59906
|
8 |
signature DERIVATION =
|
walther@59906
|
9 |
sig
|
walther@59906
|
10 |
type deriv
|
walther@59906
|
11 |
val make_deriv : theory -> Rule_Set.T -> Rule.rule list -> ((term * term) list -> term * term -> bool) ->
|
walther@59906
|
12 |
term option -> term -> deriv
|
walther@59906
|
13 |
val concat_deriv : 'a * ((term * term) list -> term * term -> bool) ->
|
walther@59906
|
14 |
Rule_Set.T -> Rule.rule list -> term -> term -> bool * (term * Rule.rule * (term * term list)) list
|
walther@59906
|
15 |
val reverse_deriv : theory -> Rule_Set.T -> Rule.rule list -> ((term * term) list -> term * term -> bool) ->
|
walther@59906
|
16 |
term option -> term -> (Rule.rule * (term * term list)) list
|
walther@59906
|
17 |
(* ---- for tests only: shifted from below to remove the Warning "unused" at fun.def. --------- *)
|
walther@59906
|
18 |
(* NONE *)
|
walther@59906
|
19 |
(*/-------------------------------------------------------- ! aktivate for Test_Isac BEGIN ---\* )
|
walther@59906
|
20 |
val trtas2str : (term * Rule.rule * (term * term list)) list -> string
|
walther@59906
|
21 |
val deriv2str : (term * Rule.rule * (term * term list)) list -> string
|
walther@59906
|
22 |
val rev_deriv' : 'a * Rule.rule * ('b * 'c) -> 'b * Rule.rule * ('a * 'c)
|
walther@59906
|
23 |
( *\--- ! aktivate for Test_Isac END ----------------------------------------------------------/*)
|
walther@59906
|
24 |
end
|
walther@59906
|
25 |
|
walther@59906
|
26 |
(**)
|
walther@59906
|
27 |
structure Derive(**): DERIVATION(**) =
|
walther@59906
|
28 |
struct
|
walther@59906
|
29 |
(**)
|
walther@59906
|
30 |
(*/------- to Derive from Rtools -------\*)
|
walther@59906
|
31 |
(*** reverse rewriting ***)
|
walther@59906
|
32 |
(*. a '_deriv'ation is constructed during 'reverse rewring' by an Rrls *
|
walther@59906
|
33 |
* of for connecting a user-input formula with the current calc-state. *
|
walther@59906
|
34 |
*# It is somewhat incompatible with the rest of the math-engine: *
|
walther@59906
|
35 |
* (1) it is not created by a script *
|
walther@59906
|
36 |
* (2) thus there cannot be another user-input within a derivation *
|
walther@59906
|
37 |
*# It suffers particularily from the not-well-foundedness of the math-engine*
|
walther@59906
|
38 |
* (1) FIXME other branchtyptes than Transitive will change 'embed_deriv' *
|
walther@59906
|
39 |
* (2) FIXME and eventually 'compare_step' (ie. the script interpreter) *
|
walther@59906
|
40 |
* (3) FIXME and eventually 'lev_back' *
|
walther@59906
|
41 |
*# SOME improvements are evident FIXME.040215 '_deriv'ation: *
|
walther@59906
|
42 |
* (1) FIXME nest Rls_ in 'make_deriv' *
|
walther@59906
|
43 |
* (2) FIXME do the not-reversed part in 'make_deriv' by scripts -- thus *
|
walther@59906
|
44 |
* user-input will become possible in this part of a derivation *
|
walther@59906
|
45 |
* (3) FIXME do (2) only if a derivation has been found -- for efficiency, *
|
walther@59906
|
46 |
* while a non-derivable inform requires to step until End_Proof' *
|
walther@59906
|
47 |
* (4) FIXME find criteria on when _not_ to step until End_Proof' *
|
walther@59906
|
48 |
* (5) FIXME
|
walther@59906
|
49 |
.*)
|
walther@59906
|
50 |
type deriv = (* derivation for inserting one level of nodes into the Ctree *)
|
walther@59906
|
51 |
( term * (* where the rule is applied to *)
|
walther@59906
|
52 |
Rule.rule * (* rule to be applied *)
|
walther@59906
|
53 |
( term * (* resulting from rule application *)
|
walther@59906
|
54 |
term list)) (* assumptions resulting from rule application *)
|
walther@59906
|
55 |
list
|
walther@59906
|
56 |
|
walther@59906
|
57 |
fun trta2str (t, r, (t', a)) =
|
walther@59906
|
58 |
"\n(" ^ UnparseC.term t ^ ", " ^ Rule.to_string_short r ^ ", (" ^ UnparseC.term t' ^ ", " ^ UnparseC.terms a ^ "))"
|
walther@59906
|
59 |
fun trtas2str trtas = (strs2str o (map trta2str)) trtas
|
walther@59906
|
60 |
val deriv2str = trtas2str
|
walther@59906
|
61 |
(*\------- to Derive from Rtools -------/*)
|
walther@59906
|
62 |
(*/------- to Derive from Rtools -------\*)
|
walther@59906
|
63 |
(* derive normalform of a rls, or derive until SOME goal,
|
walther@59906
|
64 |
and record rules applied and rewrites.
|
walther@59906
|
65 |
val it = fn
|
walther@59906
|
66 |
: theory
|
walther@59906
|
67 |
-> rls
|
walther@59906
|
68 |
-> rule list
|
walther@59906
|
69 |
-> rew_ord : the order of this rls, which 1 theorem of is used
|
walther@59906
|
70 |
for rewriting 1 single step (?14.4.03)
|
walther@59906
|
71 |
-> term option : 040214 ??? use for "derive until SOME goal" ???
|
walther@59906
|
72 |
-> term
|
walther@59906
|
73 |
-> (term * : to this term ...
|
walther@59906
|
74 |
rule * : ... this rule is applied yielding ...
|
walther@59906
|
75 |
(term * : ... this term ...
|
walther@59906
|
76 |
term list)) : ... under these assumptions.
|
walther@59906
|
77 |
list :
|
walther@59906
|
78 |
returns empty list for a normal form
|
walther@59906
|
79 |
FIXME.WN040214: treats rules as in Rls, _not_ as in Seq
|
walther@59906
|
80 |
|
walther@59906
|
81 |
WN060825 too complicated for the intended use by cancel_, common_nominator_
|
walther@59906
|
82 |
and unreflectedly adapted to extension of rules by Rls_: returns Rls_("sym_simpl..
|
walther@59906
|
83 |
-- replaced below *)
|
walther@59906
|
84 |
|
walther@59906
|
85 |
|
walther@59906
|
86 |
fun make_deriv thy erls rs ro goal tt =
|
walther@59906
|
87 |
let
|
walther@59906
|
88 |
datatype switch = Appl | Noap (* unify with version in rewrite.sml *)
|
walther@59906
|
89 |
fun rew_once _ rts t Noap [] =
|
walther@59906
|
90 |
(case goal of NONE => rts | SOME _ => error ("make_deriv: no derivation for " ^ UnparseC.term t))
|
walther@59906
|
91 |
| rew_once lim rts t Appl [] = rew_once lim rts t Noap rs
|
walther@59906
|
92 |
(*| Seq _ => rts) FIXXXXXME 14.3.03*)
|
walther@59906
|
93 |
| rew_once lim rts t apno rs' =
|
walther@59906
|
94 |
(case goal of
|
walther@59906
|
95 |
NONE => rew_or_calc lim rts t apno rs'
|
walther@59906
|
96 |
| SOME g => if g = t then rts else rew_or_calc lim rts t apno rs')
|
walther@59906
|
97 |
and rew_or_calc lim rts t apno (rrs' as (r :: rs')) =
|
walther@59906
|
98 |
if lim < 0
|
walther@59906
|
99 |
then (tracing ("make_deriv exceeds " ^ int2str (! Rewrite.lim_deriv) ^ "with deriv =\n");
|
walther@59906
|
100 |
tracing (deriv2str rts); rts)
|
walther@59906
|
101 |
else
|
walther@59906
|
102 |
(case r of
|
walther@59906
|
103 |
Rule.Thm (thmid, tm) =>
|
walther@59906
|
104 |
(if not (! Rewrite.trace_on) then () else tracing ("### trying thm \"" ^ thmid ^ "\"");
|
walther@59906
|
105 |
case Rewrite.rewrite_ thy ro erls true tm t of
|
walther@59906
|
106 |
NONE => rew_once lim rts t apno rs'
|
walther@59906
|
107 |
| SOME (t', a') =>
|
walther@59906
|
108 |
(if ! Rewrite.trace_on then tracing ("=== rewrites to: " ^ UnparseC.term t') else ();
|
walther@59906
|
109 |
rew_once (lim - 1) (rts @ [(t, r, (t', a'))]) t' Appl rrs'))
|
walther@59906
|
110 |
| Rule.Eval (c as (op_, _)) =>
|
walther@59906
|
111 |
let
|
walther@59906
|
112 |
val _ = if not (! Rewrite.trace_on) then () else tracing ("### trying calc. \"" ^ op_^"\"")
|
walther@59906
|
113 |
val t = TermC.uminus_to_string t
|
walther@59906
|
114 |
in
|
walther@59906
|
115 |
case Eval.adhoc_thm thy c t of
|
walther@59906
|
116 |
NONE => rew_once lim rts t apno rs'
|
walther@59906
|
117 |
| SOME (thmid, tm) =>
|
walther@59906
|
118 |
(let
|
walther@59906
|
119 |
val (t', a') = case Rewrite.rewrite_ thy ro erls true tm t of
|
walther@59906
|
120 |
SOME ta => ta
|
walther@59906
|
121 |
| NONE => error "adhoc_thm: NONE"
|
walther@59906
|
122 |
val _ = if not (! Rewrite.trace_on) then () else tracing("=== calc. to: " ^ UnparseC.term t')
|
walther@59906
|
123 |
val r' = Rule.Thm (thmid, tm)
|
walther@59906
|
124 |
in rew_once (lim - 1) (rts @ [(t, r', (t', a'))]) t' Appl rrs' end)
|
walther@59906
|
125 |
handle _ => raise ERROR "derive_norm, Eval: no rewrite"
|
walther@59906
|
126 |
end
|
walther@59906
|
127 |
| Rule.Rls_ rls => (* WN060829: CREATES "sym_rlsID", see 7df94616c1bd and earlier*)
|
walther@59906
|
128 |
(case Rewrite.rewrite_set_ thy true rls t of
|
walther@59906
|
129 |
NONE => rew_once lim rts t apno rs'
|
walther@59906
|
130 |
| SOME (t', a') => rew_once (lim - 1) (rts @ [(t, r, (t', a'))]) t' Appl rrs')
|
walther@59906
|
131 |
| rule => error ("rew_once: uncovered case " ^ Rule.to_string rule))
|
walther@59906
|
132 |
| rew_or_calc _ _ _ _ [] = error "rew_or_calc: called with []"
|
walther@59906
|
133 |
in rew_once (! Rewrite.lim_deriv) [] tt Noap rs end
|
walther@59906
|
134 |
|
walther@59906
|
135 |
(*version for reverse rewrite used before 040214*)
|
walther@59906
|
136 |
fun rev_deriv (t, r, (_, a)) = (ThmC.make_sym_rule r, (t, a));
|
walther@59906
|
137 |
fun reverse_deriv thy erls rs ro goal t =
|
walther@59906
|
138 |
(rev o (map rev_deriv)) (make_deriv thy erls rs ro goal t)
|
walther@59906
|
139 |
(*\------- to Derive from Rtools -------/*)
|
walther@59906
|
140 |
|
walther@59906
|
141 |
(*/------- to NEW Derive from Error_Fill_Pattern -------\*)
|
walther@59906
|
142 |
(* 040214: version for concat_deriv *)
|
walther@59906
|
143 |
fun rev_deriv' (t, r, (t', a)) = (t', ThmC.make_sym_rule r, (t, a));
|
walther@59906
|
144 |
|
walther@59906
|
145 |
(* fo = ifo excluded already in inform *)
|
walther@59906
|
146 |
fun concat_deriv rew_ord erls rules fo ifo =
|
walther@59906
|
147 |
let
|
walther@59906
|
148 |
fun derivat ([]:(term * Rule.rule * (term * term list)) list) = TermC.empty
|
walther@59906
|
149 |
| derivat dt = (#1 o #3 o last_elem) dt
|
walther@59906
|
150 |
fun equal (_,_,(t1, _)) (_,_,(t2, _)) = t1=t2
|
walther@59906
|
151 |
val fod = make_deriv (ThyC.Isac()) erls rules (snd rew_ord) NONE fo
|
walther@59906
|
152 |
val ifod = make_deriv (ThyC.Isac()) erls rules (snd rew_ord) NONE ifo
|
walther@59906
|
153 |
in
|
walther@59906
|
154 |
case (fod, ifod) of
|
walther@59906
|
155 |
([], []) => if fo = ifo then (true, []) else (false, [])
|
walther@59906
|
156 |
| (fod, []) => if derivat fod = ifo then (true, fod) (*ifo is normal form*) else (false, [])
|
walther@59906
|
157 |
| ([], ifod) => if fo = derivat ifod then (true, ((map rev_deriv') o rev) ifod) else (false, [])
|
walther@59906
|
158 |
| (fod, ifod) =>
|
walther@59906
|
159 |
if derivat fod = derivat ifod (*common normal form found*) then
|
walther@59906
|
160 |
let
|
walther@59906
|
161 |
val (fod', rifod') = dropwhile' equal (rev fod) (rev ifod)
|
walther@59906
|
162 |
in (true, fod' @ (map rev_deriv' rifod')) end
|
walther@59906
|
163 |
else (false, [])
|
walther@59906
|
164 |
end
|
walther@59906
|
165 |
(*\------- to NEW Derive from Error_Fill_Pattern-------/*)
|
walther@59906
|
166 |
|
walther@59906
|
167 |
(**)end(**)
|