src/HOL/String.thy
author paulson <lp15@cam.ac.uk>
Mon Feb 22 14:37:56 2016 +0000 (2016-02-22)
changeset 62379 340738057c8c
parent 62364 9209770bdcdf
child 62580 7011429f44f9
permissions -rw-r--r--
An assortment of useful lemmas about sums, norm, etc. Also: norm_conv_dist [symmetric] is now a simprule!
haftmann@31051
     1
(* Author: Tobias Nipkow, Florian Haftmann, TU Muenchen *)
haftmann@31051
     2
wenzelm@60758
     3
section \<open>Character and string types\<close>
haftmann@31051
     4
haftmann@31051
     5
theory String
blanchet@55969
     6
imports Enum
haftmann@31051
     7
begin
haftmann@31051
     8
haftmann@62364
     9
lemma upt_conv_Cons_Cons: -- \<open>no precondition\<close> -- \<open>FIXME move\<close>
haftmann@62364
    10
  "m # n # ns = [m..<q] \<longleftrightarrow> n # ns = [Suc m..<q]"
haftmann@62364
    11
proof (cases "m < q")
haftmann@62364
    12
  case False then show ?thesis by simp
haftmann@62364
    13
next
haftmann@62364
    14
  case True then show ?thesis by (simp add: upt_conv_Cons)
haftmann@62364
    15
qed
haftmann@62364
    16
haftmann@62364
    17
wenzelm@60758
    18
subsection \<open>Characters and strings\<close>
haftmann@31051
    19
haftmann@62364
    20
subsubsection \<open>Characters as finite algebraic type\<close>
haftmann@62364
    21
haftmann@62364
    22
typedef char = "{n::nat. n < 256}"
haftmann@62364
    23
  morphisms nat_of_char Abs_char
haftmann@62364
    24
proof
haftmann@62364
    25
  show "Suc 0 \<in> {n. n < 256}" by simp
haftmann@62364
    26
qed
haftmann@62364
    27
haftmann@62364
    28
definition char_of_nat :: "nat \<Rightarrow> char"
haftmann@62364
    29
where
haftmann@62364
    30
  "char_of_nat n = Abs_char (n mod 256)"
haftmann@62364
    31
haftmann@62364
    32
lemma char_cases [case_names char_of_nat, cases type: char]:
haftmann@62364
    33
  "(\<And>n. c = char_of_nat n \<Longrightarrow> n < 256 \<Longrightarrow> P) \<Longrightarrow> P"
haftmann@62364
    34
  by (cases c) (simp add: char_of_nat_def)
haftmann@62364
    35
haftmann@62364
    36
lemma char_of_nat_of_char [simp]:
haftmann@62364
    37
  "char_of_nat (nat_of_char c) = c"
haftmann@62364
    38
  by (cases c) (simp add: char_of_nat_def Abs_char_inject Abs_char_inverse)
haftmann@62364
    39
haftmann@62364
    40
lemma inj_nat_of_char:
haftmann@62364
    41
  "inj nat_of_char"
haftmann@62364
    42
proof (rule injI)
haftmann@62364
    43
  fix c d
haftmann@62364
    44
  assume "nat_of_char c = nat_of_char d"
haftmann@62364
    45
  then have "char_of_nat (nat_of_char c) = char_of_nat (nat_of_char d)"
haftmann@62364
    46
    by simp
haftmann@62364
    47
  then show "c = d"
haftmann@62364
    48
    by simp
haftmann@62364
    49
qed
haftmann@62364
    50
  
haftmann@62364
    51
lemma nat_of_char_eq_iff [simp]:
haftmann@62364
    52
  "nat_of_char c = nat_of_char d \<longleftrightarrow> c = d"
haftmann@62364
    53
  by (fact nat_of_char_inject)
haftmann@62364
    54
haftmann@62364
    55
lemma nat_of_char_of_nat [simp]:
haftmann@62364
    56
  "nat_of_char (char_of_nat n) = n mod 256"
haftmann@62364
    57
  by (cases "char_of_nat n") (simp add: char_of_nat_def Abs_char_inject Abs_char_inverse)
haftmann@62364
    58
haftmann@62364
    59
lemma char_of_nat_mod_256 [simp]:
haftmann@62364
    60
  "char_of_nat (n mod 256) = char_of_nat n"
haftmann@62364
    61
  by (cases "char_of_nat (n mod 256)") (simp add: char_of_nat_def)
haftmann@62364
    62
haftmann@62364
    63
lemma char_of_nat_quasi_inj [simp]:
haftmann@62364
    64
  "char_of_nat m = char_of_nat n \<longleftrightarrow> m mod 256 = n mod 256"
haftmann@62364
    65
  by (simp add: char_of_nat_def Abs_char_inject)
haftmann@62364
    66
haftmann@62364
    67
lemma inj_on_char_of_nat [simp]:
haftmann@62364
    68
  "inj_on char_of_nat {0..<256}"
haftmann@62364
    69
  by (rule inj_onI) simp
haftmann@62364
    70
haftmann@62364
    71
lemma nat_of_char_mod_256 [simp]:
haftmann@62364
    72
  "nat_of_char c mod 256 = nat_of_char c"
haftmann@62364
    73
  by (cases c) simp
haftmann@62364
    74
haftmann@62364
    75
lemma nat_of_char_less_256 [simp]:
haftmann@62364
    76
  "nat_of_char c < 256"
haftmann@62364
    77
proof -
haftmann@62364
    78
  have "nat_of_char c mod 256 < 256"
haftmann@62364
    79
    by arith
haftmann@62364
    80
  then show ?thesis by simp
haftmann@62364
    81
qed
haftmann@62364
    82
haftmann@62364
    83
lemma UNIV_char_of_nat:
haftmann@62364
    84
  "UNIV = char_of_nat ` {0..<256}"
haftmann@62364
    85
proof -
haftmann@62364
    86
  { fix c
haftmann@62364
    87
    have "c \<in> char_of_nat ` {0..<256}"
haftmann@62364
    88
      by (cases c) auto
haftmann@62364
    89
  } then show ?thesis by auto
haftmann@62364
    90
qed
haftmann@62364
    91
haftmann@62364
    92
haftmann@62364
    93
subsubsection \<open>Traditional concrete representation of characters\<close>
haftmann@62364
    94
blanchet@61348
    95
datatype (plugins del: transfer) nibble =
haftmann@31051
    96
    Nibble0 | Nibble1 | Nibble2 | Nibble3 | Nibble4 | Nibble5 | Nibble6 | Nibble7
haftmann@31051
    97
  | Nibble8 | Nibble9 | NibbleA | NibbleB | NibbleC | NibbleD | NibbleE | NibbleF
haftmann@31051
    98
haftmann@31051
    99
lemma UNIV_nibble:
haftmann@31051
   100
  "UNIV = {Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7,
haftmann@31051
   101
    Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF}" (is "_ = ?A")
haftmann@31051
   102
proof (rule UNIV_eq_I)
haftmann@31051
   103
  fix x show "x \<in> ?A" by (cases x) simp_all
haftmann@31051
   104
qed
haftmann@31051
   105
haftmann@49972
   106
lemma size_nibble [code, simp]:
blanchet@56846
   107
  "size_nibble (x::nibble) = 0"
blanchet@56846
   108
  "size (x::nibble) = 0"
blanchet@56846
   109
  by (cases x, simp_all)+
haftmann@49972
   110
haftmann@49972
   111
instantiation nibble :: enum
haftmann@49972
   112
begin
haftmann@49972
   113
haftmann@49972
   114
definition
haftmann@49972
   115
  "Enum.enum = [Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7,
haftmann@49972
   116
    Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF]"
haftmann@49972
   117
haftmann@49972
   118
definition
haftmann@49972
   119
  "Enum.enum_all P \<longleftrightarrow> P Nibble0 \<and> P Nibble1 \<and> P Nibble2 \<and> P Nibble3 \<and> P Nibble4 \<and> P Nibble5 \<and> P Nibble6 \<and> P Nibble7
haftmann@49972
   120
     \<and> P Nibble8 \<and> P Nibble9 \<and> P NibbleA \<and> P NibbleB \<and> P NibbleC \<and> P NibbleD \<and> P NibbleE \<and> P NibbleF"
haftmann@49972
   121
haftmann@49972
   122
definition
haftmann@49972
   123
  "Enum.enum_ex P \<longleftrightarrow> P Nibble0 \<or> P Nibble1 \<or> P Nibble2 \<or> P Nibble3 \<or> P Nibble4 \<or> P Nibble5 \<or> P Nibble6 \<or> P Nibble7
haftmann@49972
   124
     \<or> P Nibble8 \<or> P Nibble9 \<or> P NibbleA \<or> P NibbleB \<or> P NibbleC \<or> P NibbleD \<or> P NibbleE \<or> P NibbleF"
haftmann@49972
   125
haftmann@49972
   126
instance proof
haftmann@49972
   127
qed (simp_all only: enum_nibble_def enum_all_nibble_def enum_ex_nibble_def UNIV_nibble, simp_all)
haftmann@49972
   128
haftmann@49972
   129
end
haftmann@49972
   130
haftmann@49972
   131
lemma card_UNIV_nibble:
haftmann@49972
   132
  "card (UNIV :: nibble set) = 16"
haftmann@49972
   133
  by (simp add: card_UNIV_length_enum enum_nibble_def)
haftmann@31051
   134
haftmann@51160
   135
primrec nat_of_nibble :: "nibble \<Rightarrow> nat"
haftmann@51160
   136
where
haftmann@51160
   137
  "nat_of_nibble Nibble0 = 0"
haftmann@51160
   138
| "nat_of_nibble Nibble1 = 1"
haftmann@51160
   139
| "nat_of_nibble Nibble2 = 2"
haftmann@51160
   140
| "nat_of_nibble Nibble3 = 3"
haftmann@51160
   141
| "nat_of_nibble Nibble4 = 4"
haftmann@51160
   142
| "nat_of_nibble Nibble5 = 5"
haftmann@51160
   143
| "nat_of_nibble Nibble6 = 6"
haftmann@51160
   144
| "nat_of_nibble Nibble7 = 7"
haftmann@51160
   145
| "nat_of_nibble Nibble8 = 8"
haftmann@51160
   146
| "nat_of_nibble Nibble9 = 9"
haftmann@51160
   147
| "nat_of_nibble NibbleA = 10"
haftmann@51160
   148
| "nat_of_nibble NibbleB = 11"
haftmann@51160
   149
| "nat_of_nibble NibbleC = 12"
haftmann@51160
   150
| "nat_of_nibble NibbleD = 13"
haftmann@51160
   151
| "nat_of_nibble NibbleE = 14"
haftmann@51160
   152
| "nat_of_nibble NibbleF = 15"
haftmann@51160
   153
haftmann@51160
   154
definition nibble_of_nat :: "nat \<Rightarrow> nibble" where
haftmann@51160
   155
  "nibble_of_nat n = Enum.enum ! (n mod 16)"
haftmann@51160
   156
haftmann@51160
   157
lemma nibble_of_nat_simps [simp]:
haftmann@51160
   158
  "nibble_of_nat  0 = Nibble0"
haftmann@51160
   159
  "nibble_of_nat  1 = Nibble1"
haftmann@51160
   160
  "nibble_of_nat  2 = Nibble2"
haftmann@51160
   161
  "nibble_of_nat  3 = Nibble3"
haftmann@51160
   162
  "nibble_of_nat  4 = Nibble4"
haftmann@51160
   163
  "nibble_of_nat  5 = Nibble5"
haftmann@51160
   164
  "nibble_of_nat  6 = Nibble6"
haftmann@51160
   165
  "nibble_of_nat  7 = Nibble7"
haftmann@51160
   166
  "nibble_of_nat  8 = Nibble8"
haftmann@51160
   167
  "nibble_of_nat  9 = Nibble9"
haftmann@51160
   168
  "nibble_of_nat 10 = NibbleA"
haftmann@51160
   169
  "nibble_of_nat 11 = NibbleB"
haftmann@51160
   170
  "nibble_of_nat 12 = NibbleC"
haftmann@51160
   171
  "nibble_of_nat 13 = NibbleD"
haftmann@51160
   172
  "nibble_of_nat 14 = NibbleE"
haftmann@51160
   173
  "nibble_of_nat 15 = NibbleF"
haftmann@51160
   174
  unfolding nibble_of_nat_def by (simp_all add: enum_nibble_def)
haftmann@51160
   175
haftmann@51160
   176
lemma nibble_of_nat_of_nibble [simp]:
haftmann@51160
   177
  "nibble_of_nat (nat_of_nibble x) = x"
haftmann@51160
   178
  by (cases x) (simp_all add: nibble_of_nat_def enum_nibble_def)
haftmann@51160
   179
haftmann@51160
   180
lemma nat_of_nibble_of_nat [simp]:
haftmann@51160
   181
  "nat_of_nibble (nibble_of_nat n) = n mod 16"
haftmann@51160
   182
  by (cases "nibble_of_nat n")
haftmann@51160
   183
     (simp_all add: nibble_of_nat_def enum_nibble_def nth_equal_first_eq nth_non_equal_first_eq, arith)
haftmann@51160
   184
haftmann@51160
   185
lemma inj_nat_of_nibble:
haftmann@51160
   186
  "inj nat_of_nibble"
haftmann@51160
   187
  by (rule inj_on_inverseI) (rule nibble_of_nat_of_nibble)
haftmann@51160
   188
haftmann@51160
   189
lemma nat_of_nibble_eq_iff:
haftmann@51160
   190
  "nat_of_nibble x = nat_of_nibble y \<longleftrightarrow> x = y"
haftmann@51160
   191
  by (rule inj_eq) (rule inj_nat_of_nibble)
haftmann@51160
   192
haftmann@51160
   193
lemma nat_of_nibble_less_16:
haftmann@51160
   194
  "nat_of_nibble x < 16"
haftmann@51160
   195
  by (cases x) auto
haftmann@51160
   196
haftmann@51160
   197
lemma nibble_of_nat_mod_16:
haftmann@51160
   198
  "nibble_of_nat (n mod 16) = nibble_of_nat n"
haftmann@51160
   199
  by (simp add: nibble_of_nat_def)
haftmann@51160
   200
haftmann@62364
   201
context
haftmann@62364
   202
begin
haftmann@62364
   203
haftmann@62364
   204
local_setup \<open>Local_Theory.map_background_naming (Name_Space.add_path "char")\<close>
haftmann@62364
   205
haftmann@62364
   206
definition Char :: "nibble \<Rightarrow> nibble \<Rightarrow> char"
haftmann@62364
   207
where
haftmann@62364
   208
  "Char x y = char_of_nat (nat_of_nibble x * 16 + nat_of_nibble y)"
wenzelm@61799
   209
  \<comment> "Note: canonical order of character encoding coincides with standard term ordering"
haftmann@31051
   210
haftmann@62364
   211
end
haftmann@62364
   212
haftmann@62364
   213
lemma nat_of_char_Char:
haftmann@62364
   214
  "nat_of_char (Char x y) = nat_of_nibble x * 16 + nat_of_nibble y" (is "_ = ?rhs")
haftmann@62364
   215
proof -
haftmann@62364
   216
  have "?rhs < 256"
haftmann@62364
   217
    using nat_of_nibble_less_16 [of x] nat_of_nibble_less_16 [of y]
haftmann@62364
   218
    by arith
haftmann@62364
   219
  then show ?thesis by (simp add: Char_def)
haftmann@62364
   220
qed
haftmann@62364
   221
haftmann@62364
   222
lemma char_of_nat_Char_nibbles:
haftmann@62364
   223
  "char_of_nat n = Char (nibble_of_nat (n div 16)) (nibble_of_nat n)"
haftmann@62364
   224
proof -
haftmann@62364
   225
  from mod_mult2_eq [of n 16 16]
haftmann@62364
   226
  have "n mod 256 = 16 * (n div 16 mod 16) + n mod 16" by simp
haftmann@62364
   227
  then show ?thesis
haftmann@62364
   228
    by (simp add: Char_def)
haftmann@62364
   229
qed
haftmann@62364
   230
haftmann@62364
   231
lemma char_of_nat_nibble_pair [simp]:
haftmann@62364
   232
  "char_of_nat (nat_of_nibble a * 16 + nat_of_nibble b) = Char a b"
haftmann@62364
   233
  by (simp add: nat_of_char_Char [symmetric])
haftmann@62364
   234
haftmann@62364
   235
free_constructors char for Char
haftmann@62364
   236
proof -
haftmann@62364
   237
  fix P c
haftmann@62364
   238
  assume hyp: "\<And>x y. c = Char x y \<Longrightarrow> P"
haftmann@62364
   239
  have "nat_of_char c \<le> 255"
haftmann@62364
   240
    using nat_of_char_less_256 [of c] by arith
haftmann@62364
   241
  then have "nat_of_char c div 16 \<le> 255 div 16"
haftmann@62364
   242
    by (auto intro: div_le_mono2)
haftmann@62364
   243
  then have "nat_of_char c div 16 < 16"
haftmann@62364
   244
    by auto
haftmann@62364
   245
  then have "nat_of_char c div 16 mod 16 = nat_of_char c div 16"
haftmann@62364
   246
    by simp
haftmann@62364
   247
  then have "c = Char (nibble_of_nat (nat_of_char c div 16))
haftmann@62364
   248
    (nibble_of_nat (nat_of_char c mod 16))"
haftmann@62364
   249
    by (simp add: Char_def)
haftmann@62364
   250
  then show P by (rule hyp)
haftmann@62364
   251
next
haftmann@62364
   252
  fix x y z w
haftmann@62364
   253
  have "Char x y = Char z w
haftmann@62364
   254
    \<longleftrightarrow> nat_of_char (Char x y) = nat_of_char (Char z w)"
haftmann@62364
   255
    by auto
haftmann@62364
   256
  also have "\<dots> \<longleftrightarrow> nat_of_nibble x = nat_of_nibble z \<and> nat_of_nibble y = nat_of_nibble w" (is "?P \<longleftrightarrow> ?Q \<and> ?R")
haftmann@62364
   257
  proof
haftmann@62364
   258
    assume "?Q \<and> ?R"
haftmann@62364
   259
    then show ?P by (simp add: nat_of_char_Char)
haftmann@62364
   260
  next
haftmann@62364
   261
    assume ?P
haftmann@62364
   262
    then have ?Q
haftmann@62364
   263
      using nat_of_nibble_less_16 [of y] nat_of_nibble_less_16 [of w]
haftmann@62364
   264
      by (simp add: nat_of_char_Char)
haftmann@62364
   265
    moreover with \<open>?P\<close> have ?R by (simp add: nat_of_char_Char)
haftmann@62364
   266
    ultimately show "?Q \<and> ?R" ..
haftmann@62364
   267
  qed
haftmann@62364
   268
  also have "\<dots> \<longleftrightarrow> x = z \<and> y = w"
haftmann@62364
   269
    by (simp add: nat_of_nibble_eq_iff)
haftmann@62364
   270
  finally show "Char x y = Char z w \<longleftrightarrow> x = z \<and> y = w" .
haftmann@62364
   271
qed
haftmann@62364
   272
haftmann@31051
   273
syntax
wenzelm@46483
   274
  "_Char" :: "str_position => char"    ("CHR _")
haftmann@31051
   275
bulwahn@42163
   276
type_synonym string = "char list"
haftmann@31051
   277
haftmann@31051
   278
syntax
wenzelm@46483
   279
  "_String" :: "str_position => string"    ("_")
haftmann@31051
   280
wenzelm@48891
   281
ML_file "Tools/string_syntax.ML"
haftmann@31051
   282
haftmann@49972
   283
lemma UNIV_char:
haftmann@61032
   284
  "UNIV = image (case_prod Char) (UNIV \<times> UNIV)"
haftmann@49972
   285
proof (rule UNIV_eq_I)
haftmann@61032
   286
  fix x show "x \<in> image (case_prod Char) (UNIV \<times> UNIV)" by (cases x) auto
haftmann@49972
   287
qed
haftmann@49972
   288
haftmann@49972
   289
instantiation char :: enum
haftmann@49972
   290
begin
haftmann@49972
   291
haftmann@49972
   292
definition
haftmann@49972
   293
  "Enum.enum = [Char Nibble0 Nibble0, Char Nibble0 Nibble1, Char Nibble0 Nibble2,
haftmann@31484
   294
  Char Nibble0 Nibble3, Char Nibble0 Nibble4, Char Nibble0 Nibble5,
haftmann@31484
   295
  Char Nibble0 Nibble6, Char Nibble0 Nibble7, Char Nibble0 Nibble8,
wenzelm@55015
   296
  Char Nibble0 Nibble9, CHR ''\<newline>'', Char Nibble0 NibbleB,
haftmann@31484
   297
  Char Nibble0 NibbleC, Char Nibble0 NibbleD, Char Nibble0 NibbleE,
haftmann@31484
   298
  Char Nibble0 NibbleF, Char Nibble1 Nibble0, Char Nibble1 Nibble1,
haftmann@31484
   299
  Char Nibble1 Nibble2, Char Nibble1 Nibble3, Char Nibble1 Nibble4,
haftmann@31484
   300
  Char Nibble1 Nibble5, Char Nibble1 Nibble6, Char Nibble1 Nibble7,
haftmann@31484
   301
  Char Nibble1 Nibble8, Char Nibble1 Nibble9, Char Nibble1 NibbleA,
haftmann@31484
   302
  Char Nibble1 NibbleB, Char Nibble1 NibbleC, Char Nibble1 NibbleD,
haftmann@31484
   303
  Char Nibble1 NibbleE, Char Nibble1 NibbleF, CHR '' '', CHR ''!'',
haftmann@31484
   304
  Char Nibble2 Nibble2, CHR ''#'', CHR ''$'', CHR ''%'', CHR ''&'',
haftmann@31484
   305
  Char Nibble2 Nibble7, CHR ''('', CHR '')'', CHR ''*'', CHR ''+'', CHR '','',
haftmann@31484
   306
  CHR ''-'', CHR ''.'', CHR ''/'', CHR ''0'', CHR ''1'', CHR ''2'', CHR ''3'',
haftmann@31484
   307
  CHR ''4'', CHR ''5'', CHR ''6'', CHR ''7'', CHR ''8'', CHR ''9'', CHR '':'',
haftmann@31484
   308
  CHR '';'', CHR ''<'', CHR ''='', CHR ''>'', CHR ''?'', CHR ''@'', CHR ''A'',
haftmann@31484
   309
  CHR ''B'', CHR ''C'', CHR ''D'', CHR ''E'', CHR ''F'', CHR ''G'', CHR ''H'',
haftmann@31484
   310
  CHR ''I'', CHR ''J'', CHR ''K'', CHR ''L'', CHR ''M'', CHR ''N'', CHR ''O'',
haftmann@31484
   311
  CHR ''P'', CHR ''Q'', CHR ''R'', CHR ''S'', CHR ''T'', CHR ''U'', CHR ''V'',
haftmann@31484
   312
  CHR ''W'', CHR ''X'', CHR ''Y'', CHR ''Z'', CHR ''['', Char Nibble5 NibbleC,
haftmann@31484
   313
  CHR '']'', CHR ''^'', CHR ''_'', Char Nibble6 Nibble0, CHR ''a'', CHR ''b'',
haftmann@31484
   314
  CHR ''c'', CHR ''d'', CHR ''e'', CHR ''f'', CHR ''g'', CHR ''h'', CHR ''i'',
haftmann@31484
   315
  CHR ''j'', CHR ''k'', CHR ''l'', CHR ''m'', CHR ''n'', CHR ''o'', CHR ''p'',
haftmann@31484
   316
  CHR ''q'', CHR ''r'', CHR ''s'', CHR ''t'', CHR ''u'', CHR ''v'', CHR ''w'',
haftmann@31484
   317
  CHR ''x'', CHR ''y'', CHR ''z'', CHR ''{'', CHR ''|'', CHR ''}'', CHR ''~'',
haftmann@31484
   318
  Char Nibble7 NibbleF, Char Nibble8 Nibble0, Char Nibble8 Nibble1,
haftmann@31484
   319
  Char Nibble8 Nibble2, Char Nibble8 Nibble3, Char Nibble8 Nibble4,
haftmann@31484
   320
  Char Nibble8 Nibble5, Char Nibble8 Nibble6, Char Nibble8 Nibble7,
haftmann@31484
   321
  Char Nibble8 Nibble8, Char Nibble8 Nibble9, Char Nibble8 NibbleA,
haftmann@31484
   322
  Char Nibble8 NibbleB, Char Nibble8 NibbleC, Char Nibble8 NibbleD,
haftmann@31484
   323
  Char Nibble8 NibbleE, Char Nibble8 NibbleF, Char Nibble9 Nibble0,
haftmann@31484
   324
  Char Nibble9 Nibble1, Char Nibble9 Nibble2, Char Nibble9 Nibble3,
haftmann@31484
   325
  Char Nibble9 Nibble4, Char Nibble9 Nibble5, Char Nibble9 Nibble6,
haftmann@31484
   326
  Char Nibble9 Nibble7, Char Nibble9 Nibble8, Char Nibble9 Nibble9,
haftmann@31484
   327
  Char Nibble9 NibbleA, Char Nibble9 NibbleB, Char Nibble9 NibbleC,
haftmann@31484
   328
  Char Nibble9 NibbleD, Char Nibble9 NibbleE, Char Nibble9 NibbleF,
haftmann@31484
   329
  Char NibbleA Nibble0, Char NibbleA Nibble1, Char NibbleA Nibble2,
haftmann@31484
   330
  Char NibbleA Nibble3, Char NibbleA Nibble4, Char NibbleA Nibble5,
haftmann@31484
   331
  Char NibbleA Nibble6, Char NibbleA Nibble7, Char NibbleA Nibble8,
haftmann@31484
   332
  Char NibbleA Nibble9, Char NibbleA NibbleA, Char NibbleA NibbleB,
haftmann@31484
   333
  Char NibbleA NibbleC, Char NibbleA NibbleD, Char NibbleA NibbleE,
haftmann@31484
   334
  Char NibbleA NibbleF, Char NibbleB Nibble0, Char NibbleB Nibble1,
haftmann@31484
   335
  Char NibbleB Nibble2, Char NibbleB Nibble3, Char NibbleB Nibble4,
haftmann@31484
   336
  Char NibbleB Nibble5, Char NibbleB Nibble6, Char NibbleB Nibble7,
haftmann@31484
   337
  Char NibbleB Nibble8, Char NibbleB Nibble9, Char NibbleB NibbleA,
haftmann@31484
   338
  Char NibbleB NibbleB, Char NibbleB NibbleC, Char NibbleB NibbleD,
haftmann@31484
   339
  Char NibbleB NibbleE, Char NibbleB NibbleF, Char NibbleC Nibble0,
haftmann@31484
   340
  Char NibbleC Nibble1, Char NibbleC Nibble2, Char NibbleC Nibble3,
haftmann@31484
   341
  Char NibbleC Nibble4, Char NibbleC Nibble5, Char NibbleC Nibble6,
haftmann@31484
   342
  Char NibbleC Nibble7, Char NibbleC Nibble8, Char NibbleC Nibble9,
haftmann@31484
   343
  Char NibbleC NibbleA, Char NibbleC NibbleB, Char NibbleC NibbleC,
haftmann@31484
   344
  Char NibbleC NibbleD, Char NibbleC NibbleE, Char NibbleC NibbleF,
haftmann@31484
   345
  Char NibbleD Nibble0, Char NibbleD Nibble1, Char NibbleD Nibble2,
haftmann@31484
   346
  Char NibbleD Nibble3, Char NibbleD Nibble4, Char NibbleD Nibble5,
haftmann@31484
   347
  Char NibbleD Nibble6, Char NibbleD Nibble7, Char NibbleD Nibble8,
haftmann@31484
   348
  Char NibbleD Nibble9, Char NibbleD NibbleA, Char NibbleD NibbleB,
haftmann@31484
   349
  Char NibbleD NibbleC, Char NibbleD NibbleD, Char NibbleD NibbleE,
haftmann@31484
   350
  Char NibbleD NibbleF, Char NibbleE Nibble0, Char NibbleE Nibble1,
haftmann@31484
   351
  Char NibbleE Nibble2, Char NibbleE Nibble3, Char NibbleE Nibble4,
haftmann@31484
   352
  Char NibbleE Nibble5, Char NibbleE Nibble6, Char NibbleE Nibble7,
haftmann@31484
   353
  Char NibbleE Nibble8, Char NibbleE Nibble9, Char NibbleE NibbleA,
haftmann@31484
   354
  Char NibbleE NibbleB, Char NibbleE NibbleC, Char NibbleE NibbleD,
haftmann@31484
   355
  Char NibbleE NibbleE, Char NibbleE NibbleF, Char NibbleF Nibble0,
haftmann@31484
   356
  Char NibbleF Nibble1, Char NibbleF Nibble2, Char NibbleF Nibble3,
haftmann@31484
   357
  Char NibbleF Nibble4, Char NibbleF Nibble5, Char NibbleF Nibble6,
haftmann@31484
   358
  Char NibbleF Nibble7, Char NibbleF Nibble8, Char NibbleF Nibble9,
haftmann@31484
   359
  Char NibbleF NibbleA, Char NibbleF NibbleB, Char NibbleF NibbleC,
haftmann@31484
   360
  Char NibbleF NibbleD, Char NibbleF NibbleE, Char NibbleF NibbleF]"
haftmann@31484
   361
haftmann@49972
   362
definition
haftmann@49972
   363
  "Enum.enum_all P \<longleftrightarrow> list_all P (Enum.enum :: char list)"
haftmann@49972
   364
haftmann@49972
   365
definition
haftmann@49972
   366
  "Enum.enum_ex P \<longleftrightarrow> list_ex P (Enum.enum :: char list)"
haftmann@49972
   367
haftmann@51160
   368
lemma enum_char_product_enum_nibble:
haftmann@61032
   369
  "(Enum.enum :: char list) = map (case_prod Char) (List.product Enum.enum Enum.enum)"
haftmann@51160
   370
  by (simp add: enum_char_def enum_nibble_def)
haftmann@51160
   371
haftmann@49972
   372
instance proof
haftmann@49972
   373
  show UNIV: "UNIV = set (Enum.enum :: char list)"
nipkow@57247
   374
    by (simp add: enum_char_product_enum_nibble UNIV_char enum_UNIV)
haftmann@49972
   375
  show "distinct (Enum.enum :: char list)"
haftmann@51160
   376
    by (auto intro: inj_onI simp add: enum_char_product_enum_nibble distinct_map distinct_product enum_distinct)
haftmann@49972
   377
  show "\<And>P. Enum.enum_all P \<longleftrightarrow> Ball (UNIV :: char set) P"
haftmann@49972
   378
    by (simp add: UNIV enum_all_char_def list_all_iff)
haftmann@49972
   379
  show "\<And>P. Enum.enum_ex P \<longleftrightarrow> Bex (UNIV :: char set) P"
haftmann@49972
   380
    by (simp add: UNIV enum_ex_char_def list_ex_iff)
haftmann@49972
   381
qed
haftmann@49972
   382
haftmann@49972
   383
end
haftmann@49972
   384
haftmann@49972
   385
lemma card_UNIV_char:
haftmann@49972
   386
  "card (UNIV :: char set) = 256"
haftmann@49972
   387
  by (simp add: card_UNIV_length_enum enum_char_def)
haftmann@49948
   388
haftmann@62364
   389
lemma enum_char_unfold:
haftmann@62364
   390
  "Enum.enum = map char_of_nat [0..<256]"
haftmann@62364
   391
proof -
haftmann@62364
   392
  have *: "Suc (Suc 0) = 2" by simp
haftmann@62364
   393
  have "map nat_of_char Enum.enum = [0..<256]"
haftmann@62364
   394
    by (simp add: enum_char_def nat_of_char_Char upt_conv_Cons_Cons *)
haftmann@62364
   395
  then have "map char_of_nat (map nat_of_char Enum.enum) =
haftmann@62364
   396
    map char_of_nat [0..<256]" by simp
haftmann@62364
   397
  then show ?thesis by (simp add: comp_def)
haftmann@62364
   398
qed
haftmann@49972
   399
wenzelm@60758
   400
setup \<open>
haftmann@49972
   401
let
wenzelm@59631
   402
  val nibbles = map_range (Thm.cterm_of @{context} o HOLogic.mk_nibble) 16;
wenzelm@51717
   403
  val simpset =
wenzelm@51717
   404
    put_simpset HOL_ss @{context}
wenzelm@51717
   405
      addsimps @{thms nat_of_nibble.simps mult_0 mult_1 add_0 add_0_right arith_simps numeral_plus_one};
haftmann@51160
   406
  fun mk_code_eqn x y =
wenzelm@60801
   407
    Thm.instantiate' [] [SOME x, SOME y] @{thm nat_of_char_Char}
haftmann@51160
   408
    |> simplify simpset;
haftmann@51160
   409
  val code_eqns = map_product mk_code_eqn nibbles nibbles;
haftmann@49972
   410
in
haftmann@49972
   411
  Global_Theory.note_thmss ""
haftmann@51160
   412
    [((@{binding nat_of_char_simps}, []), [(code_eqns, [])])]
haftmann@51160
   413
  #> snd
haftmann@49972
   414
end
wenzelm@60758
   415
\<close>
haftmann@49972
   416
haftmann@51160
   417
declare nat_of_char_simps [code]
haftmann@51160
   418
haftmann@51160
   419
lemma nibble_of_nat_of_char_div_16:
haftmann@51160
   420
  "nibble_of_nat (nat_of_char c div 16) = (case c of Char x y \<Rightarrow> x)"
haftmann@51160
   421
  by (cases c)
haftmann@62364
   422
    (simp add: nat_of_char_Char add.commute nat_of_nibble_less_16)
haftmann@51160
   423
haftmann@51160
   424
lemma nibble_of_nat_nat_of_char:
haftmann@51160
   425
  "nibble_of_nat (nat_of_char c) = (case c of Char x y \<Rightarrow> y)"
haftmann@51160
   426
proof (cases c)
haftmann@51160
   427
  case (Char x y)
haftmann@51160
   428
  then have *: "nibble_of_nat ((nat_of_nibble y + nat_of_nibble x * 16) mod 16) = y"
haftmann@51160
   429
    by (simp add: nibble_of_nat_mod_16)
haftmann@51160
   430
  then have "nibble_of_nat (nat_of_nibble y + nat_of_nibble x * 16) = y"
haftmann@51160
   431
    by (simp only: nibble_of_nat_mod_16)
haftmann@62364
   432
  with Char show ?thesis by (simp add: nat_of_char_Char add.commute)
haftmann@51160
   433
qed
haftmann@51160
   434
wenzelm@61799
   435
code_datatype Char \<comment> \<open>drop case certificate for char\<close>
haftmann@51160
   436
blanchet@55416
   437
lemma case_char_code [code]:
haftmann@62364
   438
  "char f c = (let n = nat_of_char c in f (nibble_of_nat (n div 16)) (nibble_of_nat n))"
haftmann@51160
   439
  by (cases c)
blanchet@55642
   440
    (simp only: Let_def nibble_of_nat_of_char_div_16 nibble_of_nat_nat_of_char char.case)
haftmann@51160
   441
haftmann@62364
   442
lemma char_of_nat_enum [code]:
haftmann@51160
   443
  "char_of_nat n = Enum.enum ! (n mod 256)"
haftmann@62364
   444
  by (simp add: enum_char_unfold)
haftmann@49948
   445
haftmann@31051
   446
wenzelm@60758
   447
subsection \<open>Strings as dedicated type\<close>
bulwahn@39250
   448
wenzelm@49834
   449
typedef literal = "UNIV :: string set"
bulwahn@39250
   450
  morphisms explode STR ..
bulwahn@39250
   451
haftmann@59484
   452
setup_lifting type_definition_literal
haftmann@59484
   453
haftmann@59484
   454
lemma STR_inject' [simp]:
haftmann@59484
   455
  "STR s = STR t \<longleftrightarrow> s = t"
haftmann@59484
   456
  by transfer rule
Andreas@54594
   457
haftmann@57437
   458
definition implode :: "string \<Rightarrow> String.literal"
haftmann@57437
   459
where
haftmann@59484
   460
  [code del]: "implode = STR"
haftmann@59484
   461
  
bulwahn@39250
   462
instantiation literal :: size
bulwahn@39250
   463
begin
haftmann@31051
   464
bulwahn@39250
   465
definition size_literal :: "literal \<Rightarrow> nat"
bulwahn@39250
   466
where
wenzelm@61076
   467
  [code]: "size_literal (s::literal) = 0"
haftmann@31051
   468
bulwahn@39250
   469
instance ..
bulwahn@39250
   470
bulwahn@39250
   471
end
bulwahn@39250
   472
bulwahn@39250
   473
instantiation literal :: equal
bulwahn@39250
   474
begin
haftmann@31051
   475
Andreas@54594
   476
lift_definition equal_literal :: "literal \<Rightarrow> literal \<Rightarrow> bool" is "op =" .
haftmann@31051
   477
Andreas@54594
   478
instance by intro_classes (transfer, simp)
bulwahn@39250
   479
bulwahn@39250
   480
end
haftmann@31051
   481
Andreas@54594
   482
declare equal_literal.rep_eq[code]
Andreas@54594
   483
haftmann@52365
   484
lemma [code nbe]:
haftmann@52365
   485
  fixes s :: "String.literal"
haftmann@52365
   486
  shows "HOL.equal s s \<longleftrightarrow> True"
haftmann@52365
   487
  by (simp add: equal)
haftmann@52365
   488
Andreas@55426
   489
lifting_update literal.lifting
Andreas@55426
   490
lifting_forget literal.lifting
Andreas@55426
   491
wenzelm@60758
   492
subsection \<open>Code generator\<close>
haftmann@31051
   493
wenzelm@48891
   494
ML_file "Tools/string_code.ML"
haftmann@31051
   495
haftmann@33237
   496
code_reserved SML string
haftmann@33237
   497
code_reserved OCaml string
haftmann@34886
   498
code_reserved Scala string
haftmann@33237
   499
haftmann@52435
   500
code_printing
haftmann@52435
   501
  type_constructor literal \<rightharpoonup>
haftmann@52435
   502
    (SML) "string"
haftmann@52435
   503
    and (OCaml) "string"
haftmann@52435
   504
    and (Haskell) "String"
haftmann@52435
   505
    and (Scala) "String"
haftmann@31051
   506
wenzelm@60758
   507
setup \<open>
haftmann@34886
   508
  fold String_Code.add_literal_string ["SML", "OCaml", "Haskell", "Scala"]
wenzelm@60758
   509
\<close>
haftmann@31051
   510
haftmann@52435
   511
code_printing
haftmann@52435
   512
  class_instance literal :: equal \<rightharpoonup>
haftmann@52435
   513
    (Haskell) -
haftmann@52435
   514
| constant "HOL.equal :: literal \<Rightarrow> literal \<Rightarrow> bool" \<rightharpoonup>
haftmann@52435
   515
    (SML) "!((_ : string) = _)"
haftmann@52435
   516
    and (OCaml) "!((_ : string) = _)"
haftmann@52435
   517
    and (Haskell) infix 4 "=="
haftmann@52435
   518
    and (Scala) infixl 5 "=="
haftmann@31051
   519
wenzelm@60758
   520
setup \<open>Sign.map_naming (Name_Space.mandatory_path "Code")\<close>
Andreas@52910
   521
Andreas@52910
   522
definition abort :: "literal \<Rightarrow> (unit \<Rightarrow> 'a) \<Rightarrow> 'a"
Andreas@52910
   523
where [simp, code del]: "abort _ f = f ()"
Andreas@52910
   524
Andreas@54317
   525
lemma abort_cong: "msg = msg' ==> Code.abort msg f = Code.abort msg' f"
Andreas@54317
   526
by simp
Andreas@54317
   527
wenzelm@60758
   528
setup \<open>Sign.map_naming Name_Space.parent_path\<close>
Andreas@52910
   529
wenzelm@60758
   530
setup \<open>Code_Simp.map_ss (Simplifier.add_cong @{thm Code.abort_cong})\<close>
Andreas@54317
   531
Andreas@52910
   532
code_printing constant Code.abort \<rightharpoonup>
Andreas@52910
   533
    (SML) "!(raise/ Fail/ _)"
Andreas@52910
   534
    and (OCaml) "failwith"
haftmann@59483
   535
    and (Haskell) "!(error/ ::/ forall a./ String -> (() -> a) -> a)"
Andreas@52910
   536
    and (Scala) "!{/ sys.error((_));/  ((_)).apply(())/ }"
Andreas@52910
   537
wenzelm@36176
   538
hide_type (open) literal
haftmann@31205
   539
haftmann@57437
   540
hide_const (open) implode explode
haftmann@57437
   541
bulwahn@39250
   542
end