author  wenzelm 
Sat, 04 Nov 2017 12:39:25 +0100  
changeset 67001  b34fbf33a7ea 
parent 65447  fae6051ec192 
child 69593  3dda49e08b9d 
permissions  rwrr 
19761  1 
(* Title: CTT/ex/Synthesis.thy 
2 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 

3 
Copyright 1991 University of Cambridge 

4 
*) 

5 

58889  6 
section "Synthesis examples, using a crude form of narrowing" 
19761  7 

8 
theory Synthesis 

65447
fae6051ec192
clarified main CTT.thy, and avoid name clash with global HOL/Main.thy;
wenzelm
parents:
61391
diff
changeset

9 
imports "../CTT" 
19761  10 
begin 
11 

12 
text "discovery of predecessor function" 

61391  13 
schematic_goal "?a : \<Sum>pred:?A . Eq(N, pred`0, 0) \<times> (\<Prod>n:N. Eq(N, pred ` succ(n), n))" 
58972  14 
apply intr 
15 
apply eqintr 

19761  16 
apply (rule_tac [3] reduction_rls) 
17 
apply (rule_tac [5] comp_rls) 

58972  18 
apply rew 
19761  19 
done 
20 

21 
text "the function fst as an element of a function type" 

61337  22 
schematic_goal [folded basic_defs]: 
61391  23 
"A type \<Longrightarrow> ?a: \<Sum>f:?B . \<Prod>i:A. \<Prod>j:A. Eq(A, f ` <i,j>, i)" 
58972  24 
apply intr 
25 
apply eqintr 

19761  26 
apply (rule_tac [2] reduction_rls) 
27 
apply (rule_tac [4] comp_rls) 

58972  28 
apply typechk 
19761  29 
txt "now put in A everywhere" 
30 
apply assumption+ 

31 
done 

32 

33 
text "An interesting use of the eliminator, when" 

34 
(*The early implementation of unification caused nonrigid path in occur check 

35 
See following example.*) 

61391  36 
schematic_goal "?a : \<Prod>i:N. Eq(?A, ?b(inl(i)), <0 , i>) 
37 
\<times> Eq(?A, ?b(inr(i)), <succ(0), i>)" 

58972  38 
apply intr 
39 
apply eqintr 

19761  40 
apply (rule comp_rls) 
58972  41 
apply rew 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

42 
done 
19761  43 

19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

44 
(*Here we allow the type to depend on i. 
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

45 
This prevents the cycle in the first unification (no longer needed). 
19761  46 
Requires flexflex to preserve the dependence. 
61391  47 
Simpler still: make ?A into a constant type N \<times> N.*) 
48 
schematic_goal "?a : \<Prod>i:N. Eq(?A(i), ?b(inl(i)), <0 , i>) 

49 
\<times> Eq(?A(i), ?b(inr(i)), <succ(0),i>)" 

19761  50 
oops 
51 

52 
text "A tricky combination of when and split" 

53 
(*Now handled easily, but caused great problems once*) 

61337  54 
schematic_goal [folded basic_defs]: 
61391  55 
"?a : \<Prod>i:N. \<Prod>j:N. Eq(?A, ?b(inl(<i,j>)), i) 
56 
\<times> Eq(?A, ?b(inr(<i,j>)), j)" 

58972  57 
apply intr 
58 
apply eqintr 

19761  59 
apply (rule PlusC_inl [THEN trans_elem]) 
60 
apply (rule_tac [4] comp_rls) 

61 
apply (rule_tac [7] reduction_rls) 

62 
apply (rule_tac [10] comp_rls) 

58972  63 
apply typechk 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

64 
done 
19761  65 

66 
(*similar but allows the type to depend on i and j*) 

61391  67 
schematic_goal "?a : \<Prod>i:N. \<Prod>j:N. Eq(?A(i,j), ?b(inl(<i,j>)), i) 
68 
\<times> Eq(?A(i,j), ?b(inr(<i,j>)), j)" 

19761  69 
oops 
70 

71 
(*similar but specifying the type N simplifies the unification problems*) 

61391  72 
schematic_goal "?a : \<Prod>i:N. \<Prod>j:N. Eq(N, ?b(inl(<i,j>)), i) 
73 
\<times> Eq(N, ?b(inr(<i,j>)), j)" 

19761  74 
oops 
75 

76 

77 
text "Deriving the addition operator" 

61337  78 
schematic_goal [folded arith_defs]: 
61391  79 
"?c : \<Prod>n:N. Eq(N, ?f(0,n), n) 
80 
\<times> (\<Prod>m:N. Eq(N, ?f(succ(m), n), succ(?f(m,n))))" 

58972  81 
apply intr 
82 
apply eqintr 

19761  83 
apply (rule comp_rls) 
58972  84 
apply rew 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

85 
done 
19761  86 

87 
text "The addition function  using explicit lambdas" 

61337  88 
schematic_goal [folded arith_defs]: 
61391  89 
"?c : \<Sum>plus : ?A . 
90 
\<Prod>x:N. Eq(N, plus`0`x, x) 

91 
\<times> (\<Prod>y:N. Eq(N, plus`succ(y)`x, succ(plus`y`x)))" 

58972  92 
apply intr 
93 
apply eqintr 

59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58977
diff
changeset

94 
apply (tactic "resolve_tac @{context} [TSimp.split_eqn] 3") 
58963
26bf09b95dda
proper context for assume_tac (atac remains as fallback without context);
wenzelm
parents:
58889
diff
changeset

95 
apply (tactic "SELECT_GOAL (rew_tac @{context} []) 4") 
59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58977
diff
changeset

96 
apply (tactic "resolve_tac @{context} [TSimp.split_eqn] 3") 
58963
26bf09b95dda
proper context for assume_tac (atac remains as fallback without context);
wenzelm
parents:
58889
diff
changeset

97 
apply (tactic "SELECT_GOAL (rew_tac @{context} []) 4") 
19761  98 
apply (rule_tac [3] p = "y" in NC_succ) 
59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58977
diff
changeset

99 
(** by (resolve_tac @{context} comp_rls 3); caused excessive branching **) 
58972  100 
apply rew 
19761  101 
done 
102 

103 
end 

104 