1 \documentclass[runningheads]{llncs}
7 % \myincludegraphics{filename}{place}{width}{caption}{label}
8 \newcommand{\myincludegraphics}[5]{
11 \includegraphics[width=#3]{eps/#1.eps}
18 %\usepackage[show]{ed}
19 %\usepackage{draftstamp}
21 \newcommand{\musing}{\texttt{musing}}
22 \newcommand{\musings}{\texttt{musings}}
23 \newcommand{\ws}{Web-Service}
24 \newcommand{\wss}{Web-Services}
25 \newcommand{\hbugs}{H-Bugs}
26 \newcommand{\helm}{HELM}
27 \newcommand{\Omegapp}{$\Omega$mega}
28 \newcommand{\OmegaAnts}{$\Omega$mega-Ants}
30 \title{Brokers and Web-Services for Automatic Deduction: a Case Study}
33 Claudio Sacerdoti Coen\thanks{Partially supported by `MoWGLI: Math on the Web, Get it by Logic and Interfaces', EU IST-2001-33562} \and
34 Stefano Zacchiroli\thanks{Partially supported by `MyThS: Models and Types for Security in Mobile Distributed Systems', EU FET-GC IST-2001-32617}}
37 Department of Computer Science\\
38 University of Bologna\\
39 Mura Anteo Zamboni 7, 40127 Bologna, ITALY\\
40 \email{sacerdot@cs.unibo.it}
42 Department of Computer Science\\
43 \'Ecole Normale Sup\'erieure\\
44 45, Rue d'Ulm, F-75230 Paris Cedex 05, FRANCE\\
45 \email{zack@cs.unibo.it}
55 We present a planning broker and several Web-Services for automatic deduction.
56 Each Web-Service implements one of the tactics usually available in
57 interactive proof-assistants. When the broker is submitted a "proof status" (an
58 incomplete proof tree and a focus on an open goal) it dispatches the proof to
59 the Web-Services, collects the successful results, and send them back to the
60 client as "hints" as soon as they are available.
62 In our experience this architecture turns out to be helpful both for
63 experienced users (who can take benefit of distributing heavy computations)
64 and beginners (who can learn from it).
67 \section{Introduction}
68 The \ws{} approach at software development seems to be a working solution for
69 getting rid of a wide range of incompatibilities between communicating
70 software applications. W3C's efforts in standardizing related technologies
71 grant longevity and implementations availability for frameworks based on
72 \wss{} for information exchange. As a direct consequence, the number of such
73 frameworks is increasing and the World Wide Web is moving from a disorganized
74 repository of human-understandable HTML documents to a disorganized repository
75 of applications working on machine-understandable XML documents both for input
78 The big challenge for the next future is to provide stable and reliable
79 services over this disorganized, unreliable and ever-evolving architecture.
80 The standard solution is to provide a further level of
81 stable services (called \emph{brokers}) that behave as common gateways/addresses
82 for client applications to access a wide variety of services and abstract over
85 Since the \emph{Declaration of Linz}, the MONET
86 Consortium\footnote{\url{http://monet.nag.co.uk/cocoon/monet/index.html}}
87 is working on the development of a framework, based on the
88 \wss{}/brokers approach, aimed at providing a set of software tools for the
89 advertisement and the discovery of mathematical \wss{}.
90 %CSC This framework turns out to be strongly based on both \wss{} and brokers.
92 Several groups have already developed software bus and
93 services\footnote{The most part of these systems predate the development of
94 \wss. Those systems whose development is still active are slowly being
95 reimplemented as \wss.} providing both computational and reasoning
96 capabilities \cite{ws1,ws2,ws3,ws4}: the first ones are implemented on top of
97 Computer Algebra Systems; the second ones provide interfaces to well-known
99 Proof-planners, proof-assistants, CAS and
100 domain-specific problem solvers are natural candidates to be clients of these
101 services. Nevertheless, so far the number of examples in the literature has
102 been insufficient to fully assess the concrete benefits of this framework.
104 In this paper we present an architecture, namely \hbugs{}, implementing a
105 \emph{suggestion engine} for the proof assistant developed on behalf of the
106 \helm{}\footnote{Hypertextual Electronic Library of Mathematics,
107 \url{http://helm.cs.unibo.it}} project
108 \cite{helm}. We provide several \wss{} (called \emph{tutors}) able to
109 suggest possible ways to proceed in a proof. The tutors are orchestrated
110 by a broker (a \ws{} itself) that is able to dispatch a proof
111 status from a client (the proof-assistant) to the tutors;
112 each tutor try to make progress in the proof and, in case
113 of success, notify the client that shows an \emph{hint} to the user.
114 The broker is an instance of the homonymous entity of the MONET framework.
115 The tutors are MONET services. Another \ws{} (which is not described in this
116 paper and which is called Getter \cite{zack}) is used to locate and download
117 mathematical entities; the Getter plays the role of the Mathematical Object
118 Manager in the MONET framework.
120 A precursor of \hbugs{} is the \OmegaAnts{} project
121 \cite{omegaants1,omegaants2}, which provided similar functionalities to the
122 \Omegapp{} proof-planner \cite{omega}. The main architectural difference
123 between \hbugs{} and \OmegaAnts{} are that the latter is based on a
124 black-board architecture and it is not implemented using \wss{} and
127 In Sect. \ref{architecture} we present the architecture of \hbugs{}.
128 A usage session is shown in Sect. \ref{usage}.
129 Further implementation details are given in Sect. \ref{implementation}.
130 Sect. \ref{tutors} is an overview of the tutors that have been implemented.
131 As usual, the final section of this paper is devoted to conclusions and future works.
133 \section{An \hbugs{} Bird's Eye View}
135 \myincludegraphics{arch}{t}{8cm}{\hbugs{} architecture}{\hbugs{} architecture}
137 The \hbugs{} architecture (depicted in Fig. \ref{arch}) is based on three
138 different kinds of actors: \emph{clients}, \emph{brokers}, and \emph{tutors}.
139 Each actor present one or more \ws{} interfaces to its neighbors \hbugs{}
142 In this section we detail the role and requirements of each kind of
143 actors and discuss about the correspondences between them and the MONET
144 entities described in \cite{MONET-Overview}.
145 Due to lack of space, we cannot compare our framework to similar proposals,
146 as the older and more advanced \Omegapp{} system. The study of the
147 correspondences with MONET is well motivated by the fact that the
148 MONET framework is still under development and that our implementation is
149 one of the first experiments in \ws-based distributed reasoning. On the
150 other hand, the comparison with \Omegapp{} is less interesting since the
151 functionalities we provide so far are clearly a subset of the ones of
155 An \hbugs{} client is a software component able to produce \emph{proof
156 status} and to consume \emph{hints}.
158 A proof status is a representation of an incomplete proof and is supposed to
159 be informative enough to be used by an interactive proof assistant. No
160 additional requirements exist on the proof status, but there should be an
161 agreement on its format between clients and tutors. A hint is an
162 encoding of a step that can be performed in order to proceed in an
163 incomplete proof. Usually it represents a reference to a tactic available
164 on some proof assistant along with an instantiation for its formal
165 parameters. More structured hints can also be used: a hint can be
166 as complex as a whole proof-plan.
168 Using W3C's terminology \cite{ws-glossary}, clients act both as \ws{}
169 providers and requesters, see Fig. \ref{interfaces}.
170 They act as providers for the broker (to receive hints)
171 and as requesters (to submit new status). Clients
172 additionally use broker service to know which tutors are available and to
173 subscribe to one or more of them.
175 Usually, when the client role is taken by an interactive proof assistant,
176 new status are sent to the broker as soon as the proof change (e.g. when the
177 user applies a tactic or when a new proof is started) and hints are shown to
178 the user be the means of some effect in the user interface (e.g. popping a
179 dialog box or enlightening a tactic button).
181 \hbugs{} clients act as MONET clients and ask brokers to provide access to a
182 set of services (the tutors). \hbugs{} has no actors corresponding to
183 MONET's Broker Locating Service (since the client is supposed to know the
184 URI of at least one broker). The \hbugs{} client and tutors contact the
185 Getter (a MONET Mathematical Object Manager) to locate and retrieve
186 mathematical items in the \helm{} library.
187 The proof status that are exchanged
188 by the \hbugs{} actors, instead, are built on the fly and are neither
189 stored nor given an unique identifier (URI) to be managed by the
193 \myincludegraphics{interfaces}{t!}{10cm}{\hbugs{} \wss{} interfaces}
194 {\hbugs{} \wss{} interfaces}
196 Brokers are the key actors of the \hbugs{} architecture since they
197 act as intermediaries between clients and tutors. They behave as \wss{}
198 providers and requesters for \emph{both} clients and tutors, see Fig.
201 With respect to the client, a broker acts as a \ws{} provider, receiving the
202 proof status and forwarding it to one or more tutors.
203 It also acts as a \ws{} requester sending
204 hints to the client as soon as they are available from the tutors.
206 With respect to the tutors, the \ws{} provider role is accomplished by
207 receiving hints as soon as they are produced; as a requester, it is
208 accomplished by asking for computations (\emph{musings} in \hbugs{}
209 terminology) on status received by clients and by stopping already late but
210 still ongoing \musings{}.
212 Additionally brokers keep track of available tutors and clients
215 \hbugs{} brokers act as MONET brokers implementing the following components:
216 Client Manager, Service Registry Manager (keeping track of available
217 tutors), Planning Manager (choosing the available tutors among the ones to
218 which the client is subscribed), Execution Manager. The Service Manager
219 component is not required since the session handler, that identifies
220 a session between a service and a broker, is provided to the service by
221 the broker instead of being received from the service when the session is
222 initialized. In particular, a session is identified by an unique identifier
223 for the client (its URL) and an unique identifier for the broker (its
226 Notice that \hbugs{} brokers have no knowledge of the domain area of
227 proof-assistants, nor they are able to interpret the messages that they
228 are forwarding. They are indeed only in charge of maintaining the
229 abstraction of several reasoning blackboards --- one for each client ---
230 of capacity one: a blackboard is created when the client submits a problem;
231 it is then ``shared'' by the client and all the tutors until the client
232 submits a new problem. Replacing the client with a CAS and all the tutors
233 with agents implementing different resolution methods for differential
234 equations would not require any change in the broker. Notice, however,
235 that all the tutors must expose the same interface to the broker.
237 The MONET architecture specification does not state explicitly whether
238 the service and broker answers can be asynchronous. Nevertheless, the
239 described information flow implicitly suggests a synchronous implementation.
240 On the contrary, in \hbugs{} every request is asynchronous: the connection
241 used by an actor to issue a query is immediately closed; when a service
242 produces an answer, it gives it back to the issuer by calling the
243 appropriate actor's method.
246 Tutors are software component able to consume proof status producing hints.
247 \hbugs{} does not specify by which means hints should be produced: tutors
248 can use any means necessary (heuristics, external theorem prover or CAS,
249 etc.). The only requirement is that there exists an agreement on the
250 formats of proof status and hints.
252 Tutors act both as \ws{} providers and requesters for the broker, see Fig.
254 providers, they wait for commands requesting to start a new \musing{} on
255 a given proof status or to stop an old, out of date, \musing{}. As
256 requesters, they signal to the broker the end of a \musing{} along with its
257 outcome (a hint in case of success or a failure notification).
259 \hbugs{} tutors act as MONET services.
261 \section{An \hbugs{} Session Example}
263 In this section we describe a typical \hbugs{} session. The aim of the
264 session is to solve the following easy exercise:
266 Let $x$ be a generic real number. Using the \helm{} proof-engine,
269 x = \frac{(x+1)*(x+1) - 1 - x*x}{2}
273 Let us suppose that the \hbugs{} broker is already running and that the
274 tutors already registered themselves to the broker.
275 When the user starts \texttt{gTopLevel}, the system registers itself to
276 the broker, that sends back the list of available tutors. By default,
277 \texttt{gTopLevel} notifies to the broker its intention of subscribing to every
278 tutor available. The user can always open a configuration window where she
279 is presented the list of available tutors and she can independently subscribe
280 and unsubscribe the system to each tutor.
282 \myincludegraphics{step1}{t}{12cm}{Example session.}
284 %\myincludegraphics{step2}{t}{4cm}{Example session, snapshot 2.}
285 % {Example session, snapshot 2.}
287 The user can now insert into the system the statement of the theorem and start
288 proving it. Let us suppose that the first step of the user is proving
289 that the denominator 2 is different from 0. Once that this technical result
290 is proven, the user must prove the goal shown in the upper right corner
291 of the window in background in Fig. \ref{step1}.
293 While the user is wondering how to proceed in the proof, the tutors are
294 trying to progress in the proof. After a while, the tutors' suggestions
295 start to appear in the lower part of the \hbugs{} interface window
296 (the topmost window in Fig. \ref{step1}). In this case, the tutors are able
297 to produce 23 hints. The first and not very useful hint suggests to proceed in
298 the proof by exchanging the two sides of the equality.
299 The second hint suggests to reduce both sides of the equality to their normal
300 form by using only reductions which are justified by the ring structure of the
301 real numbers; the two normal forms, though, are so different that the proof is
302 not really simplified.
303 All the residual 21 hints suggest to apply one lemma from the distributed
304 library of \helm{}. The user can look at the statement of the lemma by clicking
307 The user can now look at the list of suggestions and realize that a good one is
308 applying the lemma \texttt{r\_Rmult\_mult} that allows to multiply both equality
309 members by the same scalar\footnote{Even if she does not receive the hint, the
310 user probably already knows that this is the right way to proceed. The
311 difficult part where the hint helps is guessing what is the name of the lemma
313 Double-clicking on the hint automatically applies
314 the lemma, reducing the proof to closing three new goals. The first one asks
315 the user the scalar to use as an argument of the previous lemma; the second
316 one states that the scalar is different from 0; the third lemma (the main
317 one) asks to prove the equality between the two new members.
318 % is shown in Fig. \ref{step2} where $?_3[H;x]$ stands for
319 % the still unknown scalar argument, which can have only $H$ and $x$ as
322 The user proceeds by instantiating the scalar with the number 2. The
323 \texttt{Assumption} tutor now suggests to close the second goal (that
324 states that $2 \neq 0$) by applying the hypothesis $H$.
325 No useful suggestions, instead, are generated for the main goal
326 $2*x = 2*((x+1)*(x+1)-1-x*x)*2^{-1}$.
327 To proceed in the proof the user needs to simplify the
328 expression using the lemma $Rinv\_r\_simpl\_m$ that states that
329 $\forall x,y.\;y = x * y * x^{-1}$. Since we do not provide yet any tutor
330 suggesting simplifications, the user must find out this simplification by
331 himself. Once she founds it, the goal is reduced to proving that
332 $2*x = (x+1)*(x+1) - 1 - x*x$. This equality is easily solved by the
333 \texttt{Ring} tutor, that suggests\footnote{The \texttt{Ring} suggestion is
334 just one of the 22 hints that the user receives. It is the only hint that
335 does not open new goals, but the user right now does not have any way to know
336 that.} to the user how to directly finish the proof.
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
339 % Comandi da dare a gTopLevel %
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
342 % !x.(not (eqT ? (Rplus R1 R1) R0)) -> (eqT ? x (Rdiv (Rminus (Rminus (Rmult (Rplus x R1) (Rplus x R1)) R1) (Rmult x x)) (Rplus R1 R1)))
346 % Simpl (per fare unfold di Rdiv)
348 % (Rmult_assoc (Rplus R1 R1) (Rplus (Rplus (Rmult (Rplus x R1) (Rplus x R1)) (Ropp R1)) (Ropp (Rmult x x))) (Rinv (Rplus R1 R1)))
350 % (Rinv_r_simpl_m (Rplus R1 R1) (Rplus (Rplus (Rmult (Rplus x R1) (Rplus x R1)) (Ropp R1)) (Ropp (Rmult x x))) H)
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
354 \section{Implementation's Highlights}
355 \label{implementation}
356 In this section we present some of the most relevant implementation details of
357 the \hbugs{} architecture.
360 \paragraph{Proof status}
361 In our implementation of the \hbugs{} architecture we used the proof
362 assistant of the \helm{} project (codename ``gTopLevel'') as an \hbugs{}
363 client. Thus we have implemented serialization/deserialization capabilities
364 for its internal status. In order to be able to describe \wss{} that
365 exchange status in WSDL using the XML Schema type system, we have chosen an
366 XML format as the target format for the serialization.
368 % A schematic representation of the gTopLevel internal status is depicted in
370 Each proof is represented by a tuple of four elements:
371 \emph{uri}, \emph{metasenv}, \emph{proof}, \emph{thesis}.
373 % \myincludegraphics{status}{t}{8cm}{gTopLevel proof status}{gTopLevel proof
377 \item[uri]: an URI chosen by the user at the beginning of the proof
378 process. Once (and if) proved, that URI will globally identify the term
379 inside the \helm{} library (given that the user decides to save it).
380 \item[thesis]: the thesis of the ongoing proof
381 \item[proof]: the current incomplete proof tree. It can contain
382 \emph{metavariables} (holes) that stands for the parts of the proof
383 that are still to be completed. Each metavariable appearing in the
384 tree references one element of the metavariables environment
386 \item[metasenv]: the metavariables environment is a list of
387 \emph{goals} (unproved conjectures).
388 In order to complete the proof, the user has to instantiate every
389 metavariable in the proof with a proof of the corresponding goal.
390 Each goal is identified by an unique identifier and has a context
391 and a type (the goal thesis). The context is a list of named
392 hypotheses (declarations and definitions). Thus the context and the goal
393 thesis form a sequent, which is the statement of the proof that will
394 be used to instantiate the metavariable occurrences.
397 Each of these information is represented in XML as described in
398 \cite{mowglicic}. Additionally, an \hbugs{} status carry the unique
399 identifier of the current goal, which is the goal the user is currently
400 focused on. Using this value it is possible to implement different client
401 side strategies: the user could ask the tutors to work on the goal
402 she is considering or to work on the other ``background'' goals.
405 A hint in the \hbugs{} architecture should carry enough information to
406 permit the client to progress in the current proof. In our
407 implementation each hint corresponds to either one of the tactics available
408 to the user in gTopLevel (together with its actual arguments) or a set
409 of alternative suggestions (a list of hints).
411 For tactics that don't require any particular argument (like tactics that
412 apply type constructors or decision procedures)
413 only the tactic name is represented in the hint. For tactics that need
414 terms as arguments (for example the \texttt{Apply} tactic that apply a
415 given lemma) the hint includes a textual representation of them, using the
416 same representation used by the interactive proof assistant when querying
417 user for terms. In order to be transmitted between \wss{}, hints are
420 It is also possible for a tutor to return more hints at once,
421 grouping them in a particular XML element.
422 This feature turns out to be particularly useful for the
423 \emph{searchPatternApply} tutor (see Sect. \ref{tutors}) that
424 query a lemma database and return to the client a list of all lemmas that
425 could be used to complete the proof. This particular hint is encoded as a
426 list of \texttt{Apply} hints, each of them having one of the results as term
429 We would like to stress that the \hbugs{} architecture has no dependency
430 on either the hint or the status representation: the only message parts
431 that are fixed are those representing the administrative messages
432 (the envelops in the \wss{} terminology). In particular, the broker can
433 manage at the same time several sessions working on different status/hints
434 formats. Of course, there must be an agreement between the clients
435 and the tutors on the format of the data exchanged.
437 In our implementation the client does not trust the tutors hints:
438 being encoded as references to available tactics imply
439 that an \hbugs{} client, upon receival of a hint, simply try to replay
441 done by a tutor on the local copy of the proof. The application of the hint
442 can even fail to type check and the client copy of the proof can be left
443 undamaged after spotting the error. Note, however, that it is still
444 possible to implement a complex tutor that looks for a proof doing
446 send back to the client a hint whose argument is a witness (a trace) of
447 the proof found: the client applies the hint reconstructing (and checking
448 the correctness of) the proof from the witness, without having to
449 re-discover the proof itself.
451 An alternative implementation where the tutors are trusted would simply
452 send back to the client a new proof-status. Upon receiving the
453 proof-status, the client would just override its current proof status with
454 the suggested one. In the case of those clients which are implemented
455 using proof-objects (as the Coq proof-assistant, for instance), it is
456 still possible for the client to type-check the proof-object and reject
457 wrong hints. The systems that are not based on proof-objects
458 (as PVS, NuPRL, etc.), instead, have to trust the new proof-status. In this
459 case the \hbugs{} architecture needs at least to be extended with
460 clients-tutors authentication.
462 \paragraph{Registries}
463 Being central in the \hbugs{} architecture, the broker is also responsible
464 of housekeeping operations both for clients and tutors. These operations are
465 implemented using three different data structures called \emph{registries}:
466 clients registry, tutors registry and \musings{} registry.
468 In order to use the suggestion engine a client should register itself to the
469 broker and subscribe to one or more tutors. The registration phase is
470 triggered by the client using the \texttt{Register\_client} method of the
471 broker to send him an unique identifier and its base URI as a
472 \ws{}. After the registration, the client can use broker's
473 \texttt{List\_tutors} method to get a list of available tutors.
474 Eventually the client can subscribe to one or more of these using broker's
475 \texttt{Subscribe} method. Clients can also unregister from brokers using
476 \texttt{Unregister\_client} method.
478 The broker keeps track of both registered clients and clients' subscriptions
479 in the clients registry.
481 In order to be advertised to clients during the subscription phase, tutors
482 should register to the broker using the broker's \texttt{Register\_tutor}
483 method. This method is really similar to \texttt{Register\_client}:
484 tutors are required to send an unique identify and a base URI for their
486 Additionally tutors are required to send an human readable description of
487 their capabilities; this information could be used by client's user to
488 decide which tutors he needs to subscribe to. As the clients, tutors can
489 unregister from brokers using \texttt{Unregister\_broker} method.
491 Each time the client status change, it get sent sent to the
492 broker using its \texttt{Status} method. Using both clients registry (to
493 lookup client's subscription) and tutors registry (to check if some tutors
494 has unsubscribed), the broker is able to decide to which tutors the
495 new status have to be forwarded.
496 % \ednote{CSC: qui o nei lavori futuri parlare
497 % della possibilit\'a di avere un vero brocker che multiplexi le richieste
498 % dei client localizzando i servizi, etc.}
500 The forwarding operation is performed using the \texttt{Start\_musing}
501 method of the tutors, that is a request to start a new computation
502 (\emph{\musing{}}) on a given status. The return value of
503 \texttt{Start\_musing} is a
504 \musing{} identifier that is saved in the \musings{} registry along with
505 the identifier of the client that triggered the \musing{}.
507 As soon as a tutor completes an \musing{}, it informs the broker
508 using its \texttt{Musing\_completed} method; the broker can now remove the
509 \musing{} entry from the \musings{} registry and, depending on its outcome,
510 inform the client. In case of success one of the \texttt{Musing\_completed}
511 arguments is a hint to be sent to the client, otherwise there's no need to
512 inform him and the \texttt{Musing\_completed} method is called
513 just to update the \musings{} registry.
515 Consulting the \musings{} registry, the broker is able to know, at each
516 time, which \musings{} are in execution on which tutor. This peculiarity is
517 exploited by the broker on invocation of the \texttt{Status} method.
518 Receiving a new status from the client implies indeed that the previous
519 status no longer exists and all \musings{} working on it should be stopped:
520 additionally to the already described behavior (i.e. starting new
521 \musings{} on the received status), the broker takes also care of stopping
522 ongoing computation invoking the \texttt{Stop\_musing} method of the tutors.
525 As already discussed, all \hbugs{} actors act as \wss{} offering one or more
526 services to neighbor actors. To grant as most accessibility as possible to
527 our \wss{} we have chosen to bind them using the HTTP/POST\footnote{Given
528 that our proof assistant was entirely developed in the Objective Caml
529 language, we have chosen to develop also \hbugs{} in that language in order
530 to maximize code reuse. To develop \wss{} in Objective Caml we have
531 developed an auxiliary generic library (\emph{O'HTTP}) that can be used to
532 write HTTP 1.1 Web servers and abstract over GET/POST parsing. This library
533 supports different kinds of Web servers architecture, including
534 multi-process and multi-threaded ones.} bindings described in
538 Each tutor expose a \ws{} interface and should be able to work, not only for
539 many different clients referring to a common broker, but also for many
540 different brokers. The potential high number of concurrent clients imposes
541 a multi-threaded or multi-process architecture.
543 Our current implementation is based on a multi threaded architecture
544 exploiting the capabilities of the O'HTTP library. Each tutor is composed
545 by one thread always running plus
546 an additional thread for each running \musing{}. One thread is devoted to
547 listening for incoming \ws{} request; upon correct receiving requests it
548 pass the control to a second thread, created on the fly, to handle the
549 incoming request following the classical one-thread-per-request approach in
551 If the received request is \texttt{Start\_musing}, a new thread is
552 spawned to handle it; the thread in duty to handle the HTTP request
553 returns an HTTP response containing the identifier of the just started
554 \texttt{musing}, and then dyes. If the received request is
555 \texttt{Stop\_musing}, instead, the spawned thread kills the thread
556 responsible for the \texttt{musing} whose identifier is the argument
557 of the \texttt{Stop\_musing} method.
559 This architecture turns out to be scalable and allows the running threads
560 to share the cache of loaded (and type-checked) theorems.
561 As we will explain in Sect. \ref{tutors}, this feature turns out to be
562 really useful for tactics that rely on a huge but fixed set of lemmas,
563 as every reflexive tactic.
565 The implementation of a tutor with the described architecture is not that
566 difficult having a language with good threading capabilities (as OCaml has)
567 and a pool of already implemented tactics (as gTopLevel has).
568 Still working with threads is known to be really error prone due to
569 concurrent programming intrinsic complexity. Moreover, there is a
570 non-neglectable part of code that needs to be duplicated in every tutor:
571 the code to register the tutor to the broker and to handle HTTP requests;
572 the code to manage the creation and termination of threads; and the code for
573 parsing the requests and serializing the answers. As a consequence we
574 have written a generic implementation of a tutor which is parameterized
575 over the code that actually propose the hint and some administrative
576 data (as the port the tutor will be listening to).
578 The generic tutor skeleton is really helpful in writing new tutors.
579 Nevertheless, the code obtained by converting existing tactics into tutors
580 is still quite repetitive: every tutor that wraps a tactic has to
581 instantiate its own copy of the proof-engine kernel and, for each request,
582 it has to override its status, guess the tactic arguments, apply the tactic
583 and, in case of success, send back a hint with the tactic name and the
584 chosen arguments. Of course, the complex part of the work is guessing the
585 right arguments. For the simple case of tactics that do not require
586 any argument, though, we are able to automatically generate the whole
587 tutor code given the tactic name. Concretely, we have written a
588 tactic-based tutor template and a script that parses an XML file with
589 the specification of the tutor and generates the tutor's code.
590 The XML file describes the tutor's port, the code to invoke the tactic,
591 the hint that is sent back upon successful application and a
592 human readable explanation of the tactic implemented by the tutor.
594 \section{The Implemented \hbugs Tutors}
596 To test the \hbugs{} architecture and to assess the utility of a suggestion
597 engine for the end user, we have implemented several tutors. In particular,
598 we have investigated three classes of tutors:
600 \item \emph{Tutors for beginners}. These are tutors that implement tactics
601 which are neither computationally expensive nor difficult to understand:
602 an expert user can always understand if the tactic can be applied or not
603 without having to try it. For example, the following implemented tutors
604 belong to this class:
606 \item \emph{Assumption Tutor}: it ends the proof if the thesis is
607 equivalent\footnote{In our implementation, the equivalence relation
608 imposed by the logical framework is \emph{convertibility}. Two
609 expressions are convertible when they reduce to the same normal form.
610 Two ``equal'' terms depending on free variables can be non-convertible
611 since free variables stop the reduction. For example, $2x$ is convertible
612 with $(3-1)x$ because they both reduce to the same normal form
613 $x + x + 0$; but $2x$ is not convertible to $x2$ since the latter is
614 already in normal form.}
615 to one of the hypotheses\footnote{
616 In some cases, especially when non-trivial computations are involved,
617 the user is totally unable to figure out the convertibility of two terms.
618 In these cases the tutor becomes handy also for expert users.}.
619 \item \emph{Contradiction Tutor}: it ends the proof by \emph{reductio ad
620 adsurdum} if one hypothesis is equivalent to $False$.
621 \item \emph{Symmetry Tutor}: if the goal thesis is an equality, it
622 suggests to apply the commutative property.
623 \item \emph{Left/Right/Exists/Split/Reflexivity/Constructor Tutors}:
624 the Constructor Tutor suggests to proceed in the proof by applying one
625 or more constructors when the goal thesis is an inductive type or a
626 proposition inductively defined according to the declarative
627 style\footnote{An example of a proposition that can be given in
628 declarative style is the $\le$ relation over natural numbers:
629 $\le$ is the smallest relation
630 such that $n \le n$ for every $n$ and $n \le m$ for every $n,m$ such
631 that $n \le p$ where $p$ is the predecessor of $m$. Thus, a proof
632 of $n \le n$ is simply the application of the first constructor to
633 $n$ and a proof of $n \le m$ is the application of the second
634 constructor to $n,m$ and a proof of $n \le m$.}.
635 Since disjunction, conjunction, existential quantification and
636 Leibniz equality are particular cases of inductive propositions,
637 all the other tutors of this class are instantiations of the
638 the Constructor tactic. Left and Right suggest to prove a disjunction
639 by proving its left/right member; Split reduces the proof of a
640 conjunction to the two proof of its members; Exists suggests to
641 prove an existential quantification by providing a
642 witness\footnote{This task is left to the user.}; Reflexivity proves
643 an equality whenever the two sides are convertible.
645 Beginners, when first faced with a tactic-based proof-assistant, get
646 lost quite soon since the set of tactics is large and their names and
647 semantics must be remembered by heart. Tutorials are provided to guide
648 the user step-by-step in a few proofs, suggesting the tactics that must
649 be used. We believe that our beginners tutors can provide an auxiliary
650 learning tool: after the tutorial, the user is not suddenly left alone
651 with the system, but she can experiment with variations of the proof given
652 in the tutorial as much as she like, still getting useful suggestions.
653 Thus the user is allowed to focus on learning how to do a formal proof
654 instead of wasting efforts trying to remember the interface to the system.
655 \item{Tutors for Computationally Expensive Tactics}. Several tactics have
656 an unpredictable behavior, in the sense that it is unfeasible to understand
657 whether they will succeed or they will fail when applied and what will be
658 their result. Among them, there are several tactics either computationally
659 expensive or resources consuming. In the first case, the user is not
660 willing to try a tactic and wait for a long time just to understand its
661 outcome: she would prefer to keep on concentrating on the proof and
662 have the tactic applied in background and receive out-of-band notification
663 of its success. The second case is similar, but the tactic application must
664 be performed on a remote machine to avoid overloading the user host
665 with several concurrent resource consuming applications.
667 Finally, several complex tactics and in particular all the tactics based
668 on reflexive techniques depend on a pretty large set of definitions, lemmas
669 and theorems. When these tactics are applied, the system needs to retrieve
670 and load all the lemmas. Pre-loading all the material needed by every
671 tactic can quickly lead to long initialization times and to large memory
672 footstamps. A specialized tutor running on a remote machine, instead,
673 can easily pre-load the required theorems.
675 As an example of computationally expensive task, we have implemented
676 a tutor for the \emph{Ring} tactic \cite{ringboutin}.
677 The tutor is able to prove an equality over a ring by reducing both members
678 to a common normal form. The reduction, which may require some time in
680 is based on the usual commutative, associative and neutral element properties
681 of a ring. The tactic is implemented using a reflexive technique, which
682 means that the reduction trace is not stored in the proof-object itself:
683 the type-checker is able to perform the reduction on-the-fly thanks to
684 the conversion rules of the system. As a consequence, in the library there
685 must be stored both the algorithm used for the reduction and the proof of
686 correctness of the algorithm, based on the ring axioms. This big proof
687 and all of its lemmas must be retrieved and loaded in order to apply the
688 tactic. The Ring tutor loads and cache all the required theorems the
689 first time it is contacted.
690 \item{Intelligent Tutors}. Expert users can already benefit from the previous
691 class of tutors. Nevertheless, to achieve a significative production gain,
692 they need more intelligent tutors implementing domain-specific theorem
693 provers or able to perform complex computations. These tutors are not just
694 plain implementations of tactics or decision procedures, but can be
695 more complex software agents interacting with third-parties software,
696 such as proof-planners, CAS or theorem-provers.
698 To test the productivity impact of intelligent tutors, we have implemented
699 a tutor that is interfaced with the \helm{}
700 Search-Engine\footnote{\url{http://helm.cs.unibo.it/library.html}} and that
701 is able to look for every theorem in the distributed library that can
702 be applied to proceed in the proof. Even if the tutor deductive power
703 is extremely limited\footnote{We do not attempt to check if the new goals
704 obtained applying a lemma can be automatically proved or, even better,
705 automatically disproved to reject the lemma.}, it is not unusual for
706 the tutor to come up with precious hints that can save several minutes of
707 work that would be spent in proving again already proven results or
708 figuring out where the lemmas could have been stored in the library.
711 \section{Conclusions and Future Work}
713 In this paper we described a suggestion engine architecture for
714 proof-assistants: the client (a proof-assistant) sends the current proof
715 status to several distributed \wss{} (called tutors) that try to progress
716 in the proof and, in case of success, send back an appropriate hint
717 (a proof-plan) to the user. The user, that in the meantime was able to
718 reason and progress in the proof, is notified with the hints and can decide
719 to apply or ignore them. A broker is provided to decouple the clients and
720 the tutors and to allow the client to locate and invoke the available remote
721 services. The whole architecture is an instance of the MONET architecture
722 for Mathematical \wss{}.
724 A running prototype has been implemented as part of the
725 \helm{} project \cite{helm}
726 and we already provide several tutors. Some of them are simple tutors that
727 try to apply one or more tactics of the \helm{} Proof-Engine, which is also
728 our client. We also have a much more complex tutor that is interfaced
729 with the \helm{} Search-Engine and looks for lemmas that can be directly
732 Future works comprise the implementation of new features and tutors, and
733 the embedding of the system in larger test cases. For instance, one
734 interesting case study would be interfacing a CAS as Maple to the
735 \hbugs{} broker, developing at the same time a tutor that implements the
736 Field tactic of Coq, which proves the equality of two expressions in an
737 abstract field by reducing both members to the same normal form. CAS can
738 produce several compact normal forms, which are particularly informative
739 to the user and help in proceeding in a proof. Unfortunately, CAS do not
740 provide any certificate about the correctness of the simplification. On
741 the contrary, the Field tactic certifies the equality of two expressions,
742 but produces normal forms that are hardly a simplification of the original
743 formula. The benefits for the CAS would be obtained by using the Field tutor
744 to certify the CAS simplifications, proving that the Field normal form
745 of an expression is preserved by the simplification.
746 More advanced tutors could exploit the CAS to reduce the
747 goal to compact normal forms \cite{maplemodeforCoq}, making the Field tutor
748 certify the simplification according to the skeptical approach.
750 We have many plans for further developing both the \hbugs{} architecture and
751 our prototype. Interesting results could be obtained
752 augmenting the informative content of each suggestion. We can for example
753 modify the broker so that also negative results are sent back to the client.
754 Those negative suggestions could be reflected in the user interface by
755 deactivating commands to narrow the choice of tactics available to the user.
756 This approach could be interesting especially for novice users, but require
757 the client to trust other actors a bit more than in the current approach.
759 We plan also to add some rating mechanism to the architecture. A first
760 improvement in this direction could be distinguishing between hints that, when
761 applied, are able to completely close one or more goals and
762 tactics that progress in the proof by reducing one or more goals to new goals:
763 the new goals could be false and the proof can be closed only by backtracking.
765 Other heuristics and/or measures could be added to rate
766 hints and show them to the user in a particular order: an interesting one
767 could be a measure that try to minimize the size of the generated proof,
768 privileging therefore non-overkilling solutions \cite{ring}.
770 We are also considering to follow the \OmegaAnts{} path more closely adding
771 ``recursion'' to the system so that the proof status resulting from the
772 application of old hints are cached somewhere and could be used as a starting
773 point for new hint searches. The approach is interesting, but it represents
774 a big shift towards automatic theorem proving: thus we must consider if it is
775 worth the effort given the increasing availability of automation in proof
776 assistants tactics and the ongoing development of \wss{} based on
777 already existent and well developed theorem provers.
779 Even if not strictly part of the \hbugs{} architecture, the graphical user
780 interface (GUI) of our prototype needs a lot of improvement if we would like
781 it to be really usable by novices. In particular, the user is too easily
782 distracted by the tutor's hints that are ``pushed'' to her.
784 Our \wss{} still lack a real integration in the MONET architecture,
785 since we do not provide the different ontologies to describe our problems,
786 solutions, queries and services. In the short term, completing this task
787 could provide a significative feedback to the MONET consortium and would
788 enlarge the current set of available MONET actors on the Web. In the long
789 term, new more intelligent tutors could be developed on top of already
790 existent MONET \wss{}.
792 To conclude, \hbugs{} is a nice experiment meant to understand whether the
793 current \wss{} technology is mature enough to have a concrete and useful
794 impact on the daily work of proof-assistants users. So far, only the tutor
795 that is interfaced with the \helm{} Search-Engine has effectively increased
796 the productivity of experts users. The usefulness of the tutors developed for
797 beginners, instead, need further assessment.
799 \begin{thebibliography}{01}
801 \bibitem{ws-glossary} Web Services Glossary, W3C Working Draft, 14 May 2003.\\
802 \url{http://www.w3.org/TR/2003/WD-ws-gloss-20030514/}
804 \bibitem{wsdlbindings} Web Services Description Language (WSDL)
805 Version 1.2: Bindings, W3C Working Draft, 24 January 2003.\\
806 \url{http://www.w3.org/TR/wsdl12-bindings/}
808 \bibitem{ws1}A. Armando, D. Zini. Interfacing Computer Algebra and
809 Deduction Systems via the Logic Broker Architecture. In Proceedings
810 of the Eighth Calculemus symphosium, St. Andrews, Scotland, 6--7 August 2000.
812 \bibitem{ws2} O. Caprotti. Symbolic Evaluator Service. Project Report of
813 the MathBrocker Project, RISC-Linz, Johannes Kepler University, Linz,
816 \bibitem{helm} A. Asperti, F. Guidi, L. Padovani, C. Sacerdoti Coen, I. Schena.
817 Mathematical Knowledge Management in HELM. In Annals of Mathematics and
818 Artificial Intelligence, 38(1): 27--46, May 2003.
820 \bibitem{omegaants1} C. Benzm\"uller, V. Sorge. O-Ants -- An Open Approach
821 at Combining Interactive and Automated Theorem Proving. In M. Kerber and
822 M. Kohlhase (eds.), Integration of Symbolic and Mechanized Reasoning, pp.
825 \bibitem{omegaants2} C. Benzm\"uller, M. Jamnik, M. Kerber, V. Sorge.
826 Agent-based Mathematical Reasoning. In A. Armando and T. Jebelean (eds.),
827 Electronic Notes in Theoretical Computer Science, (1999) 23(3), Elsevier.
829 \bibitem{omega} C. Benzm\"uller, L. Cheikhrouhou, D. Fehrer, A. Fiedler,
830 X. Huang, M. Kerber, M. Kohlhase, K. Konrad, E. Melis, A. Meier,
831 W. Schaarschmidt, J. Siekmann, V. Sorge. OMEGA: Towards a Mathematical
832 Assistant. In W. McCune (ed), Proceedings of the 14th Conference on
833 Automated Deduction (CADE-14), Springer LNAI vol. 1249, pp. 252--255,
834 Townsville, Australia, 1997.
836 \bibitem{ringboutin} S. Boutin. Using reflection to build efficient and
837 certified decision procedures. In Martin Abadi and Takahashi Ito, editors,
838 TACS'97, volume 1281. LNCS, Springer-Verlag, 1997.
840 \bibitem{maplemodeforCoq} David Delahaye, Micaela Mayero.
841 A Maple Mode for Coq. Contribution to the Coq library.\\
842 \url{htpp://coq.inria.fr/contribs/MapleMode.html}
844 \bibitem{MONET-Overview} The MONET Consortium, MONET Architecture Overview,
845 Public Deliverable D04 of the MONET Project.\\
846 \url{http://monet.nag.co.uk/cocoon/monet/publicsdocs/monet-overview.pdf}
848 \bibitem{mowglicic} C. Sacerdoti Coen. Exportation Module, MoWGLI Deliverable
850 \url{http://mowgli.cs.unibo.it/html\_no\_frames/deliverables/transformation/d2a.html}
852 \bibitem{ring} C. Sacerdoti Coen. Tactics in Modern Proof-Assistants: the
853 Bad Habit of Overkilling. In Supplementary Proceedings of the 14th
854 International Conference TPHOLS 2001, pp. 352--367, Edinburgh.
856 \bibitem{zack} S. Zacchiroli. \emph{Web services per il supporto alla
857 dimostrazione interattiva}, Master Thesis, University of Bologna, 2002.
859 \bibitem{ws3} J. Zimmer and M. Kohlhase. System Description: The MathWeb
860 Software Bus for Distributed Mathematical Reasoning.
861 In Proceedings of the 18th International Conference on Automated Deduction
862 CADE 18, LNAI 2392, Springer Verlag, 2002.
864 \bibitem{ws4} R. Zippel. The MathBus. In Workshop on Internet Accessible
865 Mathematical Computation at ISSAC'99, Vancouver, Canada, July 28--31, 1999.
867 \end{thebibliography}