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