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