- several changes in all the parts that made comparisons with MONET

[helm.git] / helm / papers / calculemus-2003 / hbugs-calculemus-2003.tex

\documentclass[runningheads]{llncs}
\pagestyle{headings}
\setcounter{page}{1}
\usepackage{graphicx}
\usepackage{amsfonts}

% \myincludegraphics{filename}{place}{width}{caption}{label}
\newcommand{\myincludegraphics}[5]{
   \begin{figure}[#2]
   \begin{center}
   \includegraphics[width=#3]{eps/#1.eps}
   \caption[#4]{#5}
   \label{#1}
   \end{center}
   \end{figure}
}

\usepackage[show]{ed}
\usepackage{draftstamp}

\newcommand{\musing}{\texttt{musing}}
\newcommand{\musings}{\texttt{musings}}
\newcommand{\ws}{Web-Service}
\newcommand{\wss}{Web-Services}
\newcommand{\hbugs}{H-Bugs}
\newcommand{\helm}{HELM}
\newcommand{\Omegapp}{$\Omega$mega}
\newcommand{\OmegaAnts}{$\Omega$mega-Ants}

\title{Brokers and Web-Services for Automatic Deduction: a Case Study}

\author{Claudio Sacerdoti Coen \and Stefano Zacchiroli}

\institute{
  Department of Computer Science\\
  University of Bologna\\
  Mura Anteo Zamboni 7, 40127 Bologna, ITALY\\
  \email{sacerdot@cs.unibo.it}
  \and
  Department of Computer Science\\
  \'Ecole Normale Sup\'erieure\\
  45, Rue d'Ulm, F-75230 Paris Cedex 05, FRANCE\\
  \email{zack@cs.unibo.it}
}

\date{ }

\begin{document}
\sloppy
\maketitle

\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 an
  interactive proof-assistant. When the broker is submitted a "proof status" (an
  unfinished proof tree and a focus on an open goal) it dispatches the proof to
  the Web-Services, collects the successfull 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 beginners (who can learn from it).
\end{abstract}

\section{Introduction\ednote{Zack: attualmente sembra che posto ne abbiamo: se
la situazione non muta un 10 righe su \helm{} possiamo metterle, non tanto per
la conferenza quanto per i posteri}}
  The \ws{} approach at software development seems to be a working solution for
  getting rid of a wide range of incompatibilities between communicating
  software applications. W3C's efforts in standardizing related technologies
  grant longevity and implementations availability for frameworks based on
  \wss{} for information exchange. As a direct conseguence, the number of such
  frameworks is increasing and the World Wide Web is moving from a disorganized
  repository of human-understandable HTML documents to a disorganized repository
  of applications working on machine-understandable XML documents both for input
  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 \ednote{zack: buhm! :-P} is providing a further level of
  stable services (called \emph{brokers}) that behave as common gateway/address
  for client applications to access a wide variety of services and abstract over
   them.

  \oldpart Since the \emph{Declaration of Linz}, the MONET Consortium \cite{MONET},
  following the guidelines \ednote{guidelines non e' molto appropriato, dato che
  il concetto di broker non e' definito da W3C e co} of the \wss{}/brokers
  approach, is working on the development of a framework aimed at providing a
  set of software tools for the advertisement and discovering of mathematical
  \wss{}.
  \begin{newpart}Since the \emph{Declaration of Linz}, the MONET Consortium
  \cite{MONET}, is working on the development of a framework, based on the
  \wss{}/brokers approac, aimed at providing a set of software tools for the
  advertisement and the discovery of mathematical \wss{}.\end{newpart}
  %CSC This framework turns out to be strongly based on both \wss{} and brokers.

  Several groups have already developed \wss{} providing both computational and
  reasoning capabilities \cite{???,???,???}\ednote{trovare dei puntatori carini
  dalle conferenze calculemus}: the formers are implemented on top of
  Computer Algebra Systems; the latters provide interfaces to well-known
  theorem provers. Proof-planners, proof-assistants, CAS and
  domain-specific problem solvers are natural candidates to be client 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.

  In this paper we present an architecture, namely \hbugs{}, implementing a
  \emph{suggestion engine} for the proof assistant developed on behalf of the
  \helm{} project. We provide several \wss{} (called \emph{tutors}) able to
  suggest possible ways to proceed in a proof. The tutors are orchestrated
  by a broker (a \ws{} itself) that is able to distribute 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.
  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{}) is used to locate and download
  mathematical entities; the Getter plays the role of the Mathematical Object
  Manager in the MONET framework.

  A precursor of \hbugs{} is the \OmegaAnts{} project \cite{???},
  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
  black-board architecture and it is not implemented using \wss{} and
  brokers. Other differences will be detailed in Sect. \ref{conclusions}.

  In Sect. \ref{architecture} we present the architecture of \hbugs{}.
  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 paper ends with the conclusions and future works.
  
\oldpart
{CSC:  Non so se/dove mettere queste parti.
 Zack: per ora facciamo senza e vediamo se/quanto spazio abbiamo, la prima parte
       non e' molto utile, ma la seconda sugli usi tipici di proof assistant
       come ws client si}
{
  Despite of that the proof assistant case seems to be well suited to
  investigate the usage of many different mathematical \wss{}. Indeed: most
  proof assistants are still based on non-client/server architectures, are
  application-centric instead of document-centric, offer a scarce level of
  automation leaving entirely to the user the choice of which macro (usually
  called \emph{tactic}) to use in order to make progress in a proof.

  The average proof assistant can be, for example, a client of a \ws{}\
  interfacing a specific or generic purpose theorem prover, or a client of a
  \ws{} interfacing a CAS to simplify expressions in a particular mathematical
  domain.
}

\section{An \hbugs{} Bird'S Eye View\ednote{Zack: sono in vena di boiate
stasera!}}
\label{architecture}
  \myincludegraphics{arch}{t}{8cm}{\hbugs{} architecture}{\hbugs{} architecture}

  The \hbugs{} architecture (depicted in Fig. \ref{arch}) is based on three
  different kinds of actors: \emph{clients}, \emph{brokers}, and \emph{tutors}.
  Each actor present one or more \ws{} interfaces to its neighbours \hbugs{}
  actors.

  In this section we will detail the role and requirements of each kind of
  actors and discuss about the correspondencies between them and the MONET
  entities described in \cite{MONET-Overview}.

  \paragraph{Clients}
    An \hbugs{} client is a software component able to produce \emph{proof
    status} and to consume \emph{hints}.

    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 a
    representation\ednote{CSC: non c'\'e un sinonimo pi\'u carino? Zack: l'unico
    decente sembra essere nuovamente "suggestion"}
    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
    as complex as a whole proof-plan.

    \myincludegraphics{interfaces}{t}{8cm}{\hbugs{} \wss{} interfaces}{\hbugs{}
    \wss{} interfaces}

    Using W3C's terminology \cite{ws-glossary}, clients act both as \ws{}
    provider and requester, see \ednote{Zack: va bene "see"?, "cfr" credo sia
    solo italiano ...} Fig. \ref{interfaces}.
    They act as providers for the broker (to receive hints)
    and as requesters (to submit new status) \ednote{Zack: non manca il "for"
    anche per i requesters?}. Clients
    additionally use broker service to know which tutors are available and to
    subscribe to one or more of them.

    Usually, when the role of client 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
    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
    Getter (a MONET Mathematical Object Manager) to locate and retrieve
    mathematical items in the HELM library. The proof status that are exchanged
    by the \hbugs{} actors, instead, are built on the fly and are neither
    stored nor are given an unique identifier (URI) to be managed by the
    Getter.

  \paragraph{Brokers}
    Brokers are the key actors of the \hbugs{} architecture since they
    act as intermediaries between clients and tutors. They behave as \wss{}
    providers and requesters for \emph{both} clients and tutors, see Fig.
    \ref{interfaces}.

    With respect to client, a broker act as \ws{} provider, receiving the
    proof status and forwarding it to one or more tutors.
    It also acts as a \ws{} requester sending
    hints to client as soon as they are available from the tutors.

    With respect to tutors, the \ws{} provider role is accomplished by receiving
    hints as soon as they are produced; as a requester one is accomplished
    by requesting computations (\emph{musings} in \hbugs{} terminology) on
    status received by clients and by stopping already late but still
    ongoing \musings{}
    \ednote{CSC: Sta frase va comunque riscritta perch\'e non si capisce una
    mazza. Zack: io intanto ho aggiunto una figura, vorrei pero' un tuo commento
    sulla utilita'/quantita' delle figure ...}

    Additionally brokers keep track of available tutors and clients
    subscriptions.

    \hbugs{} brokers act as MONET brokers implementing the following components:
    Client Manager, Service Registry Manager (keeping track of available
    tutors), Planning Manager (chosing the available tutors among the ones to
    which the client is subscribed), Execution Manager. The Service Manager
    component is not required since the session handler, that identifies
    a session between a service and a broker, is provided to the service by
    the broker instead of being received from the service when it is
    initialized. In particular, a session is identified by an unique identifier
    for the client (its URL) and an unique identifier for the broker (its
    URL).\ednote{CSC: OK, sto barando: \hbugs{} non \'e ancora cos\'i
    multi-sessione. Ma mi sembra la strada che prenderemmo, no?}

    The MONET architecture specification does not state explicitely whether
    the service and broker answers can be asyncronous. Nevertheless, the
    described information flow implicitly suggests a syncronous implementation.
    On the contrary, in \hbugs{} every request is asyncronous: the connection
    used by an actor to issue a query is immediately closed; when a service
    produces an answer, it gives it back to the issuer by calling the
    appropriate actor's method.

  \paragraph{Tutors}
    Tutors are software component able to consume proof status producing hints.
    \hbugs{} doesn't specify by which means hints should be produced: tutors can
    use any means necessary (heuristics, external theorem prover or CAS, ...).
    The only requirement is that exists an agreement on the formats of proof
    status and hints.

    Tutors act both as \ws{} providers and requesters for the broker. 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 notification of failure).

    \hbugs{} tutors act as MONET services.

\section{Implementation's Highlights}
\label{implementation}
\ednote{Zack: l'aspetto grafico di questa parte e' un po' peso, possiamo
aggiungere varie immagini volendo, e.g.: schema dei thread di un tutor, sample
code di un tutor generato automaticamente}
In this section we present some of the most relevant implementation details of
the \hbugs{} architecture.


  \paragraph{Proof status}
    In our implementation of the \hbugs{} architecture we used the proof
    assistant of the \helm{} project (codename ``gTopLevel'') as an \hbugs{}
    client. Thus we have implemented serialization/deserialization capabilities
    fot its internal status. In order to be able to describe \wss{} that
    exchange status in WSDL using the XML Schema type system, we have chosen an
    XML format as the target format for the serialization.

    A schematic representation of the gTopLevel internal status is depicted in
    Fig. \ref{status}. Each proof is representated by a tuple of four elements:
    \emph{uri}, \emph{metasenv}, \emph{proof}, \emph{thesis}.

    \myincludegraphics{status}{t}{8cm}{gTopLevel proof status}{gTopLevel proof
    status}

    \begin{description}
      \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[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 metavariables appearing in the
        tree references one element of the metavariables environment
        (\emph{metasenv}).
      \item[metasenv]: the metavariables environment is a list of
        \emph{goals} (unproved conjectures).
        In order to complete the proof, the user has to instantiate every
        metavariable in the proof with a proof of the corresponding goal.
        Each goal is identified by an unique identifier and has a context
        and a type ( the goal thesis). The context is a list of named
        hypotheses (declarations and definitions). Thus the context and the goal
        thesis form a sequent, which is the statement of the proof that will
        be used to instatiate the metavariable occurrences.
    \end{description}

    Each of these information is represented in XML as described in
    \cite{csc-thesis}. Additionally, an \hbugs{} status carry 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
    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
    of alternative suggestions (a list of hints).

    For tactics that don't require any particular argument (like tactics that
    apply type constructors or try to automatically conclude equality goals)
    only the tactic name is represented in the hint. For tactics that need terms
    as arguments (for example the \emph{Apply} tactic) the hint includes a
    textual representation of them, using the same representation used by the
    interactive proof assistant when querying user for terms. In order to be
    trasmitted between \wss, hints are serialized in XML.

    Actually it is also possible for a tutor to return more hints at once,
    grouping them in a particular XML element.
    This feature turns out to be particulary useful for the
    \emph{searchPatternApply} tutor (Sect. \ref{tutors}) that
    query a term database and return to the client a list of all terms that
    could be used to complete the proof. This particular hint is encoded as a
    list of 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
    manage at the same time several sessions working on different status/hints
    formats. Of couse, 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
    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 possible proof and
    send back to the client an 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.

    An alternative implementation where the tutors are trusted would simply
    send back to the client a new proof-status. Upong receiving the
    proof-status, the client would just override its current proof status with
    the suggested one. In the case of those clients which are implemented
    using proof-objects (as the Coq proof-assistant, for instance), it is
    still possible for the client to type-check the proof-object and reject
    wrong hints. The systems that are not based on proof-objects
    (as PVS, NuPRL, etc.), instead, have to trust the new proof-status. In this
    case the \hbugs{} architecture needs to be extended with clients-tutors
    autentication.
    
  \paragraph{Registries}
    Being central in the \hbugs{} architecture, the broker is also responsible
    of accounting operations both for clients and tutors. These operations are
    implemented using three different data structures called \emph{registries}:
    clients registry, tutors registry and \musings{} registry.

    In order to use the suggestion engine a client should register itself to the
    broker and subscribe to one or more tutors. The registration phase is
    triggered by the client using the \texttt{Register\_client} method of the
    broker to send him an unique identifier and its base URI as a
    \ws{}. After the registration, the client can use broker's
    \texttt{List\_tutors} method to get a list of available tutors.
    Eventually\ednote{CSC: Vuoi veramente dire eventually qui? Zack: si, prima o
    poi lo faranno ...} the
    client can subscribe to one or more of these using broker's \emph{Subscribe}
    method. Clients can also unregister from brokers using
    \texttt{Unregister\_client} method.

    The broker keeps track of both registered clients and clients' subscriptions
    in the clients registry.

    In order to be advertised to clients during the subscription phase, tutors
    should register to the broker using broker's \texttt{Register\_tutor}
    method.  This method is really similar to the \texttt{Register\_client}
    one: tutors are required to send an unique identify 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. Like clients, tutors can
    unregister from brokers using \texttt{Unregister\_broker} method.

    Track of available tutors is kept in the tutors
    registry.\ednote{Non si mette mai un paragrafo lungo meno di una linea!}

    Each time the client status change, the status is sent to the
    broker using its \emph{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
    new status must be forwarded.\ednote{CSC: qui o nei lavori futuri parlare
    della possibilit\'a di avere un vero brocker che multiplexi le richieste
    del tutor localizzando i servizi, etc.}

    The forwarding operation is performed using tutors' \texttt{Start\_musing}
    method, that is a request to start a new computation (\emph{\musing{}}) on a
    given status. The return value for \texttt{Start\_musing} method is a
    \musing{} identifier that is saved in the \musings{} registry along with
    the identifier of the client that triggered the starting of the \musing{}.

    As soon as a \musing{} is completed, the owning tutor informs the broker
    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
    inform him and the \texttt{Musing\_completed} method is called
    just to update the \musings{} registry.

    Consulting the \musings{} registry, the tutor\ednote{CSC: ma \'e vero o
    stai delirando? Zack: e' vero, non ti fidi? :-) Up to delay di rete
    ovviamente ...} is able to know, at each time,
    which \musings{} are in execution on which tutor. This peculiarity is
    exploited by the broker on invocation of Status method. Receiving a new
    status from the client imply indeed that the previous status no longer
    exists and all \musings{} working on it should be stopped: additionally to
    the already described behaviour (i.e. starting new \musings{} on the
    received status), the tutor takes also care of stopping ongoing computation
    invoking \texttt{Stop\_musing} tutors' method.

  \paragraph{\wss{}}
    As already discussed, all \hbugs{} actors act as \wss{} offering one or more
    services to neighbour actors. To grant as most accessibility as possible to
    our \wss{} we have chosen to bind them using the HTTP/POST bindings
    described in \cite{????}\footnote{Given that our proof assistant was
    entirely developed in the Objective Caml language, we have chosen to
    develop also \hbugs{} in that language in order 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 multi-process and multi-threaded ones.}.

  \paragraph{Tutors}
    Each tutor expose 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 two 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 the second always-running thread which handle the pool
    of running \musings{}. When a new \musing{} is requested, a new thread is
    spawned to work them out; when a request to interrupt an old \musing{} is
    received, the thread actually running them is killed freeing its
    resources.\ednote{CSC: A cosa dobbiamo questa architettura delirante? Se non
    ricordo male al problema dell'uccisione dei thread. Ora o si spiega
    il motivo di questa architettura o si glissa/bluffa. Zack: cosa ti sembra
    delirante? che i thread vengono uccisi? ... non mi e' molto chiaro ...}

    This architecture turns out to be scalable and allows the running threads
    to share the cache of loaded (and type-checked) theorems.
    As we will explain in Sect. \ref{tutors}, this feature turns out to be
    really useful for tactics that rely on a huge but fixed set of lemmas,
    as every reflexivite tactic.

    The implementation of a tutor with 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
    concurrent programming intrinsic complexity. Moreover, there is a
    non-neglectable part of code that needs to be duplicated in every tutor:
    the code to register the tutor to the broker and to handle HTTP requests;
    the code to manage the creation and termination of threads; and the code for
    parsing the requests and serializing the answers. As a consequence we
    have written a generic implementation of a tutor which is parameterized
    over the code that actually propose the hint and some administrative
    data (as the port the tutor will be listening to).

    The generic tutor skeleton is really helpful in writing new tutors.
    Nevertheless, the code obtained by converting existing tactics into tutors
    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
    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
    tutor code given the tactic name. Concretely, we have written a
    tactic-based tutor template and a script that parses an XML file with
    the specification of the tutor and generates the tutor's code.
    The XML file holds the tutor's port, the code to invoke the tactic,
    the hint that is sent back upon successfull application and a
    human readable explanation of the tactic implemented by the tutor.

\section{The Implemented \hbugs Tutors}
\label{tutors}
To test the \hbugs{} architecture and to assess the utility of a suggestion
engine for the end user, we have implemented several tutors. In particular,
we have investigated three classes of tutors:
\begin{enumerate}
 \item \emph{Tutors for beginners}. These are tutors that implement tactics
   which are neither computationally expensive nor difficult to understand:
   an expert user can always understand if the tactic can be applied or not
   withouth having to try it. For example, the following implemented tutors
   belong to this class:
    \begin{itemize}
     \item \emph{Assumption Tutor}: it ends the proof if the thesis is
       equivalent\footnote{In our implementation, the equivalence relation
       imposed by the logical framework is \emph{convertibility}. Two
       expressions are convertible when they reduce to the same normal form.
       Two ``equal'' terms depending on free variables can be non-convertible
       since free variables stop the reduction. For example, $2x$ is convertible
       with $(3-1)x$ because they both reduce to the same normal form
       $x + x + 0$; but $2x$ is not convertible to $x2$ since the latter is
       already in normal form.}
       to one of the hypotheses\footnote{
       In some cases, expecially when non-trivial computations are involved,
       the user is totally unable to figure out the convertibility of two terms.
       In these cases the tutor becomes handy also for expert users.}.
     \item \emph{Contradiction Tutor}: it ends the proof by \emph{reductio ad
       adsurdum} if one hypothesis is equivalent to $False$.
     \item \emph{Symmetry Tutor}: if the goal thesis is an equality, it
       suggests to apply the commutative property.
     \item \emph{Left/Right/Exists/Split/Reflexivity/Constructor Tutors}:
       the Constructor Tutor suggests to proceed in the proof by applying one
       or more constructors when the goal thesis is an inductive type or a
       proposition inductively defined according to the declarative
       style\footnote{An example of a proposition that can be given in
       declarative style is the $\le$ relation: $\le$ is the smallest relation
       such that $n \le n$ for every $n$ and $n \le m$ for every $n,m$ such
       that $n \le p$ where $p$ is the predecessor of $m$. Thus, a proof
       of $n \le n$ is simply the application of the first constructor to
       $n$ and a proof of $n \le m$ is the application of the second
       constructor to $n,m$ and a proof of $n \le m$.}.
       Since disjunction, conjunction, existential quantification and
       Leibniz equality are particular cases of inductive propositions,
       all the other tutors of this class are restrictions of the
       the Constructor tactic: Left and Right suggest to prove a disjunction
       by proving its left/right member; Split reduces the proof of a
       conjunction to the two proof of its members; Exists suggests to
       prove an existential quantification by providing a
       witness\footnote{This task is left to the user.}; Reflexivity proves
       an equality whenever the two sides are convertible.
    \end{itemize}
  Beginners, when first faced with a tactic-based proof-assistant, get
  lost quite soon since the set of tactics is large and their names and
  semantics must be remembered by heart. Tutorials are provided to guide
  the user step-by-step in a few proofs, suggesting the tactics that must
  be used. We believe that our beginners tutors can provide an auxiliary
  learning tool: after the tutorial, the user is not suddendly left alone
  with the system, but she can experiment with variations of the proof given
  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
  an unpredictable behaviour, in the sense that it is unfeasible to understand
  wether 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
  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
  of its success. The second case is similar, but the tactic application must
  be performed on a remote machine to avoid overloading the user host
  with several concurrent resource consuming applications.

  Finally, several complex tactics and in particular all the tactics based
  on reflexive techniques depend on a pretty large set of definitions, lemmas
  and theorems. When these tactics are applied, the system needs to retrieve
  and load all the lemmas. Pre-loading all the material needed by every
  tactic can quickly lead to long initialization times and to large memory
  footstamps. A specialized tutor running on a remote machine, instead,
  can easily pre-load the required theorems.

  As an example of computationally expensive task, we have implemented
  a tutor for the \emph{Ring} tactic. The tutor is able to prove an equality
  over a ring by reducing both members to a common normal form. The reduction,
  which may require some time in complex cases,
  is based on the usual commutative, associative and neutral element properties
  of a ring. The tactic is implemented using a reflexive technique, which
  means that the reduction trace is not stored in the proof-object itself:
  the type-checker is able to perform the reduction on-the-fly thanks to
  the conversion rules of the system. As a consequence, in the library there
  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
  first time it is conctacted.
 \item{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
  plain implementations of tactics or decision procedures, but can be
  more complex software agents interacting with third-parties software,
  such as proof-planners, CAS or theorem-provers.

  To test the productivity impact of intelligent tutors, we have implemented
  a tutor that is interfaced with the HELM
  Search-Engine\footnote{\url{http://mowgli.cs.unibo.it/library.html}} and that
  is able to look for every theorem in the distributed library that can
  be applied to proceed in the proof. Even if the tutor deductive power
  is extremely limited\footnote{We do not attempt to check if the new goals
  obtained applying a lemma can be authomatically proved or, even better,
  auhomatically disproved to reject the lemma.}, it is not unusual for
  the tutor to come up with precious hints that can save several minutes of
  work that would be spent in proving again already proven results or
  figuring out where the lemmas could have been stored in the library.
\end{enumerate}

\section{Conclusions and Future Work}
\label{conclusions}
  In this paper we described a suggestion engine architecture for
  proof-assistants: the client (a proof-assistant) sends the current proof
  status to several distributed \wss (called tutors) that try to progress
  in the proof and, in case of success, send back an appropriate hint
  (a proof-plan) to the user. The user, that in the meantime was able to
  reason and progress in the proof, is notified with the hints and can decide
  to apply or ignore them. A broker is provided to decouple the clients and
  the tutors and to allow the client to locate and invoke the available remote
  services. The whole architecture is an instance of the MONET architecture
  for Mathematical \wss.

  A running prototype has been implemented as part of the HELM project \cite{}
  and we already provide several tutors. Some of them are simple tutors that
  try to apply one or more tactics of the HELM Proof-Engine, which is also
  our client. We also have a much more complex tutor that is interfaced
  with the HELM Search-Engine and looks for lemmas that can be directly applied.

  We have many plan for further developing both the \hbugs{} architecture and
  our prototype implementing them. 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 expecially for novice users, but require
  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
  improvement in this direction could be to distinguish between hints that, when
  applied, are able to completely close one or more goals and
  tactics that progress in the proof by reducing one or more goals to new goals:
  the new goals could be false and the proof can be closed only by backtraking.

  Other heuristics and/or measures could be added to rate
  hints and show them to the user in a particular order: an interesting one
  could be a measure that try to minimize the size of the generated proof,
  privileging therefore non-overkilling solutions \cite{ring}.

  We are also considering to follow the \OmegaAnts{} path more closely adding
  ``recursion'' to the system so that proof status resulting from the
  application of old hints are cached somewhere and could be used as a starting
  point for new hint searches. The approach is interesting, but it represents
  a big shift towards automatic theorem proving: thus we must consider if it is
  worth the effort given the increasing availability of automation in proof
  assistants' tactics and the ongoing development of \wss{} based on
  already existent and well developed theorem provers.

  Even if not strictly part of the \hbugs{} architecture, the graphical user
  interface (GUI) of our prototype needs a lot of improvement if we would like
  it to be usable by novices. In particular, the user is too easily distracted
  by the tutor's hints that are ``pushed'' to her.

  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
  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
  existent MONET \wss.

  To conclude, \hbugs{} is a nice experiment meant to understand whether the
  current \wss technology is mature enough to have a concrete and useful impact
  on the daily work of users of proof-assistants. So far, only the tutor that
  is interfaced with the HELM Search-Engine has effectively increased the
  productivity of experts users. The usefullness of the tutors developed for
  beginners, instead, need further assessment.

\begin{thebibliography}{01}

% \bibitem{ALF} The ALF family of proof-assistants:\\
% {\tt http://www.cs.chalmers.se/ComputingScience/Research/\\Logic/implementation.mhtml}
% 
% \bibitem{Coq} The Coq proof-assistant:\\
%  {\tt http://coq.inria.fr/}
% 
% \bibitem{FORMAVIE} The Formavie project:\\
%  {\tt http://http://www-sop.inria.fr/oasis/Formavie/}
% 
% \bibitem{EHELM} The HELM project:\\
%  {\tt http://www.cs.unibo.it/helm/}
% 
% \bibitem{MATHWEB} The MathWeb project:\\
%  {\tt http://www.mathweb.org/}
% 
% \bibitem{PCOQ} The PCoq project:\\
%  {\tt http://www-sop.inria.fr/lemme/pcoq/}
% 
% \bibitem{HELM} A.Asperti, L.Padovani, C.Sacerdoti Coen, I.Schena.
% Towards a library of formal mathematics. Panel session of
% the 13th International Conference on Theorem Proving in Higher Order Logics (TPHOLS'2000),
% Portland, Oregon, USA.
% 
% \bibitem{Ring} S. Boutin. Using reflection to build efficient and certified
%  decision procedures. In Martin Abadi and Takahashi Ito, editors, TACS'97,
%  volume 1281. LNCS, Springer-Verlag, 1997.
% 
% \bibitem{YANNTHESIS} Y.Coscoy. \emph{Explication textuelle de preuves pour le
% Calcul des Constructions Inductives}, PhD. Thesis, Universit\'e de Nice-Sophia
% Antipolis, 2000.
% 
% \bibitem{ALFA} T. Hallgreen, Aarne Ranta. An Extensible Proof Text Editor.
% Presented at LPAR2000.
% 
% \bibitem{Necula} G. Necula, P. Lee. Safe Kernel Extensions Without Run-Time
%  Checking. Presented at OSDI'96, October 1996.
% 
% \bibitem{Necula2} G. Necula, P. Lee. Efficient Representation and Validation of Proofs. Presented at LICS'98, June 1998
% 
% \bibitem{Werner} B. Werner. \emph{Une Th\'eorie des Constructions Inductives},
%  PhD. Thesis, Universit\'e Paris VII, May 1994.

\end{thebibliography}
 
\end{document}