\title{Brokers and Web-Services for Automatic Deduction: a Case Study}
-\author{Claudio Sacerdoti Coen \and Stefano Zacchiroli}
+\author{
+ Claudio Sacerdoti Coen\thanks{Partially supported by `MoWGLI: Math on the Web, Get it by Logic and Interfaces', EU IST-2001-33562} \and
+ Stefano Zacchiroli\thanks{Partially supported by `MyThS: Models and Types for Security in Mobile Distributed Systems', EU FET-GC IST-2001-32617}}
\institute{
Department of Computer Science\\
\begin{abstract}
We present a planning broker and several Web-Services for automatic deduction.
Each Web-Service implements one of the tactics usually available in
- interactive proof-assistants. When the broker is submitted a "proof status" (an
- incomplete proof tree and a focus on an open goal) it dispatches the proof to
- the Web-Services, collects the successful results, and send them back to the
- client as "hints" as soon as they are available.
+ interactive proof-assistants. When the broker is submitted a ``proof status''
+ (an incomplete proof tree and a focus on an open goal) it dispatches the proof
+ to the Web-Services, collects the successful results, and send them back to
+ the client as ``hints'' as soon as they are available.
In our experience this architecture turns out to be helpful both for
experienced users (who can take benefit of distributing heavy computations)
and output.
The big challenge for the next future is to provide stable and reliable
- services over this disorganized, unreliable and ever-evolving architecture.
- The standard solution is to provide a further level of
- stable services (called \emph{brokers}) that behave as common gateways/addresses
- for client applications to access a wide variety of services and abstract over
- them.
+ services over this disorganized, unreliable, and ever-evolving architecture.
+ The standard solution is to provide a further level of stable services (called
+ \emph{brokers}) that behave as common gateways/addresses for client
+ applications to access a wide variety of services and abstract over them.
Since the \emph{Declaration of Linz}, the MONET
Consortium\footnote{\url{http://monet.nag.co.uk/cocoon/monet/index.html}}
Proof-planners, proof-assistants, CAS and
domain-specific problem solvers are natural candidates to be clients of these
services. Nevertheless, so far the number of examples in the literature has
- been extremely low and the concrete benefits are still to be assessed.
+ been insufficient to fully assess the concrete benefits of this framework.
In this paper we present an architecture, namely \hbugs{}, implementing a
\emph{suggestion engine} for the proof assistant developed on behalf of the
suggest possible ways to proceed in a proof. The tutors are orchestrated
by a broker (a \ws{} itself) that is able to dispatch a proof
status from a client (the proof-assistant) to the tutors;
- each tutor try to make progress in the proof and, in case
- of success, notify the client that shows an \emph{hint} to the user.
+ each tutor tries to make progress in the proof and, in case
+ of success, notifies the client that shows an \emph{hint} to the user.
The broker is an instance of the homonymous entity of the MONET framework.
The tutors are MONET services. Another \ws{} (which is not described in this
paper and which is called Getter \cite{zack}) is used to locate and download
mathematical entities; the Getter plays the role of the Mathematical Object
- Manager in the MONET framework.
+ Manager of the MONET framework.
A precursor of \hbugs{} is the \OmegaAnts{} project
\cite{omegaants1,omegaants2}, which provided similar functionalities to the
\Omegapp{} proof-planner \cite{omega}. The main architectural difference
- between \hbugs{} and \OmegaAnts{} are that the latter is based on a
+ between \hbugs{} and \OmegaAnts{} is that the latter is based on a
black-board architecture and it is not implemented using \wss{} and
brokers.
In Sect. \ref{architecture} we present the architecture of \hbugs{}.
- An usage session is shown in Sect. \ref{usage}.
+ A usage session is shown in Sect. \ref{usage}.
Further implementation details are given in Sect. \ref{implementation}.
Sect. \ref{tutors} is an overview of the tutors that have been implemented.
As usual, the final section of this paper is devoted to conclusions and future works.
In this section we detail the role and requirements of each kind of
actors and discuss about the correspondences between them and the MONET
entities described in \cite{MONET-Overview}.
+ Due to lack of space, we cannot compare our framework to similar proposals, as
+ the older and more advanced \Omegapp{} system. The study of the
+ correspondences with MONET is well motivated by the fact that the MONET
+ framework is still under development and that our implementation is one of the
+ first experiments in \ws-based distributed reasoning. On the other hand, the
+ comparison with \Omegapp{} is less interesting since the functionalities we
+ provide so far are clearly a subset of the \OmegaAnts ones.
\paragraph{Clients}
An \hbugs{} client is a software component able to produce \emph{proof
A proof status is a representation of an incomplete proof and is supposed to
be informative enough to be used by an interactive proof assistant. No
additional requirements exist on the proof status, but there should be an
- agreement on its format between clients and tutors. An hint is an
+ agreement on its format between clients and tutors. A hint is an
encoding of a step that can be performed in order to proceed in an
incomplete proof. Usually it represents a reference to a tactic available
on some proof assistant along with an instantiation for its formal
- parameters. More structured hints can also be used: an hint can be
+ parameters. More structured hints can also be used: a hint can be
as complex as a whole proof-plan.
Using W3C's terminology \cite{ws-glossary}, clients act both as \ws{}
- providers and requesters, see Fig. \ref{interfaces}.
- They act as providers for the broker (to receive hints)
- and as requesters (to submit new status). Clients
- additionally use broker service to know which tutors are available and to
- subscribe to one or more of them.
+ providers and requesters, see Fig. \ref{interfaces}. They act as providers
+ for the broker (to receive hints) and as requesters (to submit new status).
+ Clients additionally use broker services to know which tutors are available
+ and to subscribe to one or more of them.
Usually, when the client role is taken by an interactive proof assistant,
new status are sent to the broker as soon as the proof change (e.g. when the
user applies a tactic or when a new proof is started) and hints are shown to
- the user be the means of some effect in the user interface (e.g. popping a
+ the user by the means of some effects in the user interface (e.g. popping a
dialog box or enlightening a tactic button).
\hbugs{} clients act as MONET clients and ask brokers to provide access to a
set of services (the tutors). \hbugs{} has no actors corresponding to
MONET's Broker Locating Service (since the client is supposed to know the
- URI of at least one broker). The \hbugs{} client and tutors contact the
+ URI of at least one broker). The \hbugs{} clients and tutors contact the
Getter (a MONET Mathematical Object Manager) to locate and retrieve
- mathematical items in the \helm{} library.
+ mathematical items from the \helm{} library.
The proof status that are exchanged
by the \hbugs{} actors, instead, are built on the fly and are neither
stored nor given an unique identifier (URI) to be managed by the
for the client (its URL) and an unique identifier for the broker (its
URL).
+ Notice that \hbugs{} brokers have no knowledge of the domain area of
+ proof-assistants, nor they are able to interpret the messages that they
+ are forwarding. They are indeed only in charge of maintaining the
+ abstraction of several reasoning blackboards --- one for each client ---
+ of capacity one: a blackboard is created when the client submits a problem;
+ it is then ``shared'' by the client and all the tutors until the client
+ submits a new problem. Replacing the client with a CAS and all the tutors
+ with agents implementing different resolution methods for differential
+ equations would not require any change in the broker. Notice, however,
+ that all the tutors must expose the same interface to the broker.
+
The MONET architecture specification does not state explicitly whether
the service and broker answers can be asynchronous. Nevertheless, the
described information flow implicitly suggests a synchronous implementation.
appropriate actor's method.
\paragraph{Tutors}
- Tutors are software component able to consume proof status producing hints.
+ Tutors are software components able to consume proof status producing hints.
\hbugs{} does not specify by which means hints should be produced: tutors
can use any means necessary (heuristics, external theorem prover or CAS,
- etc.). The only requirement is that there exists an agreement on the
- formats of proof status and hints.
+ etc.). The only requirement is that there exists an agreement on the formats
+ of proof status and hints.
Tutors act both as \ws{} providers and requesters for the broker, see Fig.
\ref{interfaces}. As
providers, they wait for commands requesting to start a new \musing{} on
a given proof status or to stop an old, out of date, \musing{}. As
requesters, they signal to the broker the end of a \musing{} along with its
- outcome (an hint in case of success or a failure notification).
+ outcome (a hint in case of success or a failure notification).
\hbugs{} tutors act as MONET services.
one states that the scalar is different from 0; the third lemma (the main
one) asks to prove the equality between the two new members.
% is shown in Fig. \ref{step2} where $?_3[H;x]$ stands for
-% the still unkown scalar argument, which can have only $H$ and $x$ as
+% the still unknown scalar argument, which can have only $H$ and $x$ as
% free variables.
-The user proceeds by istantiating the scalar with the number 2. The
+The user proceeds by instantiating the scalar with the number 2. The
\texttt{Assumption} tutor now suggests to close the second goal (that
states that $2 \neq 0$) by applying the hypothesis $H$.
No useful suggestions, instead, are generated for the main goal
$2*x = 2*((x+1)*(x+1)-1-x*x)*2^{-1}$.
-To proceed in the proof the user needs to symplify the
+To proceed in the proof the user needs to simplify the
expression using the lemma $Rinv\_r\_simpl\_m$ that states that
$\forall x,y.\;y = x * y * x^{-1}$. Since we do not provide yet any tutor
-suggesting symplifications, the user must find out this symplication by
+suggesting simplifications, the user must find out this simplification by
himself. Once she founds it, the goal is reduced to proving that
$2*x = (x+1)*(x+1) - 1 - x*x$. This equality is easily solved by the
\texttt{Ring} tutor, that suggests\footnote{The \texttt{Ring} suggestion is
\item[uri]: an URI chosen by the user at the beginning of the proof
process. Once (and if) proved, that URI will globally identify the term
inside the \helm{} library (given that the user decides to save it).
- \item[thesis]: the thesis of the ongoing proof
+ \item[thesis]: the ongoing proof thesis
\item[proof]: the current incomplete proof tree. It can contain
\emph{metavariables} (holes) that stands for the parts of the proof
that are still to be completed. Each metavariable appearing in the
\end{description}
Each of these information is represented in XML as described in
- \cite{mowglicic}. Additionally, an \hbugs{} status carry the unique
+ \cite{mowglicic}. Additionally, an \hbugs{} status carries the unique
identifier of the current goal, which is the goal the user is currently
focused on. Using this value it is possible to implement different client
side strategies: the user could ask the tutors to work on the goal
she is considering or to work on the other ``background'' goals.
\paragraph{Hints}
- An hint in the \hbugs{} architecture should carry enough information to
+ A hint in the \hbugs{} architecture should carry enough information to
permit the client to progress in the current proof. In our
implementation each hint corresponds to either one of the tactics available
to the user in gTopLevel (together with its actual arguments) or a set
grouping them in a particular XML element.
This feature turns out to be particularly useful for the
\emph{searchPatternApply} tutor (see Sect. \ref{tutors}) that
- query a lemma database and return to the client a list of all lemmas that
+ queries a lemma database and returns to the client a list of all lemmas that
could be used to complete the proof. This particular hint is encoded as a
list of \texttt{Apply} hints, each of them having one of the results as term
argument.
We would like to stress that the \hbugs{} architecture has no dependency
on either the hint or the status representation: the only message parts
that are fixed are those representing the administrative messages
- (the envelops in the \wss{} terminology). In particular, the broker can
+ (the envelopes in the \wss{} terminology). In particular, the broker can
manage at the same time several sessions working on different status/hints
formats. Of course, there must be an agreement between the clients
and the tutors on the format of the data exchanged.
In our implementation the client does not trust the tutors hints:
being encoded as references to available tactics imply
- that an \hbugs{} client, on receipt of an hint, simply try to reply the work
+ that an \hbugs{} client, upon receival of a hint, simply try to replay
+ the work
done by a tutor on the local copy of the proof. The application of the hint
can even fail to type check and the client copy of the proof can be left
undamaged after spotting the error. Note, however, that it is still
possible to implement a complex tutor that looks for a proof doing
backtracking and
- send back to the client an hint whose argument is a witness (a trace) of
+ send back to the client a hint whose argument is a witness (a trace) of
the proof found: the client applies the hint reconstructing (and checking
the correctness of) the proof from the witness, without having to
re-discover the proof itself.
In order to be advertised to clients during the subscription phase, tutors
should register to the broker using the broker's \texttt{Register\_tutor}
method. This method is really similar to \texttt{Register\_client}:
- tutors are required to send an unique identify and a base URI for their
+ tutors are required to send an unique identifier and a base URI for their
\ws{}.
Additionally tutors are required to send an human readable description of
their capabilities; this information could be used by client's user to
- decide which tutors he needs to subscribe to. As the clients, tutors can
+ decide which tutors he wants to subscribe to. As the clients, tutors can
unregister from brokers using \texttt{Unregister\_broker} method.
- Each time the client status change, it get sent sent to the
+ Each time the client status changes, it get sent sent to the
broker using its \texttt{Status} method. Using both clients registry (to
lookup client's subscription) and tutors registry (to check if some tutors
has unsubscribed), the broker is able to decide to which tutors the
using its \texttt{Musing\_completed} method; the broker can now remove the
\musing{} entry from the \musings{} registry and, depending on its outcome,
inform the client. In case of success one of the \texttt{Musing\_completed}
- arguments is an hint to be sent to the client, otherwise there's no need to
+ arguments is a hint to be sent to the client, otherwise there's no need to
inform him and the \texttt{Musing\_completed} method is called
just to update the \musings{} registry.
to maximize code reuse. To develop \wss{} in Objective Caml we have
developed an auxiliary generic library (\emph{O'HTTP}) that can be used to
write HTTP 1.1 Web servers and abstract over GET/POST parsing. This library
- supports different kinds of Web servers architecture, including
+ supports different kinds of Web servers architectures, including
multi-process and multi-threaded ones.} bindings described in
\cite{wsdlbindings}.
\paragraph{Tutors}
- Each tutor expose a \ws{} interface and should be able to work, not only for
+ Each tutor exposes a \ws{} interface and should be able to work, not only for
many different clients referring to a common broker, but also for many
different brokers. The potential high number of concurrent clients imposes
a multi-threaded or multi-process architecture.
Our current implementation is based on a multi threaded architecture
- exploiting the capabilities of the O'HTTP library. Each tutor is composed
- by one thread always running plus
+ exploiting the capabilities of the O'HTTP library \cite{zack}. Each tutor is
+ composed by one thread always running plus
an additional thread for each running \musing{}. One thread is devoted to
listening for incoming \ws{} request; upon correct receiving requests it
pass the control to a second thread, created on the fly, to handle the
If the received request is \texttt{Start\_musing}, a new thread is
spawned to handle it; the thread in duty to handle the HTTP request
returns an HTTP response containing the identifier of the just started
- \texttt{musing}, and then dyes. If the received request is
+ \texttt{musing}, and then dies. If the received request is
\texttt{Stop\_musing}, instead, the spawned thread kills the thread
responsible for the \texttt{musing} whose identifier is the argument
of the \texttt{Stop\_musing} method.
really useful for tactics that rely on a huge but fixed set of lemmas,
as every reflexive tactic.
- The implementation of a tutor with the described architecture is not that
+ The implementation of a tutor within the described architecture is not that
difficult having a language with good threading capabilities (as OCaml has)
and a pool of already implemented tactics (as gTopLevel has).
Still working with threads is known to be really error prone due to
is still quite repetitive: every tutor that wraps a tactic has to
instantiate its own copy of the proof-engine kernel and, for each request,
it has to override its status, guess the tactic arguments, apply the tactic
- and, in case of success, send back an hint with the tactic name and the
+ and, in case of success, send back a hint with the tactic name and the
chosen arguments. Of course, the complex part of the work is guessing the
right arguments. For the simple case of tactics that do not require
any argument, though, we are able to automatically generate the whole
in the tutorial as much as she like, still getting useful suggestions.
Thus the user is allowed to focus on learning how to do a formal proof
instead of wasting efforts trying to remember the interface to the system.
- \item{Tutors for Computationally Expensive Tactics}. Several tactics have
+ \item \emph{Tutors for Computationally Expensive Tactics}. Several tactics have
an unpredictable behavior, in the sense that it is unfeasible to understand
whether they will succeed or they will fail when applied and what will be
their result. Among them, there are several tactics either computationally
- expensive or resources consuming. In the first case, the user is not
+ expensive or resource consuming. In the first case, the user is not
willing to try a tactic and wait for a long time just to understand its
outcome: she would prefer to keep on concentrating on the proof and
have the tactic applied in background and receive out-of-band notification
must be stored both the algorithm used for the reduction and the proof of
correctness of the algorithm, based on the ring axioms. This big proof
and all of its lemmas must be retrieved and loaded in order to apply the
- tactic. The Ring tutor loads and cache all the required theorems the
+ tactic. The Ring tutor loads and caches all the required theorems the
first time it is contacted.
- \item{Intelligent Tutors}. Expert users can already benefit from the previous
+ \item \emph{Intelligent Tutors}. Expert users can already benefit from the previous
class of tutors. Nevertheless, to achieve a significative production gain,
they need more intelligent tutors implementing domain-specific theorem
provers or able to perform complex computations. These tutors are not just
with the \helm{} Search-Engine and looks for lemmas that can be directly
applied.
+ Future works comprise the implementation of new features and tutors, and
+ the embedding of the system in larger test cases. For instance, one
+ interesting case study would be interfacing a CAS as Maple to the
+ \hbugs{} broker, developing at the same time a tutor that implements the
+ Field tactic of Coq, which proves the equality of two expressions in an
+ abstract field by reducing both members to the same normal form. CAS can
+ produce several compact normal forms, which are particularly informative
+ to the user and help in proceeding in a proof. Unfortunately, CAS do not
+ provide any certificate about the correctness of the simplification. On
+ the contrary, the Field tactic certifies the equality of two expressions,
+ but produces normal forms that are hardly a simplification of the original
+ formula. The benefits for the CAS would be obtained by using the Field tutor
+ to certify the CAS simplifications, proving that the Field normal form
+ of an expression is preserved by the simplification.
+ More advanced tutors could exploit the CAS to reduce the
+ goal to compact normal forms \cite{maplemodeforCoq}, making the Field tutor
+ certify the simplification according to the skeptical approach.
+
We have many plans for further developing both the \hbugs{} architecture and
our prototype. Interesting results could be obtained
augmenting the informative content of each suggestion. We can for example
modify the broker so that also negative results are sent back to the client.
Those negative suggestions could be reflected in the user interface by
deactivating commands to narrow the choice of tactics available to the user.
- This approach could be interesting especially for novice users, but require
+ This approach could be interesting especially for novice users, but requires
the client to trust other actors a bit more than in the current approach.
We plan also to add some rating mechanism to the architecture. A first
Our \wss{} still lack a real integration in the MONET architecture,
since we do not provide the different ontologies to describe our problems,
- solutions, queries and services. In the short term, completing this task
+ solutions, queries, and services. In the short term, completing this task
could provide a significative feedback to the MONET consortium and would
enlarge the current set of available MONET actors on the Web. In the long
term, new more intelligent tutors could be developed on top of already
\begin{thebibliography}{01}
\bibitem{ws-glossary} Web Services Glossary, W3C Working Draft, 14 May 2003.\\
- \url{http://www.w3.org/TR/ws-gloss/}
+ \url{http://www.w3.org/TR/2003/WD-ws-gloss-20030514/}
\bibitem{wsdlbindings} Web Services Description Language (WSDL)
Version 1.2: Bindings, W3C Working Draft, 24 January 2003.\\
certified decision procedures. In Martin Abadi and Takahashi Ito, editors,
TACS'97, volume 1281. LNCS, Springer-Verlag, 1997.
+\bibitem{maplemodeforCoq} David Delahaye, Micaela Mayero.
+ A Maple Mode for Coq. Contribution to the Coq library.\\
+ \url{htpp://coq.inria.fr/contribs/MapleMode.html}
+
\bibitem{MONET-Overview} The MONET Consortium, MONET Architecture Overview,
Public Deliverable D04 of the MONET Project.\\
\url{http://monet.nag.co.uk/cocoon/monet/publicsdocs/monet-overview.pdf}
\bibitem{zack} S. Zacchiroli. \emph{Web services per il supporto alla
dimostrazione interattiva}, Master Thesis, University of Bologna, 2002.
-\bibitem{ws3} J. Zimmer and L. Dennis. Inductive Theorem Proving and
- Computer Algebra in the MathWeb Software Bus. In Proceedings of the 10th
- CALCULEMUS Symposium 2002, 3--5 July 2002.
+\bibitem{ws3} J. Zimmer and M. Kohlhase. System Description: The MathWeb
+ Software Bus for Distributed Mathematical Reasoning.
+ In Proceedings of the 18th International Conference on Automated Deduction
+ CADE 18, LNAI 2392, Springer Verlag, 2002.
\bibitem{ws4} R. Zippel. The MathBus. In Workshop on Internet Accessible
Mathematical Computation at ISSAC'99, Vancouver, Canada, July 28--31, 1999.
projects / helm.git / blobdiff