api.tex 17.2 KB
Newer Older
MARCHE Claude's avatar
MARCHE Claude committed
1
\chapter{The \why API}
2
\label{chap:api}\index{API}
MARCHE Claude's avatar
doc  
MARCHE Claude committed
3

4
This chapter is a tutorial for the users who want to link their own
MARCHE Claude's avatar
MARCHE Claude committed
5
OCaml code with the \why library. We progressively introduce the way
MARCHE Claude's avatar
MARCHE Claude committed
6 7
one can use the library to build terms, formulas, theories, proof
tasks, call external provers on tasks, and apply transformations on
8
tasks. The complete documentation for API calls is given
9
at URL~\url{http://why3.lri.fr/api/}.
10

MARCHE Claude's avatar
MARCHE Claude committed
11
We assume the reader has a fair knowledge of the OCaml
MARCHE Claude's avatar
MARCHE Claude committed
12
language. Notice that the \why library must be installed, see
13
Section~\ref{sec:installlib}. The OCaml code given below is available in
Andrei Paskevich's avatar
Andrei Paskevich committed
14
the source distribution as \url{examples/use_api/use_api.ml}.
MARCHE Claude's avatar
doc  
MARCHE Claude committed
15

MARCHE Claude's avatar
MARCHE Claude committed
16 17 18 19 20 21

\section{Building Propositional Formulas}

The first step is to know how to build propositional formulas. The
module \texttt{Term} gives a few functions for building these. Here is
a piece of OCaml code for building the formula $true \lor false$.
22
\begin{ocamlcode}
MARCHE Claude's avatar
MARCHE Claude committed
23
(* opening the Why3 library *)
24
open Why3
MARCHE Claude's avatar
MARCHE Claude committed
25 26

(* a ground propositional goal: true or false *)
Andrei Paskevich's avatar
Andrei Paskevich committed
27 28 29
let fmla_true : Term.term = Term.t_true
let fmla_false : Term.term = Term.t_false
let fmla1 : Term.term = Term.t_or fmla_true fmla_false
30
\end{ocamlcode}
Andrei Paskevich's avatar
Andrei Paskevich committed
31
The library uses the common type \texttt{term} both for terms
32 33
(\ie expressions that produce a value of some particular type)
and formulas (\ie boolean-valued expressions).
Andrei Paskevich's avatar
Andrei Paskevich committed
34 35 36 37
% To distinguish terms from formulas, one can look at the
% \texttt{t_ty} field of the \texttt{term} record: in formulas,
% this field has the value \texttt{None}, and in terms,
% \texttt{Some t}, where \texttt{t} is of type \texttt{Ty.ty}.
MARCHE Claude's avatar
MARCHE Claude committed
38 39 40

Such a formula can be printed using the module \texttt{Pretty}
providing pretty-printers.
41
\begin{ocamlcode}
Andrei Paskevich's avatar
Andrei Paskevich committed
42
(* printing it *)
MARCHE Claude's avatar
MARCHE Claude committed
43
open Format
Andrei Paskevich's avatar
Andrei Paskevich committed
44
let () = printf "@[formula 1 is:@ %a@]@." Pretty.print_term fmla1
45
\end{ocamlcode}
MARCHE Claude's avatar
MARCHE Claude committed
46 47 48 49 50 51 52 53 54

Assuming the lines above are written in a file \texttt{f.ml}, it can
be compiled using
\begin{verbatim}
ocamlc str.cma unix.cma nums.cma dynlink.cma \
        -I +ocamlgraph -I +why3 graph.cma why.cma f.ml -o f
\end{verbatim}
Running the generated executable \texttt{f} results in the following output.
\begin{verbatim}
55
formula 1 is: true \/ false
MARCHE Claude's avatar
MARCHE Claude committed
56 57 58 59 60
\end{verbatim}

Let's now build a formula with propositional variables: $A \land B
\rightarrow A$. Propositional variables must be declared first before
using them in formulas. This is done as follows.
61
\begin{ocamlcode}
62
let prop_var_A : Term.lsymbol =
MARCHE Claude's avatar
MARCHE Claude committed
63
  Term.create_psymbol (Ident.id_fresh "A") []
64
let prop_var_B : Term.lsymbol =
MARCHE Claude's avatar
MARCHE Claude committed
65
  Term.create_psymbol (Ident.id_fresh "B") []
66
\end{ocamlcode}
Andrei Paskevich's avatar
Andrei Paskevich committed
67 68 69 70
The type \texttt{lsymbol} is the type of function and predicate symbols (which
we call logic symbols for brevity). Then the atoms $A$ and $B$ must be built
by the general function for applying a predicate symbol to a list of terms.
Here we just need the empty list of arguments.
71
\begin{ocamlcode}
Andrei Paskevich's avatar
Andrei Paskevich committed
72 73 74 75 76
let atom_A : Term.term = Term.ps_app prop_var_A []
let atom_B : Term.term = Term.ps_app prop_var_B []
let fmla2 : Term.term =
  Term.t_implies (Term.t_and atom_A atom_B) atom_A
let () = printf "@[formula 2 is:@ %a@]@." Pretty.print_term fmla2
77
\end{ocamlcode}
MARCHE Claude's avatar
MARCHE Claude committed
78 79 80

As expected, the output is as follows.
\begin{verbatim}
81
formula 2 is: A /\ B -> A
MARCHE Claude's avatar
MARCHE Claude committed
82
\end{verbatim}
Andrei Paskevich's avatar
Andrei Paskevich committed
83 84 85 86
Notice that the concrete syntax of \why forbids function and predicate
names to start with a capital letter (except for the algebraic type
constructors which must start with one). This constraint is not enforced
when building those directly using library calls.
87

MARCHE Claude's avatar
roadmap  
MARCHE Claude committed
88
\section{Building Tasks}
89 90 91 92 93

Let's see how we can call a prover to prove a formula. As said in
previous chapters, a prover must be given a task, so we need to build
tasks from our formulas. Task can be build incrementally from an empty
task by adding declaration to it, using the functions
94
\texttt{add\_*\_decl} of module \texttt{Task}. For the formula $true \lor
95
false$ above, this is done as follows.
96
\begin{ocamlcode}
97
let task1 : Task.task = None (* empty task *)
98 99 100
let goal_id1 : Decl.prsymbol =
  Decl.create_prsymbol (Ident.id_fresh "goal1")
let task1 : Task.task =
101
  Task.add_prop_decl task1 Decl.Pgoal goal_id1 fmla1
102
\end{ocamlcode}
103
To make the formula a goal, we must give a name to it, here ``goal1''. A
104 105
goal name has type \texttt{prsymbol}, for identifiers denoting
propositions in a theory or a task. Notice again that the concrete
MARCHE Claude's avatar
MARCHE Claude committed
106
syntax of \why requires these symbols to be capitalized, but it is not
107 108
mandatory when using the library. The second argument of
\texttt{add\_prop\_decl} is the kind of the proposition:
109 110 111
\texttt{Paxiom}, \texttt{Plemma} or \texttt{Pgoal}
(notice, however, that lemmas are not allowed in tasks
and can only be used in theories).
112 113


114
Once a task is built, it can be printed.
115
\begin{ocamlcode}
116 117
(* printing the task *)
let () = printf "@[task 1 is:@\n%a@]@." Pretty.print_task task1
118
\end{ocamlcode}
119

120
The task for our second formula is a bit more complex to build, because
121
the variables A and B must be added as abstract (\ie not defined)
Andrei Paskevich's avatar
Andrei Paskevich committed
122
propositional symbols in the task.
123
\begin{ocamlcode}
124 125
(* task for formula 2 *)
let task2 = None
Andrei Paskevich's avatar
Andrei Paskevich committed
126 127
let task2 = Task.add_param_decl task2 prop_var_A
let task2 = Task.add_param_decl task2 prop_var_B
128
let goal_id2 = Decl.create_prsymbol (Ident.id_fresh "goal2")
129 130
let task2 = Task.add_prop_decl task2 Decl.Pgoal goal_id2 fmla2
let () = printf "@[task 2 is:@\n%a@]@." Pretty.print_task task2
131
\end{ocamlcode}
132 133 134 135 136

Execution of our OCaml program now outputs:
\begin{verbatim}
task 1 is:
theory Task
137
  goal Goal1 : true \/ false
138 139 140 141
end

task 2 is:
theory Task
142
  predicate A
143

144
  predicate B
145

146
  goal Goal2 : A /\ B -> A
147 148 149 150
end
\end{verbatim}

\section{Calling External Provers}
MARCHE Claude's avatar
doc  
MARCHE Claude committed
151

152
To call an external prover, we need to access the Why configuration
153
file \texttt{why3.conf}, as it was built using the \texttt{why3config}
154 155 156
command line tool or the \textsf{Detect Provers} menu of the graphical
IDE. The following API calls allow to access the content of this
configuration file.
157
\begin{ocamlcode}
158 159 160 161 162
(* reads the config file *)
let config : Whyconf.config = Whyconf.read_config None
(* the [main] section of the config file *)
let main : Whyconf.main = Whyconf.get_main config
(* all the provers detected, from the config file *)
163
let provers : Whyconf.config_prover Whyconf.Mprover.t =
164
  Whyconf.get_provers config
165
\end{ocamlcode}
166 167 168 169 170
The type \texttt{'a Whyconf.Mprover.t} is a map indexed by provers. A
provers is a record with a name, a version and an alternative description
(if someone want to compare different command line options of the same
provers for example). It's definition is in the module
\texttt{Whyconf} :
171
\begin{ocamlcode}
172 173 174 175 176
type prover =
    { prover_name : string; (* "Alt-Ergo" *)
      prover_version : string; (* "2.95" *)
      prover_altern : string; (* "special" *)
    }
177
\end{ocamlcode}
178 179
The map \texttt{provers} provides the set of existing provers.
In the following, we directly
MARCHE Claude's avatar
MARCHE Claude committed
180 181
attempt to access the prover Alt-Ergo, which is known to be identified
with id \texttt{"alt-ergo"}.
182
\begin{ocamlcode}
183
(* the [prover alt-ergo] section of the config file *)
184
let alt_ergo : Whyconf.config_prover =
185
  try
186 187 188 189
    Whyconf.prover_by_id config "alt-ergo"
  with Whyconf.ProverNotFound _ ->
    eprintf "Prover alt-ergo not installed or not configured@.";
    exit 0
190
\end{ocamlcode}
191
We could also get a specific version with :
192
\begin{ocamlcode}
193 194 195 196 197 198
let alt_ergo : Whyconf.config_prover =
  try
    let prover = {Whyconf.prover_name = "Alt-Ergo";
                  prover_version = "0.92.3";
                  prover_altern = ""} in
    Whyconf.Mprover.find prover provers
199 200 201
  with Not_found ->
    eprintf "Prover alt-ergo not installed or not configured@.";
    exit 0
202
\end{ocamlcode}
MARCHE Claude's avatar
doc  
MARCHE Claude committed
203

MARCHE Claude's avatar
MARCHE Claude committed
204 205 206
The next step is to obtain the driver associated to this prover. A
driver typically depends on the standard theories so these should be
loaded first.
207
\begin{ocamlcode}
208
(* builds the environment from the [loadpath] *)
209
let env : Env.env =
210
  Env.create_env (Whyconf.loadpath main)
211
(* loading the Alt-Ergo driver *)
212
let alt_ergo_driver : Driver.driver =
213 214 215 216 217 218
  try
    Driver.load_driver env alt_ergo.Whyconf.driver
  with e ->
    eprintf "Failed to load driver for alt-ergo: %a@."
      Exn_printer.exn_printer e;
    exit 1
219
\end{ocamlcode}
220 221 222

We are now ready to call the prover on the tasks. This is done by a
function call that launches the external executable and waits for its
223
termination. Here is a simple way to proceed:
224
\begin{ocamlcode}
225 226
(* calls Alt-Ergo *)
let result1 : Call_provers.prover_result =
227 228 229
  Call_provers.wait_on_call
    (Driver.prove_task ~command:alt_ergo.Whyconf.command
    alt_ergo_driver task1 ()) ()
230
(* prints Alt-Ergo answer *)
231
let () = printf "@[On task 1, alt-ergo answers %a@]@."
232
  Call_provers.print_prover_result result1
233
\end{ocamlcode}
234
This way to call a prover is in general too naive, since it may never
MARCHE Claude's avatar
MARCHE Claude committed
235 236 237 238 239
return if the prover runs without time limit. The function
\texttt{prove\_task} has two optional parameters: \texttt{timelimit}
is the maximum allowed running time in seconds, and \texttt{memlimit}
is the maximum allowed memory in megabytes.  The type
\texttt{prover\_result} is a record with three fields:
240
\begin{itemize}
241
\item \texttt{pr\_answer}: the prover answer, explained below;
242
\item \texttt{pr\_output}: the output of the prover, \ie both
MARCHE Claude's avatar
MARCHE Claude committed
243
  standard output and the standard error of the process
244
  (a redirection in \texttt{why3.conf} is required);
245
\item \texttt{pr\_time} : the time taken by the prover, in seconds.
246
\end{itemize}
247
A \texttt{pr\_answer} is a sum of several kind of answers:
248 249 250
\begin{itemize}
\item \texttt{Valid}: the task is valid according to the prover.
\item \texttt{Invalid}: the task is invalid.
251
\item \texttt{Timeout}: the prover exceeds the time or memory limit.
MARCHE Claude's avatar
MARCHE Claude committed
252
\item \texttt{Unknown} $msg$: the prover can't determine if the task
253
  is valid; the string parameter $msg$ indicates some extra
MARCHE Claude's avatar
MARCHE Claude committed
254
  information.
255
\item \texttt{Failure} $msg$: the prover reports a failure, \ie it
MARCHE Claude's avatar
MARCHE Claude committed
256 257
  was unable to read correctly its input task.
\item \texttt{HighFailure}: an error occurred while trying to call the
258
  prover, or the prover answer was not understood (\ie none of the
259 260
  given regular expressions in the driver file matches the output
  of the prover).
261
\end{itemize}
MARCHE Claude's avatar
MARCHE Claude committed
262 263
Here is thus another way of calling the Alt-Ergo prover, on our second
task.
264
\begin{ocamlcode}
265
let result2 : Call_provers.prover_result =
266 267
   Call_provers.wait_on_call
    (Driver.prove_task ~command:alt_ergo.Whyconf.command
268
    ~timelimit:10
269
    alt_ergo_driver task2 ()) ()
270

271
let () =
272
  printf "@[On task 2, alt-ergo answers %a in %5.2f seconds@."
273
    Call_provers.print_prover_answer
274 275
    result1.Call_provers.pr_answer
    result1.Call_provers.pr_time
276
\end{ocamlcode}
277 278 279 280 281 282 283
The output of our program is now as follows.
\begin{verbatim}
On task 1, alt-ergo answers Valid (0.01s)
On task 2, alt-ergo answers Valid in  0.01 seconds
\end{verbatim}

\section{Building Terms}
MARCHE Claude's avatar
MARCHE Claude committed
284 285 286 287 288

An important feature of the functions for building terms and formulas
is that they statically guarantee that only well-typed terms can be
constructed.

289
Here is the way we build the formula $2+2=4$. The main difficulty is to
290 291
access the internal identifier for addition: it must be retrieved from
the standard theory \texttt{Int} of the file \texttt{int.why} (see
MARCHE Claude's avatar
MARCHE Claude committed
292
Chap~\ref{chap:library}).
293
\begin{ocamlcode}
294 295 296 297
let two : Term.term = 
  Term.t_const (Number.ConstInt (Number.int_const_dec "2"))
let four : Term.term = 
  Term.t_const (Number.ConstInt (Number.int_const_dec "4"))
298
let int_theory : Theory.theory =
299
  Env.find_theory env ["int"] "Int"
300
let plus_symbol : Term.lsymbol =
301
  Theory.ns_find_ls int_theory.Theory.th_export ["infix +"]
302 303
let two_plus_two : Term.term =
  Term.t_app_infer plus_symbol [two;two]
Andrei Paskevich's avatar
Andrei Paskevich committed
304
let fmla3 : Term.term = Term.t_equ two_plus_two four
305
\end{ocamlcode}
306 307 308
An important point to notice as that when building the application of
$+$ to the arguments, it is checked that the types are correct. Indeed
the constructor \texttt{t\_app\_infer} infers the type of the resulting
309
term. One could also provide the expected type as follows.
310
\begin{ocamlcode}
311
let two_plus_two : Term.term =
Andrei Paskevich's avatar
Andrei Paskevich committed
312
  Term.fs_app plus_symbol [two;two] Ty.ty_int
313
\end{ocamlcode}
314

315 316
When building a task with this formula, we need to declare that we use
theory \texttt{Int}:
317
\begin{ocamlcode}
318 319
let task3 = None
let task3 = Task.use_export task3 int_theory
320
let goal_id3 = Decl.create_prsymbol (Ident.id_fresh "goal3")
321
let task3 = Task.add_prop_decl task3 Decl.Pgoal goal_id3 fmla3
322
\end{ocamlcode}
323 324 325

\section{Building Quantified Formulas}

326 327 328
To illustrate how to build quantified formulas, let us consider
the formula $\forall x:int. x*x \geq 0$. The first step is to
obtain the symbols from \texttt{Int}.
329
\begin{ocamlcode}
330 331
let zero : Term.term = 
  Term.t_const (Number.ConstInt (Number.int_const_dec "0"))
332
let mult_symbol : Term.lsymbol =
333
  Theory.ns_find_ls int_theory.Theory.th_export ["infix *"]
334
let ge_symbol : Term.lsymbol =
335
  Theory.ns_find_ls int_theory.Theory.th_export ["infix >="]
336
\end{ocamlcode}
337
The next step is to introduce the variable $x$ with the type int.
338
\begin{ocamlcode}
339
let var_x : Term.vsymbol =
340
  Term.create_vsymbol (Ident.id_fresh "x") Ty.ty_int
341
\end{ocamlcode}
342
The formula $x*x \geq 0$ is obtained as in the previous example.
343
\begin{ocamlcode}
344
let x : Term.term = Term.t_var var_x
345
let x_times_x : Term.term = Term.t_app_infer mult_symbol [x;x]
Andrei Paskevich's avatar
Andrei Paskevich committed
346
let fmla4_aux : Term.term = Term.ps_app ge_symbol [x_times_x;zero]
347
\end{ocamlcode}
348
To quantify on $x$, we use the appropriate smart constructor as follows.
349
\begin{ocamlcode}
350
let fmla4 : Term.term = Term.t_forall_close [var_x] [] fmla4_aux
351
\end{ocamlcode}
352

MARCHE Claude's avatar
MARCHE Claude committed
353 354
\section{Building Theories}

355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430
We illustrate now how one can build theories. Building a theory must
be done by a sequence of calls:
\begin{itemize}
\item creating a theory ``under construction'', of type \verb|Theory.theory_uc| ;
\item adding declarations, one at a time ;
\item closing the theory under construction, obtaining something of type \verb|Theory.theory|.
\end{itemize}

Creation of a theory named \verb|My_theory| is done by:
\begin{ocamlcode}
let my_theory : Theory.theory_uc = 
  Theory.create_theory (Ident.id_fresh "My_theory")
\end{ocamlcode}

First let's add the formula 1 above as a goal:
\begin{ocamlcode}
let decl_goal1 : Decl.decl =
  Decl.create_prop_decl Decl.Pgoal goal_id1 fmla1 
let my_theory : Theory.theory_uc =
  Theory.add_decl my_theory decl_goal1
\end{ocamlcode}
Note that we reused the goal identifier \verb|goal_id1| that we
already defined to create task 1 above.

Adding formula 2 needs to add the declarations of predicate variables A
and B first:
\begin{ocamlcode}
let my_theory : Theory.theory_uc = 
  Theory.add_param_decl my_theory prop_var_A 
let my_theory : Theory.theory_uc = 
  Theory.add_param_decl my_theory prop_var_B 
let decl_goal2 : Decl.decl =
  Decl.create_prop_decl Decl.Pgoal goal_id2 fmla2 
let my_theory : Theory.theory_uc = Theory.add_decl my_theory decl_goal2
\end{ocamlcode}

Adding formula 3 is a bit more complex since it uses integers, thus it
requires to ``use'' the theory \verb|int.Int|. Using a theory is
indeed not a primitive operation in the API: it must be done by a
combination of an ``export'' and the creation of a namespace. We
provide a helper function for that:
\begin{ocamlcode}
(* [use th1 th2] insert the equivalent of a "use import th2" in
  theory th1 under construction *) 
let use th1 th2 = 
  let name = th2.Theory.th_name in 
  Theory.close_namespace 
    (Theory.use_export 
      (Theory.open_namespace th1 name.Ident.id_string) th2) true
\end{ocamlcode}
Addition of formula 3 is then
\begin{ocamlcode}
let my_theory : Theory.theory_uc = use my_theory int_theory
let decl_goal3 : Decl.decl = 
  Decl.create_prop_decl Decl.Pgoal goal_id3 fmla3
let my_theory : Theory.theory_uc = 
  Theory.add_decl my_theory decl_goal3  
\end{ocamlcode}

Addition of goal 4 is nothing more complex:
\begin{ocamlcode}
let decl_goal4 : Decl.decl = 
  Decl.create_prop_decl Decl.Pgoal goal_id4 fmla4
let my_theory : 
  Theory.theory_uc = Theory.add_decl my_theory decl_goal4  
\end{ocamlcode}

Finally, we close our theory under construction as follows.
\begin{ocamlcode}
let my_theory : Theory.theory = Theory.close_theory my_theory  
\end{ocamlcode}

We can inspect what we did for example by printing that theory:
\begin{ocamlcode}
let () = printf "@[theory is:@\n%a@]@." Pretty.print_theory my_theory
\end{ocamlcode}
431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
which outputs
\begin{verbatim}
theory is:
theory My_theory
  (* use BuiltIn *)
  
  goal goal1 : true \/ false
  
  predicate A
  
  predicate B
  
  goal goal2 : A /\ B -> A
  
  (* use int.Int *)
  
  goal goal3 : (2 + 2) = 4
  
  goal goal4 : forall x:int. (x * x) >= 0
end
\end{verbatim}
452 453 454 455 456 457 458

From a theory, one can compute at once all the proof tasks it contains
as follows:
\begin{ocamlcode}
let my_tasks : Task.task list = 
  List.rev (Task.split_theory my_theory None None)
\end{ocamlcode}
459 460
Note that the tasks are returned in reverse order, so we reverse the
list above.
461 462 463 464 465 466 467 468 469 470 471 472 473

We can check our generated tasks by printing them:
\begin{ocamlcode}
let () = 
  printf "Tasks are:@.";
  let _ =
    List.fold_left
      (fun i t -> printf "Task %d: %a@." i Pretty.print_task t; i+1)
      1 my_tasks
  in ()
\end{ocamlcode}

One can run provers on those tasks exactly as we did above.
474

MARCHE Claude's avatar
doc  
MARCHE Claude committed
475 476
\section{Applying transformations}

MARCHE Claude's avatar
MARCHE Claude committed
477
[TO BE COMPLETED]
478 479 480

\section{Writing new functions on term}

MARCHE Claude's avatar
MARCHE Claude committed
481 482 483
[TO BE COMPLETED]
% pattern-matching on terms, opening a quantifier

484 485
\section{Proof sessions}

Andrei Paskevich's avatar
Andrei Paskevich committed
486
See the example \url{examples/use_api/create_session.ml} of the distribution for
487
an illustration on how to manipulate proof sessions from an OCaml program.
488

MARCHE Claude's avatar
MARCHE Claude committed
489 490


491

MARCHE Claude's avatar
doc  
MARCHE Claude committed
492 493 494 495 496
%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: "manual"
%%% End: