author  wenzelm 
Tue, 11 Nov 2014 11:41:58 +0100  
changeset 58972  5b026cfc5f04 
parent 58963  26bf09b95dda 
child 58974  cbc2ac19d783 
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 

9 
imports Arith 

10 
begin 

11 

12 
text "discovery of predecessor function" 

36319  13 
schematic_lemma "?a : SUM pred:?A . Eq(N, pred`0, 0) 
19761  14 
* (PROD n:N. Eq(N, pred ` succ(n), n))" 
58972  15 
apply intr 
16 
apply eqintr 

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

58972  19 
apply rew 
19761  20 
done 
21 

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

36319  23 
schematic_lemma [folded basic_defs]: 
19761  24 
"A type ==> ?a: SUM f:?B . PROD i:A. PROD j:A. Eq(A, f ` <i,j>, i)" 
58972  25 
apply intr 
26 
apply eqintr 

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

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

32 
done 

33 

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

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

36 
See following example.*) 

36319  37 
schematic_lemma "?a : PROD i:N. Eq(?A, ?b(inl(i)), <0 , i>) 
19761  38 
* Eq(?A, ?b(inr(i)), <succ(0), i>)" 
58972  39 
apply intr 
40 
apply eqintr 

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

43 
done 
19761  44 

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

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

46 
This prevents the cycle in the first unification (no longer needed). 
19761  47 
Requires flexflex to preserve the dependence. 
48 
Simpler still: make ?A into a constant type N*N.*) 

36319  49 
schematic_lemma "?a : PROD i:N. Eq(?A(i), ?b(inl(i)), <0 , i>) 
19761  50 
* Eq(?A(i), ?b(inr(i)), <succ(0),i>)" 
51 
oops 

52 

53 
text "A tricky combination of when and split" 

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

36319  55 
schematic_lemma [folded basic_defs]: 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

56 
"?a : PROD i:N. PROD j:N. Eq(?A, ?b(inl(<i,j>)), i) 
19761  57 
* Eq(?A, ?b(inr(<i,j>)), j)" 
58972  58 
apply intr 
59 
apply eqintr 

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

62 
apply (rule_tac [7] reduction_rls) 

63 
apply (rule_tac [10] comp_rls) 

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

65 
done 
19761  66 

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

36319  68 
schematic_lemma "?a : PROD i:N. PROD j:N. Eq(?A(i,j), ?b(inl(<i,j>)), i) 
19761  69 
* Eq(?A(i,j), ?b(inr(<i,j>)), j)" 
70 
oops 

71 

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

36319  73 
schematic_lemma "?a : PROD i:N. PROD j:N. Eq(N, ?b(inl(<i,j>)), i) 
19761  74 
* Eq(N, ?b(inr(<i,j>)), j)" 
75 
oops 

76 

77 

78 
text "Deriving the addition operator" 

36319  79 
schematic_lemma [folded arith_defs]: 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

80 
"?c : PROD n:N. Eq(N, ?f(0,n), n) 
19761  81 
* (PROD m:N. Eq(N, ?f(succ(m), n), succ(?f(m,n))))" 
58972  82 
apply intr 
83 
apply eqintr 

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

86 
done 
19761  87 

88 
text "The addition function  using explicit lambdas" 

36319  89 
schematic_lemma [folded arith_defs]: 
19774
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

90 
"?c : SUM plus : ?A . 
5fe7731d0836
allow nontrivial schematic goals (via embedded term vars);
wenzelm
parents:
19761
diff
changeset

91 
PROD x:N. Eq(N, plus`0`x, x) 
19761  92 
* (PROD y:N. Eq(N, plus`succ(y)`x, succ(plus`y`x)))" 
58972  93 
apply intr 
94 
apply eqintr 

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

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

98 
apply (tactic "SELECT_GOAL (rew_tac @{context} []) 4") 
19761  99 
apply (rule_tac [3] p = "y" in NC_succ) 
100 
(** by (resolve_tac comp_rls 3); caused excessive branching **) 

58972  101 
apply rew 
19761  102 
done 
103 

104 
end 

105 