blob: 1a3220f63aca9081593c29ace3fb93f27f784775 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
|
(************************************************************************)
(* * The Coq Proof Assistant / The Coq Development Team *)
(* v * INRIA, CNRS and contributors - Copyright 1999-2018 *)
(* <O___,, * (see CREDITS file for the list of authors) *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(* * (see LICENSE file for the text of the license) *)
(************************************************************************)
Require Import Decimal Ascii String.
(** * Conversion between decimal numbers and Coq strings *)
(** Pretty straightforward, which is precisely the point of the
[Decimal.int] datatype. The only catch is [Decimal.Nil] : we could
choose to convert it as [""] or as ["0"]. In the first case, it is
awkward to consider "" (or "-") as a number, while in the second case
we don't have a perfect bijection. Since the second variant is implemented
thanks to the first one, we provide both. *)
Local Open Scope string_scope.
(** Parsing one char *)
Definition uint_of_char (a:ascii)(d:option uint) :=
match d with
| None => None
| Some d =>
match a with
| "0" => Some (D0 d)
| "1" => Some (D1 d)
| "2" => Some (D2 d)
| "3" => Some (D3 d)
| "4" => Some (D4 d)
| "5" => Some (D5 d)
| "6" => Some (D6 d)
| "7" => Some (D7 d)
| "8" => Some (D8 d)
| "9" => Some (D9 d)
| _ => None
end
end%char.
Lemma uint_of_char_spec c d d' :
uint_of_char c (Some d) = Some d' ->
(c = "0" /\ d' = D0 d \/
c = "1" /\ d' = D1 d \/
c = "2" /\ d' = D2 d \/
c = "3" /\ d' = D3 d \/
c = "4" /\ d' = D4 d \/
c = "5" /\ d' = D5 d \/
c = "6" /\ d' = D6 d \/
c = "7" /\ d' = D7 d \/
c = "8" /\ d' = D8 d \/
c = "9" /\ d' = D9 d)%char.
Proof.
destruct c as [[|] [|] [|] [|] [|] [|] [|] [|]];
intros [= <-]; intuition.
Qed.
(** Decimal/String conversion where [Nil] is [""] *)
Module NilEmpty.
Fixpoint string_of_uint (d:uint) :=
match d with
| Nil => EmptyString
| D0 d => String "0" (string_of_uint d)
| D1 d => String "1" (string_of_uint d)
| D2 d => String "2" (string_of_uint d)
| D3 d => String "3" (string_of_uint d)
| D4 d => String "4" (string_of_uint d)
| D5 d => String "5" (string_of_uint d)
| D6 d => String "6" (string_of_uint d)
| D7 d => String "7" (string_of_uint d)
| D8 d => String "8" (string_of_uint d)
| D9 d => String "9" (string_of_uint d)
end.
Fixpoint uint_of_string s :=
match s with
| EmptyString => Some Nil
| String a s => uint_of_char a (uint_of_string s)
end.
Definition string_of_int (d:int) :=
match d with
| Pos d => string_of_uint d
| Neg d => String "-" (string_of_uint d)
end.
Definition int_of_string s :=
match s with
| EmptyString => Some (Pos Nil)
| String a s' =>
if ascii_dec a "-" then option_map Neg (uint_of_string s')
else option_map Pos (uint_of_string s)
end.
(* NB: For the moment whitespace between - and digits are not accepted.
And in this variant [int_of_string "-" = Some (Neg Nil)].
Compute int_of_string "-123456890123456890123456890123456890".
Compute string_of_int (-123456890123456890123456890123456890).
*)
(** Corresponding proofs *)
Lemma usu d :
uint_of_string (string_of_uint d) = Some d.
Proof.
induction d; simpl; rewrite ?IHd; simpl; auto.
Qed.
Lemma sus s d :
uint_of_string s = Some d -> string_of_uint d = s.
Proof.
revert d.
induction s; simpl.
- now intros d [= <-].
- intros d.
destruct (uint_of_string s); [intros H | intros [=]].
apply uint_of_char_spec in H.
intuition subst; simpl; f_equal; auto.
Qed.
Lemma isi d : int_of_string (string_of_int d) = Some d.
Proof.
destruct d; simpl.
- unfold int_of_string.
destruct (string_of_uint d) eqn:Hd.
+ now destruct d.
+ destruct ascii_dec; subst.
* now destruct d.
* rewrite <- Hd, usu; auto.
- rewrite usu; auto.
Qed.
Lemma sis s d :
int_of_string s = Some d -> string_of_int d = s.
Proof.
destruct s; [intros [= <-]| ]; simpl; trivial.
destruct ascii_dec; subst; simpl.
- destruct (uint_of_string s) eqn:Hs; simpl; intros [= <-].
simpl; f_equal. now apply sus.
- destruct d; [ | now destruct uint_of_char].
simpl string_of_int.
intros. apply sus; simpl.
destruct uint_of_char; simpl in *; congruence.
Qed.
End NilEmpty.
(** Decimal/String conversions where [Nil] is ["0"] *)
Module NilZero.
Definition string_of_uint (d:uint) :=
match d with
| Nil => "0"
| _ => NilEmpty.string_of_uint d
end.
Definition uint_of_string s :=
match s with
| EmptyString => None
| _ => NilEmpty.uint_of_string s
end.
Definition string_of_int (d:int) :=
match d with
| Pos d => string_of_uint d
| Neg d => String "-" (string_of_uint d)
end.
Definition int_of_string s :=
match s with
| EmptyString => None
| String a s' =>
if ascii_dec a "-" then option_map Neg (uint_of_string s')
else option_map Pos (uint_of_string s)
end.
(** Corresponding proofs *)
Lemma uint_of_string_nonnil s : uint_of_string s <> Some Nil.
Proof.
destruct s; simpl.
- easy.
- destruct (NilEmpty.uint_of_string s); [intros H | intros [=]].
apply uint_of_char_spec in H.
now intuition subst.
Qed.
Lemma sus s d :
uint_of_string s = Some d -> string_of_uint d = s.
Proof.
destruct s; [intros [=] | intros H].
apply NilEmpty.sus in H. now destruct d.
Qed.
Lemma usu d :
d<>Nil -> uint_of_string (string_of_uint d) = Some d.
Proof.
destruct d; (now destruct 1) || (intros _; apply NilEmpty.usu).
Qed.
Lemma usu_nil :
uint_of_string (string_of_uint Nil) = Some Decimal.zero.
Proof.
reflexivity.
Qed.
Lemma usu_gen d :
uint_of_string (string_of_uint d) = Some d \/
uint_of_string (string_of_uint d) = Some Decimal.zero.
Proof.
destruct d; (now right) || (left; now apply usu).
Qed.
Lemma isi d :
d<>Pos Nil -> d<>Neg Nil ->
int_of_string (string_of_int d) = Some d.
Proof.
destruct d; simpl.
- intros H _.
unfold int_of_string.
destruct (string_of_uint d) eqn:Hd.
+ now destruct d.
+ destruct ascii_dec; subst.
* now destruct d.
* rewrite <- Hd, usu; auto. now intros ->.
- intros _ H.
rewrite usu; auto. now intros ->.
Qed.
Lemma isi_posnil :
int_of_string (string_of_int (Pos Nil)) = Some (Pos Decimal.zero).
Proof.
reflexivity.
Qed.
(** Warning! (-0) won't parse (compatibility with the behavior of Z). *)
Lemma isi_negnil :
int_of_string (string_of_int (Neg Nil)) = Some (Neg (D0 Nil)).
Proof.
reflexivity.
Qed.
Lemma sis s d :
int_of_string s = Some d -> string_of_int d = s.
Proof.
destruct s; [intros [=]| ]; simpl.
destruct ascii_dec; subst; simpl.
- destruct (uint_of_string s) eqn:Hs; simpl; intros [= <-].
simpl; f_equal. now apply sus.
- destruct d; [ | now destruct uint_of_char].
simpl string_of_int.
intros. apply sus; simpl.
destruct uint_of_char; simpl in *; congruence.
Qed.
End NilZero.
|
