src/HOL/String.thy
author haftmann
Sun Jun 23 21:16:07 2013 +0200 (2013-06-23)
changeset 52435 6646bb548c6b
parent 52365 95186e6e4bf4
child 52910 7bfe0df532a9
permissions -rw-r--r--
migration from code_(const|type|class|instance) to code_printing and from code_module to code_identifier
haftmann@31051
     1
(* Author: Tobias Nipkow, Florian Haftmann, TU Muenchen *)
haftmann@31051
     2
haftmann@31051
     3
header {* Character and string types *}
haftmann@31051
     4
haftmann@31051
     5
theory String
haftmann@49972
     6
imports List Enum
haftmann@31051
     7
begin
haftmann@31051
     8
haftmann@49972
     9
subsection {* Characters and strings *}
haftmann@31051
    10
haftmann@31051
    11
datatype nibble =
haftmann@31051
    12
    Nibble0 | Nibble1 | Nibble2 | Nibble3 | Nibble4 | Nibble5 | Nibble6 | Nibble7
haftmann@31051
    13
  | Nibble8 | Nibble9 | NibbleA | NibbleB | NibbleC | NibbleD | NibbleE | NibbleF
haftmann@31051
    14
haftmann@31051
    15
lemma UNIV_nibble:
haftmann@31051
    16
  "UNIV = {Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7,
haftmann@31051
    17
    Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF}" (is "_ = ?A")
haftmann@31051
    18
proof (rule UNIV_eq_I)
haftmann@31051
    19
  fix x show "x \<in> ?A" by (cases x) simp_all
haftmann@31051
    20
qed
haftmann@31051
    21
haftmann@49972
    22
lemma size_nibble [code, simp]:
haftmann@49972
    23
  "size (x::nibble) = 0" by (cases x) simp_all
haftmann@49972
    24
haftmann@49972
    25
lemma nibble_size [code, simp]:
haftmann@49972
    26
  "nibble_size (x::nibble) = 0" by (cases x) simp_all
haftmann@49972
    27
haftmann@49972
    28
instantiation nibble :: enum
haftmann@49972
    29
begin
haftmann@49972
    30
haftmann@49972
    31
definition
haftmann@49972
    32
  "Enum.enum = [Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7,
haftmann@49972
    33
    Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF]"
haftmann@49972
    34
haftmann@49972
    35
definition
haftmann@49972
    36
  "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
    37
     \<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
    38
haftmann@49972
    39
definition
haftmann@49972
    40
  "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
    41
     \<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
    42
haftmann@49972
    43
instance proof
haftmann@49972
    44
qed (simp_all only: enum_nibble_def enum_all_nibble_def enum_ex_nibble_def UNIV_nibble, simp_all)
haftmann@49972
    45
haftmann@49972
    46
end
haftmann@49972
    47
haftmann@49972
    48
lemma card_UNIV_nibble:
haftmann@49972
    49
  "card (UNIV :: nibble set) = 16"
haftmann@49972
    50
  by (simp add: card_UNIV_length_enum enum_nibble_def)
haftmann@31051
    51
haftmann@51160
    52
primrec nat_of_nibble :: "nibble \<Rightarrow> nat"
haftmann@51160
    53
where
haftmann@51160
    54
  "nat_of_nibble Nibble0 = 0"
haftmann@51160
    55
| "nat_of_nibble Nibble1 = 1"
haftmann@51160
    56
| "nat_of_nibble Nibble2 = 2"
haftmann@51160
    57
| "nat_of_nibble Nibble3 = 3"
haftmann@51160
    58
| "nat_of_nibble Nibble4 = 4"
haftmann@51160
    59
| "nat_of_nibble Nibble5 = 5"
haftmann@51160
    60
| "nat_of_nibble Nibble6 = 6"
haftmann@51160
    61
| "nat_of_nibble Nibble7 = 7"
haftmann@51160
    62
| "nat_of_nibble Nibble8 = 8"
haftmann@51160
    63
| "nat_of_nibble Nibble9 = 9"
haftmann@51160
    64
| "nat_of_nibble NibbleA = 10"
haftmann@51160
    65
| "nat_of_nibble NibbleB = 11"
haftmann@51160
    66
| "nat_of_nibble NibbleC = 12"
haftmann@51160
    67
| "nat_of_nibble NibbleD = 13"
haftmann@51160
    68
| "nat_of_nibble NibbleE = 14"
haftmann@51160
    69
| "nat_of_nibble NibbleF = 15"
haftmann@51160
    70
haftmann@51160
    71
definition nibble_of_nat :: "nat \<Rightarrow> nibble" where
haftmann@51160
    72
  "nibble_of_nat n = Enum.enum ! (n mod 16)"
haftmann@51160
    73
haftmann@51160
    74
lemma nibble_of_nat_simps [simp]:
haftmann@51160
    75
  "nibble_of_nat  0 = Nibble0"
haftmann@51160
    76
  "nibble_of_nat  1 = Nibble1"
haftmann@51160
    77
  "nibble_of_nat  2 = Nibble2"
haftmann@51160
    78
  "nibble_of_nat  3 = Nibble3"
haftmann@51160
    79
  "nibble_of_nat  4 = Nibble4"
haftmann@51160
    80
  "nibble_of_nat  5 = Nibble5"
haftmann@51160
    81
  "nibble_of_nat  6 = Nibble6"
haftmann@51160
    82
  "nibble_of_nat  7 = Nibble7"
haftmann@51160
    83
  "nibble_of_nat  8 = Nibble8"
haftmann@51160
    84
  "nibble_of_nat  9 = Nibble9"
haftmann@51160
    85
  "nibble_of_nat 10 = NibbleA"
haftmann@51160
    86
  "nibble_of_nat 11 = NibbleB"
haftmann@51160
    87
  "nibble_of_nat 12 = NibbleC"
haftmann@51160
    88
  "nibble_of_nat 13 = NibbleD"
haftmann@51160
    89
  "nibble_of_nat 14 = NibbleE"
haftmann@51160
    90
  "nibble_of_nat 15 = NibbleF"
haftmann@51160
    91
  unfolding nibble_of_nat_def by (simp_all add: enum_nibble_def)
haftmann@51160
    92
haftmann@51160
    93
lemma nibble_of_nat_of_nibble [simp]:
haftmann@51160
    94
  "nibble_of_nat (nat_of_nibble x) = x"
haftmann@51160
    95
  by (cases x) (simp_all add: nibble_of_nat_def enum_nibble_def)
haftmann@51160
    96
haftmann@51160
    97
lemma nat_of_nibble_of_nat [simp]:
haftmann@51160
    98
  "nat_of_nibble (nibble_of_nat n) = n mod 16"
haftmann@51160
    99
  by (cases "nibble_of_nat n")
haftmann@51160
   100
     (simp_all add: nibble_of_nat_def enum_nibble_def nth_equal_first_eq nth_non_equal_first_eq, arith)
haftmann@51160
   101
haftmann@51160
   102
lemma inj_nat_of_nibble:
haftmann@51160
   103
  "inj nat_of_nibble"
haftmann@51160
   104
  by (rule inj_on_inverseI) (rule nibble_of_nat_of_nibble)
haftmann@51160
   105
haftmann@51160
   106
lemma nat_of_nibble_eq_iff:
haftmann@51160
   107
  "nat_of_nibble x = nat_of_nibble y \<longleftrightarrow> x = y"
haftmann@51160
   108
  by (rule inj_eq) (rule inj_nat_of_nibble)
haftmann@51160
   109
haftmann@51160
   110
lemma nat_of_nibble_less_16:
haftmann@51160
   111
  "nat_of_nibble x < 16"
haftmann@51160
   112
  by (cases x) auto
haftmann@51160
   113
haftmann@51160
   114
lemma nibble_of_nat_mod_16:
haftmann@51160
   115
  "nibble_of_nat (n mod 16) = nibble_of_nat n"
haftmann@51160
   116
  by (simp add: nibble_of_nat_def)
haftmann@51160
   117
haftmann@31051
   118
datatype char = Char nibble nibble
haftmann@31051
   119
  -- "Note: canonical order of character encoding coincides with standard term ordering"
haftmann@31051
   120
haftmann@31051
   121
syntax
wenzelm@46483
   122
  "_Char" :: "str_position => char"    ("CHR _")
haftmann@31051
   123
bulwahn@42163
   124
type_synonym string = "char list"
haftmann@31051
   125
haftmann@31051
   126
syntax
wenzelm@46483
   127
  "_String" :: "str_position => string"    ("_")
haftmann@31051
   128
wenzelm@48891
   129
ML_file "Tools/string_syntax.ML"
wenzelm@35123
   130
setup String_Syntax.setup
haftmann@31051
   131
haftmann@49972
   132
lemma UNIV_char:
haftmann@49972
   133
  "UNIV = image (split Char) (UNIV \<times> UNIV)"
haftmann@49972
   134
proof (rule UNIV_eq_I)
haftmann@49972
   135
  fix x show "x \<in> image (split Char) (UNIV \<times> UNIV)" by (cases x) auto
haftmann@49972
   136
qed
haftmann@49972
   137
haftmann@49972
   138
lemma size_char [code, simp]:
haftmann@49972
   139
  "size (c::char) = 0" by (cases c) simp
haftmann@49972
   140
haftmann@49972
   141
lemma char_size [code, simp]:
haftmann@49972
   142
  "char_size (c::char) = 0" by (cases c) simp
haftmann@49972
   143
haftmann@49972
   144
instantiation char :: enum
haftmann@49972
   145
begin
haftmann@49972
   146
haftmann@49972
   147
definition
haftmann@49972
   148
  "Enum.enum = [Char Nibble0 Nibble0, Char Nibble0 Nibble1, Char Nibble0 Nibble2,
haftmann@31484
   149
  Char Nibble0 Nibble3, Char Nibble0 Nibble4, Char Nibble0 Nibble5,
haftmann@31484
   150
  Char Nibble0 Nibble6, Char Nibble0 Nibble7, Char Nibble0 Nibble8,
haftmann@31484
   151
  Char Nibble0 Nibble9, Char Nibble0 NibbleA, Char Nibble0 NibbleB,
haftmann@31484
   152
  Char Nibble0 NibbleC, Char Nibble0 NibbleD, Char Nibble0 NibbleE,
haftmann@31484
   153
  Char Nibble0 NibbleF, Char Nibble1 Nibble0, Char Nibble1 Nibble1,
haftmann@31484
   154
  Char Nibble1 Nibble2, Char Nibble1 Nibble3, Char Nibble1 Nibble4,
haftmann@31484
   155
  Char Nibble1 Nibble5, Char Nibble1 Nibble6, Char Nibble1 Nibble7,
haftmann@31484
   156
  Char Nibble1 Nibble8, Char Nibble1 Nibble9, Char Nibble1 NibbleA,
haftmann@31484
   157
  Char Nibble1 NibbleB, Char Nibble1 NibbleC, Char Nibble1 NibbleD,
haftmann@31484
   158
  Char Nibble1 NibbleE, Char Nibble1 NibbleF, CHR '' '', CHR ''!'',
haftmann@31484
   159
  Char Nibble2 Nibble2, CHR ''#'', CHR ''$'', CHR ''%'', CHR ''&'',
haftmann@31484
   160
  Char Nibble2 Nibble7, CHR ''('', CHR '')'', CHR ''*'', CHR ''+'', CHR '','',
haftmann@31484
   161
  CHR ''-'', CHR ''.'', CHR ''/'', CHR ''0'', CHR ''1'', CHR ''2'', CHR ''3'',
haftmann@31484
   162
  CHR ''4'', CHR ''5'', CHR ''6'', CHR ''7'', CHR ''8'', CHR ''9'', CHR '':'',
haftmann@31484
   163
  CHR '';'', CHR ''<'', CHR ''='', CHR ''>'', CHR ''?'', CHR ''@'', CHR ''A'',
haftmann@31484
   164
  CHR ''B'', CHR ''C'', CHR ''D'', CHR ''E'', CHR ''F'', CHR ''G'', CHR ''H'',
haftmann@31484
   165
  CHR ''I'', CHR ''J'', CHR ''K'', CHR ''L'', CHR ''M'', CHR ''N'', CHR ''O'',
haftmann@31484
   166
  CHR ''P'', CHR ''Q'', CHR ''R'', CHR ''S'', CHR ''T'', CHR ''U'', CHR ''V'',
haftmann@31484
   167
  CHR ''W'', CHR ''X'', CHR ''Y'', CHR ''Z'', CHR ''['', Char Nibble5 NibbleC,
haftmann@31484
   168
  CHR '']'', CHR ''^'', CHR ''_'', Char Nibble6 Nibble0, CHR ''a'', CHR ''b'',
haftmann@31484
   169
  CHR ''c'', CHR ''d'', CHR ''e'', CHR ''f'', CHR ''g'', CHR ''h'', CHR ''i'',
haftmann@31484
   170
  CHR ''j'', CHR ''k'', CHR ''l'', CHR ''m'', CHR ''n'', CHR ''o'', CHR ''p'',
haftmann@31484
   171
  CHR ''q'', CHR ''r'', CHR ''s'', CHR ''t'', CHR ''u'', CHR ''v'', CHR ''w'',
haftmann@31484
   172
  CHR ''x'', CHR ''y'', CHR ''z'', CHR ''{'', CHR ''|'', CHR ''}'', CHR ''~'',
haftmann@31484
   173
  Char Nibble7 NibbleF, Char Nibble8 Nibble0, Char Nibble8 Nibble1,
haftmann@31484
   174
  Char Nibble8 Nibble2, Char Nibble8 Nibble3, Char Nibble8 Nibble4,
haftmann@31484
   175
  Char Nibble8 Nibble5, Char Nibble8 Nibble6, Char Nibble8 Nibble7,
haftmann@31484
   176
  Char Nibble8 Nibble8, Char Nibble8 Nibble9, Char Nibble8 NibbleA,
haftmann@31484
   177
  Char Nibble8 NibbleB, Char Nibble8 NibbleC, Char Nibble8 NibbleD,
haftmann@31484
   178
  Char Nibble8 NibbleE, Char Nibble8 NibbleF, Char Nibble9 Nibble0,
haftmann@31484
   179
  Char Nibble9 Nibble1, Char Nibble9 Nibble2, Char Nibble9 Nibble3,
haftmann@31484
   180
  Char Nibble9 Nibble4, Char Nibble9 Nibble5, Char Nibble9 Nibble6,
haftmann@31484
   181
  Char Nibble9 Nibble7, Char Nibble9 Nibble8, Char Nibble9 Nibble9,
haftmann@31484
   182
  Char Nibble9 NibbleA, Char Nibble9 NibbleB, Char Nibble9 NibbleC,
haftmann@31484
   183
  Char Nibble9 NibbleD, Char Nibble9 NibbleE, Char Nibble9 NibbleF,
haftmann@31484
   184
  Char NibbleA Nibble0, Char NibbleA Nibble1, Char NibbleA Nibble2,
haftmann@31484
   185
  Char NibbleA Nibble3, Char NibbleA Nibble4, Char NibbleA Nibble5,
haftmann@31484
   186
  Char NibbleA Nibble6, Char NibbleA Nibble7, Char NibbleA Nibble8,
haftmann@31484
   187
  Char NibbleA Nibble9, Char NibbleA NibbleA, Char NibbleA NibbleB,
haftmann@31484
   188
  Char NibbleA NibbleC, Char NibbleA NibbleD, Char NibbleA NibbleE,
haftmann@31484
   189
  Char NibbleA NibbleF, Char NibbleB Nibble0, Char NibbleB Nibble1,
haftmann@31484
   190
  Char NibbleB Nibble2, Char NibbleB Nibble3, Char NibbleB Nibble4,
haftmann@31484
   191
  Char NibbleB Nibble5, Char NibbleB Nibble6, Char NibbleB Nibble7,
haftmann@31484
   192
  Char NibbleB Nibble8, Char NibbleB Nibble9, Char NibbleB NibbleA,
haftmann@31484
   193
  Char NibbleB NibbleB, Char NibbleB NibbleC, Char NibbleB NibbleD,
haftmann@31484
   194
  Char NibbleB NibbleE, Char NibbleB NibbleF, Char NibbleC Nibble0,
haftmann@31484
   195
  Char NibbleC Nibble1, Char NibbleC Nibble2, Char NibbleC Nibble3,
haftmann@31484
   196
  Char NibbleC Nibble4, Char NibbleC Nibble5, Char NibbleC Nibble6,
haftmann@31484
   197
  Char NibbleC Nibble7, Char NibbleC Nibble8, Char NibbleC Nibble9,
haftmann@31484
   198
  Char NibbleC NibbleA, Char NibbleC NibbleB, Char NibbleC NibbleC,
haftmann@31484
   199
  Char NibbleC NibbleD, Char NibbleC NibbleE, Char NibbleC NibbleF,
haftmann@31484
   200
  Char NibbleD Nibble0, Char NibbleD Nibble1, Char NibbleD Nibble2,
haftmann@31484
   201
  Char NibbleD Nibble3, Char NibbleD Nibble4, Char NibbleD Nibble5,
haftmann@31484
   202
  Char NibbleD Nibble6, Char NibbleD Nibble7, Char NibbleD Nibble8,
haftmann@31484
   203
  Char NibbleD Nibble9, Char NibbleD NibbleA, Char NibbleD NibbleB,
haftmann@31484
   204
  Char NibbleD NibbleC, Char NibbleD NibbleD, Char NibbleD NibbleE,
haftmann@31484
   205
  Char NibbleD NibbleF, Char NibbleE Nibble0, Char NibbleE Nibble1,
haftmann@31484
   206
  Char NibbleE Nibble2, Char NibbleE Nibble3, Char NibbleE Nibble4,
haftmann@31484
   207
  Char NibbleE Nibble5, Char NibbleE Nibble6, Char NibbleE Nibble7,
haftmann@31484
   208
  Char NibbleE Nibble8, Char NibbleE Nibble9, Char NibbleE NibbleA,
haftmann@31484
   209
  Char NibbleE NibbleB, Char NibbleE NibbleC, Char NibbleE NibbleD,
haftmann@31484
   210
  Char NibbleE NibbleE, Char NibbleE NibbleF, Char NibbleF Nibble0,
haftmann@31484
   211
  Char NibbleF Nibble1, Char NibbleF Nibble2, Char NibbleF Nibble3,
haftmann@31484
   212
  Char NibbleF Nibble4, Char NibbleF Nibble5, Char NibbleF Nibble6,
haftmann@31484
   213
  Char NibbleF Nibble7, Char NibbleF Nibble8, Char NibbleF Nibble9,
haftmann@31484
   214
  Char NibbleF NibbleA, Char NibbleF NibbleB, Char NibbleF NibbleC,
haftmann@31484
   215
  Char NibbleF NibbleD, Char NibbleF NibbleE, Char NibbleF NibbleF]"
haftmann@31484
   216
haftmann@49972
   217
definition
haftmann@49972
   218
  "Enum.enum_all P \<longleftrightarrow> list_all P (Enum.enum :: char list)"
haftmann@49972
   219
haftmann@49972
   220
definition
haftmann@49972
   221
  "Enum.enum_ex P \<longleftrightarrow> list_ex P (Enum.enum :: char list)"
haftmann@49972
   222
haftmann@51160
   223
lemma enum_char_product_enum_nibble:
haftmann@51160
   224
  "(Enum.enum :: char list) = map (split Char) (List.product Enum.enum Enum.enum)"
haftmann@51160
   225
  by (simp add: enum_char_def enum_nibble_def)
haftmann@51160
   226
haftmann@49972
   227
instance proof
haftmann@49972
   228
  show UNIV: "UNIV = set (Enum.enum :: char list)"
haftmann@51160
   229
    by (simp add: enum_char_product_enum_nibble UNIV_char product_list_set enum_UNIV)
haftmann@49972
   230
  show "distinct (Enum.enum :: char list)"
haftmann@51160
   231
    by (auto intro: inj_onI simp add: enum_char_product_enum_nibble distinct_map distinct_product enum_distinct)
haftmann@49972
   232
  show "\<And>P. Enum.enum_all P \<longleftrightarrow> Ball (UNIV :: char set) P"
haftmann@49972
   233
    by (simp add: UNIV enum_all_char_def list_all_iff)
haftmann@49972
   234
  show "\<And>P. Enum.enum_ex P \<longleftrightarrow> Bex (UNIV :: char set) P"
haftmann@49972
   235
    by (simp add: UNIV enum_ex_char_def list_ex_iff)
haftmann@49972
   236
qed
haftmann@49972
   237
haftmann@49972
   238
end
haftmann@49972
   239
haftmann@49972
   240
lemma card_UNIV_char:
haftmann@49972
   241
  "card (UNIV :: char set) = 256"
haftmann@49972
   242
  by (simp add: card_UNIV_length_enum enum_char_def)
haftmann@49948
   243
haftmann@51160
   244
definition nat_of_char :: "char \<Rightarrow> nat"
haftmann@51160
   245
where
haftmann@51160
   246
  "nat_of_char c = (case c of Char x y \<Rightarrow> nat_of_nibble x * 16 + nat_of_nibble y)"
haftmann@51160
   247
haftmann@51160
   248
lemma nat_of_char_Char:
haftmann@51160
   249
  "nat_of_char (Char x y) = nat_of_nibble x * 16 + nat_of_nibble y"
haftmann@51160
   250
  by (simp add: nat_of_char_def)
haftmann@49972
   251
haftmann@49972
   252
setup {*
haftmann@49972
   253
let
haftmann@49972
   254
  val nibbles = map_range (Thm.cterm_of @{theory} o HOLogic.mk_nibble) 16;
wenzelm@51717
   255
  val simpset =
wenzelm@51717
   256
    put_simpset HOL_ss @{context}
wenzelm@51717
   257
      addsimps @{thms nat_of_nibble.simps mult_0 mult_1 add_0 add_0_right arith_simps numeral_plus_one};
haftmann@51160
   258
  fun mk_code_eqn x y =
haftmann@51160
   259
    Drule.instantiate' [] [SOME x, SOME y] @{thm nat_of_char_Char}
haftmann@51160
   260
    |> simplify simpset;
haftmann@51160
   261
  val code_eqns = map_product mk_code_eqn nibbles nibbles;
haftmann@49972
   262
in
haftmann@49972
   263
  Global_Theory.note_thmss ""
haftmann@51160
   264
    [((@{binding nat_of_char_simps}, []), [(code_eqns, [])])]
haftmann@51160
   265
  #> snd
haftmann@49972
   266
end
haftmann@49972
   267
*}
haftmann@49972
   268
haftmann@51160
   269
declare nat_of_char_simps [code]
haftmann@51160
   270
haftmann@51160
   271
lemma nibble_of_nat_of_char_div_16:
haftmann@51160
   272
  "nibble_of_nat (nat_of_char c div 16) = (case c of Char x y \<Rightarrow> x)"
haftmann@51160
   273
  by (cases c)
haftmann@51160
   274
    (simp add: nat_of_char_def add_commute nat_of_nibble_less_16)
haftmann@51160
   275
haftmann@51160
   276
lemma nibble_of_nat_nat_of_char:
haftmann@51160
   277
  "nibble_of_nat (nat_of_char c) = (case c of Char x y \<Rightarrow> y)"
haftmann@51160
   278
proof (cases c)
haftmann@51160
   279
  case (Char x y)
haftmann@51160
   280
  then have *: "nibble_of_nat ((nat_of_nibble y + nat_of_nibble x * 16) mod 16) = y"
haftmann@51160
   281
    by (simp add: nibble_of_nat_mod_16)
haftmann@51160
   282
  then have "nibble_of_nat (nat_of_nibble y + nat_of_nibble x * 16) = y"
haftmann@51160
   283
    by (simp only: nibble_of_nat_mod_16)
haftmann@51160
   284
  with Char show ?thesis by (simp add: nat_of_char_def add_commute)
haftmann@51160
   285
qed
haftmann@51160
   286
haftmann@51160
   287
code_datatype Char -- {* drop case certificate for char *}
haftmann@51160
   288
haftmann@51160
   289
lemma char_case_code [code]:
haftmann@51160
   290
  "char_case f c = (let n = nat_of_char c in f (nibble_of_nat (n div 16)) (nibble_of_nat n))"
haftmann@51160
   291
  by (cases c)
haftmann@51160
   292
    (simp only: Let_def nibble_of_nat_of_char_div_16 nibble_of_nat_nat_of_char char.cases)
haftmann@51160
   293
haftmann@51160
   294
lemma [code]:
haftmann@51160
   295
  "char_rec = char_case"
haftmann@49972
   296
  by (simp add: fun_eq_iff split: char.split)
haftmann@49972
   297
haftmann@51160
   298
definition char_of_nat :: "nat \<Rightarrow> char" where
haftmann@51160
   299
  "char_of_nat n = Enum.enum ! (n mod 256)"
haftmann@51160
   300
haftmann@51160
   301
lemma char_of_nat_Char_nibbles:
haftmann@51160
   302
  "char_of_nat n = Char (nibble_of_nat (n div 16)) (nibble_of_nat n)"
haftmann@51160
   303
proof -
haftmann@51160
   304
  from mod_mult2_eq [of n 16 16]
haftmann@51160
   305
  have "n mod 256 = 16 * (n div 16 mod 16) + n mod 16" by simp
haftmann@51160
   306
  then show ?thesis
haftmann@51160
   307
    by (simp add: char_of_nat_def enum_char_product_enum_nibble card_UNIV_nibble
haftmann@51160
   308
      card_UNIV_length_enum [symmetric] nibble_of_nat_def product_nth add_commute)
haftmann@51160
   309
qed
haftmann@51160
   310
haftmann@51160
   311
lemma char_of_nat_of_char [simp]:
haftmann@51160
   312
  "char_of_nat (nat_of_char c) = c"
haftmann@51160
   313
  by (cases c)
haftmann@51160
   314
    (simp add: char_of_nat_Char_nibbles nibble_of_nat_of_char_div_16 nibble_of_nat_nat_of_char)
haftmann@51160
   315
haftmann@51160
   316
lemma nat_of_char_of_nat [simp]:
haftmann@51160
   317
  "nat_of_char (char_of_nat n) = n mod 256"
haftmann@51160
   318
proof -
haftmann@51160
   319
  have "n mod 256 = n mod (16 * 16)" by simp
haftmann@51160
   320
  then have "n div 16 mod 16 * 16 + n mod 16 = n mod 256" by (simp only: mod_mult2_eq)
haftmann@51160
   321
  then show ?thesis
haftmann@51160
   322
    by (cases "char_of_nat n") (auto simp add: nat_of_char_def char_of_nat_Char_nibbles)
haftmann@51160
   323
qed
haftmann@51160
   324
haftmann@51160
   325
lemma inj_nat_of_char:
haftmann@51160
   326
  "inj nat_of_char"
haftmann@51160
   327
  by (rule inj_on_inverseI) (rule char_of_nat_of_char)
haftmann@51160
   328
haftmann@51160
   329
lemma nat_of_char_eq_iff:
haftmann@51160
   330
  "nat_of_char c = nat_of_char d \<longleftrightarrow> c = d"
haftmann@51160
   331
  by (rule inj_eq) (rule inj_nat_of_char)
haftmann@51160
   332
haftmann@51160
   333
lemma nat_of_char_less_256:
haftmann@51160
   334
  "nat_of_char c < 256"
haftmann@51160
   335
proof (cases c)
haftmann@51160
   336
  case (Char x y)
haftmann@51160
   337
  with nat_of_nibble_less_16 [of x] nat_of_nibble_less_16 [of y]
haftmann@51160
   338
  show ?thesis by (simp add: nat_of_char_def)
haftmann@51160
   339
qed
haftmann@51160
   340
haftmann@51160
   341
lemma char_of_nat_mod_256:
haftmann@51160
   342
  "char_of_nat (n mod 256) = char_of_nat n"
haftmann@51160
   343
proof -
haftmann@51160
   344
  from nibble_of_nat_mod_16 [of "n mod 256"]
haftmann@51160
   345
  have "nibble_of_nat (n mod 256) = nibble_of_nat (n mod 256 mod 16)" by simp
haftmann@51160
   346
  with nibble_of_nat_mod_16 [of n]
haftmann@51160
   347
  have *: "nibble_of_nat (n mod 256) = nibble_of_nat n" by (simp add: mod_mod_cancel)
haftmann@51160
   348
  have "n mod 256 = n mod (16 * 16)" by simp
haftmann@51160
   349
  then have **: "n mod 256 = n div 16 mod 16 * 16 + n mod 16" by (simp only: mod_mult2_eq)
haftmann@51160
   350
  show ?thesis
haftmann@51160
   351
    by (simp add: char_of_nat_Char_nibbles *)
haftmann@51160
   352
     (simp add: div_add1_eq nibble_of_nat_mod_16 [of "n div 16"] **)
haftmann@51160
   353
qed
haftmann@49948
   354
haftmann@31051
   355
bulwahn@39250
   356
subsection {* Strings as dedicated type *}
bulwahn@39250
   357
wenzelm@49834
   358
typedef literal = "UNIV :: string set"
bulwahn@39250
   359
  morphisms explode STR ..
bulwahn@39250
   360
bulwahn@39250
   361
instantiation literal :: size
bulwahn@39250
   362
begin
haftmann@31051
   363
bulwahn@39250
   364
definition size_literal :: "literal \<Rightarrow> nat"
bulwahn@39250
   365
where
bulwahn@39250
   366
  [code]: "size_literal (s\<Colon>literal) = 0"
haftmann@31051
   367
bulwahn@39250
   368
instance ..
bulwahn@39250
   369
bulwahn@39250
   370
end
bulwahn@39250
   371
bulwahn@39250
   372
instantiation literal :: equal
bulwahn@39250
   373
begin
haftmann@31051
   374
bulwahn@39250
   375
definition equal_literal :: "literal \<Rightarrow> literal \<Rightarrow> bool"
bulwahn@39250
   376
where
bulwahn@39250
   377
  "equal_literal s1 s2 \<longleftrightarrow> explode s1 = explode s2"
haftmann@31051
   378
bulwahn@39250
   379
instance
bulwahn@39250
   380
proof
bulwahn@39250
   381
qed (auto simp add: equal_literal_def explode_inject)
bulwahn@39250
   382
bulwahn@39250
   383
end
haftmann@31051
   384
haftmann@52365
   385
lemma [code nbe]:
haftmann@52365
   386
  fixes s :: "String.literal"
haftmann@52365
   387
  shows "HOL.equal s s \<longleftrightarrow> True"
haftmann@52365
   388
  by (simp add: equal)
haftmann@52365
   389
haftmann@51160
   390
lemma STR_inject' [simp]:
haftmann@51160
   391
  "STR xs = STR ys \<longleftrightarrow> xs = ys"
haftmann@51160
   392
  by (simp add: STR_inject)
bulwahn@39274
   393
bulwahn@39274
   394
haftmann@31051
   395
subsection {* Code generator *}
haftmann@31051
   396
wenzelm@48891
   397
ML_file "Tools/string_code.ML"
haftmann@31051
   398
haftmann@33237
   399
code_reserved SML string
haftmann@33237
   400
code_reserved OCaml string
haftmann@34886
   401
code_reserved Scala string
haftmann@33237
   402
haftmann@52435
   403
code_printing
haftmann@52435
   404
  type_constructor literal \<rightharpoonup>
haftmann@52435
   405
    (SML) "string"
haftmann@52435
   406
    and (OCaml) "string"
haftmann@52435
   407
    and (Haskell) "String"
haftmann@52435
   408
    and (Scala) "String"
haftmann@31051
   409
haftmann@31051
   410
setup {*
haftmann@34886
   411
  fold String_Code.add_literal_string ["SML", "OCaml", "Haskell", "Scala"]
haftmann@31051
   412
*}
haftmann@31051
   413
haftmann@52435
   414
code_printing
haftmann@52435
   415
  class_instance literal :: equal \<rightharpoonup>
haftmann@52435
   416
    (Haskell) -
haftmann@52435
   417
| constant "HOL.equal :: literal \<Rightarrow> literal \<Rightarrow> bool" \<rightharpoonup>
haftmann@52435
   418
    (SML) "!((_ : string) = _)"
haftmann@52435
   419
    and (OCaml) "!((_ : string) = _)"
haftmann@52435
   420
    and (Haskell) infix 4 "=="
haftmann@52435
   421
    and (Scala) infixl 5 "=="
haftmann@31051
   422
wenzelm@36176
   423
hide_type (open) literal
haftmann@31205
   424
bulwahn@39250
   425
end
haftmann@49948
   426