author  lcp 
Thu, 25 Aug 1994 10:41:17 +0200  
changeset 577  776b5ba748d8 
parent 545  fc4ff96bb0e9 
child 678  6151b7f3b606 
permissions  rwrr 
39
deb04a336a99
"The error/exception above ...": errorneous goal now quoted;
wenzelm
parents:
0
diff
changeset

1 
(* Title: Pure/goals.ML 
0  2 
ID: $Id$ 
3 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 

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 

577  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 

57 
val prove_goalw : theory>thm list>string>(thm list>tactic list)>thm 

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 

74 
sharing type Pattern.type_sig = Drule.Thm.Sign.Type.type_sig 

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 

230  103 
val dummy = trivial(read_cterm Sign.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; 
0  131 
val p_rew = if null rths then I else rewrite_rule rths; 
132 
val c_rew = if null rths then I else rewrite_goals_rule rths; 

133 
val prems = map (p_rew o forall_elim_vars(0) o assume) cAs 

230  134 
and st0 = c_rew (trivial (cterm_of sign B)) 
0  135 
fun result_error state msg = 
136 
(writeln ("Bad final proof state:"); 

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

137 
!print_goals_ref (!goals_limit) state; 
0  138 
error msg) 
139 
(*discharges assumptions from state in the order they appear in goal; 

140 
checks (if requested) that resulting theorem is equivalent to goal. *) 

141 
fun mkresult (check,state) = 

142 
let val ngoals = nprems_of state 

143 
val th = implies_intr_list cAs state 

144 
val {hyps,prop,sign=sign',...} = rep_thm th 

145 
in if not check then standard th 

253  146 
else if not (Sign.eq_sg(sign,sign')) then result_error state 
0  147 
("Signature of proof state has changed!" ^ 
148 
sign_error (sign,sign')) 

149 
else if ngoals>0 then result_error state 

150 
(string_of_int ngoals ^ " unsolved goals!") 

151 
else if not (null hyps) then result_error state 

152 
("Additional hypotheses:\n" ^ 

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

154 
else if Pattern.eta_matches (#tsig(Sign.rep_sg sign)) 

230  155 
(term_of chorn, prop) 
0  156 
then standard th 
157 
else result_error state "proved a different theorem" 

158 
end 

159 
in 

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

163 
sign_error (sign, #sign(rep_thm st0))) 

164 
end 

165 
handle THM(s,_,_) => error("prepare_proof: exception THM was raised!\n" ^ s); 

166 

167 
(*Prints exceptions readably to users*) 

577  168 
fun print_sign_exn_unit sign e = 
0  169 
case e of 
170 
THM (msg,i,thms) => 

171 
(writeln ("Exception THM " ^ string_of_int i ^ " raised:\n" ^ msg); 

172 
seq print_thm thms) 

173 
 THEORY (msg,thys) => 

174 
(writeln ("Exception THEORY raised:\n" ^ msg); 

175 
seq print_theory thys) 

176 
 TERM (msg,ts) => 

177 
(writeln ("Exception TERM raised:\n" ^ msg); 

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

179 
 TYPE (msg,Ts,ts) => 

180 
(writeln ("Exception TYPE raised:\n" ^ msg); 

181 
seq (writeln o Sign.string_of_typ sign) Ts; 

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

183 
 e => raise e; 

184 

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

187 

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

190 
Augment signature with all type assignments of goal. 

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

192 

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

194 
fun prove_goalw_cterm rths chorn tacsf = 

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

196 
val tac = EVERY (tacsf prems) 

197 
fun statef() = 

198 
(case Sequence.pull (tapply(tac,st0)) of 

199 
Some(st,_) => st 

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

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

201 
in mkresult (true, cond_timeit (!proof_timing) statef) end 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

202 
handle e => (print_sign_exn (#sign (rep_cterm chorn)) e; 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

203 
error ("The exception above was raised for\n" ^ 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

204 
string_of_cterm chorn)); 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

205 

0  206 

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

208 
fun prove_goalw thy rths agoal tacsf = 

209 
let val sign = sign_of thy 

230  210 
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

211 
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

212 
handle ERROR => error (*from read_cterm?*) 
fc4ff96bb0e9
Pure/goals.ML: prove_goalw_cterm now does its own exceptionhandling, moved
lcp
parents:
253
diff
changeset

213 
("The error above occurred for " ^ quote agoal); 
0  214 

215 
(*String version with no metarewriterules*) 

216 
fun prove_goal thy = prove_goalw thy []; 

217 

218 

219 
(*** Commands etc ***) 

220 

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

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

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

224 
 x::_ => x; 

225 

226 
(*Pops the given goal stack*) 

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

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

229 

230 

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

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

233 
(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

234 
!print_goals_ref (!goals_limit) th); 
0  235 

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

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

238 
fun setstate newgoals = 

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

240 

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

242 
the goal stack*) 

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

244 

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

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

247 

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

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

250 

251 
(*Return the final result. *) 

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

253 

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

255 
answer extraction, or other instantiation of Vars *) 

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

257 

258 
(*Get subgoal i from goal stack*) 

259 
fun getgoal i = 

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

261 
[] => error"getgoal: Goal number out of range" 

262 
 Q::_ => Q); 

263 

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

265 
For debugging uses of METAHYPS*) 

266 
local exception GETHYPS of thm list 

267 
in 

268 
fun gethyps i = 

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

270 
handle GETHYPS hyps => hyps 

271 
end; 

272 

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

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

275 

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

277 
fun chop_level n (pair,pairs) = 

278 
let val level = length pairs 

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

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

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

282 
string_of_int level) 

283 
end; 

284 

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

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

287 
fun pr () = apply_fun print_top; 

288 

289 
(** the goal.... commands 

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

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

292 

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

230  294 
goalw_cterm rths (cterm_of (sign_of thy) t); *) 
0  295 
fun goalw_cterm rths chorn = 
296 
let val (prems, st0, mkresult) = prepare_proof rths chorn 

297 
in undo_list := []; 

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

299 
curr_prems := prems; 

300 
curr_mkresult := mkresult; 

301 
prems 

302 
end; 

303 

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

305 
fun goalw thy rths agoal = 

230  306 
goalw_cterm rths (read_cterm(sign_of thy)(agoal,propT)) 
0  307 
handle ERROR => error (*from type_assign, etc via prepare_proof*) 
39
deb04a336a99
"The error/exception above ...": errorneous goal now quoted;
wenzelm
parents:
0
diff
changeset

308 
("The error above occurred for " ^ quote agoal); 
0  309 

310 
(*String version with no metarewriterules*) 

311 
fun goal thy = goalw thy []; 

312 

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

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

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

316 
None => error"by: tactic failed" 

317 
 Some(th2,ths2) => 

318 
(if eq_thm(th,th2) 

319 
then writeln"Warning: same as previous level" 

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

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

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

323 
((th2,ths2)::(th,ths)::pairs))); 

324 

325 
fun by tac = cond_timeit (!proof_timing) 

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

327 

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

329 
Good for debugging proofs involving prove_goal.*) 

330 
val byev = by o EVERY; 

331 

332 

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

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

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

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

337 
(case Sequence.pull thstr of 

338 
None => (writeln"Going back a level..."; backtrack pairs) 

339 
 Some(th2,thstr2) => 

340 
(if eq_thm(th,th2) 

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

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

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

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

345 

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

347 

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

349 
fun choplev n = make_command (chop_level n); 

350 

351 
(*Chopping back the goal stack*) 

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

353 

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

355 
fun undo() = case !undo_list of 

356 
[] => error"No proof state" 

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

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

359 

360 

361 
(*** Managing the proof stack ***) 

362 

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

364 

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

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

367 

368 

369 
fun top_proof() = case !proofstack of 

370 
[] => error("Stack of proof attempts is empty!") 

371 
 p::ps => (p,ps); 

372 

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

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

375 

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

377 
fun pop_proof() = 

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

379 
val prems = restore_proof p 

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

381 

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

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

384 
in proofstack := ps@[save_proof()]; 

385 
restore_proof p; 

386 
pr(); 

387 
!curr_prems 

388 
end; 

389 

390 

391 
(** Shortcuts for commonlyused tactics **) 

392 

393 
fun bws rls = by (rewrite_goals_tac rls); 

394 
fun bw rl = bws [rl]; 

395 

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

397 
fun br rl = brs [rl]; 

398 

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

400 
fun be rl = bes [rl]; 

401 

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

403 
fun bd rl = bds [rl]; 

404 

405 
fun ba i = by (assume_tac i); 

406 

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

408 

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

410 

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

412 
fun fr rl = frs [rl]; 

413 

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

415 
fun fe rl = fes [rl]; 

416 

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

418 
fun fd rl = fds [rl]; 

419 

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

421 

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

423 

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

425 

230  426 
fun read s = term_of (read_cterm (top_sg()) 
0  427 
(s, (TVar(("DUMMY",0),[])))); 
428 

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

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

431 

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

433 

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

435 

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

437 

438 
(*Prints exceptions nicely at top level; 

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

440 
fun print_exn e = (print_sign_exn (top_sg()) e; raise e); 

441 

442 
end; 

443 
end; 