author | webertj |
Mon, 07 Mar 2005 19:17:07 +0100 | |
changeset 15582 | 7219facb3fd0 |
parent 9251 | bd57acd44fc1 |
child 17441 | 5b5feca0344a |
permissions | -rw-r--r-- |
1459 | 1 |
(* Title: CTT/ex/synth |
0 | 2 |
ID: $Id$ |
1459 | 3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
0 | 4 |
Copyright 1991 University of Cambridge |
5 |
*) |
|
6 |
||
7 |
writeln"Synthesis examples, using a crude form of narrowing"; |
|
8 |
||
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
9 |
context Arith.thy; |
0 | 10 |
|
11 |
writeln"discovery of predecessor function"; |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
12 |
Goal |
1459 | 13 |
"?a : SUM pred:?A . Eq(N, pred`0, 0) \ |
14 |
\ * (PROD n:N. Eq(N, pred ` succ(n), n))"; |
|
0 | 15 |
by (intr_tac[]); |
16 |
by eqintr_tac; |
|
17 |
by (resolve_tac reduction_rls 3); |
|
18 |
by (resolve_tac comp_rls 5); |
|
19 |
by (rew_tac[]); |
|
20 |
result(); |
|
21 |
||
22 |
writeln"the function fst as an element of a function type"; |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
23 |
Goal "A type ==> ?a: SUM f:?B . PROD i:A. PROD j:A. Eq(A, f ` <i,j>, i)"; |
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
24 |
by (intr_tac []); |
0 | 25 |
by eqintr_tac; |
26 |
by (resolve_tac reduction_rls 2); |
|
27 |
by (resolve_tac comp_rls 4); |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
28 |
by (typechk_tac []); |
0 | 29 |
writeln"now put in A everywhere"; |
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
30 |
by (REPEAT (assume_tac 1)); |
0 | 31 |
by (fold_tac basic_defs); |
32 |
result(); |
|
33 |
||
34 |
writeln"An interesting use of the eliminator, when"; |
|
35 |
(*The early implementation of unification caused non-rigid path in occur check |
|
36 |
See following example.*) |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
37 |
Goal "?a : PROD i:N. Eq(?A, ?b(inl(i)), <0 , i>) \ |
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
38 |
\ * Eq(?A, ?b(inr(i)), <succ(0), i>)"; |
0 | 39 |
by (intr_tac[]); |
40 |
by eqintr_tac; |
|
41 |
by (resolve_tac comp_rls 1); |
|
42 |
by (rew_tac[]); |
|
43 |
uresult(); |
|
44 |
||
45 |
(*Here we allow the type to depend on i. |
|
46 |
This prevents the cycle in the first unification (no longer needed). |
|
47 |
Requires flex-flex to preserve the dependence. |
|
48 |
Simpler still: make ?A into a constant type N*N.*) |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
49 |
Goal "?a : PROD i:N. Eq(?A(i), ?b(inl(i)), <0 , i>) \ |
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
50 |
\ * Eq(?A(i), ?b(inr(i)), <succ(0),i>)"; |
0 | 51 |
|
52 |
writeln"A tricky combination of when and split"; |
|
53 |
(*Now handled easily, but caused great problems once*) |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
54 |
Goal |
0 | 55 |
"?a : PROD i:N. PROD j:N. Eq(?A, ?b(inl(<i,j>)), i) \ |
1459 | 56 |
\ * Eq(?A, ?b(inr(<i,j>)), j)"; |
0 | 57 |
by (intr_tac[]); |
58 |
by eqintr_tac; |
|
59 |
by (resolve_tac [ PlusC_inl RS trans_elem ] 1); |
|
60 |
by (resolve_tac comp_rls 4); |
|
61 |
by (resolve_tac reduction_rls 7); |
|
62 |
by (resolve_tac comp_rls 10); |
|
63 |
by (typechk_tac[]); (*2 secs*) |
|
64 |
by (fold_tac basic_defs); |
|
65 |
uresult(); |
|
66 |
||
67 |
(*similar but allows the type to depend on i and j*) |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
68 |
Goal "?a : PROD i:N. PROD j:N. Eq(?A(i,j), ?b(inl(<i,j>)), i) \ |
1459 | 69 |
\ * Eq(?A(i,j), ?b(inr(<i,j>)), j)"; |
0 | 70 |
|
71 |
(*similar but specifying the type N simplifies the unification problems*) |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
72 |
Goal "?a : PROD i:N. PROD j:N. Eq(N, ?b(inl(<i,j>)), i) \ |
1459 | 73 |
\ * Eq(N, ?b(inr(<i,j>)), j)"; |
0 | 74 |
|
75 |
||
76 |
writeln"Deriving the addition operator"; |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
77 |
Goal "?c : PROD n:N. Eq(N, ?f(0,n), n) \ |
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
78 |
\ * (PROD m:N. Eq(N, ?f(succ(m), n), succ(?f(m,n))))"; |
0 | 79 |
by (intr_tac[]); |
80 |
by eqintr_tac; |
|
81 |
by (resolve_tac comp_rls 1); |
|
82 |
by (rew_tac[]); |
|
83 |
by (fold_tac arith_defs); |
|
84 |
result(); |
|
85 |
||
86 |
writeln"The addition function -- using explicit lambdas"; |
|
9251
bd57acd44fc1
more tidying. also generalized some tactics to prove "Type A" and
paulson
parents:
1459
diff
changeset
|
87 |
Goal |
0 | 88 |
"?c : SUM plus : ?A . \ |
1459 | 89 |
\ PROD x:N. Eq(N, plus`0`x, x) \ |
90 |
\ * (PROD y:N. Eq(N, plus`succ(y)`x, succ(plus`y`x)))"; |
|
0 | 91 |
by (intr_tac[]); |
92 |
by eqintr_tac; |
|
93 |
by (resolve_tac [TSimp.split_eqn] 3); |
|
94 |
by (SELECT_GOAL (rew_tac[]) 4); |
|
95 |
by (resolve_tac [TSimp.split_eqn] 3); |
|
96 |
by (SELECT_GOAL (rew_tac[]) 4); |
|
97 |
by (res_inst_tac [("p","y")] NC_succ 3); |
|
98 |
(** by (resolve_tac comp_rls 3); caused excessive branching **) |
|
99 |
by (rew_tac[]); |
|
100 |
by (fold_tac arith_defs); |
|
101 |
result(); |
|
102 |
||
103 |
writeln"Reached end of file."; |