src/HOL/Record.thy
author wenzelm
Thu Feb 11 23:00:22 2010 +0100 (2010-02-11)
changeset 35115 446c5063e4fd
parent 34151 8d57ce46b3f7
child 35132 d137efecf793
permissions -rw-r--r--
modernized translations;
formal markup of @{syntax_const} and @{const_syntax};
minor tuning;
wenzelm@4870
     1
(*  Title:      HOL/Record.thy
wenzelm@32763
     2
    Author:     Wolfgang Naraschewski, TU Muenchen
wenzelm@32763
     3
    Author:     Markus Wenzel, TU Muenchen
wenzelm@32763
     4
    Author:     Norbert Schirmer, TU Muenchen
wenzelm@32763
     5
    Author:     Thomas Sewell, NICTA
haftmann@33595
     6
    Author:     Florian Haftmann, TU Muenchen
wenzelm@4870
     7
*)
wenzelm@4870
     8
wenzelm@22817
     9
header {* Extensible records with structural subtyping *}
wenzelm@22817
    10
nipkow@15131
    11
theory Record
haftmann@33595
    12
imports Datatype
tsewell@32744
    13
uses ("Tools/record.ML")
nipkow@15131
    14
begin
wenzelm@4870
    15
haftmann@33595
    16
subsection {* Introduction *}
haftmann@33595
    17
haftmann@33595
    18
text {*
haftmann@33595
    19
  Records are isomorphic to compound tuple types. To implement
haftmann@33595
    20
  efficient records, we make this isomorphism explicit. Consider the
haftmann@33595
    21
  record access/update simplification @{text "alpha (beta_update f
haftmann@33595
    22
  rec) = alpha rec"} for distinct fields alpha and beta of some record
haftmann@33595
    23
  rec with n fields. There are @{text "n ^ 2"} such theorems, which
haftmann@33595
    24
  prohibits storage of all of them for large n. The rules can be
haftmann@33595
    25
  proved on the fly by case decomposition and simplification in O(n)
haftmann@33595
    26
  time. By creating O(n) isomorphic-tuple types while defining the
haftmann@33595
    27
  record, however, we can prove the access/update simplification in
haftmann@33595
    28
  @{text "O(log(n)^2)"} time.
haftmann@33595
    29
haftmann@33595
    30
  The O(n) cost of case decomposition is not because O(n) steps are
haftmann@33595
    31
  taken, but rather because the resulting rule must contain O(n) new
haftmann@33595
    32
  variables and an O(n) size concrete record construction. To sidestep
haftmann@33595
    33
  this cost, we would like to avoid case decomposition in proving
haftmann@33595
    34
  access/update theorems.
haftmann@33595
    35
haftmann@33595
    36
  Record types are defined as isomorphic to tuple types. For instance,
haftmann@33595
    37
  a record type with fields @{text "'a"}, @{text "'b"}, @{text "'c"}
haftmann@33595
    38
  and @{text "'d"} might be introduced as isomorphic to @{text "'a \<times>
haftmann@33595
    39
  ('b \<times> ('c \<times> 'd))"}. If we balance the tuple tree to @{text "('a \<times>
haftmann@33595
    40
  'b) \<times> ('c \<times> 'd)"} then accessors can be defined by converting to the
haftmann@33595
    41
  underlying type then using O(log(n)) fst or snd operations.
haftmann@33595
    42
  Updators can be defined similarly, if we introduce a @{text
haftmann@33595
    43
  "fst_update"} and @{text "snd_update"} function. Furthermore, we can
haftmann@33595
    44
  prove the access/update theorem in O(log(n)) steps by using simple
haftmann@33595
    45
  rewrites on fst, snd, @{text "fst_update"} and @{text "snd_update"}.
haftmann@33595
    46
haftmann@33595
    47
  The catch is that, although O(log(n)) steps were taken, the
haftmann@33595
    48
  underlying type we converted to is a tuple tree of size
haftmann@33595
    49
  O(n). Processing this term type wastes performance. We avoid this
haftmann@33595
    50
  for large n by taking each subtree of size K and defining a new type
haftmann@33595
    51
  isomorphic to that tuple subtree. A record can now be defined as
haftmann@33595
    52
  isomorphic to a tuple tree of these O(n/K) new types, or, if @{text
haftmann@33595
    53
  "n > K*K"}, we can repeat the process, until the record can be
haftmann@33595
    54
  defined in terms of a tuple tree of complexity less than the
haftmann@33595
    55
  constant K.
haftmann@33595
    56
haftmann@33595
    57
  If we prove the access/update theorem on this type with the
haftmann@33595
    58
  analagous steps to the tuple tree, we consume @{text "O(log(n)^2)"}
haftmann@33595
    59
  time as the intermediate terms are @{text "O(log(n))"} in size and
haftmann@33595
    60
  the types needed have size bounded by K.  To enable this analagous
haftmann@33595
    61
  traversal, we define the functions seen below: @{text
haftmann@34151
    62
  "iso_tuple_fst"}, @{text "iso_tuple_snd"}, @{text "iso_tuple_fst_update"}
haftmann@34151
    63
  and @{text "iso_tuple_snd_update"}. These functions generalise tuple
haftmann@33595
    64
  operations by taking a parameter that encapsulates a tuple
haftmann@33595
    65
  isomorphism.  The rewrites needed on these functions now need an
haftmann@33595
    66
  additional assumption which is that the isomorphism works.
haftmann@33595
    67
haftmann@33595
    68
  These rewrites are typically used in a structured way. They are here
haftmann@33595
    69
  presented as the introduction rule @{text "isomorphic_tuple.intros"}
haftmann@33595
    70
  rather than as a rewrite rule set. The introduction form is an
haftmann@33595
    71
  optimisation, as net matching can be performed at one term location
haftmann@33595
    72
  for each step rather than the simplifier searching the term for
haftmann@33595
    73
  possible pattern matches. The rule set is used as it is viewed
haftmann@33595
    74
  outside the locale, with the locale assumption (that the isomorphism
haftmann@33595
    75
  is valid) left as a rule assumption. All rules are structured to aid
haftmann@33595
    76
  net matching, using either a point-free form or an encapsulating
haftmann@33595
    77
  predicate.
haftmann@33595
    78
*}
haftmann@33595
    79
haftmann@33595
    80
subsection {* Operators and lemmas for types isomorphic to tuples *}
haftmann@33595
    81
haftmann@34151
    82
datatype ('a, 'b, 'c) tuple_isomorphism = Tuple_Isomorphism "'a \<Rightarrow> 'b \<times> 'c" "'b \<times> 'c \<Rightarrow> 'a"
haftmann@33595
    83
haftmann@33595
    84
primrec repr :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'c" where
haftmann@34151
    85
  "repr (Tuple_Isomorphism r a) = r"
haftmann@33595
    86
haftmann@33595
    87
primrec abst :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'b \<times> 'c \<Rightarrow> 'a" where
haftmann@34151
    88
  "abst (Tuple_Isomorphism r a) = a"
haftmann@33595
    89
haftmann@34151
    90
definition iso_tuple_fst :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'b" where
haftmann@34151
    91
  "iso_tuple_fst isom = fst \<circ> repr isom"
haftmann@33595
    92
haftmann@34151
    93
definition iso_tuple_snd :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'c" where
haftmann@34151
    94
  "iso_tuple_snd isom = snd \<circ> repr isom"
haftmann@33595
    95
haftmann@34151
    96
definition iso_tuple_fst_update :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> ('b \<Rightarrow> 'b) \<Rightarrow> ('a \<Rightarrow> 'a)" where
haftmann@34151
    97
  "iso_tuple_fst_update isom f = abst isom \<circ> apfst f \<circ> repr isom"
haftmann@33595
    98
haftmann@34151
    99
definition iso_tuple_snd_update :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> ('c \<Rightarrow> 'c) \<Rightarrow> ('a \<Rightarrow> 'a)" where
haftmann@34151
   100
  "iso_tuple_snd_update isom f = abst isom \<circ> apsnd f \<circ> repr isom"
haftmann@33595
   101
haftmann@34151
   102
definition iso_tuple_cons :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> 'a" where
haftmann@34151
   103
  "iso_tuple_cons isom = curry (abst isom)"
haftmann@33595
   104
haftmann@33595
   105
haftmann@33595
   106
subsection {* Logical infrastructure for records *}
haftmann@33595
   107
haftmann@34151
   108
definition iso_tuple_surjective_proof_assist :: "'a \<Rightarrow> 'b \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool" where
haftmann@34151
   109
  "iso_tuple_surjective_proof_assist x y f \<longleftrightarrow> f x = y"
haftmann@33595
   110
haftmann@34151
   111
definition iso_tuple_update_accessor_cong_assist :: "(('b \<Rightarrow> 'b) \<Rightarrow> ('a \<Rightarrow> 'a)) \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool" where
haftmann@34151
   112
  "iso_tuple_update_accessor_cong_assist upd acc \<longleftrightarrow> 
haftmann@33595
   113
     (\<forall>f v. upd (\<lambda>x. f (acc v)) v = upd f v) \<and> (\<forall>v. upd id v = v)"
haftmann@33595
   114
haftmann@34151
   115
definition iso_tuple_update_accessor_eq_assist :: "(('b \<Rightarrow> 'b) \<Rightarrow> ('a \<Rightarrow> 'a)) \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'a \<Rightarrow> ('b \<Rightarrow> 'b) \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> bool" where
haftmann@34151
   116
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<longleftrightarrow>
haftmann@34151
   117
     upd f v = v' \<and> acc v = x \<and> iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   118
haftmann@33595
   119
lemma update_accessor_congruence_foldE:
haftmann@34151
   120
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   121
  and       r: "r = r'" and v: "acc r' = v'"
haftmann@33595
   122
  and       f: "\<And>v. v' = v \<Longrightarrow> f v = f' v"
haftmann@33595
   123
  shows        "upd f r = upd f' r'"
haftmann@33595
   124
  using uac r v [symmetric]
haftmann@33595
   125
  apply (subgoal_tac "upd (\<lambda>x. f (acc r')) r' = upd (\<lambda>x. f' (acc r')) r'")
haftmann@34151
   126
   apply (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   127
  apply (simp add: f)
haftmann@33595
   128
  done
haftmann@33595
   129
haftmann@33595
   130
lemma update_accessor_congruence_unfoldE:
haftmann@34151
   131
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow> r = r' \<Longrightarrow> acc r' = v' \<Longrightarrow> (\<And>v. v = v' \<Longrightarrow> f v = f' v)
haftmann@33595
   132
     \<Longrightarrow> upd f r = upd f' r'"
haftmann@33595
   133
  apply (erule(2) update_accessor_congruence_foldE)
haftmann@33595
   134
  apply simp
haftmann@33595
   135
  done
haftmann@33595
   136
haftmann@34151
   137
lemma iso_tuple_update_accessor_cong_assist_id:
haftmann@34151
   138
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow> upd id = id"
haftmann@34151
   139
  by rule (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   140
haftmann@33595
   141
lemma update_accessor_noopE:
haftmann@34151
   142
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   143
      and acc: "f (acc x) = acc x"
haftmann@33595
   144
  shows        "upd f x = x"
haftmann@34151
   145
using uac by (simp add: acc iso_tuple_update_accessor_cong_assist_id [OF uac, unfolded id_def]
haftmann@33595
   146
  cong: update_accessor_congruence_unfoldE [OF uac])
haftmann@33595
   147
haftmann@33595
   148
lemma update_accessor_noop_compE:
haftmann@34151
   149
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   150
  assumes acc: "f (acc x) = acc x"
haftmann@33595
   151
  shows      "upd (g \<circ> f) x = upd g x"
haftmann@33595
   152
  by (simp add: acc cong: update_accessor_congruence_unfoldE[OF uac])
haftmann@33595
   153
haftmann@33595
   154
lemma update_accessor_cong_assist_idI:
haftmann@34151
   155
  "iso_tuple_update_accessor_cong_assist id id"
haftmann@34151
   156
  by (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   157
haftmann@33595
   158
lemma update_accessor_cong_assist_triv:
haftmann@34151
   159
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow> iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   160
  by assumption
haftmann@33595
   161
haftmann@33595
   162
lemma update_accessor_accessor_eqE:
haftmann@34151
   163
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> acc v = x"
haftmann@34151
   164
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   165
haftmann@33595
   166
lemma update_accessor_updator_eqE:
haftmann@34151
   167
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> upd f v = v'"
haftmann@34151
   168
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   169
haftmann@34151
   170
lemma iso_tuple_update_accessor_eq_assist_idI:
haftmann@34151
   171
  "v' = f v \<Longrightarrow> iso_tuple_update_accessor_eq_assist id id v f v' v"
haftmann@34151
   172
  by (simp add: iso_tuple_update_accessor_eq_assist_def update_accessor_cong_assist_idI)
haftmann@33595
   173
haftmann@34151
   174
lemma iso_tuple_update_accessor_eq_assist_triv:
haftmann@34151
   175
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> iso_tuple_update_accessor_eq_assist upd acc v f v' x"
haftmann@33595
   176
  by assumption
haftmann@33595
   177
haftmann@34151
   178
lemma iso_tuple_update_accessor_cong_from_eq:
haftmann@34151
   179
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> iso_tuple_update_accessor_cong_assist upd acc"
haftmann@34151
   180
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   181
haftmann@34151
   182
lemma iso_tuple_surjective_proof_assistI:
haftmann@34151
   183
  "f x = y \<Longrightarrow> iso_tuple_surjective_proof_assist x y f"
haftmann@34151
   184
  by (simp add: iso_tuple_surjective_proof_assist_def)
haftmann@33595
   185
haftmann@34151
   186
lemma iso_tuple_surjective_proof_assist_idE:
haftmann@34151
   187
  "iso_tuple_surjective_proof_assist x y id \<Longrightarrow> x = y"
haftmann@34151
   188
  by (simp add: iso_tuple_surjective_proof_assist_def)
haftmann@33595
   189
haftmann@33595
   190
locale isomorphic_tuple =
haftmann@33595
   191
  fixes isom :: "('a, 'b, 'c) tuple_isomorphism"
haftmann@34151
   192
  assumes repr_inv: "\<And>x. abst isom (repr isom x) = x"
haftmann@34151
   193
  assumes abst_inv: "\<And>y. repr isom (abst isom y) = y"
haftmann@33595
   194
begin
haftmann@33595
   195
haftmann@33595
   196
lemma repr_inj:
haftmann@34151
   197
  "repr isom x = repr isom y \<longleftrightarrow> x = y"
haftmann@34151
   198
  by (auto dest: arg_cong [of "repr isom x" "repr isom y" "abst isom"] simp add: repr_inv)
haftmann@33595
   199
haftmann@33595
   200
lemma abst_inj:
haftmann@34151
   201
  "abst isom x = abst isom y \<longleftrightarrow> x = y"
haftmann@34151
   202
  by (auto dest: arg_cong [of "abst isom x" "abst isom y" "repr isom"] simp add: abst_inv)
haftmann@34151
   203
haftmann@34151
   204
lemmas simps = Let_def repr_inv abst_inv repr_inj abst_inj
haftmann@33595
   205
haftmann@34151
   206
lemma iso_tuple_access_update_fst_fst:
haftmann@33595
   207
  "f o h g = j o f \<Longrightarrow>
haftmann@34151
   208
    (f o iso_tuple_fst isom) o (iso_tuple_fst_update isom o h) g
haftmann@34151
   209
          = j o (f o iso_tuple_fst isom)"
haftmann@34151
   210
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_fst_def simps
haftmann@33595
   211
             intro!: ext elim!: o_eq_elim)
haftmann@33595
   212
haftmann@34151
   213
lemma iso_tuple_access_update_snd_snd:
haftmann@33595
   214
  "f o h g = j o f \<Longrightarrow>
haftmann@34151
   215
    (f o iso_tuple_snd isom) o (iso_tuple_snd_update isom o h) g
haftmann@34151
   216
          = j o (f o iso_tuple_snd isom)"
haftmann@34151
   217
  by (clarsimp simp: iso_tuple_snd_update_def iso_tuple_snd_def simps
haftmann@33595
   218
             intro!: ext elim!: o_eq_elim)
haftmann@33595
   219
haftmann@34151
   220
lemma iso_tuple_access_update_fst_snd:
haftmann@34151
   221
  "(f o iso_tuple_fst isom) o (iso_tuple_snd_update isom o h) g
haftmann@34151
   222
          = id o (f o iso_tuple_fst isom)"
haftmann@34151
   223
  by (clarsimp simp: iso_tuple_snd_update_def iso_tuple_fst_def simps
haftmann@33595
   224
             intro!: ext elim!: o_eq_elim)
haftmann@33595
   225
haftmann@34151
   226
lemma iso_tuple_access_update_snd_fst:
haftmann@34151
   227
  "(f o iso_tuple_snd isom) o (iso_tuple_fst_update isom o h) g
haftmann@34151
   228
          = id o (f o iso_tuple_snd isom)"
haftmann@34151
   229
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_def simps
haftmann@33595
   230
             intro!: ext elim!: o_eq_elim)
haftmann@33595
   231
haftmann@34151
   232
lemma iso_tuple_update_swap_fst_fst:
haftmann@33595
   233
  "h f o j g = j g o h f \<Longrightarrow>
haftmann@34151
   234
    (iso_tuple_fst_update isom o h) f o (iso_tuple_fst_update isom o j) g
haftmann@34151
   235
          = (iso_tuple_fst_update isom o j) g o (iso_tuple_fst_update isom o h) f"
haftmann@34151
   236
  by (clarsimp simp: iso_tuple_fst_update_def simps apfst_compose intro!: ext)
haftmann@33595
   237
haftmann@34151
   238
lemma iso_tuple_update_swap_snd_snd:
haftmann@33595
   239
  "h f o j g = j g o h f \<Longrightarrow>
haftmann@34151
   240
    (iso_tuple_snd_update isom o h) f o (iso_tuple_snd_update isom o j) g
haftmann@34151
   241
          = (iso_tuple_snd_update isom o j) g o (iso_tuple_snd_update isom o h) f"
haftmann@34151
   242
  by (clarsimp simp: iso_tuple_snd_update_def simps apsnd_compose intro!: ext)
haftmann@33595
   243
haftmann@34151
   244
lemma iso_tuple_update_swap_fst_snd:
haftmann@34151
   245
  "(iso_tuple_snd_update isom o h) f o (iso_tuple_fst_update isom o j) g
haftmann@34151
   246
          = (iso_tuple_fst_update isom o j) g o (iso_tuple_snd_update isom o h) f"
haftmann@34151
   247
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_update_def simps intro!: ext)
haftmann@33595
   248
haftmann@34151
   249
lemma iso_tuple_update_swap_snd_fst:
haftmann@34151
   250
  "(iso_tuple_fst_update isom o h) f o (iso_tuple_snd_update isom o j) g
haftmann@34151
   251
          = (iso_tuple_snd_update isom o j) g o (iso_tuple_fst_update isom o h) f"
haftmann@34151
   252
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_update_def simps intro!: ext)
haftmann@33595
   253
haftmann@34151
   254
lemma iso_tuple_update_compose_fst_fst:
haftmann@33595
   255
  "h f o j g = k (f o g) \<Longrightarrow>
haftmann@34151
   256
    (iso_tuple_fst_update isom o h) f o (iso_tuple_fst_update isom o j) g
haftmann@34151
   257
          = (iso_tuple_fst_update isom o k) (f o g)"
haftmann@34151
   258
  by (clarsimp simp: iso_tuple_fst_update_def simps apfst_compose intro!: ext)
haftmann@33595
   259
haftmann@34151
   260
lemma iso_tuple_update_compose_snd_snd:
haftmann@33595
   261
  "h f o j g = k (f o g) \<Longrightarrow>
haftmann@34151
   262
    (iso_tuple_snd_update isom o h) f o (iso_tuple_snd_update isom o j) g
haftmann@34151
   263
          = (iso_tuple_snd_update isom o k) (f o g)"
haftmann@34151
   264
  by (clarsimp simp: iso_tuple_snd_update_def simps apsnd_compose intro!: ext)
haftmann@33595
   265
haftmann@34151
   266
lemma iso_tuple_surjective_proof_assist_step:
haftmann@34151
   267
  "iso_tuple_surjective_proof_assist v a (iso_tuple_fst isom o f) \<Longrightarrow>
haftmann@34151
   268
     iso_tuple_surjective_proof_assist v b (iso_tuple_snd isom o f)
haftmann@34151
   269
      \<Longrightarrow> iso_tuple_surjective_proof_assist v (iso_tuple_cons isom a b) f"
haftmann@34151
   270
  by (clarsimp simp: iso_tuple_surjective_proof_assist_def simps
haftmann@34151
   271
    iso_tuple_fst_def iso_tuple_snd_def iso_tuple_cons_def)
haftmann@33595
   272
haftmann@34151
   273
lemma iso_tuple_fst_update_accessor_cong_assist:
haftmann@34151
   274
  assumes "iso_tuple_update_accessor_cong_assist f g"
haftmann@34151
   275
  shows "iso_tuple_update_accessor_cong_assist (iso_tuple_fst_update isom o f) (g o iso_tuple_fst isom)"
haftmann@33595
   276
proof -
haftmann@34151
   277
  from assms have "f id = id" by (rule iso_tuple_update_accessor_cong_assist_id)
haftmann@34151
   278
  with assms show ?thesis by (clarsimp simp: iso_tuple_update_accessor_cong_assist_def simps
haftmann@34151
   279
    iso_tuple_fst_update_def iso_tuple_fst_def)
haftmann@33595
   280
qed
haftmann@33595
   281
haftmann@34151
   282
lemma iso_tuple_snd_update_accessor_cong_assist:
haftmann@34151
   283
  assumes "iso_tuple_update_accessor_cong_assist f g"
haftmann@34151
   284
  shows "iso_tuple_update_accessor_cong_assist (iso_tuple_snd_update isom o f) (g o iso_tuple_snd isom)"
haftmann@33595
   285
proof -
haftmann@34151
   286
  from assms have "f id = id" by (rule iso_tuple_update_accessor_cong_assist_id)
haftmann@34151
   287
  with assms show ?thesis by (clarsimp simp: iso_tuple_update_accessor_cong_assist_def simps
haftmann@34151
   288
    iso_tuple_snd_update_def iso_tuple_snd_def)
haftmann@33595
   289
qed
haftmann@33595
   290
haftmann@34151
   291
lemma iso_tuple_fst_update_accessor_eq_assist:
haftmann@34151
   292
  assumes "iso_tuple_update_accessor_eq_assist f g a u a' v"
haftmann@34151
   293
  shows "iso_tuple_update_accessor_eq_assist (iso_tuple_fst_update isom o f) (g o iso_tuple_fst isom)
haftmann@34151
   294
    (iso_tuple_cons isom a b) u (iso_tuple_cons isom a' b) v"
haftmann@33595
   295
proof -
haftmann@33595
   296
  from assms have "f id = id"
haftmann@34151
   297
    by (auto simp add: iso_tuple_update_accessor_eq_assist_def intro: iso_tuple_update_accessor_cong_assist_id)
haftmann@34151
   298
  with assms show ?thesis by (clarsimp simp: iso_tuple_update_accessor_eq_assist_def
haftmann@34151
   299
    iso_tuple_fst_update_def iso_tuple_fst_def iso_tuple_update_accessor_cong_assist_def iso_tuple_cons_def simps)
haftmann@33595
   300
qed
haftmann@33595
   301
haftmann@34151
   302
lemma iso_tuple_snd_update_accessor_eq_assist:
haftmann@34151
   303
  assumes "iso_tuple_update_accessor_eq_assist f g b u b' v"
haftmann@34151
   304
  shows "iso_tuple_update_accessor_eq_assist (iso_tuple_snd_update isom o f) (g o iso_tuple_snd isom)
haftmann@34151
   305
    (iso_tuple_cons isom a b) u (iso_tuple_cons isom a b') v"
haftmann@33595
   306
proof -
haftmann@33595
   307
  from assms have "f id = id"
haftmann@34151
   308
    by (auto simp add: iso_tuple_update_accessor_eq_assist_def intro: iso_tuple_update_accessor_cong_assist_id)
haftmann@34151
   309
  with assms show ?thesis by (clarsimp simp: iso_tuple_update_accessor_eq_assist_def
haftmann@34151
   310
    iso_tuple_snd_update_def iso_tuple_snd_def iso_tuple_update_accessor_cong_assist_def iso_tuple_cons_def simps)
haftmann@33595
   311
qed
haftmann@33595
   312
haftmann@34151
   313
lemma iso_tuple_cons_conj_eqI:
haftmann@33595
   314
  "a = c \<and> b = d \<and> P \<longleftrightarrow> Q \<Longrightarrow>
haftmann@34151
   315
    iso_tuple_cons isom a b = iso_tuple_cons isom c d \<and> P \<longleftrightarrow> Q"
haftmann@34151
   316
  by (clarsimp simp: iso_tuple_cons_def simps)
haftmann@33595
   317
haftmann@33595
   318
lemmas intros =
haftmann@34151
   319
    iso_tuple_access_update_fst_fst
haftmann@34151
   320
    iso_tuple_access_update_snd_snd
haftmann@34151
   321
    iso_tuple_access_update_fst_snd
haftmann@34151
   322
    iso_tuple_access_update_snd_fst
haftmann@34151
   323
    iso_tuple_update_swap_fst_fst
haftmann@34151
   324
    iso_tuple_update_swap_snd_snd
haftmann@34151
   325
    iso_tuple_update_swap_fst_snd
haftmann@34151
   326
    iso_tuple_update_swap_snd_fst
haftmann@34151
   327
    iso_tuple_update_compose_fst_fst
haftmann@34151
   328
    iso_tuple_update_compose_snd_snd
haftmann@34151
   329
    iso_tuple_surjective_proof_assist_step
haftmann@34151
   330
    iso_tuple_fst_update_accessor_eq_assist
haftmann@34151
   331
    iso_tuple_snd_update_accessor_eq_assist
haftmann@34151
   332
    iso_tuple_fst_update_accessor_cong_assist
haftmann@34151
   333
    iso_tuple_snd_update_accessor_cong_assist
haftmann@34151
   334
    iso_tuple_cons_conj_eqI
haftmann@33595
   335
haftmann@33595
   336
end
haftmann@33595
   337
haftmann@33595
   338
lemma isomorphic_tuple_intro:
haftmann@33595
   339
  fixes repr abst
haftmann@33595
   340
  assumes repr_inj: "\<And>x y. repr x = repr y \<longleftrightarrow> x = y"
haftmann@33595
   341
     and abst_inv: "\<And>z. repr (abst z) = z"
haftmann@34151
   342
  assumes v: "v \<equiv> Tuple_Isomorphism repr abst"
haftmann@33595
   343
  shows "isomorphic_tuple v"
haftmann@34151
   344
proof
haftmann@34151
   345
  have "\<And>x. repr (abst (repr x)) = repr x"
haftmann@34151
   346
    by (simp add: abst_inv)
haftmann@34151
   347
  then show "\<And>x. Record.abst v (Record.repr v x) = x"
haftmann@34151
   348
    by (simp add: v repr_inj)
haftmann@34151
   349
  show P: "\<And>y. Record.repr v (Record.abst v y) = y"
haftmann@34151
   350
    by (simp add: v) (fact abst_inv)
haftmann@34151
   351
qed
haftmann@33595
   352
haftmann@33595
   353
definition
haftmann@34151
   354
  "tuple_iso_tuple \<equiv> Tuple_Isomorphism id id"
haftmann@33595
   355
haftmann@34151
   356
lemma tuple_iso_tuple:
haftmann@34151
   357
  "isomorphic_tuple tuple_iso_tuple"
haftmann@34151
   358
  by (simp add: isomorphic_tuple_intro [OF _ _ reflexive] tuple_iso_tuple_def)
haftmann@33595
   359
haftmann@33595
   360
lemma refl_conj_eq:
haftmann@33595
   361
  "Q = R \<Longrightarrow> P \<and> Q \<longleftrightarrow> P \<and> R"
haftmann@33595
   362
  by simp
haftmann@33595
   363
haftmann@34151
   364
lemma iso_tuple_UNIV_I: "x \<in> UNIV \<equiv> True"
haftmann@33595
   365
  by simp
haftmann@33595
   366
haftmann@34151
   367
lemma iso_tuple_True_simp: "(True \<Longrightarrow> PROP P) \<equiv> PROP P"
haftmann@33595
   368
  by simp
haftmann@33595
   369
schirmer@14700
   370
lemma prop_subst: "s = t \<Longrightarrow> PROP P t \<Longrightarrow> PROP P s"
schirmer@14700
   371
  by simp
wenzelm@11826
   372
schirmer@25705
   373
lemma K_record_comp: "(\<lambda>x. c) \<circ> f = (\<lambda>x. c)" 
schirmer@25705
   374
  by (simp add: comp_def)
wenzelm@11821
   375
tsewell@32743
   376
lemma o_eq_dest_lhs:
tsewell@32743
   377
  "a o b = c \<Longrightarrow> a (b v) = c v"
tsewell@32743
   378
  by clarsimp
tsewell@32743
   379
tsewell@32743
   380
lemma o_eq_id_dest:
tsewell@32743
   381
  "a o b = id o c \<Longrightarrow> a (b v) = c v"
tsewell@32743
   382
  by clarsimp
wenzelm@22817
   383
haftmann@33595
   384
wenzelm@11833
   385
subsection {* Concrete record syntax *}
wenzelm@4870
   386
wenzelm@4870
   387
nonterminals
wenzelm@5198
   388
  ident field_type field_types field fields update updates
wenzelm@4870
   389
syntax
wenzelm@11821
   390
  "_constify"           :: "id => ident"                        ("_")
wenzelm@11821
   391
  "_constify"           :: "longid => ident"                    ("_")
wenzelm@5198
   392
wenzelm@11821
   393
  "_field_type"         :: "[ident, type] => field_type"        ("(2_ ::/ _)")
wenzelm@11821
   394
  ""                    :: "field_type => field_types"          ("_")
wenzelm@11821
   395
  "_field_types"        :: "[field_type, field_types] => field_types"    ("_,/ _")
wenzelm@11821
   396
  "_record_type"        :: "field_types => type"                ("(3'(| _ |'))")
wenzelm@10093
   397
  "_record_type_scheme" :: "[field_types, type] => type"        ("(3'(| _,/ (2... ::/ _) |'))")
wenzelm@5198
   398
wenzelm@11821
   399
  "_field"              :: "[ident, 'a] => field"               ("(2_ =/ _)")
wenzelm@11821
   400
  ""                    :: "field => fields"                    ("_")
wenzelm@11821
   401
  "_fields"             :: "[field, fields] => fields"          ("_,/ _")
wenzelm@11821
   402
  "_record"             :: "fields => 'a"                       ("(3'(| _ |'))")
wenzelm@10093
   403
  "_record_scheme"      :: "[fields, 'a] => 'a"                 ("(3'(| _,/ (2... =/ _) |'))")
wenzelm@5198
   404
wenzelm@10641
   405
  "_update_name"        :: idt
wenzelm@11821
   406
  "_update"             :: "[ident, 'a] => update"              ("(2_ :=/ _)")
wenzelm@11821
   407
  ""                    :: "update => updates"                  ("_")
wenzelm@11821
   408
  "_updates"            :: "[update, updates] => updates"       ("_,/ _")
wenzelm@10093
   409
  "_record_update"      :: "['a, updates] => 'b"                ("_/(3'(| _ |'))" [900,0] 900)
wenzelm@4870
   410
wenzelm@10331
   411
syntax (xsymbols)
wenzelm@11821
   412
  "_record_type"        :: "field_types => type"                ("(3\<lparr>_\<rparr>)")
wenzelm@10093
   413
  "_record_type_scheme" :: "[field_types, type] => type"        ("(3\<lparr>_,/ (2\<dots> ::/ _)\<rparr>)")
wenzelm@10093
   414
  "_record"             :: "fields => 'a"                               ("(3\<lparr>_\<rparr>)")
wenzelm@10093
   415
  "_record_scheme"      :: "[fields, 'a] => 'a"                 ("(3\<lparr>_,/ (2\<dots> =/ _)\<rparr>)")
wenzelm@10093
   416
  "_record_update"      :: "['a, updates] => 'b"                ("_/(3\<lparr>_\<rparr>)" [900,0] 900)
wenzelm@9729
   417
tsewell@32752
   418
haftmann@33595
   419
subsection {* Record package *}
tsewell@32752
   420
tsewell@32744
   421
use "Tools/record.ML"
tsewell@32744
   422
setup Record.setup
wenzelm@10641
   423
haftmann@34151
   424
hide (open) const Tuple_Isomorphism repr abst iso_tuple_fst iso_tuple_snd
haftmann@34151
   425
  iso_tuple_fst_update iso_tuple_snd_update iso_tuple_cons
haftmann@34151
   426
  iso_tuple_surjective_proof_assist iso_tuple_update_accessor_cong_assist
haftmann@34151
   427
  iso_tuple_update_accessor_eq_assist tuple_iso_tuple
haftmann@33595
   428
wenzelm@4870
   429
end