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