author  clasohm 
Mon, 29 Jan 1996 14:16:13 +0100  
changeset 1460  5a6f2aabd538 
parent 1458  fd510875fb71 
child 1500  b2de3b3277b8 
permissions  rwrr 
1460  1 
(* Title: Pure/goals.ML 
0  2 
ID: $Id$ 
1460  3 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 
0  4 
Copyright 1993 University of Cambridge 
5 

6 
Goal stack package. The goal stack initially holds a dummy proof, and can 

7 
never become empty. Each goal stack consists of a list of levels. The 

8 
undo list is a list of goal stacks. Finally, there may be a stack of 

9 
pending proofs. 

10 
*) 

11 

12 

13 
signature GOALS = 

14 
sig 

15 
structure Tactical: TACTICAL 

16 
local open Tactical Tactical.Thm in 

17 
type proof 

1460  18 
val ba : int > unit 
19 
val back : unit > unit 

20 
val bd : thm > int > unit 

21 
val bds : thm list > int > unit 

22 
val be : thm > int > unit 

23 
val bes : thm list > int > unit 

24 
val br : thm > int > unit 

25 
val brs : thm list > int > unit 

26 
val bw : thm > unit 

27 
val bws : thm list > unit 

28 
val by : tactic > unit 

29 
val byev : tactic list > unit 

30 
val chop : unit > unit 

31 
val choplev : int > unit 

32 
val fa : unit > unit 

33 
val fd : thm > unit 

34 
val fds : thm list > unit 

35 
val fe : thm > unit 

36 
val fes : thm list > unit 

37 
val filter_goal : (term*term>bool) > thm list > int > thm list 

38 
val fr : thm > unit 

39 
val frs : thm list > unit 

40 
val getgoal : int > term 

41 
val gethyps : int > thm list 

42 
val goal : theory > string > thm list 

43 
val goalw : theory > thm list > string > thm list 

44 
val goalw_cterm : thm list > cterm > thm list 

45 
val pop_proof : unit > thm list 

46 
val pr : unit > unit 

47 
val premises : unit > thm list 

48 
val prin : term > unit 

49 
val printyp : typ > unit 

50 
val pprint_term : term > pprint_args > unit 

51 
val pprint_typ : typ > pprint_args > unit 

52 
val print_exn : exn > 'a 

53 
val print_sign_exn : Sign.sg > exn > 'a 

54 
val prlev : int > unit 

55 
val proof_timing : bool ref 

56 
val prove_goal : theory > string > (thm list > tactic list) > thm 

577  57 
val prove_goalw : theory>thm list>string>(thm list>tactic list)>thm 
1460  58 
val prove_goalw_cterm : thm list>cterm>(thm list>tactic list)>thm 
59 
val push_proof : unit > unit 

60 
val read : string > term 

61 
val ren : string > int > unit 

62 
val restore_proof : proof > thm list 

63 
val result : unit > thm 

64 
val rotate_proof : unit > thm list 

65 
val uresult : unit > thm 

66 
val save_proof : unit > proof 

67 
val topthm : unit > thm 

68 
val undo : unit > unit 

0  69 
end 
70 
end; 

71 

72 
functor GoalsFun (structure Logic: LOGIC and Drule: DRULE and Tactic: TACTIC 

73 
and Pattern:PATTERN 

1460  74 
sharing type Pattern.type_sig = Drule.Thm.Sign.Type.type_sig 
0  75 
and Drule.Thm = Tactic.Tactical.Thm) : GOALS = 
76 
struct 

77 
structure Tactical = Tactic.Tactical 

78 
local open Tactic Tactic.Tactical Tactic.Tactical.Thm Drule 

79 
in 

80 

81 
(*Each level of goal stack includes a proof state and alternative states, 

82 
the output of the tactic applied to the preceeding level. *) 

83 
type gstack = (thm * thm Sequence.seq) list; 

84 

85 
datatype proof = Proof of gstack list * thm list * (bool*thm>thm); 

86 

87 
(*** References ***) 

88 

89 
(*Should process time be printed after proof steps?*) 

90 
val proof_timing = ref false; 

91 

92 
(*Current assumption list  set by "goal".*) 

93 
val curr_prems = ref([] : thm list); 

94 

95 
(*Return assumption list  useful if you didn't save "goal"'s result. *) 

96 
fun premises() = !curr_prems; 

97 

98 
(*Current result maker  set by "goal", used by "result". *) 

99 
val curr_mkresult = 

100 
ref((fn _=> error"No goal has been supplied in subgoal module") 

101 
: bool*thm>thm); 

102 

922
196ca0973a6d
added CPure (curried functions) and ProtoPure (ancestor of Pure and CPure)
clasohm
parents:
914
diff
changeset

103 
val dummy = trivial(read_cterm Sign.proto_pure 
0  104 
("PROP No_goal_has_been_supplied",propT)); 
105 

106 
(*List of previous goal stacks, for the undo operation. Set by setstate. 

107 
A list of lists!*) 

108 
val undo_list = ref([[(dummy, Sequence.null)]] : gstack list); 

109 

110 
(* Stack of proof attempts *) 

111 
val proofstack = ref([]: proof list); 

112 

113 

114 
(*** Setting up goaldirected proof ***) 

115 

116 
(*Generates the list of new theories when the proof state's signature changes*) 

117 
fun sign_error (sign,sign') = 

118 
let val stamps = #stamps(Sign.rep_sg sign') \\ 

119 
#stamps(Sign.rep_sg sign) 

120 
in case stamps of 

121 
[stamp] => "\nNew theory: " ^ !stamp 

122 
 _ => "\nNew theories: " ^ space_implode ", " (map ! stamps) 

123 
end; 

124 

125 
(*Common treatment of "goal" and "prove_goal": 

126 
Return assumptions, initial proof state, and function to make result. *) 

127 
fun prepare_proof rths chorn = 

230  128 
let val {sign, t=horn,...} = rep_cterm chorn; 
0  129 
val (_,As,B) = Logic.strip_horn(horn); 
230  130 
val cAs = map (cterm_of sign) As; 
1413  131 
val prems = map (rewrite_rule rths o forall_elim_vars(0) o assume) cAs 
132 
and st0 = (rewrite_goals_rule rths o trivial) (cterm_of sign B) 

0  133 
fun result_error state msg = 
134 
(writeln ("Bad final proof state:"); 

1460  135 
!print_goals_ref (!goals_limit) state; 
136 
error msg) 

0  137 
(*discharges assumptions from state in the order they appear in goal; 
1460  138 
checks (if requested) that resulting theorem is equivalent to goal. *) 
0  139 
fun mkresult (check,state) = 
696
eb5b42442b14
Pure/goals/prepare_proof/mkresult: now smashes flexflex pairs in the final
lcp
parents:
678
diff
changeset

140 
let val state = Sequence.hd (flexflex_rule state) 
1460  141 
handle _ => state (*smash flexflex pairs*) 
142 
val ngoals = nprems_of state 

1219  143 
val th = strip_shyps (implies_intr_list cAs state) 
1240  144 
val {hyps,prop,sign=sign',...} = rep_thm th 
145 
val xshyps = extra_shyps th; 

0  146 
in if not check then standard th 
1460  147 
else if not (Sign.eq_sg(sign,sign')) then result_error state 
148 
("Signature of proof state has changed!" ^ 

149 
sign_error (sign,sign')) 

0  150 
else if ngoals>0 then result_error state 
1460  151 
(string_of_int ngoals ^ " unsolved goals!") 
0  152 
else if not (null hyps) then result_error state 
153 
("Additional hypotheses:\n" ^ 

154 
cat_lines (map (Sign.string_of_term sign) hyps)) 

1460  155 
else if not (null xshyps) then result_error state 
1240  156 
("Extra sort hypotheses: " ^ 
157 
commas (map Sign.Type.str_of_sort xshyps)) 

1460  158 
else if Pattern.matches (#tsig(Sign.rep_sg sign)) 
159 
(term_of chorn, prop) 

160 
then standard th 

161 
else result_error state "proved a different theorem" 

0  162 
end 
678
6151b7f3b606
Modified pattern.ML to perform proper matching of HigherOrder Patterns.
nipkow
parents:
577
diff
changeset

163 
in 
6151b7f3b606
Modified pattern.ML to perform proper matching of HigherOrder Patterns.
nipkow
parents:
577
diff
changeset

164 
if Sign.eq_sg(sign, #sign(rep_thm st0)) 
0  165 
then (prems, st0, mkresult) 
166 
else error ("Definitions would change the proof state's signature" ^ 

1460  167 
sign_error (sign, #sign(rep_thm st0))) 
0  168 
end 
169 
handle THM(s,_,_) => error("prepare_proof: exception THM was raised!\n" ^ s); 

170 

171 
(*Prints exceptions readably to users*) 

577  172 
fun print_sign_exn_unit sign e = 
0  173 
case e of 
174 
THM (msg,i,thms) => 

1460  175 
(writeln ("Exception THM " ^ string_of_int i ^ " raised:\n" ^ msg); 
176 
seq print_thm thms) 

0  177 
 THEORY (msg,thys) => 
1460  178 
(writeln ("Exception THEORY raised:\n" ^ msg); 
179 
seq print_theory thys) 

0  180 
 TERM (msg,ts) => 
1460  181 
(writeln ("Exception TERM raised:\n" ^ msg); 
182 
seq (writeln o Sign.string_of_term sign) ts) 

0  183 
 TYPE (msg,Ts,ts) => 
1460  184 
(writeln ("Exception TYPE raised:\n" ^ msg); 
185 
seq (writeln o Sign.string_of_typ sign) Ts; 

186 
seq (writeln o Sign.string_of_term sign) ts) 

0  187 
 e => raise e; 
188 

577  189 
(*Prints an exception, then fails*) 
190 
fun print_sign_exn sign e = (print_sign_exn_unit sign e; raise ERROR); 

191 

0  192 
(** the prove_goal.... commands 
193 
Prove theorem using the listed tactics; check it has the specified form. 

194 
Augment signature with all type assignments of goal. 

195 
Syntax is similar to "goal" command for easy keyboard use. **) 

196 

197 
(*Version taking the goal as a cterm*) 

198 
fun prove_goalw_cterm rths chorn tacsf = 

199 
let val (prems, st0, mkresult) = prepare_proof rths chorn 

200 
val tac = EVERY (tacsf prems) 

201 
fun statef() = 

1460  202 
(case Sequence.pull (tapply(tac,st0)) of 
203 
Some(st,_) => st 

204 
 _ => error ("prove_goal: tactic failed")) 

545
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

205 
in mkresult (true, cond_timeit (!proof_timing) statef) end 
914
cae574c09137
Now prove_goalw_cterm calls print_sign_exn_unit, so that the rest
lcp
parents:
696
diff
changeset

206 
handle e => (print_sign_exn_unit (#sign (rep_cterm chorn)) e; 
1460  207 
error ("The exception above was raised for\n" ^ 
208 
string_of_cterm chorn)); 

545
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

209 

0  210 

211 
(*Version taking the goal as a string*) 

212 
fun prove_goalw thy rths agoal tacsf = 

213 
let val sign = sign_of thy 

230  214 
val chorn = read_cterm sign (agoal,propT) 
545
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

215 
in prove_goalw_cterm rths chorn tacsf end 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

216 
handle ERROR => error (*from read_cterm?*) 
1460  217 
("The error above occurred for " ^ quote agoal); 
0  218 

219 
(*String version with no metarewriterules*) 

220 
fun prove_goal thy = prove_goalw thy []; 

221 

222 

223 
(*** Commands etc ***) 

224 

225 
(*Return the current goal stack, if any, from undo_list*) 

226 
fun getstate() : gstack = case !undo_list of 

227 
[] => error"No current state in subgoal module" 

228 
 x::_ => x; 

229 

230 
(*Pops the given goal stack*) 

231 
fun pop [] = error"Cannot go back past the beginning of the proof!" 

232 
 pop (pair::pairs) = (pair,pairs); 

233 

234 

235 
(*Print a level of the goal stack.*) 

236 
fun print_top ((th,_), pairs) = 

237 
(prs("Level " ^ string_of_int(length pairs) ^ "\n"); 

68
d8f380764934
goals/print_top,prepare_proof: now call \!print_goals_ref
lcp
parents:
39
diff
changeset

238 
!print_goals_ref (!goals_limit) th); 
0  239 

240 
(*Printing can raise exceptions, so the assignment occurs last. 

241 
Can do setstate[(st,Sequence.null)] to set st as the state. *) 

242 
fun setstate newgoals = 

243 
(print_top (pop newgoals); undo_list := newgoals :: !undo_list); 

244 

245 
(*Given a proof state transformation, return a command that updates 

246 
the goal stack*) 

247 
fun make_command com = setstate (com (pop (getstate()))); 

248 

249 
(*Apply a function on proof states to the current goal stack*) 

250 
fun apply_fun f = f (pop(getstate())); 

251 

252 
(*Return the top theorem, representing the proof state*) 

253 
fun topthm () = apply_fun (fn ((th,_), _) => th); 

254 

255 
(*Return the final result. *) 

256 
fun result () = !curr_mkresult (true, topthm()); 

257 

258 
(*Return the result UNCHECKED that it equals the goal  for synthesis, 

259 
answer extraction, or other instantiation of Vars *) 

260 
fun uresult () = !curr_mkresult (false, topthm()); 

261 

262 
(*Get subgoal i from goal stack*) 

263 
fun getgoal i = 

264 
(case drop (i1, prems_of (topthm())) of 

1460  265 
[] => error"getgoal: Goal number out of range" 
266 
 Q::_ => Q); 

0  267 

268 
(*Return subgoal i's hypotheses as metalevel assumptions. 

269 
For debugging uses of METAHYPS*) 

270 
local exception GETHYPS of thm list 

271 
in 

272 
fun gethyps i = 

273 
(tapply(METAHYPS (fn hyps => raise (GETHYPS hyps)) i, topthm()); []) 

274 
handle GETHYPS hyps => hyps 

275 
end; 

276 

277 
(*Which thms could apply to goal i? (debugs tactics involving filter_thms) *) 

278 
fun filter_goal could ths i = filter_thms could (999, getgoal i, ths); 

279 

280 
(*For inspecting earlier levels of the backward proof*) 

281 
fun chop_level n (pair,pairs) = 

282 
let val level = length pairs 

283 
in if 0<=n andalso n<= level 

284 
then drop (level  n, pair::pairs) 

285 
else error ("Level number must lie between 0 and " ^ 

1460  286 
string_of_int level) 
0  287 
end; 
288 

289 
(*Print the given level of the proof*) 

290 
fun prlev n = apply_fun (print_top o pop o (chop_level n)); 

291 
fun pr () = apply_fun print_top; 

292 

293 
(** the goal.... commands 

294 
Read main goal. Set global variables curr_prems, curr_mkresult. 

295 
Initial subgoal and premises are rewritten using rths. **) 

296 

297 
(*Version taking the goal as a cterm; if you have a term t and theory thy, use 

230  298 
goalw_cterm rths (cterm_of (sign_of thy) t); *) 
0  299 
fun goalw_cterm rths chorn = 
300 
let val (prems, st0, mkresult) = prepare_proof rths chorn 

301 
in undo_list := []; 

302 
setstate [ (st0, Sequence.null) ]; 

303 
curr_prems := prems; 

304 
curr_mkresult := mkresult; 

305 
prems 

306 
end; 

307 

308 
(*Version taking the goal as a string*) 

309 
fun goalw thy rths agoal = 

230  310 
goalw_cterm rths (read_cterm(sign_of thy)(agoal,propT)) 
0  311 
handle ERROR => error (*from type_assign, etc via prepare_proof*) 
1460  312 
("The error above occurred for " ^ quote agoal); 
0  313 

314 
(*String version with no metarewriterules*) 

315 
fun goal thy = goalw thy []; 

316 

317 
(*Proof step "by" the given tactic  apply tactic to the proof state*) 

318 
fun by_com tac ((th,ths), pairs) : gstack = 

319 
(case Sequence.pull(tapply(tac, th)) of 

320 
None => error"by: tactic failed" 

321 
 Some(th2,ths2) => 

322 
(if eq_thm(th,th2) 

1460  323 
then writeln"Warning: same as previous level" 
324 
else if eq_thm_sg(th,th2) then () 

325 
else writeln("Warning: signature of proof state has changed" ^ 

326 
sign_error (#sign(rep_thm th), #sign(rep_thm th2))); 

0  327 
((th2,ths2)::(th,ths)::pairs))); 
328 

329 
fun by tac = cond_timeit (!proof_timing) 

330 
(fn() => make_command (by_com tac)); 

331 

332 
(* byev[tac1,...,tacn] applies tac1 THEN ... THEN tacn. 

333 
Good for debugging proofs involving prove_goal.*) 

334 
val byev = by o EVERY; 

335 

336 

337 
(*Backtracking means find an alternative result from a tactic. 

338 
If none at this level, try earlier levels*) 

339 
fun backtrack [] = error"back: no alternatives" 

340 
 backtrack ((th,thstr) :: pairs) = 

341 
(case Sequence.pull thstr of 

1460  342 
None => (writeln"Going back a level..."; backtrack pairs) 
343 
 Some(th2,thstr2) => 

344 
(if eq_thm(th,th2) 

345 
then writeln"Warning: same as previous choice at this level" 

346 
else if eq_thm_sg(th,th2) then () 

347 
else writeln"Warning: signature of proof state has changed"; 

348 
(th2,thstr2)::pairs)); 

0  349 

350 
fun back() = setstate (backtrack (getstate())); 

351 

352 
(*Chop back to previous level of the proof*) 

353 
fun choplev n = make_command (chop_level n); 

354 

355 
(*Chopping back the goal stack*) 

356 
fun chop () = make_command (fn (_,pairs) => pairs); 

357 

358 
(*Restore the previous proof state; discard current state. *) 

359 
fun undo() = case !undo_list of 

360 
[] => error"No proof state" 

361 
 [_] => error"Already at initial state" 

362 
 _::newundo => (undo_list := newundo; pr()) ; 

363 

364 

365 
(*** Managing the proof stack ***) 

366 

367 
fun save_proof() = Proof(!undo_list, !curr_prems, !curr_mkresult); 

368 

369 
fun restore_proof(Proof(ul,prems,mk)) = 

370 
(undo_list:= ul; curr_prems:= prems; curr_mkresult := mk; prems); 

371 

372 

373 
fun top_proof() = case !proofstack of 

1460  374 
[] => error("Stack of proof attempts is empty!") 
0  375 
 p::ps => (p,ps); 
376 

377 
(* push a copy of the current proof state on to the stack *) 

378 
fun push_proof() = (proofstack := (save_proof() :: !proofstack)); 

379 

380 
(* discard the top proof state of the stack *) 

381 
fun pop_proof() = 

382 
let val (p,ps) = top_proof() 

383 
val prems = restore_proof p 

384 
in proofstack := ps; pr(); prems end; 

385 

386 
(* rotate the stack so that the top element goes to the bottom *) 

387 
fun rotate_proof() = let val (p,ps) = top_proof() 

1460  388 
in proofstack := ps@[save_proof()]; 
389 
restore_proof p; 

390 
pr(); 

391 
!curr_prems 

392 
end; 

0  393 

394 

395 
(** Shortcuts for commonlyused tactics **) 

396 

397 
fun bws rls = by (rewrite_goals_tac rls); 

398 
fun bw rl = bws [rl]; 

399 

400 
fun brs rls i = by (resolve_tac rls i); 

401 
fun br rl = brs [rl]; 

402 

403 
fun bes rls i = by (eresolve_tac rls i); 

404 
fun be rl = bes [rl]; 

405 

406 
fun bds rls i = by (dresolve_tac rls i); 

407 
fun bd rl = bds [rl]; 

408 

409 
fun ba i = by (assume_tac i); 

410 

411 
fun ren str i = by (rename_tac str i); 

412 

413 
(** Shortcuts to work on the first applicable subgoal **) 

414 

415 
fun frs rls = by (FIRSTGOAL (trace_goalno_tac (resolve_tac rls))); 

416 
fun fr rl = frs [rl]; 

417 

418 
fun fes rls = by (FIRSTGOAL (trace_goalno_tac (eresolve_tac rls))); 

419 
fun fe rl = fes [rl]; 

420 

421 
fun fds rls = by (FIRSTGOAL (trace_goalno_tac (dresolve_tac rls))); 

422 
fun fd rl = fds [rl]; 

423 

424 
fun fa() = by (FIRSTGOAL (trace_goalno_tac assume_tac)); 

425 

426 
(** Reading and printing terms wrt the current theory **) 

427 

428 
fun top_sg() = #sign(rep_thm(topthm())); 

429 

230  430 
fun read s = term_of (read_cterm (top_sg()) 
1460  431 
(s, (TVar(("DUMMY",0),[])))); 
0  432 

433 
(*Print a term under the current signature of the proof state*) 

434 
fun prin t = writeln (Sign.string_of_term (top_sg()) t); 

435 

436 
fun printyp T = writeln (Sign.string_of_typ (top_sg()) T); 

437 

438 
fun pprint_term t = Sign.pprint_term (top_sg()) t; 

439 

440 
fun pprint_typ T = Sign.pprint_typ (top_sg()) T; 

441 

442 
(*Prints exceptions nicely at top level; 

443 
raises the exception in order to have a polymorphic type!*) 

914
cae574c09137
Now prove_goalw_cterm calls print_sign_exn_unit, so that the rest
lcp
parents:
696
diff
changeset

444 
fun print_exn e = (print_sign_exn_unit (top_sg()) e; raise e); 
0  445 

446 
end; 

447 
end; 