src/HOL/Record.thy
author wenzelm
Fri Apr 16 21:28:09 2010 +0200 (2010-04-16)
changeset 36176 3fe7e97ccca8
parent 35146 f7bf73b0d7e5
child 38394 3142c1e21a0e
permissions -rw-r--r--
replaced generic 'hide' command by more conventional 'hide_class', 'hide_type', 'hide_const', 'hide_fact' -- frees some popular keywords;
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
wenzelm@35132
    82
datatype ('a, 'b, 'c) tuple_isomorphism =
wenzelm@35132
    83
  Tuple_Isomorphism "'a \<Rightarrow> 'b \<times> 'c" "'b \<times> 'c \<Rightarrow> 'a"
haftmann@33595
    84
wenzelm@35132
    85
primrec
wenzelm@35132
    86
  repr :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'c" where
haftmann@34151
    87
  "repr (Tuple_Isomorphism r a) = r"
haftmann@33595
    88
wenzelm@35132
    89
primrec
wenzelm@35132
    90
  abst :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'b \<times> 'c \<Rightarrow> 'a" where
haftmann@34151
    91
  "abst (Tuple_Isomorphism r a) = a"
haftmann@33595
    92
wenzelm@35132
    93
definition
wenzelm@35132
    94
  iso_tuple_fst :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'b" where
haftmann@34151
    95
  "iso_tuple_fst isom = fst \<circ> repr isom"
haftmann@33595
    96
wenzelm@35132
    97
definition
wenzelm@35132
    98
  iso_tuple_snd :: "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'a \<Rightarrow> 'c" where
haftmann@34151
    99
  "iso_tuple_snd isom = snd \<circ> repr isom"
haftmann@33595
   100
wenzelm@35132
   101
definition
wenzelm@35132
   102
  iso_tuple_fst_update ::
wenzelm@35132
   103
    "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> ('b \<Rightarrow> 'b) \<Rightarrow> ('a \<Rightarrow> 'a)" where
haftmann@34151
   104
  "iso_tuple_fst_update isom f = abst isom \<circ> apfst f \<circ> repr isom"
haftmann@33595
   105
wenzelm@35132
   106
definition
wenzelm@35132
   107
  iso_tuple_snd_update ::
wenzelm@35132
   108
    "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> ('c \<Rightarrow> 'c) \<Rightarrow> ('a \<Rightarrow> 'a)" where
haftmann@34151
   109
  "iso_tuple_snd_update isom f = abst isom \<circ> apsnd f \<circ> repr isom"
haftmann@33595
   110
wenzelm@35132
   111
definition
wenzelm@35132
   112
  iso_tuple_cons ::
wenzelm@35132
   113
    "('a, 'b, 'c) tuple_isomorphism \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> 'a" where
haftmann@34151
   114
  "iso_tuple_cons isom = curry (abst isom)"
haftmann@33595
   115
haftmann@33595
   116
haftmann@33595
   117
subsection {* Logical infrastructure for records *}
haftmann@33595
   118
wenzelm@35132
   119
definition
wenzelm@35132
   120
  iso_tuple_surjective_proof_assist :: "'a \<Rightarrow> 'b \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool" where
haftmann@34151
   121
  "iso_tuple_surjective_proof_assist x y f \<longleftrightarrow> f x = y"
haftmann@33595
   122
wenzelm@35132
   123
definition
wenzelm@35132
   124
  iso_tuple_update_accessor_cong_assist ::
wenzelm@35132
   125
    "(('b \<Rightarrow> 'b) \<Rightarrow> ('a \<Rightarrow> 'a)) \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool" where
wenzelm@35132
   126
  "iso_tuple_update_accessor_cong_assist upd acc \<longleftrightarrow>
haftmann@33595
   127
     (\<forall>f v. upd (\<lambda>x. f (acc v)) v = upd f v) \<and> (\<forall>v. upd id v = v)"
haftmann@33595
   128
wenzelm@35132
   129
definition
wenzelm@35132
   130
  iso_tuple_update_accessor_eq_assist ::
wenzelm@35132
   131
    "(('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
   132
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<longleftrightarrow>
haftmann@34151
   133
     upd f v = v' \<and> acc v = x \<and> iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   134
haftmann@33595
   135
lemma update_accessor_congruence_foldE:
haftmann@34151
   136
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
wenzelm@35132
   137
    and r: "r = r'" and v: "acc r' = v'"
wenzelm@35132
   138
    and f: "\<And>v. v' = v \<Longrightarrow> f v = f' v"
wenzelm@35132
   139
  shows "upd f r = upd f' r'"
haftmann@33595
   140
  using uac r v [symmetric]
haftmann@33595
   141
  apply (subgoal_tac "upd (\<lambda>x. f (acc r')) r' = upd (\<lambda>x. f' (acc r')) r'")
haftmann@34151
   142
   apply (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   143
  apply (simp add: f)
haftmann@33595
   144
  done
haftmann@33595
   145
haftmann@33595
   146
lemma update_accessor_congruence_unfoldE:
wenzelm@35132
   147
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow>
wenzelm@35132
   148
    r = r' \<Longrightarrow> acc r' = v' \<Longrightarrow> (\<And>v. v = v' \<Longrightarrow> f v = f' v) \<Longrightarrow>
wenzelm@35132
   149
    upd f r = upd f' r'"
haftmann@33595
   150
  apply (erule(2) update_accessor_congruence_foldE)
haftmann@33595
   151
  apply simp
haftmann@33595
   152
  done
haftmann@33595
   153
haftmann@34151
   154
lemma iso_tuple_update_accessor_cong_assist_id:
haftmann@34151
   155
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow> upd id = id"
haftmann@34151
   156
  by rule (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   157
haftmann@33595
   158
lemma update_accessor_noopE:
haftmann@34151
   159
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
wenzelm@35132
   160
    and acc: "f (acc x) = acc x"
wenzelm@35132
   161
  shows "upd f x = x"
wenzelm@35132
   162
  using uac
wenzelm@35132
   163
  by (simp add: acc iso_tuple_update_accessor_cong_assist_id [OF uac, unfolded id_def]
wenzelm@35132
   164
    cong: update_accessor_congruence_unfoldE [OF uac])
haftmann@33595
   165
haftmann@33595
   166
lemma update_accessor_noop_compE:
haftmann@34151
   167
  assumes uac: "iso_tuple_update_accessor_cong_assist upd acc"
wenzelm@35132
   168
    and acc: "f (acc x) = acc x"
wenzelm@35132
   169
  shows "upd (g \<circ> f) x = upd g x"
haftmann@33595
   170
  by (simp add: acc cong: update_accessor_congruence_unfoldE[OF uac])
haftmann@33595
   171
haftmann@33595
   172
lemma update_accessor_cong_assist_idI:
haftmann@34151
   173
  "iso_tuple_update_accessor_cong_assist id id"
haftmann@34151
   174
  by (simp add: iso_tuple_update_accessor_cong_assist_def)
haftmann@33595
   175
haftmann@33595
   176
lemma update_accessor_cong_assist_triv:
wenzelm@35132
   177
  "iso_tuple_update_accessor_cong_assist upd acc \<Longrightarrow>
wenzelm@35132
   178
    iso_tuple_update_accessor_cong_assist upd acc"
haftmann@33595
   179
  by assumption
haftmann@33595
   180
haftmann@33595
   181
lemma update_accessor_accessor_eqE:
haftmann@34151
   182
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> acc v = x"
haftmann@34151
   183
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   184
haftmann@33595
   185
lemma update_accessor_updator_eqE:
haftmann@34151
   186
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow> upd f v = v'"
haftmann@34151
   187
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   188
haftmann@34151
   189
lemma iso_tuple_update_accessor_eq_assist_idI:
haftmann@34151
   190
  "v' = f v \<Longrightarrow> iso_tuple_update_accessor_eq_assist id id v f v' v"
haftmann@34151
   191
  by (simp add: iso_tuple_update_accessor_eq_assist_def update_accessor_cong_assist_idI)
haftmann@33595
   192
haftmann@34151
   193
lemma iso_tuple_update_accessor_eq_assist_triv:
wenzelm@35132
   194
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow>
wenzelm@35132
   195
    iso_tuple_update_accessor_eq_assist upd acc v f v' x"
haftmann@33595
   196
  by assumption
haftmann@33595
   197
haftmann@34151
   198
lemma iso_tuple_update_accessor_cong_from_eq:
wenzelm@35132
   199
  "iso_tuple_update_accessor_eq_assist upd acc v f v' x \<Longrightarrow>
wenzelm@35132
   200
    iso_tuple_update_accessor_cong_assist upd acc"
haftmann@34151
   201
  by (simp add: iso_tuple_update_accessor_eq_assist_def)
haftmann@33595
   202
haftmann@34151
   203
lemma iso_tuple_surjective_proof_assistI:
haftmann@34151
   204
  "f x = y \<Longrightarrow> iso_tuple_surjective_proof_assist x y f"
haftmann@34151
   205
  by (simp add: iso_tuple_surjective_proof_assist_def)
haftmann@33595
   206
haftmann@34151
   207
lemma iso_tuple_surjective_proof_assist_idE:
haftmann@34151
   208
  "iso_tuple_surjective_proof_assist x y id \<Longrightarrow> x = y"
haftmann@34151
   209
  by (simp add: iso_tuple_surjective_proof_assist_def)
haftmann@33595
   210
haftmann@33595
   211
locale isomorphic_tuple =
haftmann@33595
   212
  fixes isom :: "('a, 'b, 'c) tuple_isomorphism"
haftmann@34151
   213
  assumes repr_inv: "\<And>x. abst isom (repr isom x) = x"
wenzelm@35132
   214
    and abst_inv: "\<And>y. repr isom (abst isom y) = y"
haftmann@33595
   215
begin
haftmann@33595
   216
wenzelm@35132
   217
lemma repr_inj: "repr isom x = repr isom y \<longleftrightarrow> x = y"
wenzelm@35132
   218
  by (auto dest: arg_cong [of "repr isom x" "repr isom y" "abst isom"]
wenzelm@35132
   219
    simp add: repr_inv)
haftmann@33595
   220
wenzelm@35132
   221
lemma abst_inj: "abst isom x = abst isom y \<longleftrightarrow> x = y"
wenzelm@35132
   222
  by (auto dest: arg_cong [of "abst isom x" "abst isom y" "repr isom"]
wenzelm@35132
   223
    simp add: abst_inv)
haftmann@34151
   224
haftmann@34151
   225
lemmas simps = Let_def repr_inv abst_inv repr_inj abst_inj
haftmann@33595
   226
haftmann@34151
   227
lemma iso_tuple_access_update_fst_fst:
haftmann@33595
   228
  "f o h g = j o f \<Longrightarrow>
wenzelm@35132
   229
    (f o iso_tuple_fst isom) o (iso_tuple_fst_update isom o h) g =
wenzelm@35132
   230
      j o (f o iso_tuple_fst isom)"
haftmann@34151
   231
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_fst_def simps
wenzelm@35132
   232
    intro!: ext elim!: o_eq_elim)
haftmann@33595
   233
haftmann@34151
   234
lemma iso_tuple_access_update_snd_snd:
haftmann@33595
   235
  "f o h g = j o f \<Longrightarrow>
wenzelm@35132
   236
    (f o iso_tuple_snd isom) o (iso_tuple_snd_update isom o h) g =
wenzelm@35132
   237
      j o (f o iso_tuple_snd isom)"
haftmann@34151
   238
  by (clarsimp simp: iso_tuple_snd_update_def iso_tuple_snd_def simps
wenzelm@35132
   239
    intro!: ext elim!: o_eq_elim)
haftmann@33595
   240
haftmann@34151
   241
lemma iso_tuple_access_update_fst_snd:
wenzelm@35132
   242
  "(f o iso_tuple_fst isom) o (iso_tuple_snd_update isom o h) g =
wenzelm@35132
   243
    id o (f o iso_tuple_fst isom)"
haftmann@34151
   244
  by (clarsimp simp: iso_tuple_snd_update_def iso_tuple_fst_def simps
wenzelm@35132
   245
    intro!: ext elim!: o_eq_elim)
haftmann@33595
   246
haftmann@34151
   247
lemma iso_tuple_access_update_snd_fst:
wenzelm@35132
   248
  "(f o iso_tuple_snd isom) o (iso_tuple_fst_update isom o h) g =
wenzelm@35132
   249
    id o (f o iso_tuple_snd isom)"
haftmann@34151
   250
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_def simps
wenzelm@35132
   251
    intro!: ext elim!: o_eq_elim)
haftmann@33595
   252
haftmann@34151
   253
lemma iso_tuple_update_swap_fst_fst:
haftmann@33595
   254
  "h f o j g = j g o h f \<Longrightarrow>
wenzelm@35132
   255
    (iso_tuple_fst_update isom o h) f o (iso_tuple_fst_update isom o j) g =
wenzelm@35132
   256
      (iso_tuple_fst_update isom o j) g o (iso_tuple_fst_update isom o h) f"
haftmann@34151
   257
  by (clarsimp simp: iso_tuple_fst_update_def simps apfst_compose intro!: ext)
haftmann@33595
   258
haftmann@34151
   259
lemma iso_tuple_update_swap_snd_snd:
haftmann@33595
   260
  "h f o j g = j g o h f \<Longrightarrow>
wenzelm@35132
   261
    (iso_tuple_snd_update isom o h) f o (iso_tuple_snd_update isom o j) g =
wenzelm@35132
   262
      (iso_tuple_snd_update isom o j) g o (iso_tuple_snd_update isom o h) f"
haftmann@34151
   263
  by (clarsimp simp: iso_tuple_snd_update_def simps apsnd_compose intro!: ext)
haftmann@33595
   264
haftmann@34151
   265
lemma iso_tuple_update_swap_fst_snd:
wenzelm@35132
   266
  "(iso_tuple_snd_update isom o h) f o (iso_tuple_fst_update isom o j) g =
wenzelm@35132
   267
    (iso_tuple_fst_update isom o j) g o (iso_tuple_snd_update isom o h) f"
wenzelm@35132
   268
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_update_def
wenzelm@35132
   269
    simps intro!: ext)
haftmann@33595
   270
haftmann@34151
   271
lemma iso_tuple_update_swap_snd_fst:
wenzelm@35132
   272
  "(iso_tuple_fst_update isom o h) f o (iso_tuple_snd_update isom o j) g =
wenzelm@35132
   273
    (iso_tuple_snd_update isom o j) g o (iso_tuple_fst_update isom o h) f"
haftmann@34151
   274
  by (clarsimp simp: iso_tuple_fst_update_def iso_tuple_snd_update_def simps intro!: ext)
haftmann@33595
   275
haftmann@34151
   276
lemma iso_tuple_update_compose_fst_fst:
haftmann@33595
   277
  "h f o j g = k (f o g) \<Longrightarrow>
wenzelm@35132
   278
    (iso_tuple_fst_update isom o h) f o (iso_tuple_fst_update isom o j) g =
wenzelm@35132
   279
      (iso_tuple_fst_update isom o k) (f o g)"
haftmann@34151
   280
  by (clarsimp simp: iso_tuple_fst_update_def simps apfst_compose intro!: ext)
haftmann@33595
   281
haftmann@34151
   282
lemma iso_tuple_update_compose_snd_snd:
haftmann@33595
   283
  "h f o j g = k (f o g) \<Longrightarrow>
wenzelm@35132
   284
    (iso_tuple_snd_update isom o h) f o (iso_tuple_snd_update isom o j) g =
wenzelm@35132
   285
      (iso_tuple_snd_update isom o k) (f o g)"
haftmann@34151
   286
  by (clarsimp simp: iso_tuple_snd_update_def simps apsnd_compose intro!: ext)
haftmann@33595
   287
haftmann@34151
   288
lemma iso_tuple_surjective_proof_assist_step:
haftmann@34151
   289
  "iso_tuple_surjective_proof_assist v a (iso_tuple_fst isom o f) \<Longrightarrow>
wenzelm@35132
   290
    iso_tuple_surjective_proof_assist v b (iso_tuple_snd isom o f) \<Longrightarrow>
wenzelm@35132
   291
    iso_tuple_surjective_proof_assist v (iso_tuple_cons isom a b) f"
haftmann@34151
   292
  by (clarsimp simp: iso_tuple_surjective_proof_assist_def simps
haftmann@34151
   293
    iso_tuple_fst_def iso_tuple_snd_def iso_tuple_cons_def)
haftmann@33595
   294
haftmann@34151
   295
lemma iso_tuple_fst_update_accessor_cong_assist:
haftmann@34151
   296
  assumes "iso_tuple_update_accessor_cong_assist f g"
wenzelm@35132
   297
  shows "iso_tuple_update_accessor_cong_assist
wenzelm@35132
   298
    (iso_tuple_fst_update isom o f) (g o iso_tuple_fst isom)"
haftmann@33595
   299
proof -
wenzelm@35132
   300
  from assms have "f id = id"
wenzelm@35132
   301
    by (rule iso_tuple_update_accessor_cong_assist_id)
wenzelm@35132
   302
  with assms show ?thesis
wenzelm@35132
   303
    by (clarsimp simp: iso_tuple_update_accessor_cong_assist_def simps
wenzelm@35132
   304
      iso_tuple_fst_update_def iso_tuple_fst_def)
haftmann@33595
   305
qed
haftmann@33595
   306
haftmann@34151
   307
lemma iso_tuple_snd_update_accessor_cong_assist:
haftmann@34151
   308
  assumes "iso_tuple_update_accessor_cong_assist f g"
wenzelm@35132
   309
  shows "iso_tuple_update_accessor_cong_assist
wenzelm@35132
   310
    (iso_tuple_snd_update isom o f) (g o iso_tuple_snd isom)"
haftmann@33595
   311
proof -
wenzelm@35132
   312
  from assms have "f id = id"
wenzelm@35132
   313
    by (rule iso_tuple_update_accessor_cong_assist_id)
wenzelm@35132
   314
  with assms show ?thesis
wenzelm@35132
   315
    by (clarsimp simp: iso_tuple_update_accessor_cong_assist_def simps
wenzelm@35132
   316
      iso_tuple_snd_update_def iso_tuple_snd_def)
haftmann@33595
   317
qed
haftmann@33595
   318
haftmann@34151
   319
lemma iso_tuple_fst_update_accessor_eq_assist:
haftmann@34151
   320
  assumes "iso_tuple_update_accessor_eq_assist f g a u a' v"
wenzelm@35132
   321
  shows "iso_tuple_update_accessor_eq_assist
wenzelm@35132
   322
    (iso_tuple_fst_update isom o f) (g o iso_tuple_fst isom)
haftmann@34151
   323
    (iso_tuple_cons isom a b) u (iso_tuple_cons isom a' b) v"
haftmann@33595
   324
proof -
haftmann@33595
   325
  from assms have "f id = id"
wenzelm@35132
   326
    by (auto simp add: iso_tuple_update_accessor_eq_assist_def
wenzelm@35132
   327
      intro: iso_tuple_update_accessor_cong_assist_id)
wenzelm@35132
   328
  with assms show ?thesis
wenzelm@35132
   329
    by (clarsimp simp: iso_tuple_update_accessor_eq_assist_def
wenzelm@35132
   330
      iso_tuple_fst_update_def iso_tuple_fst_def
wenzelm@35132
   331
      iso_tuple_update_accessor_cong_assist_def iso_tuple_cons_def simps)
haftmann@33595
   332
qed
haftmann@33595
   333
haftmann@34151
   334
lemma iso_tuple_snd_update_accessor_eq_assist:
haftmann@34151
   335
  assumes "iso_tuple_update_accessor_eq_assist f g b u b' v"
wenzelm@35132
   336
  shows "iso_tuple_update_accessor_eq_assist
wenzelm@35132
   337
    (iso_tuple_snd_update isom o f) (g o iso_tuple_snd isom)
haftmann@34151
   338
    (iso_tuple_cons isom a b) u (iso_tuple_cons isom a b') v"
haftmann@33595
   339
proof -
haftmann@33595
   340
  from assms have "f id = id"
wenzelm@35132
   341
    by (auto simp add: iso_tuple_update_accessor_eq_assist_def
wenzelm@35132
   342
      intro: iso_tuple_update_accessor_cong_assist_id)
wenzelm@35132
   343
  with assms show ?thesis
wenzelm@35132
   344
    by (clarsimp simp: iso_tuple_update_accessor_eq_assist_def
wenzelm@35132
   345
      iso_tuple_snd_update_def iso_tuple_snd_def
wenzelm@35132
   346
      iso_tuple_update_accessor_cong_assist_def iso_tuple_cons_def simps)
haftmann@33595
   347
qed
haftmann@33595
   348
haftmann@34151
   349
lemma iso_tuple_cons_conj_eqI:
haftmann@33595
   350
  "a = c \<and> b = d \<and> P \<longleftrightarrow> Q \<Longrightarrow>
haftmann@34151
   351
    iso_tuple_cons isom a b = iso_tuple_cons isom c d \<and> P \<longleftrightarrow> Q"
haftmann@34151
   352
  by (clarsimp simp: iso_tuple_cons_def simps)
haftmann@33595
   353
haftmann@33595
   354
lemmas intros =
wenzelm@35132
   355
  iso_tuple_access_update_fst_fst
wenzelm@35132
   356
  iso_tuple_access_update_snd_snd
wenzelm@35132
   357
  iso_tuple_access_update_fst_snd
wenzelm@35132
   358
  iso_tuple_access_update_snd_fst
wenzelm@35132
   359
  iso_tuple_update_swap_fst_fst
wenzelm@35132
   360
  iso_tuple_update_swap_snd_snd
wenzelm@35132
   361
  iso_tuple_update_swap_fst_snd
wenzelm@35132
   362
  iso_tuple_update_swap_snd_fst
wenzelm@35132
   363
  iso_tuple_update_compose_fst_fst
wenzelm@35132
   364
  iso_tuple_update_compose_snd_snd
wenzelm@35132
   365
  iso_tuple_surjective_proof_assist_step
wenzelm@35132
   366
  iso_tuple_fst_update_accessor_eq_assist
wenzelm@35132
   367
  iso_tuple_snd_update_accessor_eq_assist
wenzelm@35132
   368
  iso_tuple_fst_update_accessor_cong_assist
wenzelm@35132
   369
  iso_tuple_snd_update_accessor_cong_assist
wenzelm@35132
   370
  iso_tuple_cons_conj_eqI
haftmann@33595
   371
haftmann@33595
   372
end
haftmann@33595
   373
haftmann@33595
   374
lemma isomorphic_tuple_intro:
haftmann@33595
   375
  fixes repr abst
haftmann@33595
   376
  assumes repr_inj: "\<And>x y. repr x = repr y \<longleftrightarrow> x = y"
wenzelm@35132
   377
    and abst_inv: "\<And>z. repr (abst z) = z"
wenzelm@35132
   378
    and v: "v \<equiv> Tuple_Isomorphism repr abst"
haftmann@33595
   379
  shows "isomorphic_tuple v"
haftmann@34151
   380
proof
wenzelm@35132
   381
  fix x have "repr (abst (repr x)) = repr x"
haftmann@34151
   382
    by (simp add: abst_inv)
wenzelm@35132
   383
  then show "Record.abst v (Record.repr v x) = x"
haftmann@34151
   384
    by (simp add: v repr_inj)
wenzelm@35132
   385
next
wenzelm@35132
   386
  fix y
wenzelm@35132
   387
  show "Record.repr v (Record.abst v y) = y"
haftmann@34151
   388
    by (simp add: v) (fact abst_inv)
haftmann@34151
   389
qed
haftmann@33595
   390
haftmann@33595
   391
definition
haftmann@34151
   392
  "tuple_iso_tuple \<equiv> Tuple_Isomorphism id id"
haftmann@33595
   393
haftmann@34151
   394
lemma tuple_iso_tuple:
haftmann@34151
   395
  "isomorphic_tuple tuple_iso_tuple"
haftmann@34151
   396
  by (simp add: isomorphic_tuple_intro [OF _ _ reflexive] tuple_iso_tuple_def)
haftmann@33595
   397
wenzelm@35132
   398
lemma refl_conj_eq: "Q = R \<Longrightarrow> P \<and> Q \<longleftrightarrow> P \<and> R"
haftmann@33595
   399
  by simp
haftmann@33595
   400
haftmann@34151
   401
lemma iso_tuple_UNIV_I: "x \<in> UNIV \<equiv> True"
haftmann@33595
   402
  by simp
haftmann@33595
   403
haftmann@34151
   404
lemma iso_tuple_True_simp: "(True \<Longrightarrow> PROP P) \<equiv> PROP P"
haftmann@33595
   405
  by simp
haftmann@33595
   406
schirmer@14700
   407
lemma prop_subst: "s = t \<Longrightarrow> PROP P t \<Longrightarrow> PROP P s"
schirmer@14700
   408
  by simp
wenzelm@11826
   409
wenzelm@35132
   410
lemma K_record_comp: "(\<lambda>x. c) \<circ> f = (\<lambda>x. c)"
schirmer@25705
   411
  by (simp add: comp_def)
wenzelm@11821
   412
wenzelm@35132
   413
lemma o_eq_dest_lhs: "a o b = c \<Longrightarrow> a (b v) = c v"
tsewell@32743
   414
  by clarsimp
tsewell@32743
   415
wenzelm@35132
   416
lemma o_eq_id_dest: "a o b = id o c \<Longrightarrow> a (b v) = c v"
tsewell@32743
   417
  by clarsimp
wenzelm@22817
   418
haftmann@33595
   419
wenzelm@11833
   420
subsection {* Concrete record syntax *}
wenzelm@4870
   421
wenzelm@4870
   422
nonterminals
wenzelm@35146
   423
  ident field_type field_types field fields field_update field_updates
wenzelm@4870
   424
syntax
wenzelm@11821
   425
  "_constify"           :: "id => ident"                        ("_")
wenzelm@11821
   426
  "_constify"           :: "longid => ident"                    ("_")
wenzelm@5198
   427
wenzelm@35144
   428
  "_field_type"         :: "ident => type => field_type"        ("(2_ ::/ _)")
wenzelm@11821
   429
  ""                    :: "field_type => field_types"          ("_")
wenzelm@35144
   430
  "_field_types"        :: "field_type => field_types => field_types"    ("_,/ _")
wenzelm@11821
   431
  "_record_type"        :: "field_types => type"                ("(3'(| _ |'))")
wenzelm@35144
   432
  "_record_type_scheme" :: "field_types => type => type"        ("(3'(| _,/ (2... ::/ _) |'))")
wenzelm@5198
   433
wenzelm@35144
   434
  "_field"              :: "ident => 'a => field"               ("(2_ =/ _)")
wenzelm@11821
   435
  ""                    :: "field => fields"                    ("_")
wenzelm@35144
   436
  "_fields"             :: "field => fields => fields"          ("_,/ _")
wenzelm@11821
   437
  "_record"             :: "fields => 'a"                       ("(3'(| _ |'))")
wenzelm@35144
   438
  "_record_scheme"      :: "fields => 'a => 'a"                 ("(3'(| _,/ (2... =/ _) |'))")
wenzelm@5198
   439
wenzelm@35146
   440
  "_field_update"       :: "ident => 'a => field_update"        ("(2_ :=/ _)")
wenzelm@35146
   441
  ""                    :: "field_update => field_updates"      ("_")
wenzelm@35146
   442
  "_field_updates"      :: "field_update => field_updates => field_updates"  ("_,/ _")
wenzelm@35146
   443
  "_record_update"      :: "'a => field_updates => 'b"          ("_/(3'(| _ |'))" [900, 0] 900)
wenzelm@4870
   444
wenzelm@10331
   445
syntax (xsymbols)
wenzelm@11821
   446
  "_record_type"        :: "field_types => type"                ("(3\<lparr>_\<rparr>)")
wenzelm@35132
   447
  "_record_type_scheme" :: "field_types => type => type"        ("(3\<lparr>_,/ (2\<dots> ::/ _)\<rparr>)")
wenzelm@35132
   448
  "_record"             :: "fields => 'a"                       ("(3\<lparr>_\<rparr>)")
wenzelm@35132
   449
  "_record_scheme"      :: "fields => 'a => 'a"                 ("(3\<lparr>_,/ (2\<dots> =/ _)\<rparr>)")
wenzelm@35146
   450
  "_record_update"      :: "'a => field_updates => 'b"          ("_/(3\<lparr>_\<rparr>)" [900, 0] 900)
wenzelm@9729
   451
tsewell@32752
   452
haftmann@33595
   453
subsection {* Record package *}
tsewell@32752
   454
tsewell@32744
   455
use "Tools/record.ML"
tsewell@32744
   456
setup Record.setup
wenzelm@10641
   457
wenzelm@36176
   458
hide_const (open) Tuple_Isomorphism repr abst iso_tuple_fst iso_tuple_snd
haftmann@34151
   459
  iso_tuple_fst_update iso_tuple_snd_update iso_tuple_cons
haftmann@34151
   460
  iso_tuple_surjective_proof_assist iso_tuple_update_accessor_cong_assist
haftmann@34151
   461
  iso_tuple_update_accessor_eq_assist tuple_iso_tuple
haftmann@33595
   462
wenzelm@4870
   463
end