src/HOL/String.thy
author haftmann
Wed May 06 16:01:23 2009 +0200 (2009-05-06)
changeset 31051 4d9b52e0a48c
child 31055 2cf6efca6c71
permissions -rw-r--r--
refined HOL string theories and corresponding ML fragments
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@31051
     6
imports List
haftmann@31051
     7
uses "Tools/string_syntax.ML"
haftmann@31051
     8
begin
haftmann@31051
     9
haftmann@31051
    10
subsection {* Characters *}
haftmann@31051
    11
haftmann@31051
    12
datatype nibble =
haftmann@31051
    13
    Nibble0 | Nibble1 | Nibble2 | Nibble3 | Nibble4 | Nibble5 | Nibble6 | Nibble7
haftmann@31051
    14
  | Nibble8 | Nibble9 | NibbleA | NibbleB | NibbleC | NibbleD | NibbleE | NibbleF
haftmann@31051
    15
haftmann@31051
    16
lemma UNIV_nibble:
haftmann@31051
    17
  "UNIV = {Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7,
haftmann@31051
    18
    Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF}" (is "_ = ?A")
haftmann@31051
    19
proof (rule UNIV_eq_I)
haftmann@31051
    20
  fix x show "x \<in> ?A" by (cases x) simp_all
haftmann@31051
    21
qed
haftmann@31051
    22
haftmann@31051
    23
instance nibble :: finite
haftmann@31051
    24
  by default (simp add: UNIV_nibble)
haftmann@31051
    25
haftmann@31051
    26
datatype char = Char nibble nibble
haftmann@31051
    27
  -- "Note: canonical order of character encoding coincides with standard term ordering"
haftmann@31051
    28
haftmann@31051
    29
lemma UNIV_char:
haftmann@31051
    30
  "UNIV = image (split Char) (UNIV \<times> UNIV)"
haftmann@31051
    31
proof (rule UNIV_eq_I)
haftmann@31051
    32
  fix x show "x \<in> image (split Char) (UNIV \<times> UNIV)" by (cases x) auto
haftmann@31051
    33
qed
haftmann@31051
    34
haftmann@31051
    35
instance char :: finite
haftmann@31051
    36
  by default (simp add: UNIV_char)
haftmann@31051
    37
haftmann@31051
    38
lemma size_char [code, simp]:
haftmann@31051
    39
  "size (c::char) = 0" by (cases c) simp
haftmann@31051
    40
haftmann@31051
    41
lemma char_size [code, simp]:
haftmann@31051
    42
  "char_size (c::char) = 0" by (cases c) simp
haftmann@31051
    43
haftmann@31051
    44
primrec nibble_pair_of_char :: "char \<Rightarrow> nibble \<times> nibble" where
haftmann@31051
    45
  "nibble_pair_of_char (Char n m) = (n, m)"
haftmann@31051
    46
haftmann@31051
    47
declare nibble_pair_of_char.simps [code del]
haftmann@31051
    48
haftmann@31051
    49
setup {*
haftmann@31051
    50
let
haftmann@31051
    51
  val nibbles = map (Thm.cterm_of @{theory} o HOLogic.mk_nibble) (0 upto 15);
haftmann@31051
    52
  val thms = map_product
haftmann@31051
    53
   (fn n => fn m => Drule.instantiate' [] [SOME n, SOME m] @{thm nibble_pair_of_char.simps})
haftmann@31051
    54
      nibbles nibbles;
haftmann@31051
    55
in
haftmann@31051
    56
  PureThy.note_thmss Thm.lemmaK [((Binding.name "nibble_pair_of_char_simps", []), [(thms, [])])]
haftmann@31051
    57
  #-> (fn [(_, thms)] => fold_rev Code.add_eqn thms)
haftmann@31051
    58
end
haftmann@31051
    59
*}
haftmann@31051
    60
haftmann@31051
    61
lemma char_case_nibble_pair [code, code inline]:
haftmann@31051
    62
  "char_case f = split f o nibble_pair_of_char"
haftmann@31051
    63
  by (simp add: expand_fun_eq split: char.split)
haftmann@31051
    64
haftmann@31051
    65
lemma char_rec_nibble_pair [code, code inline]:
haftmann@31051
    66
  "char_rec f = split f o nibble_pair_of_char"
haftmann@31051
    67
  unfolding char_case_nibble_pair [symmetric]
haftmann@31051
    68
  by (simp add: expand_fun_eq split: char.split)
haftmann@31051
    69
haftmann@31051
    70
syntax
haftmann@31051
    71
  "_Char" :: "xstr => char"    ("CHR _")
haftmann@31051
    72
haftmann@31051
    73
haftmann@31051
    74
subsection {* Strings *}
haftmann@31051
    75
haftmann@31051
    76
types string = "char list"
haftmann@31051
    77
haftmann@31051
    78
syntax
haftmann@31051
    79
  "_String" :: "xstr => string"    ("_")
haftmann@31051
    80
haftmann@31051
    81
setup StringSyntax.setup
haftmann@31051
    82
haftmann@31051
    83
haftmann@31051
    84
subsection {* Strings as dedicated datatype *}
haftmann@31051
    85
haftmann@31051
    86
datatype message_string = STR string
haftmann@31051
    87
haftmann@31051
    88
lemmas [code del] =
haftmann@31051
    89
  message_string.recs message_string.cases
haftmann@31051
    90
haftmann@31051
    91
lemma [code]: "size (s\<Colon>message_string) = 0"
haftmann@31051
    92
  by (cases s) simp_all
haftmann@31051
    93
haftmann@31051
    94
lemma [code]: "message_string_size (s\<Colon>message_string) = 0"
haftmann@31051
    95
  by (cases s) simp_all
haftmann@31051
    96
haftmann@31051
    97
haftmann@31051
    98
subsection {* Code generator *}
haftmann@31051
    99
haftmann@31051
   100
text {* This also covers pretty syntax for list literals. *}
haftmann@31051
   101
haftmann@31051
   102
ML {*
haftmann@31051
   103
local
haftmann@31051
   104
haftmann@31051
   105
open Basic_Code_Thingol;
haftmann@31051
   106
haftmann@31051
   107
fun implode_list naming t = case pairself
haftmann@31051
   108
  (Code_Thingol.lookup_const naming) (@{const_name Nil}, @{const_name Cons})
haftmann@31051
   109
   of (SOME nil', SOME cons') => let
haftmann@31051
   110
          fun dest_cons (IConst (c, _) `$ t1 `$ t2) =
haftmann@31051
   111
                if c = cons'
haftmann@31051
   112
                then SOME (t1, t2)
haftmann@31051
   113
                else NONE
haftmann@31051
   114
            | dest_cons _ = NONE;
haftmann@31051
   115
          val (ts, t') = Code_Thingol.unfoldr dest_cons t;
haftmann@31051
   116
        in case t'
haftmann@31051
   117
         of IConst (c, _) => if c = nil' then SOME ts else NONE
haftmann@31051
   118
          | _ => NONE
haftmann@31051
   119
        end
haftmann@31051
   120
    | _ => NONE
haftmann@31051
   121
haftmann@31051
   122
fun decode_char naming (IConst (c1, _), IConst (c2, _)) = (case map_filter
haftmann@31051
   123
  (Code_Thingol.lookup_const naming)[@{const_name Nibble0}, @{const_name Nibble1},
haftmann@31051
   124
   @{const_name Nibble2}, @{const_name Nibble3},
haftmann@31051
   125
   @{const_name Nibble4}, @{const_name Nibble5},
haftmann@31051
   126
   @{const_name Nibble6}, @{const_name Nibble7},
haftmann@31051
   127
   @{const_name Nibble8}, @{const_name Nibble9},
haftmann@31051
   128
   @{const_name NibbleA}, @{const_name NibbleB},
haftmann@31051
   129
   @{const_name NibbleC}, @{const_name NibbleD},
haftmann@31051
   130
   @{const_name NibbleE}, @{const_name NibbleF}]
haftmann@31051
   131
   of nibbles' as [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _] => let
haftmann@31051
   132
          fun idx c = find_index (curry (op =) c) nibbles';
haftmann@31051
   133
          fun decode ~1 _ = NONE
haftmann@31051
   134
            | decode _ ~1 = NONE
haftmann@31051
   135
            | decode n m = SOME (chr (n * 16 + m));
haftmann@31051
   136
        in decode (idx c1) (idx c2) end
haftmann@31051
   137
    | _ => NONE)
haftmann@31051
   138
 | decode_char _ _ = NONE
haftmann@31051
   139
   
haftmann@31051
   140
fun implode_string naming mk_char mk_string ts = case
haftmann@31051
   141
  Code_Thingol.lookup_const naming @{const_name Char}
haftmann@31051
   142
   of SOME char' => let
haftmann@31051
   143
        fun implode_char (IConst (c, _) `$ t1 `$ t2) =
haftmann@31051
   144
              if c = char' then decode_char naming (t1, t2) else NONE
haftmann@31051
   145
          | implode_char _ = NONE;
haftmann@31051
   146
        val ts' = map implode_char ts;
haftmann@31051
   147
      in if forall is_some ts'
haftmann@31051
   148
        then (SOME o Code_Printer.str o mk_string o implode o map_filter I) ts'
haftmann@31051
   149
        else NONE
haftmann@31051
   150
      end
haftmann@31051
   151
    | _ => NONE;
haftmann@31051
   152
haftmann@31051
   153
fun default_list (target_fxy, target_cons) pr fxy t1 t2 =
haftmann@31051
   154
  Code_Printer.brackify_infix (target_fxy, Code_Printer.R) fxy [
haftmann@31051
   155
    pr (Code_Printer.INFX (target_fxy, Code_Printer.X)) t1,
haftmann@31051
   156
    Code_Printer.str target_cons,
haftmann@31051
   157
    pr (Code_Printer.INFX (target_fxy, Code_Printer.R)) t2
haftmann@31051
   158
  ];
haftmann@31051
   159
haftmann@31051
   160
fun pretty_list literals =
haftmann@31051
   161
  let
haftmann@31051
   162
    val mk_list = Code_Printer.literal_list literals;
haftmann@31051
   163
    fun pretty pr naming thm vars fxy [(t1, _), (t2, _)] =
haftmann@31051
   164
      case Option.map (cons t1) (implode_list naming t2)
haftmann@31051
   165
       of SOME ts => mk_list (map (pr vars Code_Printer.NOBR) ts)
haftmann@31051
   166
        | NONE => default_list (Code_Printer.infix_cons literals) (pr vars) fxy t1 t2;
haftmann@31051
   167
  in (2, pretty) end;
haftmann@31051
   168
haftmann@31051
   169
fun pretty_list_string literals =
haftmann@31051
   170
  let
haftmann@31051
   171
    val mk_list = Code_Printer.literal_list literals;
haftmann@31051
   172
    val mk_char = Code_Printer.literal_char literals;
haftmann@31051
   173
    val mk_string = Code_Printer.literal_string literals;
haftmann@31051
   174
    fun pretty pr naming thm vars fxy [(t1, _), (t2, _)] =
haftmann@31051
   175
      case Option.map (cons t1) (implode_list naming t2)
haftmann@31051
   176
       of SOME ts => (case implode_string naming mk_char mk_string ts
haftmann@31051
   177
           of SOME p => p
haftmann@31051
   178
            | NONE => mk_list (map (pr vars Code_Printer.NOBR) ts))
haftmann@31051
   179
        | NONE => default_list (Code_Printer.infix_cons literals) (pr vars) fxy t1 t2;
haftmann@31051
   180
  in (2, pretty) end;
haftmann@31051
   181
haftmann@31051
   182
fun pretty_char literals =
haftmann@31051
   183
  let
haftmann@31051
   184
    val mk_char = Code_Printer.literal_char literals;
haftmann@31051
   185
    fun pretty _ naming thm _ _ [(t1, _), (t2, _)] =
haftmann@31051
   186
      case decode_char naming (t1, t2)
haftmann@31051
   187
       of SOME c => (Code_Printer.str o mk_char) c
haftmann@31051
   188
        | NONE => Code_Printer.nerror thm "Illegal character expression";
haftmann@31051
   189
  in (2, pretty) end;
haftmann@31051
   190
haftmann@31051
   191
fun pretty_message literals =
haftmann@31051
   192
  let
haftmann@31051
   193
    val mk_char = Code_Printer.literal_char literals;
haftmann@31051
   194
    val mk_string = Code_Printer.literal_string literals;
haftmann@31051
   195
    fun pretty _ naming thm _ _ [(t, _)] =
haftmann@31051
   196
      case implode_list naming t
haftmann@31051
   197
       of SOME ts => (case implode_string naming mk_char mk_string ts
haftmann@31051
   198
           of SOME p => p
haftmann@31051
   199
            | NONE => Code_Printer.nerror thm "Illegal message expression")
haftmann@31051
   200
        | NONE => Code_Printer.nerror thm "Illegal message expression";
haftmann@31051
   201
  in (1, pretty) end;
haftmann@31051
   202
haftmann@31051
   203
in
haftmann@31051
   204
haftmann@31051
   205
fun add_literal_list target thy =
haftmann@31051
   206
  let
haftmann@31051
   207
    val pr = pretty_list (Code_Target.the_literals thy target);
haftmann@31051
   208
  in
haftmann@31051
   209
    thy
haftmann@31051
   210
    |> Code_Target.add_syntax_const target @{const_name Cons} (SOME pr)
haftmann@31051
   211
  end;
haftmann@31051
   212
haftmann@31051
   213
fun add_literal_list_string target thy =
haftmann@31051
   214
  let
haftmann@31051
   215
    val pr = pretty_list_string (Code_Target.the_literals thy target);
haftmann@31051
   216
  in
haftmann@31051
   217
    thy
haftmann@31051
   218
    |> Code_Target.add_syntax_const target @{const_name Cons} (SOME pr)
haftmann@31051
   219
  end;
haftmann@31051
   220
haftmann@31051
   221
fun add_literal_char target thy =
haftmann@31051
   222
  let
haftmann@31051
   223
    val pr = pretty_char (Code_Target.the_literals thy target);
haftmann@31051
   224
  in
haftmann@31051
   225
    thy
haftmann@31051
   226
    |> Code_Target.add_syntax_const target @{const_name Char} (SOME pr)
haftmann@31051
   227
  end;
haftmann@31051
   228
haftmann@31051
   229
fun add_literal_message str target thy =
haftmann@31051
   230
  let
haftmann@31051
   231
    val pr = pretty_message (Code_Target.the_literals thy target);
haftmann@31051
   232
  in
haftmann@31051
   233
    thy
haftmann@31051
   234
    |> Code_Target.add_syntax_const target str (SOME pr)
haftmann@31051
   235
  end;
haftmann@31051
   236
haftmann@31051
   237
end;
haftmann@31051
   238
*}
haftmann@31051
   239
haftmann@31051
   240
setup {*
haftmann@31051
   241
  fold (fn target => add_literal_list target) ["SML", "OCaml", "Haskell"]
haftmann@31051
   242
*}
haftmann@31051
   243
haftmann@31051
   244
code_type message_string
haftmann@31051
   245
  (SML "string")
haftmann@31051
   246
  (OCaml "string")
haftmann@31051
   247
  (Haskell "String")
haftmann@31051
   248
haftmann@31051
   249
setup {*
haftmann@31051
   250
  fold (fn target => add_literal_message @{const_name STR} target)
haftmann@31051
   251
    ["SML", "OCaml", "Haskell"]
haftmann@31051
   252
*}
haftmann@31051
   253
haftmann@31051
   254
code_instance message_string :: eq
haftmann@31051
   255
  (Haskell -)
haftmann@31051
   256
haftmann@31051
   257
code_const "eq_class.eq \<Colon> message_string \<Rightarrow> message_string \<Rightarrow> bool"
haftmann@31051
   258
  (SML "!((_ : string) = _)")
haftmann@31051
   259
  (OCaml "!((_ : string) = _)")
haftmann@31051
   260
  (Haskell infixl 4 "==")
haftmann@31051
   261
haftmann@31051
   262
code_reserved SML string
haftmann@31051
   263
code_reserved OCaml string
haftmann@31051
   264
haftmann@31051
   265
haftmann@31051
   266
types_code
haftmann@31051
   267
  "char" ("string")
haftmann@31051
   268
attach (term_of) {*
haftmann@31051
   269
val term_of_char = HOLogic.mk_char o ord;
haftmann@31051
   270
*}
haftmann@31051
   271
attach (test) {*
haftmann@31051
   272
fun gen_char i =
haftmann@31051
   273
  let val j = random_range (ord "a") (Int.min (ord "a" + i, ord "z"))
haftmann@31051
   274
  in (chr j, fn () => HOLogic.mk_char j) end;
haftmann@31051
   275
*}
haftmann@31051
   276
haftmann@31051
   277
setup {*
haftmann@31051
   278
let
haftmann@31051
   279
haftmann@31051
   280
fun char_codegen thy defs dep thyname b t gr =
haftmann@31051
   281
  let
haftmann@31051
   282
    val i = HOLogic.dest_char t;
haftmann@31051
   283
    val (_, gr') = Codegen.invoke_tycodegen thy defs dep thyname false
haftmann@31051
   284
      (fastype_of t) gr;
haftmann@31051
   285
  in SOME (Codegen.str (ML_Syntax.print_string (chr i)), gr')
haftmann@31051
   286
  end handle TERM _ => NONE;
haftmann@31051
   287
haftmann@31051
   288
in Codegen.add_codegen "char_codegen" char_codegen end
haftmann@31051
   289
*}
haftmann@31051
   290
haftmann@31051
   291
end