1(*  Title:      CTT/ex/Synthesis.thy
2    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
3    Copyright   1991  University of Cambridge
4*)
5
6section "Synthesis examples, using a crude form of narrowing"
7
8theory Synthesis
9imports "../CTT"
10begin
11
12text "discovery of predecessor function"
13schematic_goal "?a : \<Sum>pred:?A . Eq(N, pred`0, 0) \<times> (\<Prod>n:N. Eq(N, pred ` succ(n), n))"
14apply intr
15apply eqintr
16apply (rule_tac [3] reduction_rls)
17apply (rule_tac [5] comp_rls)
18apply rew
19done
20
21text "the function fst as an element of a function type"
22schematic_goal [folded basic_defs]:
23  "A type \<Longrightarrow> ?a: \<Sum>f:?B . \<Prod>i:A. \<Prod>j:A. Eq(A, f ` <i,j>, i)"
24apply intr
25apply eqintr
26apply (rule_tac [2] reduction_rls)
27apply (rule_tac [4] comp_rls)
28apply typechk
29txt "now put in A everywhere"
30apply assumption+
31done
32
33text "An interesting use of the eliminator, when"
34(*The early implementation of unification caused non-rigid path in occur check
35  See following example.*)
36schematic_goal "?a : \<Prod>i:N. Eq(?A, ?b(inl(i)), <0    ,   i>)
37                   \<times> Eq(?A, ?b(inr(i)), <succ(0), i>)"
38apply intr
39apply eqintr
40apply (rule comp_rls)
41apply rew
42done
43
44(*Here we allow the type to depend on i.
45 This prevents the cycle in the first unification (no longer needed).
46 Requires flex-flex to preserve the dependence.
47 Simpler still: make ?A into a constant type N \<times> N.*)
48schematic_goal "?a : \<Prod>i:N. Eq(?A(i), ?b(inl(i)), <0   ,   i>)
49                  \<times>  Eq(?A(i), ?b(inr(i)), <succ(0),i>)"
50oops
51
52text "A tricky combination of when and split"
53(*Now handled easily, but caused great problems once*)
54schematic_goal [folded basic_defs]:
55  "?a : \<Prod>i:N. \<Prod>j:N. Eq(?A, ?b(inl(<i,j>)), i)
56                           \<times>  Eq(?A, ?b(inr(<i,j>)), j)"
57apply intr
58apply eqintr
59apply (rule PlusC_inl [THEN trans_elem])
60apply (rule_tac [4] comp_rls)
61apply (rule_tac [7] reduction_rls)
62apply (rule_tac [10] comp_rls)
63apply typechk
64done
65
66(*similar but allows the type to depend on i and j*)
67schematic_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)"
69oops
70
71(*similar but specifying the type N simplifies the unification problems*)
72schematic_goal "?a : \<Prod>i:N. \<Prod>j:N. Eq(N, ?b(inl(<i,j>)), i)
73                          \<times>   Eq(N, ?b(inr(<i,j>)), j)"
74oops
75
76
77text "Deriving the addition operator"
78schematic_goal [folded arith_defs]:
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))))"
81apply intr
82apply eqintr
83apply (rule comp_rls)
84apply rew
85done
86
87text "The addition function -- using explicit lambdas"
88schematic_goal [folded arith_defs]:
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)))"
92apply intr
93apply eqintr
94apply (tactic "resolve_tac \<^context> [TSimp.split_eqn] 3")
95apply (tactic "SELECT_GOAL (rew_tac \<^context> []) 4")
96apply (tactic "resolve_tac \<^context> [TSimp.split_eqn] 3")
97apply (tactic "SELECT_GOAL (rew_tac \<^context> []) 4")
98apply (rule_tac [3] p = "y" in NC_succ)
99  (**  by (resolve_tac @{context} comp_rls 3);  caused excessive branching  **)
100apply rew
101done
102
103end
104
105