README.md 14.3 KB
Newer Older
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1
2
3
4
5
6
7
8
9
10
11
CoqInterval
===========

This library provides vernacular files containing tactics for
simplifying the proofs of inequalities on expressions of real numbers
for the [Coq proof assistant](https://coq.inria.fr/).

This package is free software; you can redistribute it and/or modify it
under the terms of CeCILL-C Free Software License (see the [COPYING](COPYING) file).
Main author is Guillaume Melquiond <guillaume.melquiond@inria.fr>.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
12
13
14
15
16
17
See the file [INSTALL.md](INSTALL.md) for installation instructions.


Project Home
------------

Guillaume Melquiond's avatar
Guillaume Melquiond committed
18
Homepage: https://coqinterval.gitlabpages.inria.fr/
Guillaume Melquiond's avatar
Guillaume Melquiond committed
19
20
21
22
23
24

Repository: https://gitlab.inria.fr/coqinterval/interval

Bug tracker: https://gitlab.inria.fr/coqinterval/interval/issues


Guillaume Melquiond's avatar
Guillaume Melquiond committed
25
26
27
28
Invocation
----------

In order to use the tactics of the library, one has to import the
29
`Interval.Tactic` file into a Coq proof script. The main tactic is named
Guillaume Melquiond's avatar
Guillaume Melquiond committed
30
31
32
33
34
35
`interval`.

The tactic can be applied on a goal of the form `c1 <= e <= c2` with
`e` an expression involving real-valued operators. Sub-expressions that
are not recognized by the tactic should be either terms `t` appearing in
hypothesis inequalities `c3 <= t <= c4` or simple integers. The
Guillaume Melquiond's avatar
Guillaume Melquiond committed
36
bounds `c1`, `c2`, etc, are expressions that contain only constant leaves,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
37
38
39
40
41
e.g., `5 / sqrt (1 + PI)`.

The complete list of recognized goals is as follows:

  - `c1 <= e <= c2`;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
42
43
44
45
46
47
48
  - `e <= c1`, `c1 <= e`, `e >= c1`, and `c1 >= e`;
  - `e < c1`, `c1 < e`, `e > c1`, and `c1 > e`;
  - `e <> c1` and `c1 <> e`;
  - `Rabs e <= c1`, handled as `-c1 <= e <= c1`.

The complete list of recognized hypotheses is as follows:

49
  - `c1 <= t <= c2`, `c1 <= e < c2`, `c1 < e <= c2`, and `c1 < e < c2`;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
50
  - `t <= c1`, `c1 <= t`, `t >= c1`, and `c1 >= t`;
51
52
  - `t < c1`, `c1 < t`, `t > c1`, and `c1 > t`;
  - `Rabs t <= c1` and `Rabs t < c1`, handled as `-c1 <= e <= c1`.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
53

54
The tactic recognizes the following operators: `PI`, `Ropp`, `Rabs`, `Rinv`,
55
56
`Rsqr`, `sqrt`, `cos`, `sin`, `tan`, `atan`, `exp`, `ln`, `pow`, `Rpower`,
`powerRZ`, `Rplus`, `Rminus`, `Rmult`, `Rdiv`. Flocq's operators `Zfloor`,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
57
58
59
60
`Zceil`, `Ztrunc`, `ZnearestE` (composed with `IZR`) are also recognized.
There are some restrictions on the domain of a few functions: `pow` and
`powerRZ` should be written with a numeric exponent; the input of `cos`
and `sin` should be between `-2*PI` and `2*PI`; the input of `tan` should
Guillaume Melquiond's avatar
Guillaume Melquiond committed
61
be between `-PI/2` and `PI/2`. Outside of these domains, the
62
trigonometric functions return tight results only for singleton
Guillaume Melquiond's avatar
Guillaume Melquiond committed
63
input intervals.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
64

Guillaume Melquiond's avatar
Guillaume Melquiond committed
65
66
67
68
69
70
71
72
73
74
A helper tactic `interval_intro e` is also available. Instead of proving
the current goal, it computes an enclosure of the expression `e` passed
as argument and it introduces the resulting inequalities into the proof
context. If only one bound is needed, the keywords `lower` and `upper`
can be passed to the tactic, so that it does not perform useless
computations. For example, `interval_intro e lower` introduces only the
inequality corresponding to the lower bound of `e` in the context. The
`interval_intro` tactic uses a fresh name for the generated inequalities,
unless one uses `as` followed by an intro pattern.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
75
76
The `integral` tactic is a specialized version of `interval` that can be
used when the target enclosure involves an expression containing an integral.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
77
78
79
80
81
82
83
84
Such an integral should be expressed using `RInt`; its bounds should be
constant; and its integrand should be an expression containing only
constant leaves except for the integration variable. Improper integrals
are also supported, when expressed using `RInt_gen`. The supported bounds
are then `(at_right 0) (at_point _)` and `(at_point _) (Rbar_locally
p_infty)`. In the improper case, the integrand should be of the form
`(fun t => f t * g t)` with `f` a function bounded on the integration
domain and `g` one of the following expressions:
Guillaume Melquiond's avatar
Guillaume Melquiond committed
85
86
87
88

  - `powerRZ t _ * (ln t) ^ _`,
  - `/ (t * (ln t) ^ _)`.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
89
90
91
92
93
94
95
The `root H` tactic is a specialized version of `interval` that can be
used when the target enclosure involves an expression that is
constrained by an equation whose proof is `H`. Rather than an equality
proof, the tactic can also be passed an equality statement or even
just a real expression (then assumed to be zero), in which case the
tactic generates a new goal that asks for a proof of this equality.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
96
The helper tactic `integral_intro` is the counterpart of `interval_intro`,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
97
98
but for introducing enclosures of integrals into the proof context. As
with `interval_intro`, keywords `lower`, `upper`, and `as`, are
Guillaume Melquiond's avatar
Guillaume Melquiond committed
99
100
101
102
103
104
105
106
107
108
109
110
111
112
supported. Similarly, `root_intro` introduces enclosures of roots into
the proof context. Only `as` is supported in that case. When an
equality (rather than a proof) is passed to `root_intro`, no new goal
is generated, but the introduced hypothesis uses the equality as its
antecedent.

Tactics `interval_intro`, `integral_intro`, and `root_intro` are
available as degenerate forms that unify the obtained enclosure with
the current goal. They are meant to be used when the goal is an
existential variable, e.g., in a tactic-in-term context. Those
degenerate forms are named `interval`, `integral`, and `root`, for
conciseness, but they should not be confused with the original
tactics. For all intents and purposes, they behave like the `*_intro`
tactics.
113

Guillaume Melquiond's avatar
Guillaume Melquiond committed
114
115
116
117
118
119
120
121
122
123
The `plot` tactic produces correct function graphs, that is, two curves
that are guaranteed to enclose the given function on the given input
interval. It is invoked as `plot f x1 x2`. An output range can optionally
be passed: `plot f x1 x2 y1 y2`. If not, it is computed on the fly.

The `Interval.Plot` file provides a `Plot` command that can be used to
display a function graph. This is done by invoking the `gnuplot` command,
which thus needs to be installed. If a string is passed as an optional
argument, instead of invoking `gnuplot`, a file is created with the
corresponding Gnuplot script.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
124
125
126
127
128
129
130
131
132
133

Fine-tuning
-----------

The behavior of the tactics can be tuned by passing an optional set of
parameters `with (param1, param2, ...)`. These parameters are parsed from
left to right. If some parameters are conflicting, the earlier ones are
discarded. Available parameters are as follows (with the type of their
arguments, if any):

Guillaume Melquiond's avatar
Guillaume Melquiond committed
134
135
  - `i_prec (p:positive)`

136
137
138
139
140
141
    Set the precision used to emulate floating-point computations. If
    this parameter is not specified, the tactics perform computations
    using machine floating-point numbers, when available. Otherwise, the
    tactic defaults to using `i_prec 53`. Note that, in some corner
    cases, the tactics might fail when using native numbers, despite the
    goals being provable using a 53-bit emulation.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
142
143
144

  - `i_native_compute`

145
146
147
148
    Perform computations using `native_compute` instead of `vm_compute`.
    This greatly increases the startup time of the tactics, but makes the
    computations faster. This is useful only for
    computationally-intensive proofs.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
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

  - `i_bisect (x:R)`

    Instruct the tactics to split the interval enclosing `x` until the
    goal is proved on all the sub-intervals. Several `i_bisect`
    parameters can be given. In that case, the tactic cycles through all
    of them, splitting the input domain along the corresponding variable.
    Computation time is more or less proportional to the final number of
    sub-domains. This parameter is only meaningful for the `interval` and
    `interval_intro` tactics.

  - `i_depth (n:nat)`

    Set the maximal bisection depth. Setting it to a nonzero value has no
    effect unless `i_bisect` parameters are also passed. If the maximal
    depth is `n`, the tactic will consider up to `2^n` sub-domains in the
    worst case. As with `i_bisect`, this parameter is only meaningful for
    the `interval` and `interval_intro` tactics. The maximal depth
    defaults to `15` for `interval`, and to `5` for `interval_intro`.
    Note that `interval_intro` computes the best enclosure that could be
    verified by `interval` using the same maximal depth.

  - `i_autodiff (x:R)`

    Instruct the tactics to perform an automatic differentiation of the
    target expression with respect to `x`. This makes the tactic about
    twice slower on each sub-domain. But it makes it possible to detect
    some monotony properties of the target expression, thus reducing the
    amount of sub-domains that need to be considered. Note that this is
    only useful if there are several occurrences of `x` in the goal. This
    parameter is only meaningful for the `interval` and `interval_intro`
Guillaume Melquiond's avatar
Guillaume Melquiond committed
180
181
182
    tactics. It is mutually exclusive with `i_taylor`. This parameter can
    also be used with the `root` and `root_intro` tactics, if they did
    not guess the correct target variable.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
183
184
185
186
187
188
189
190
191
192
193
194

  - `i_taylor (x:R)`

    Instruct the tactics to compute a reliable polynomial enclosure of
    the target expression using Taylor models in `x`. As with
    `i_autodiff`, this is useful only if `x` occurs several times in the
    goal. Computing polynomial enclosures is much slower than automatic
    differentiation, but it can reduce the final number of sub-domains
    even further, thus speeding up proofs. Note that it might fail to
    prove goals that are feasible using automatic differentiation. As
    with `i_autodiff`, the `i_taylor` parameter is only meaningful for
    the `interval` and `interval_intro` tactics. It is implicit for the
Guillaume Melquiond's avatar
Guillaume Melquiond committed
195
196
197
    `integral`, `integral_intro`, and `plot` tactics, as Taylor models of
    the integrand (respectively, plotted function) are computed with
    respect to its variable.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
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

  - `i_degree (d:nat)`

    Set the degree of polynomials used as enclosures. The default degree
    is 10. For `interval` and `interval_intro`, this parameter is only
    meaningful in conjunction with `i_taylor`.

  - `i_fuel (n:positive)`

    Set the maximum number of sub-domains considered when bounding
    integrals. The tactics maintain a set of integration sub-domains; it
    splits the sub-domains that contribute the most to the inaccuracy of
    the integral until its enclosure is tight enough to satisfy the goal.
    By default, the tactics will split the integration domain into at
    most 100 sub-domains. This parameter is only meaningful for the
    `integral` and `integral_intro` tactics.

  - `i_width (p:Z)`

    Instruct the `integral_intro` tactic to compute an enclosure of the
    integral that is no larger than `2^p`. The tactic will split the
    integration domain until the resulting enclosure reaches this width
    or `i_fuel` is exhausted. This parameter is meaningless for the other
    tactics. It is mutually exclusive with `i_relwidth`.

  - `i_relwidth (p:positive)`

    Instruct the `integral_intro` tactic to compute an enclosure of the
    integral whose relative width is no larger than `2^-p`. This
    parameter is meaningless for the other tactics. It defaults to 10.
    This means that, if neither `i_width` nor `i_relwidth` is used,
    `integral_intro` will compute an enclosure of the integral accurate
    to three decimal digits, assuming `i_fuel` is large enough.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
232
233
234
235
236
237
238
239
  - `i_size (w h:positive)`

    Instruct the `plot` tactic to target a resolution of `w` by `h`
    pixels. This parameter is meaningless for the other tactics. It
    defaults to a resolution of `512x384`. The tactic will subdivide the
    input interval into `w` subintervals, and it will try to ensure that
    the function graph is no larger than a few pixels vertically.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
240
241
242
243
244
245
246
247
248
249
250
251
252
253
  - `i_delay`

    Prevent Coq from verifying the generated proof at invocation time.
    Instead, Coq will check the proof term at `Qed` time. This makes the
    tactics `interval` and `integral` instant. But it also means that
    failures, if any, will only be detected at `Qed` time, possibly with
    an inscrutable error message. This parameter is thus meant to be used
    when editing a proof script for which the tactics are already known
    to succeed. For the tactics `interval_intro` and `integral_intro`,
    computations are still performed (the risk of failure is thus
    negligible), but the `i_delay` parameter delays their verification to
    `Qed` time. This makes these tactics twice as fast. This is
    especially useful when looking for optimal values for parameters such
    as `i_prec` and `i_degree`.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
254
255
256
257
258
259


Examples
--------

```coq
Guillaume Melquiond's avatar
Guillaume Melquiond committed
260
From Coq Require Import Reals Lra.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
261
From Interval Require Import Tactic.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
262
263

Open Scope R_scope.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
264
265
266
267
Notation "x = y ± z" := (Rle (Rabs (x - y)) z)
  (at level 70, y at next level).

(* Tactic interval *)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291

Goal
  forall x, -1 <= x <= 1 ->
  sqrt (1 - x) <= 3/2.
Proof.
  intros.
  interval.
Qed.

Goal
  forall x, -1 <= x <= 1 ->
  sqrt (1 - x) <= 141422/100000.
Proof.
  intros.
  interval.
Qed.

Goal
  forall x, -1 <= x <= 1 ->
  sqrt (1 - x) <= 141422/100000.
Proof.
  intros.
  interval_intro (sqrt (1 - x)) upper as H'.
  apply Rle_trans with (1 := H').
Guillaume Melquiond's avatar
Guillaume Melquiond committed
292
  lra.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
293
294
295
296
297
Qed.

Goal
  forall x, 3/2 <= x <= 2 ->
  forall y, 1 <= y <= 33/32 ->
Guillaume Melquiond's avatar
Guillaume Melquiond committed
298
  sqrt(1 + x/sqrt(x+y)) = 144/1000*x + 118/100 ± 71/32768.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
299
300
301
302
303
304
305
Proof.
  intros.
  interval with (i_prec 19, i_bisect x).
Qed.

Goal
  forall x, 1/2 <= x <= 2 ->
Guillaume Melquiond's avatar
Guillaume Melquiond committed
306
307
308
  sqrt x = ((((122 / 7397 * x + (-1733) / 13547) * x
             + 529 / 1274) * x + (-767) / 999) * x
             + 407 / 334) * x + 227 / 925 ± 5/65536.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
309
310
Proof.
  intros.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
311
  interval with (i_bisect x, i_taylor x, i_degree 3).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
312
313
314
315
316
317
318
Qed.

Goal
  forall x, -1 <= x ->
  x < 1 + powerRZ x 3.
Proof.
  intros.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
319
  apply Rminus_lt.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
320
  interval with (i_bisect x, i_autodiff x).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
321
322
Qed.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
323
324
(* Tactic integral *)

Guillaume Melquiond's avatar
Guillaume Melquiond committed
325
From Coquelicot Require Import Coquelicot.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
326
327

Goal
Guillaume Melquiond's avatar
Guillaume Melquiond committed
328
329
  RInt (fun x => atan (sqrt (x*x + 2)) / (sqrt (x*x + 2) * (x*x + 1))) 0 1
    = 5/96*PI*PI ± 1/1000.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
330
Proof.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
331
  integral with (i_fuel 2, i_degree 5).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
332
333
334
335
336
337
338
Qed.

Goal
  RInt_gen (fun x => 1 * (powerRZ x 3 * ln x^2))
           (at_right 0) (at_point 1) = 1/32.
Proof.
  refine ((fun H => Rle_antisym _ _ (proj2 H) (proj1 H)) _).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
339
  integral with (i_prec 10).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
340
Qed.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
341

Guillaume Melquiond's avatar
Guillaume Melquiond committed
342
343
344
345
346
347
348
349
350
351
352
353
(* Tactic root *)

Goal
  forall x:R, 999 <= x <= 1000 ->
  sin x = 0 -> x = 318 * PI ± 1/1000.
Proof.
  intros x Hx Hs.
  root Hs.
Qed.

(* Degenerate forms *)

354
Definition equal_1 x `(0 <= x <= PI/2) :=
355
356
  ltac:(interval ((cos x)² + (sin x)²) with (i_taylor x)).

357
Definition equal_PI_over_4 :=
Guillaume Melquiond's avatar
Guillaume Melquiond committed
358
359
360
361
362
363
  ltac:(integral (RInt (fun x => 1 / (1+x*x)) 0 1)).

Definition equal_0_442854401002 x :=
  ltac:(root (exp x = 2 - x)).

(* Tactic plot and command Plot *)
364

Guillaume Melquiond's avatar
Guillaume Melquiond committed
365
366
367
368
369
370
371
372
373
374
375
376
From Interval Require Import Plot.

Definition p1 := ltac:(plot (fun x => x^2 * sin (x^2)) (-4) 4).
Plot p1.

Definition p2 := ltac:(
  plot (fun x => sin (x + exp x))
    0 6 (-5/4) (5/4) with (i_size 120 90, i_degree 6)).
Plot p2 as "picture.gnuplot".

Plot ltac:(plot (fun x => sqrt (1 - x^2) * sin (x * 200)) (-1) 1
  with (i_degree 1, i_size 100 300)).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
377
```