author  wenzelm 
Mon, 08 Feb 1999 17:32:06 +0100  
changeset 6262  0ebfcf181d84 
parent 6091  e3cdbd929a24 
child 6404  2daaf2943c79 
permissions  rwrr 
5820  1 
(* Title: Pure/Isar/proof.ML 
2 
ID: $Id$ 

3 
Author: Markus Wenzel, TU Muenchen 

4 

5 
Proof states and methods. 

6 

7 
TODO: 

8 
 assume: improve schematic Vars handling (!?); 

5918  9 
 warn_vars; 
5820  10 
 bind: check rhs (extra (T)Vars etc.) (How to handle these anyway?); 
11 
 prep_result: avoid duplicate asms; 

12 
 prep_result error: use error channel (!); 

5918  13 
 check_finished: trace results (!?); 
5820  14 
 next_block: fetch_facts (!?); 
15 
*) 

16 

17 
signature PROOF = 

18 
sig 

19 
type context 

20 
type state 

21 
exception STATE of string * state 

22 
val context_of: state > context 

23 
val theory_of: state > theory 

24 
val sign_of: state > Sign.sg 

6091  25 
val the_facts: state > thm list 
26 
val goal_facts: (state > thm list) > state > state 

5820  27 
val use_facts: state > state 
28 
val reset_facts: state > state 

29 
val assert_backward: state > state 

30 
val enter_forward: state > state 

31 
val print_state: state > unit 

32 
type method 

6091  33 
val method: (thm list > thm > 
34 
(thm * (indexname * term) list * (string * thm list) list) Seq.seq) > method 

5820  35 
val refine: (context > method) > state > state Seq.seq 
36 
val bind: (indexname * string) list > state > state 

37 
val bind_i: (indexname * term) list > state > state 

5936  38 
val match_bind: (string list * string) list > state > state 
39 
val match_bind_i: (term list * term) list > state > state 

6091  40 
val have_thmss: string > context attribute list > 
41 
(thm list * context attribute list) list > state > state 

5936  42 
val assume: string > context attribute list > (string * string list) list > state > state 
43 
val assume_i: string > context attribute list > (term * term list) list > state > state 

5820  44 
val fix: (string * string option) list > state > state 
45 
val fix_i: (string * typ) list > state > state 

5936  46 
val theorem: bstring > theory attribute list > string * string list > theory > state 
47 
val theorem_i: bstring > theory attribute list > term * term list > theory > state 

48 
val lemma: bstring > theory attribute list > string * string list > theory > state 

49 
val lemma_i: bstring > theory attribute list > term * term list > theory > state 

5820  50 
val chain: state > state 
6091  51 
val from_facts: thm list > state > state 
5936  52 
val show: string > context attribute list > string * string list > state > state 
53 
val show_i: string > context attribute list > term * term list > state > state 

54 
val have: string > context attribute list > string * string list > state > state 

55 
val have_i: string > context attribute list > term * term list > state > state 

5820  56 
val begin_block: state > state 
57 
val next_block: state > state 

58 
val end_block: (context > method) > state > state Seq.seq 

59 
val qed: (context > method) > bstring option > theory attribute list option > state 

6091  60 
> theory * (string * string * thm) 
5820  61 
end; 
62 

63 
signature PROOF_PRIVATE = 

64 
sig 

65 
include PROOF 

66 
val put_data: Object.kind > ('a > Object.T) > 'a > state > state 

67 
end; 

68 

69 
structure Proof: PROOF_PRIVATE = 

70 
struct 

71 

72 

73 
(** proof state **) 

74 

75 
type context = ProofContext.context; 

76 

77 

78 
(* type goal *) 

79 

80 
datatype kind = 

81 
Theorem of theory attribute list  (*toplevel theorem*) 

82 
Lemma of theory attribute list  (*toplevel lemma*) 

83 
Goal of context attribute list  (*intermediate result, solving subgoal*) 

84 
Aux of context attribute list ; (*intermediate result*) 

85 

86 
val kind_name = 

6001  87 
fn Theorem _ => "theorem"  Lemma _ => "lemma"  Goal _ => "show"  Aux _ => "have"; 
5820  88 

89 
type goal = 

6091  90 
(kind * (*result kind*) 
5820  91 
string * (*result name*) 
92 
cterm list * (*result assumptions*) 

93 
term) * (*result statement*) 

6091  94 
(thm list * (*use facts*) 
5820  95 
thm); (*goal: subgoals ==> statement*) 
96 

97 

98 
(* type mode *) 

99 

100 
datatype mode = Forward  ForwardChain  Backward; 

101 

102 
val mode_name = 

6030  103 
fn Forward => "state"  ForwardChain => "chain"  Backward => "prove"; 
5820  104 

105 

106 
(* type node *) 

107 

108 
type node = 

109 
{context: context, 

6091  110 
facts: thm list option, 
5820  111 
mode: mode, 
112 
goal: goal option}; 

113 

114 
fun make_node (context, facts, mode, goal) = 

115 
{context = context, facts = facts, mode = mode, goal = goal}: node; 

116 

117 

118 
(* datatype state *) 

119 

120 
datatype state = 

121 
State of 

122 
node * (*current*) 

123 
node list; (*parents wrt. block structure*) 

124 

125 
exception STATE of string * state; 

126 

127 
fun err_malformed name state = 

128 
raise STATE (name ^ ": internal error  malformed proof state", state); 

129 

130 

131 
fun map_current f (State ({context, facts, mode, goal}, nodes)) = 

132 
State (make_node (f (context, facts, mode, goal)), nodes); 

133 

134 
fun init_state thy = 

5875  135 
State (make_node (ProofContext.init thy, None, Forward, None), []); 
5820  136 

137 

138 

139 
(** basic proof state operations **) 

140 

141 
(* context *) 

142 

143 
fun context_of (State ({context, ...}, _)) = context; 

144 
val theory_of = ProofContext.theory_of o context_of; 

145 
val sign_of = ProofContext.sign_of o context_of; 

146 

147 
fun map_context f = map_current (fn (ctxt, facts, mode, goal) => (f ctxt, facts, mode, goal)); 

148 

149 
fun map_context_result f (state as State ({context, facts, mode, goal}, nodes)) = 

150 
let val (context', result) = f context 

151 
in (State (make_node (context', facts, mode, goal), nodes), result) end; 

152 

153 

154 
fun put_data kind f = map_context o ProofContext.put_data kind f; 

155 
val declare_term = map_context o ProofContext.declare_term; 

156 
val add_binds = map_context o ProofContext.add_binds_i; 

6091  157 
val put_thms = map_context o ProofContext.put_thms; 
158 
val put_thmss = map_context o ProofContext.put_thmss; 

5820  159 

160 

161 
(* bind statements *) 

162 

163 
fun bind_props bs state = 

164 
let val mk_bind = map (fn (x, t) => ((Syntax.binding x, 0), t)) o ObjectLogic.dest_statement 

165 
in state > add_binds (flat (map mk_bind bs)) end; 

166 

6091  167 
fun bind_thms (name, thms) state = 
5820  168 
let 
6091  169 
val props = map (#prop o Thm.rep_thm) thms; 
5820  170 
val named_props = 
171 
(case props of 

172 
[prop] => [(name, prop)] 

173 
 props => map2 (fn (i, t) => (name ^ string_of_int i, t)) (1 upto length props, props)); 

174 
in state > bind_props named_props end; 

175 

6091  176 
fun let_thms name_thms state = 
5820  177 
state 
6091  178 
> put_thms name_thms 
179 
> bind_thms name_thms; 

5820  180 

181 

182 
(* facts *) 

183 

184 
fun the_facts (State ({facts = Some facts, ...}, _)) = facts 

185 
 the_facts state = raise STATE ("No current facts available", state); 

186 

187 
fun put_facts facts state = 

188 
state 

189 
> map_current (fn (ctxt, _, mode, goal) => (ctxt, facts, mode, goal)) 

6091  190 
> let_thms ("facts", if_none facts []); 
5820  191 

192 
val reset_facts = put_facts None; 

193 

194 
fun have_facts (name, facts) state = 

195 
state 

196 
> put_facts (Some facts) 

6091  197 
> let_thms (name, facts); 
5820  198 

199 
fun these_facts (state, ths) = have_facts ths state; 

200 
fun fetch_facts (State ({facts, ...}, _)) = put_facts facts; 

201 

202 

203 
(* goal *) 

204 

205 
fun find_goal i (State ({goal = Some goal, ...}, _)) = (i, goal) 

206 
 find_goal i (State ({goal = None, ...}, node :: nodes)) = 

207 
find_goal (i + 1) (State (node, nodes)) 

208 
 find_goal _ (state as State (_, [])) = err_malformed "find_goal" state; 

209 

210 
fun put_goal goal = map_current (fn (ctxt, facts, mode, _) => (ctxt, facts, mode, goal)); 

211 

212 
fun map_goal f (State ({context, facts, mode, goal = Some goal}, nodes)) = 

213 
State (make_node (context, facts, mode, Some (f goal)), nodes) 

214 
 map_goal f (State (nd, node :: nodes)) = 

215 
let val State (node', nodes') = map_goal f (State (node, nodes)) 

216 
in State (nd, node' :: nodes') end 

217 
 map_goal _ state = state; 

218 

219 
fun goal_facts get state = 

220 
state 

221 
> map_goal (fn (result, (_, thm)) => (result, (get state, thm))); 

222 

223 
fun use_facts state = 

224 
state 

225 
> goal_facts the_facts 

226 
> reset_facts; 

227 

228 

229 
(* mode *) 

230 

231 
fun get_mode (State ({mode, ...}, _)) = mode; 

232 
fun put_mode mode = map_current (fn (ctxt, facts, _, goal) => (ctxt, facts, mode, goal)); 

233 

234 
val enter_forward = put_mode Forward; 

235 
val enter_forward_chain = put_mode ForwardChain; 

236 
val enter_backward = put_mode Backward; 

237 

238 
fun assert_mode pred state = 

239 
let val mode = get_mode state in 

240 
if pred mode then state 

241 
else raise STATE ("Illegal application of command in " ^ mode_name mode ^ " mode", state) 

242 
end; 

243 

244 
fun is_chain state = get_mode state = ForwardChain; 

245 
val assert_forward = assert_mode (equal Forward); 

246 
val assert_forward_or_chain = assert_mode (equal Forward orf equal ForwardChain); 

247 
val assert_backward = assert_mode (equal Backward); 

248 

249 

250 
(* blocks *) 

251 

252 
fun open_block (State (node, nodes)) = State (node, node :: nodes); 

253 

254 
fun new_block state = 

255 
state 

256 
> open_block 

257 
> put_goal None; 

258 

259 
fun close_block (State (_, node :: nodes)) = State (node, nodes) 

260 
 close_block state = raise STATE ("Unbalanced block parentheses", state); 

261 

262 

263 

264 
(** print_state **) 

265 

266 
fun print_state (state as State ({context, facts, mode, goal = _}, nodes)) = 

267 
let 

5945
63184e276c1d
print_state: use begin_goal from Goals.current_goals_markers;
wenzelm
parents:
5936
diff
changeset

268 
val ref (_, _, begin_goal) = Goals.current_goals_markers; 
5820  269 

270 
fun print_facts None = () 

271 
 print_facts (Some ths) = 

6091  272 
Pretty.writeln (Pretty.big_list "Current facts:" (map Display.pretty_thm ths)); 
5820  273 

274 
fun levels_up 0 = "" 

275 
 levels_up i = " (" ^ string_of_int i ^ " levels up)"; 

276 

277 
fun print_goal (i, ((kind, name, _, _), (_, thm))) = 

6262  278 
(writeln (kind_name kind ^ " " ^ quote name ^ levels_up (i div 2) ^ ":"); 
5945
63184e276c1d
print_state: use begin_goal from Goals.current_goals_markers;
wenzelm
parents:
5936
diff
changeset

279 
Locale.print_goals_marker begin_goal (! goals_limit) thm); 
5820  280 
in 
6262  281 
writeln ("Nesting level: " ^ string_of_int (length nodes div 2)); 
5820  282 
writeln ""; 
5993  283 
writeln (mode_name mode ^ " mode"); 
284 
writeln ""; 

5820  285 
ProofContext.print_context context; 
286 
writeln ""; 

287 
print_facts facts; 

5993  288 
print_goal (find_goal 0 state) 
5820  289 
end; 
290 

291 

292 

293 
(** proof steps **) 

294 

295 
(* datatype method *) 

296 

297 
datatype method = Method of 

6091  298 
thm list > (*use facts*) 
5820  299 
thm (*goal: subgoals ==> statement*) 
300 
> (thm * (*refined goal*) 

301 
(indexname * term) list * (*new bindings*) 

6091  302 
(string * thm list) list) (*new thms*) 
5820  303 
Seq.seq; 
304 

305 
val method = Method; 

306 

307 

308 
(* refine goal *) 

309 

310 
fun check_sign sg state = 

311 
if Sign.subsig (sg, sign_of state) then state 

312 
else raise STATE ("Bad signature of result: " ^ Sign.str_of_sg sg, state); 

313 

314 
fun refine meth_fun (state as State ({context, ...}, _)) = 

315 
let 

316 
val Method meth = meth_fun context; 

317 
val (_, (result, (facts, thm))) = find_goal 0 state; 

318 

319 
fun refn (thm', new_binds, new_thms) = 

320 
state 

321 
> check_sign (sign_of_thm thm') 

322 
> map_goal (K (result, (facts, thm'))) 

323 
> add_binds new_binds 

6091  324 
> put_thmss new_thms; 
5820  325 
in Seq.map refn (meth facts thm) end; 
326 

327 

328 
(* prepare result *) 

329 

330 
fun varify_frees names thm = 

331 
let 

332 
fun get_free x (None, t as Free (y, _)) = if x = y then Some t else None 

333 
 get_free _ (opt, _) = opt; 

334 

335 
fun find_free t x = foldl_aterms (get_free x) (None, t); 

336 

337 
val {sign, maxidx, prop, ...} = Thm.rep_thm thm; 

338 
val frees = map (Thm.cterm_of sign) (mapfilter (find_free prop) names); 

339 
in 

340 
thm 

341 
> Drule.forall_intr_list frees 

342 
> Drule.forall_elim_vars (maxidx + 1) 

343 
end; 

344 

345 
fun implies_elim_hyps thm = 

346 
foldl (uncurry Thm.implies_elim) (thm, map Thm.assume (Drule.cprems_of thm)); 

347 

348 
fun prep_result state asms t raw_thm = 

349 
let 

350 
val ctxt = context_of state; 

351 
fun err msg = raise STATE (msg, state); 

352 

353 
val ngoals = Thm.nprems_of raw_thm; 

354 
val _ = 

355 
if ngoals = 0 then () 

356 
else (Locale.print_goals ngoals raw_thm; err (string_of_int ngoals ^ " unsolved goal(s)!")); 

357 

358 
val thm = 

359 
raw_thm RS Drule.rev_triv_goal 

360 
> implies_elim_hyps 

361 
> Drule.implies_intr_list asms 

362 
> varify_frees (ProofContext.fixed_names ctxt); 

363 

364 
val {hyps, prop, sign, ...} = Thm.rep_thm thm; 

365 
val tsig = Sign.tsig_of sign; 

366 
in 

367 
(* FIXME 

368 
if not (Pattern.matches tsig (t, Logic.skip_flexpairs prop)) then 

369 
warning ("Proved a different theorem: " ^ Sign.string_of_term sign prop) 

370 
else (); 

371 
*) 

372 
if not (null hyps) then 

373 
err ("Additional hypotheses:\n" ^ cat_lines (map (Sign.string_of_term sign) hyps)) 

374 
(* FIXME else if not (Pattern.matches tsig (t, Logic.skip_flexpairs prop)) then 

375 
err ("Proved a different theorem: " ^ Sign.string_of_term sign prop) *) 

376 
else thm 

377 
end; 

378 

379 

380 
(* prepare final result *) 

381 

382 
fun strip_flexflex thm = 

383 
Seq.hd (Thm.flexflex_rule thm) handle THM _ => thm; 

384 

385 
fun final_result state pre_thm = 

386 
let 

387 
val thm = 

388 
pre_thm 

389 
> strip_flexflex 

390 
> Thm.strip_shyps 

391 
> Drule.standard; 

392 

393 
val str_of_sort = Sign.str_of_sort (Thm.sign_of_thm thm); 

394 
val xshyps = Thm.extra_shyps thm; 

395 
in 

396 
if not (null xshyps) then 

397 
raise STATE ("Extra sort hypotheses: " ^ commas (map str_of_sort xshyps), state) 

398 
else thm 

399 
end; 

400 

401 

402 
(* solve goal *) 

403 

404 
fun solve_goal rule state = 

405 
let 

406 
val (_, (result, (facts, thm))) = find_goal 0 state; 

5993  407 
val thms' = FIRSTGOAL (rtac rule THEN_ALL_NEW (TRY o assume_tac)) thm; 
5820  408 
in Seq.map (fn thm' => map_goal (K (result, (facts, thm'))) state) thms' end; 
409 

410 

411 

412 
(*** structured proof commands ***) 

413 

414 
(** context **) 

415 

416 
(* bind *) 

417 

418 
fun gen_bind f x state = 

419 
state 

420 
> assert_forward 

421 
> map_context (f x) 

422 
> reset_facts; 

423 

424 
val bind = gen_bind ProofContext.add_binds; 

425 
val bind_i = gen_bind ProofContext.add_binds_i; 

426 

427 
val match_bind = gen_bind ProofContext.match_binds; 

428 
val match_bind_i = gen_bind ProofContext.match_binds_i; 

429 

430 

6091  431 
(* have_thmss *) 
5820  432 

6091  433 
fun have_thmss name atts ths_atts state = 
5820  434 
state 
435 
> assert_forward 

6091  436 
> map_context_result (ProofContext.have_thmss (PureThy.default_name name) atts ths_atts) 
5820  437 
> these_facts; 
438 

439 

440 
(* fix *) 

441 

442 
fun gen_fix f xs state = 

443 
state 

444 
> assert_forward 

445 
> map_context (f xs) 

446 
> reset_facts; 

447 

448 
val fix = gen_fix ProofContext.fix; 

449 
val fix_i = gen_fix ProofContext.fix_i; 

450 

451 

452 
(* assume *) 

453 

454 
fun gen_assume f name atts props state = 

455 
state 

456 
> assert_forward 

5918  457 
> map_context_result (f (PureThy.default_name name) atts props) 
5820  458 
> these_facts 
6091  459 
> (fn st => let_thms ("prems", ProofContext.assumptions (context_of st)) st); 
5820  460 

461 
val assume = gen_assume ProofContext.assume; 

462 
val assume_i = gen_assume ProofContext.assume_i; 

463 

464 

465 

466 
(** goals **) 

467 

468 
(* forward chaining *) 

469 

470 
fun chain state = 

471 
state 

472 
> assert_forward 

473 
> enter_forward_chain; 

474 

475 
fun from_facts facts state = 

476 
state 

477 
> put_facts (Some facts) 

478 
> chain; 

479 

480 

481 
(* setup goals *) 

482 

5936  483 
fun setup_goal opt_block prepp kind name atts raw_propp state = 
5820  484 
let 
5936  485 
val (state', concl) = 
486 
state 

487 
> assert_forward_or_chain 

488 
> enter_forward 

489 
> opt_block 

490 
> map_context_result (fn c => prepp (c, raw_propp)); 

5820  491 

6091  492 
val casms = map (#prop o Thm.crep_thm) (ProofContext.assumptions (context_of state')); 
5820  493 
val asms = map Thm.term_of casms; 
494 

5936  495 
val prop = Logic.list_implies (asms, concl); 
496 
val cprop = Thm.cterm_of (sign_of state') prop; 

5820  497 
val thm = Drule.mk_triv_goal cprop; 
498 
in 

5936  499 
state' 
5918  500 
> put_goal (Some ((kind atts, (PureThy.default_name name), casms, prop), ([], thm))) 
5820  501 
> bind_props [("thesis", prop)] 
502 
> (if is_chain state then use_facts else reset_facts) 

503 
> new_block 

504 
> enter_backward 

505 
end; 

506 

507 

508 
(*global goals*) 

509 
fun global_goal prep kind name atts x thy = 

510 
setup_goal I prep kind name atts x (init_state thy); 

511 

5936  512 
val theorem = global_goal ProofContext.bind_propp Theorem; 
513 
val theorem_i = global_goal ProofContext.bind_propp_i Theorem; 

514 
val lemma = global_goal ProofContext.bind_propp Lemma; 

515 
val lemma_i = global_goal ProofContext.bind_propp_i Lemma; 

5820  516 

517 

518 
(*local goals*) 

519 
fun local_goal prep kind name atts x = 

520 
setup_goal open_block prep kind name atts x; 

521 

5936  522 
val show = local_goal ProofContext.bind_propp Goal; 
523 
val show_i = local_goal ProofContext.bind_propp_i Goal; 

524 
val have = local_goal ProofContext.bind_propp Aux; 

525 
val have_i = local_goal ProofContext.bind_propp_i Aux; 

5820  526 

527 

528 

529 
(** blocks **) 

530 

531 
(* begin_block *) 

532 

533 
fun begin_block state = 

534 
state 

535 
> assert_forward 

536 
> new_block 

537 
> reset_facts 

538 
> open_block; 

539 

540 

541 
(* next_block *) 

542 

543 
fun next_block state = 

544 
state 

545 
> assert_forward 

546 
> close_block 

547 
> new_block; 

548 

549 

550 

551 
(** conclusions **) 

552 

553 
(* current goal *) 

554 

555 
fun current_goal (State ({goal = Some goal, ...}, _)) = goal 

556 
 current_goal state = raise STATE ("No current goal!", state); 

557 

558 
fun assert_current_goal state = (current_goal state; state); 

559 

560 
fun assert_bottom true (state as State (_, _ :: _)) = 

561 
raise STATE ("Not at bottom of proof!", state) 

562 
 assert_bottom false (state as State (_, [])) = 

563 
raise STATE ("Already at bottom of proof!", state) 

564 
 assert_bottom _ state = state; 

565 

566 

567 
(* finish proof *) 

568 

569 
fun check_finished state states = 

570 
(case Seq.pull states of 

571 
None => raise STATE ("Failed to finish proof", state) 

572 
 Some s_sq => Seq.cons s_sq); 

573 

574 
fun finish_proof bot meth_fun state = 

575 
state 

576 
> assert_forward 

577 
> close_block 

578 
> assert_bottom bot 

579 
> assert_current_goal 

580 
> refine meth_fun 

581 
> check_finished state; 

582 

583 

584 
(* conclude local proof *) 

585 

586 
fun finish_local state = 

587 
let 

588 
val ((kind, name, asms, t), (_, raw_thm)) = current_goal state; 

589 
val result = prep_result state asms t raw_thm; 

590 
val (atts, opt_solve) = 

591 
(case kind of 

592 
Goal atts => (atts, solve_goal result) 

593 
 Aux atts => (atts, Seq.single) 

594 
 _ => raise STATE ("No local goal!", state)); 

595 
in 

596 
state 

597 
> close_block 

6091  598 
> have_thmss name atts [Thm.no_attributes [result]] 
5820  599 
> opt_solve 
600 
end; 

601 

602 
fun end_block meth_fun state = 

603 
if can assert_current_goal (close_block state) then 

604 
state 

605 
> finish_proof false meth_fun 

606 
> (Seq.flat o Seq.map finish_local) 

607 
else 

608 
state 

609 
> assert_forward 

610 
> close_block 

611 
> close_block 

612 
> fetch_facts state 

613 
> Seq.single; 

614 

615 

616 
(* conclude global proof *) 

617 

618 
fun finish_global alt_name alt_atts state = 

619 
let 

620 
val ((kind, def_name, asms, t), (_, raw_thm)) = current_goal state; 

621 
val result = final_result state (prep_result state asms t raw_thm); 

622 

623 
val name = if_none alt_name def_name; 

624 
val atts = 

625 
(case kind of 

626 
Theorem atts => if_none alt_atts atts 

6091  627 
 Lemma atts => (if_none alt_atts atts) @ [Drule.tag_lemma] 
5820  628 
 _ => raise STATE ("No global goal!", state)); 
629 

6091  630 
val (thy', result') = PureThy.store_thm ((name, result), atts) (theory_of state); 
6001  631 
in (thy', (kind_name kind, name, result')) end; 
5820  632 

633 
fun qed meth_fun alt_name alt_atts state = 

634 
state 

635 
> finish_proof true meth_fun 

636 
> Seq.hd 

637 
> finish_global alt_name alt_atts; 

638 

639 

640 
end; 