4 % \usepackage{amssymb,amsmath}
11 \definecolor{gray}{gray}{0.85}
12 %\newcommand{\logo}[3]{
13 %\parpic(0cm,0cm)(#2,#3)[l]{\includegraphics[width=#1]{whelp-bw}}
16 \newcommand{\AUTO}{\textsc{Auto}}
17 \newcommand{\COQ}{Coq}
18 \newcommand{\ELIM}{\textsc{Elim}}
19 \newcommand{\GDOME}{Gdome}
20 \newcommand{\HELM}{Helm}
21 \newcommand{\HINT}{\textsc{Hint}}
22 \newcommand{\IN}{\ensuremath{\dN}}
23 \newcommand{\INSTANCE}{\textsc{Instance}}
24 \newcommand{\IR}{\ensuremath{\dR}}
25 \newcommand{\IZ}{\ensuremath{\dZ}}
26 \newcommand{\LIBXSLT}{LibXSLT}
27 \newcommand{\LOCATE}{\textsc{Locate}}
28 \newcommand{\MATCH}{\textsc{Match}}
29 \newcommand{\MATITA}{Matita}
30 \newcommand{\METAHEADING}{Symbol & Position \\ \hline\hline}
31 \newcommand{\MOWGLI}{MoWGLI}
32 \newcommand{\NAT}{\ensuremath{\mathit{nat}}}
33 \newcommand{\NATIND}{\mathit{nat\_ind}}
34 \newcommand{\NUPRL}{NuPRL}
35 \newcommand{\OCAML}{OCaml}
36 \newcommand{\PROP}{\mathit{Prop}}
37 \newcommand{\REF}[3]{\ensuremath{\mathit{Ref}_{#1}(#2,#3)}}
38 \newcommand{\TEXMACRO}[1]{\texttt{\char92 #1}}
39 \newcommand{\UWOBO}{UWOBO}
40 \newcommand{\GETTER}{Getter}
41 \newcommand{\WHELP}{Whelp}
42 \newcommand{\DOT}{\ensuremath{\mbox{\textbf{.}}}}
43 \newcommand{\SEMICOLON}{\ensuremath{\mbox{\textbf{;}}}}
44 \newcommand{\BRANCH}{\ensuremath{\mbox{\textbf{[}}}}
45 \newcommand{\SHIFT}{\ensuremath{\mbox{\textbf{\textbar}}}}
46 \newcommand{\POS}[1]{\ensuremath{#1\mbox{\textbf{:}}}}
47 \newcommand{\MERGE}{\ensuremath{\mbox{\textbf{]}}}}
48 \newcommand{\FOCUS}[1]{\ensuremath{\mathtt{focus}~#1}}
49 \newcommand{\UNFOCUS}{\ensuremath{\mathtt{unfocus}}}
50 \newcommand{\SKIP}{\MATHTT{skip}}
51 \newcommand{\TACTIC}[1]{\ensuremath{\mathtt{tactic}~#1}}
53 \definecolor{gray}{gray}{0.85} % 1 -> white; 0 -> black
54 \newcommand{\NT}[1]{\langle\mathit{#1}\rangle}
55 \newcommand{\URI}[1]{\texttt{#1}}
57 %{\end{SaveVerbatim}\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{2mm}%
58 \newenvironment{grafite}{\VerbatimEnvironment
59 \begin{SaveVerbatim}{boxtmp}}%
60 {\end{SaveVerbatim}\setlength{\fboxsep}{3mm}%
62 \fcolorbox{black}{gray}{\BUseVerbatim[boxwidth=0.9\linewidth]{boxtmp}}
66 \newenvironment{example}{\stepcounter{example}\vspace{0.5em}\noindent\emph{Example} \arabic{example}.}
68 \newcommand{\ASSIGNEDTO}[1]{\textbf{Assigned to:} #1}
69 \newcommand{\FILE}[1]{\texttt{#1}}
70 % \newcommand{\NOTE}[1]{\ifodd \arabic{page} \else \hspace{-2cm}\fi\ednote{#1}}
71 \newcommand{\NOTE}[1]{\ednote{#1}{foo}}
72 \newcommand{\TODO}[1]{\textbf{TODO: #1}}
75 \newcommand{\sequent}[2]{
76 \savebox{\tmpxyz}[0.9\linewidth]{
77 \begin{minipage}{0.9\linewidth}
81 \end{minipage}}\setlength{\fboxsep}{3mm}%
83 \fcolorbox{black}{gray}{\usebox{\tmpxyz}}
86 \bibliographystyle{plain}
92 \title{The \MATITA{} Proof Assistant}
94 \author{Andrea \surname{Asperti} \email{asperti@cs.unibo.it}}
95 \author{Claudio \surname{Sacerdoti Coen} \email{sacerdot@cs.unibo.it}}
96 \author{Enrico \surname{Tassi} \email{tassi@cs.unibo.it}}
97 \author{Stefano \surname{Zacchiroli} \email{zacchiro@cs.unibo.it}}
98 \institute{Department of Computer Science, University of Bologna\\
99 Mura Anteo Zamboni, 7 --- 40127 Bologna, ITALY}
101 \runningtitle{The Matita proof assistant}
102 \runningauthor{Asperti, Sacerdoti Coen, Tassi, Zacchiroli}
107 ``We are nearly bug-free'' -- \emph{CSC, Oct 2005}
114 \keywords{Proof Assistant, Mathematical Knowledge Management, XML, Authoring,
119 \section{Introduction}
121 In this paper we describe the architecture and a few distintive features of the
122 \emph{\MATITA} proof assistant. \MATITA{} was not conceived out of the blue
123 one single day; it has been the next natural step in the evolution of one
124 line of research we started six years ago. Thus, to better understand the
125 system, we start from its historical roots.
127 \subsection{Historical Perspective}
128 \MATITA{} is under development by the \HELM{} team
129 \cite{mkm-helm} at the University of Bologna, under the direction of
131 The origin of the system goes back to 1999. At the time we were mostly
132 interested to develop tools and techniques to enhance the accessibility
133 via Web of formal libraries of mathematics. Due to its dimension, the
134 library of the \COQ{} proof assistant (of the order of 35'000 theorems)
135 was choosed as a privileged test bench for our work, although experiments
136 have been also conducted with other systems, and notably with \NUPRL{}.
137 The work, mostly performed in the framework of the recently concluded
138 European project IST-33562 \MOWGLI{}~\cite{pechino}, mainly consisted in the
141 \item exporting the information from the internal representation of
142 \COQ{} to a system and platform independent format. Since XML was at the
143 time an emerging standard, we naturally adopted this technology, fostering
144 a content-centric architecture for future system, where the documents
145 of the library were the the main components around which everything else
147 \item developing indexing and searching techniques supporting semantic
148 queries to the library; these efforts gave birth to our \WHELP{}
149 search engine, described in~\cite{whelp};
150 \item developing languages and tools for a high-quality notational
151 rendering of mathematical information; in particular, we have been
152 active in the MathML Working group since 1999, and developed inside
153 \HELM{} a MathML-compliant widget for the GTK graphical environment
154 which can be integrated in any application.
157 According to our content-centric commitment, the library exported from
158 Coq was conceived as being distributed and most of the tools were developed
159 as Web services. The user could interact with the library and the tools by
160 means of a Web interface that orchestrates the Web services.
162 The Web services and the other tools have been implemented as front-ends
163 to a set of libraries, collectively called the \HELM{} libraries.
164 At the end of the \MOWGLI{} project we already disposed of the following
165 techniques and libraries:
167 \item XML specifications for the Calculus of Inductive Constructions,
168 with libraries for parsing and saving mathematical objects in such a format;
169 \item metadata specifications with libraries for indexing and querying the
171 \item a proof checker library (i.e. the {\em kernel} of a proof assistant),
172 implemented to check that we exported form the \COQ{} library all the
173 logically relevant content;
174 \item a sophisticated parser (used by the search engine), able to deal
175 with potentially ambiguous and incomplete information, typical of the
176 mathematical notation \cite{disambiguation};
177 \item a {\em refiner} library, i.e. a type inference system, based on
178 partially specified terms, used by the disambiguating parser;
179 \item complex transformation algorithms for proof rendering in natural
181 \item an innovative rendering widget, supporting high-quality bidimensional
182 rendering, and semantic selection, i.e. the possibility to select semantically
183 meaningful rendering expressions, and to past the respective content into
184 a different text area.
186 Starting from all this, the further step of developing our own
187 proof assistant was too
188 small and too tempting to be neglected. Essentially, we ``just'' had to
189 add an authoring interface, and a set of functionalities for the
190 overall management of the library, integrating everything into a
191 single system. \MATITA{} is the result of this effort.
193 \subsection{The System}
194 DESCRIZIONE DEL SISTEMA DAL PUNTO DI VISTA ``UTENTE''
197 \item scelta del sistema fondazionale
198 \item sistema indipendente (da Coq)
199 \item compatibilit\`a con sistemi legacy
202 \subsection{Relationship with \COQ{}}
204 At first sight, \MATITA{} looks as (and partly is) a \COQ{} clone. This is
205 more the effect of the circumstances of its creation described
206 above than the result of a deliberate design. In particular, we
207 (essentially) share the same foundational dialect of \COQ{} (the
208 Calculus of (Co)Inductive Constructions), the same implementative
209 language (\OCAML{}), and the same (script based) authoring philosophy.
210 However, the analogy essentially stops here and no code is shared by the
213 In a sense; we like to think of \MATITA{} as the way \COQ{} would
214 look like if entirely rewritten from scratch: just to give an
215 idea, although \MATITA{} currently supports almost all functionalities of
216 \COQ{}, it links 60'000 lines of \OCAML{} code, against the 166'000 lines linked
217 by \COQ{} (and we are convinced that, starting from scratch again,
218 we could furtherly reduce our code in sensible way).
220 Moreover, the complexity of the code of \MATITA{} is greatly reduced with
221 respect to \COQ. For instance, the API of the libraries of \MATITA{} comprise
222 916 functions, to be compared with the 4'286 functions of \COQ.
224 Finally, \MATITA{} has several innovatives features over \COQ{} that derive
225 from the integration of Mathematical Knowledge Management tools with proof
226 assistants. Among them, the advanced indexing tools over the library and
227 the parser for ambiguous mathematical notation.
229 The size and complexity improvements over \COQ{} must be understood
230 historically. \COQ{} is a quite old
231 system whose development started 15\NOTE{Verificare} years ago. Since then
232 several developers have took over the code and several new research ideas
233 that were not considered in the original architecture have been experimented
234 and integrated in the system. Moreover, there exists a lot of developments
235 for \COQ{} that require backward compatibility between each pair of releases;
236 since many central functionalities of a proof assistant are based on heuristics
237 or arbitrary choices to overcome undecidability (e.g. for higher order
238 unification), changing these functionalities mantaining backward compatibility
239 is very difficult. Finally, the code of \COQ{} has been greatly optimized
240 over the years; optimization reduces maintenability and rises the complexity
243 In writing \MATITA{} we have not been hindered by backward compatibility and
244 we have took advantage of the research results and experiences previously
245 developed by others, comprising the authors of \COQ. Moreover, starting from
246 scratch, we have designed in advance the architecture and we have splitted
247 the code in coherent minimally coupled libraries.
249 In the future we plan to exploit \MATITA{} as a test bench for new ideas and
250 extensions. Keeping the single libraries and the whole architecture as
251 simple as possible is thus crucial to speed up future experiments and to
252 allow other developers to quickly understand our code and contribute.
254 %For direct experience of the authors, the learning curve to understand and
255 %be able to contribute to \COQ{}'s code is quite steep and requires direct
256 %and frequent interactions with \COQ{} developers.
260 \includegraphics[width=0.9\textwidth]{librariesCluster.ps}
261 \caption{\label{fig:libraries}\MATITA{} libraries}
265 \section{Overview of the Architecture}
266 Fig.~\ref{fig:libraries} shows the architecture of the \emph{libraries} (circle nodes)
267 and \emph{applications} (squared nodes) developed in the HELM project.
269 Applications and libraries depend over other libraries forming a
270 directed acyclic graph (DAG). Each library can be decomposed in
271 a a set of \emph{modules} also forming a DAG.
273 Modules and libraries provide coherent sets of functionalities
274 at different scales. Applications that require only a few functionalities
275 depend on a restricted set of libraries.
277 Only the proof assistant \MATITA{} and the \WHELP{} search engine are
278 applications meant to be used directly by the user. All the other applications
279 are Web services developed in the HELM and MoWGLI projects and already described
280 elsewhere. In particular:
282 \item The \emph{Getter} is a Web service to retrieve an (XML) document
283 from a physical location (URL) given its logical name (URI). The Getter is
284 responsible of updating a table that maps URIs to URLs. Thanks to the Getter
285 it is possible to work on a logically monolithic library that is physically
286 distributed on the network. More information on the Getter can be found
287 in~\cite{zack-master}.
288 \item \emph{Whelp} is a search engine to index and locate mathematical
289 notions (axioms, theorems, definitions) in the logical library managed
290 by the Getter. Typical examples of a query to Whelp are queries that search
291 for a theorem that generalize or instantiate a given formula, or that
292 can be immediately applied to prove a given goal. The output of Whelp is
293 an XML document that lists the URIs of a complete set of candidates that
294 are likely to satisfy the given query. The set is complete in the sense
295 that no notion that actually satisfies the query is thrown away. However,
296 the query is only approssimated in the sense that false matches can be
297 returned. Whelp has been described in~\cite{whelp}.
298 \item \emph{Uwobo} is a Web service that, given the URI of a mathematical
299 notion in the distributed library, renders it according to the user provided
300 two dimensional mathematical notation. Uwobo may also embed the rendering
301 of mathematical notions into arbitrary documents before returning them.
302 The Getter is used by Uwobo to retrieve the document to be rendered.
303 Uwobo has been described in~\cite{zack-master}.
304 \item The \emph{Proof Checker} is a Web service that, given the URI of
305 notion in the distributed library, checks its correctness. Since the notion
306 is likely to depend in an acyclic way over other notions, the proof checker
307 is also responsible of building in a top-down way the DAG of all
308 dependencies, checking in turn every notion for correctness.
309 The proof checker has been described in~\cite{zack-master}.
310 \item The \emph{Dependency Analyzer} is a Web service that can produce
311 a textual or graphical representation of the dependecies of an object.
312 The dependency analyzer has been described in~\cite{zack-master}.
315 The dependency of a library or application over another library can
316 be satisfied by linking the library in the same executable.
317 For those libraries whose functionalities are also provided by the
318 aforementioned Web services, it is also possible to link stub code that
319 forwards the request to a remote Web service. For instance, the Getter
320 is just a wrapper to the \texttt{getter} library that allows the library
321 to be used as a Web service. \MATITA{} can directly link the code of the
322 \texttt{getter} library, or it can use a stub library with the same API
323 that forwards every request to the Getter.
325 To better understand the architecture of \MATITA{} and the role of each
326 library, we can focus on the representation of the mathematical information.
327 \MATITA{} is based on (a variant of) the Calculus of (Co)Inductive
328 Constructions (CIC). In CIC terms are used to represent mathematical
329 expressions, types and proofs. \MATITA{} is able to handle terms at
330 four different levels of specification. On each level it is possible to provide
331 a different set of functionalities. The four different levels are:
332 fully specified terms; partially specified terms;
333 content level terms; presentation level terms.
335 \subsection{Fully specified terms}
336 \emph{Fully specified terms} are CIC terms where no information is
337 missing or left implicit. A fully specified term should be well-typed.
338 The mathematical notions (axioms, definitions, theorems) that are stored
339 in our mathematical library are fully specified and well-typed terms.
340 Fully specified terms are extremely verbose (to make type-checking
341 decidable). Their syntax is fixed and does not resemble the usual
342 extendible mathematical notation. They are not meant for direct user
345 The \texttt{cic} library defines the data type that represents CIC terms
346 and provides a parser for terms stored in an XML format.
348 The most important library that deals with fully specified terms is
349 \texttt{cic\_proof\_checking}. It implements the procedure that verifies
350 if a fully specified term is well-typed. It also implements the
351 \emph{conversion} judgement that verifies if two given terms are
352 computationally equivalent (i.e. they share the same normal form).
354 Terms may reference other mathematical notions in the library.
355 One commitment of our project is that the library should be physically
356 distributed. The \texttt{getter} library manages the distribution,
357 providing a mapping from logical names (URIs) to the physical location
358 of a notion (an URL). The \texttt{urimanager} library provides the URI
359 data type and several utility functions over URIs. The
360 \texttt{cic\_proof\_checking} library calls the \texttt{getter} library
361 every time it needs to retrieve the definition of a mathematical notion
362 referenced by a term that is being type-checked.
364 The Proof Checker is the Web service that provides an interface
365 to the \texttt{cic\_proof\_checking} library.
367 We use metadata and a sort of crawler to index the mathematical notions
368 in the distributed library. We are interested in retrieving a notion
369 by matching, instantiation or generalization of a user or system provided
370 mathematical expression. Thus we need to collect metadata over the fully
371 specified terms and to store the metadata in some kind of (relational)
372 database for later usage. The \texttt{hmysql} library provides a simplified
373 interface to a (possibly remote) MySql database system used to store the
374 metadata. The \texttt{metadata} library defines the data type of the metadata
375 we are collecting and the functions that extracts the metadata from the
376 mathematical notions (the main functionality of the crawler).
377 The \texttt{whelp} library implements a search engine that performs
378 approximated queries by matching/instantiation/generalization. The queries
379 operate only on the metadata and do not involve any actual matching
380 (that will be described later on and that is implemented in the
381 \texttt{cic\_unification} library). Not performing any actual matching
382 the query only returns a complete and hopefully small set of matching
383 candidates. The process that has issued the query is responsible of
384 actually retrieving from the distributed library the candidates to prune
385 out false matches if interested in doing so.
387 The Whelp search engine is the Web service that provides an interface to
388 the \texttt{whelp} library.
390 \subsection{Partially specified terms}
391 \emph{Partially specified terms} are CIC terms where subterms can be omitted.
392 Omitted subterms can bear no information at all or they may be associated to
393 a sequent. The formers are called \emph{implicit terms} and they occur only
394 linearly. The latters may occur multiple times and are called
395 \emph{metavariables}. An \emph{explicit substitution} is applied to each
396 occurrence of a metavariable. A metavariable stand for a term whose type is
397 given by the conclusion of the sequent. The term must be closed in the
398 context that is given by the ordered list of hypotheses of the sequent.
399 The explicit substitution instantiates every hypothesis with an actual
400 value for the term bound by the hypothesis.
402 Partially specified terms are not required to be well-typed. However a
403 partially specified term should be \emph{refinable}. A \emph{refiner} is
404 a type-inference procedure that can instantiate implicit terms and
405 metavariables and that can introduce \emph{implicit coercions} to make a
406 partially specified term be well-typed. The refiner of \MATITA{} is implemented
407 in the \texttt{cic\_unification} library. As the type checker is based on
408 the conversion check, the refiner is based on \emph{unification} that is
409 a procedure that makes two partially specified term convertible by instantiating
410 as few as possible metavariables that occur in them.
412 Since terms are used in CIC to represent proofs, correct incomplete
413 proofs are represented by refinable partially specified terms. The metavariables
414 that occur in the proof correspond to the conjectures still to be proved.
415 The sequent associated to the metavariable is the conjecture the user needs to
418 \emph{Tactics} are the procedures that the user can apply to progress in the
419 proof. A tactic proves a conjecture possibly creating new (and hopefully
420 simpler) conjectures. The implementation of tactics is given in the
421 \texttt{tactics} library. It is heavily based on the refinement and unification
422 procedures of the \texttt{cic\_unification} library. \TODO{citare paramodulation
423 da qualche part o toglierla dal grafo}
425 As fully specified terms, partially specified terms are not well suited
426 for user consumption since their syntax is not extendible and it is not
427 possible to adopt the usual mathematical notation. However they are already
428 an improvement over fully specified terms since they allow to omit redundant
429 information that can be inferred by the refiner.
431 \subsection{Content level terms}
432 \label{sec:contentintro}
434 The language used to communicate proofs and expecially expressions with the
435 user does not only needs to be extendible and accomodate the usual mathematical
436 notation. It must also reflect the comfortable degree of imprecision and
437 ambiguity that the mathematical language provides.
439 For instance, it is common practice in mathematics to speak of a generic
440 equality that can be used to compare any two terms. However, it is well known
441 that several equalities can be distinguished as soon as we care for decidability
442 or for their computational properties. For instance equality over real
443 numbers is well known to be undecidable, whereas it is decidable over
446 Similarly, we usually speak of natural numbers and their operations and
447 properties without caring about their representation. However the computational
448 properties of addition over the binary representation are very different from
449 those of addition over the unary representation. And addition over two natural
450 numbers is definitely different from addition over two real numbers.
452 Formal mathematics cannot hide these differences and obliges the user to be
453 very precise on the types he is using and their representation. However,
454 to communicate formulae with the user and with external tools, it seems good
455 practice to stick to the usual imprecise mathematical ontology. In the
456 Mathematical Knowledge Management community this imprecise language is called
457 the \emph{content level} representation of expressions.
459 In \MATITA{} we provide two translations: from partially specified terms
460 to content level terms and the other way around. The first translation can also
461 be applied to fully specified terms since a fully specified term is a special
462 case of partially specified term where no metavariable or implicit term occurs.
464 The translation from partially specified terms to content level terms must
465 discriminate between terms used to represent proofs and terms used to represent
466 expressions. The firsts are translated to a content level representation of
467 proof steps that can easily be rendered in natural language. The latters
468 are translated to MathML Content formulae. MathML Content~\cite{mathml} is a W3C
470 for the representation of content level expressions in an XML extensible format.
472 The translation to content level is implemented in the
473 \texttt{acic\_content} library. Its input are \emph{annotated partially
474 specified terms}, that are maximally unshared
475 partially specified terms enriched with additional typing information for each
476 subterm. This information is used to discriminate between terms that represent
477 proofs and terms that represent expressions. Part of it is also stored at the
478 content level since it is required to generate the natural language rendering
479 of proofs. The terms need to be maximally unshared (i.e. they must be a tree
480 and not a DAG). The reason is that to the occurrences of a subterm in
481 two different positions we need to associate different typing informations.
482 This association is made easier when the term is represented as a tree since
483 it is possible to label each node with an unique identifier and associate
484 the typing information using a map on the identifiers.
485 The \texttt{cic\_acic} library annotates partially specified terms.
487 We do not provide yet a reverse translation from content level proofs to
488 partially specified terms. But in \texttt{disambiguation} we do provide
489 the reverse translation for expressions. The mapping from
490 content level expressions to partially specified terms is not unique due to
491 the ambiguity of the content level. As a consequence the translation
492 is guided by an \emph{interpretation}, that is a function that chooses for
493 every ambiguous expression one partially specified term. The
494 \texttt{disambiguation} library contains the implementation of the
495 disambiguation algorithm we presented in~\cite{disambiguation} that is
496 responsible of building in an efficicent way the set of all ``correct''
497 interpretations. An interpretation is correct if the partially specified term
498 obtained using the interpretation is refinable.
500 \subsection{Presentation level terms}
502 Content level terms are a sort of abstract syntax trees for mathematical
503 expressions and proofs. The concrete syntax given to these abstract trees
504 is called \emph{presentation level}.
506 The main important difference between the content level language and the
507 presentation level language is that only the former is extendible. Indeed,
508 the presentation level language is a finite language that comprises all
509 the usual mathematical symbols. Mathematicians invent new notions every
510 single day, but they stick to a set of symbols that is more or less fixed.
512 The fact that the presentation language is finite allows the definition of
513 standard languages. In particular, for formulae we have adopt MathML
514 Presentation~\cite{mathml} that is an XML dialect standardized by the W3C. To
516 represent proofs it is enough to embed formulae in plain text enriched with
517 formatting boxes. Since the language of formatting boxes is very simple,
518 many equivalent specifications exist and we have adopted our own, called
521 The \texttt{content\_pres} library contains the implementation of the
522 translation from content level terms to presentation level terms. The
523 rendering of presentation level terms is left to the application that uses
524 the library. However, in the \texttt{hgdome} library we provide a few
525 utility functions to build a \GDOME~\cite{gdome2} MathML+BoxML tree from our
527 level terms. \GDOME{} MathML+BoxML trees can be rendered by the GtkMathView
528 widget developed by Luca Padovani \cite{padovani}. The widget is
529 particularly interesting since it allows to implement \emph{semantic
532 Semantic selection is a technique that consists in enriching the presentation
533 level terms with pointers to the content level terms and to the partially
534 specified terms they correspond to. Highlight of formulae in the widget is
535 constrained to selection of meaningful expressions, i.e. expressions that
536 correspond to a lower\footnote{\TODO{non abbiamo parlato di ``ordine''}} level term. Once the rendering of a lower level term is
537 selected it is possible for the application to retrieve the pointer to the
538 lower level term. An example of applications of semantic selection is
539 \emph{semantic cut\&paste}: the user can select an expression and paste it
540 elsewhere preserving its semantics (i.e. the partially specified term),
541 possibly performing some semantic transformation over it (e.g. renaming
542 variables that would be captured or lambda-lifting free variables).
544 The reverse translation from presentation level terms to content level terms
545 is implemented by a parser that is also found in \texttt{content\_pres}.
546 Differently from the translation from content level terms to partially
547 refined terms, this translation is not ambiguous. The reason is that the
548 parsing library we have adopted (CamlP4) is not able to parse ambiguous
549 grammars. Thus we require the mapping from presentation level terms
550 (concrete syntax) to content level terms (abstract syntax) to be unique.
551 This means that the user must fix once and for all the associativity and
552 precedence level of every operator he is using. In prctice this limitation
553 does not seem too strong. The reason is that the target of the
554 translation is an ambiguous language and the user is free to associate
555 to every content level term several different interpretations (as a
556 partially specified term).
558 The \MATITA{} proof assistant and the \WHELP{} search engine are both linked
559 against the \texttt{cic\_disambiguation} and \texttt{content\_pres} libraries
560 since they provide an interface to the user. In both cases the formulae
561 written by the user are parsed using the \texttt{content\_pres} library and
562 then disambiguated using the \texttt{cic\_disambiguation} library.
564 The \UWOBO{} Web service wraps the \texttt{content\_pres} library,
565 providing a rendering service for the documents in the distributed library.
566 To render a document given its URI, \UWOBO{} retrieves it using the
567 \GETTER{} obtaining a document with fully specified terms. Then it translates
568 it to the presentation level passing through the content level. Finally
569 it returns the result document to be rendered by the user's
570 browser.\footnote{\TODO{manca la passata verso HTML}}
574 At the bottom of the DAG we have a few libraries (\texttt{extlib},
575 \texttt{xml} and the \texttt{registry}) that provide a core of
576 useful functions used everywhere else. In particular, the \texttt{xml} library
577 to easily represent, parse and pretty-print XML files is a central component
578 since in HELM every piece of information is stored in \ldots. [FINIRE]
579 The other basic libraries provide often needed operations over generic
580 data structures (\texttt{extlib}) and central storage for configuration options
581 (the \texttt{registry}).
589 \section{Partially specified terms}
590 --- il mondo delle tattiche e dintorni ---
591 serve una intro che almeno cita il widget (per i patterns) e che fa
592 il resoconto delle cose che abbiamo e che non descriviamo,
593 sottolineando che abbiamo qualcosa da dire sui pattern e sui
598 \subsection{Patterns}
599 Patterns are the textual counterpart of the MathML widget graphical
602 Matita benefits of a graphical interface and a powerful MathML rendering
603 widget that allows the user to select pieces of the sequent he is working
604 on. While this is an extremely intuitive way for the user to
605 restrict the application of tactics, for example, to some subterms of the
606 conclusion or some hypothesis, the way this action is recorded to the text
607 script is not obvious.\\
608 In \MATITA{} this issue is addressed by patterns.
610 \subsubsection{Pattern syntax}
611 A pattern is composed of two terms: a $\NT{sequent\_path}$ and a
613 The former mocks-up a sequent, discharging unwanted subterms with $?$ and
614 selecting the interesting parts with the placeholder $\%$.
615 The latter is a term that lives in the context of the placeholders.
617 The concrete syntax is reported in table \ref{tab:pathsyn}
618 \NOTE{uso nomi diversi dalla grammatica ma che hanno + senso}
620 \caption{\label{tab:pathsyn} Concrete syntax of \MATITA{} patterns.\strut}
623 \begin{array}{@{}rcll@{}}
625 ::= & [~\verb+in match+~\NT{wanted}~]~[~\verb+in+~\NT{sequent\_path}~] & \\
627 ::= & \{~\NT{ident}~[~\verb+:+~\NT{multipath}~]~\}~
628 [~\verb+\vdash+~\NT{multipath}~] & \\
629 \NT{wanted} & ::= & \NT{term} & \\
630 \NT{multipath} & ::= & \NT{term\_with\_placeholders} & \\
636 \subsubsection{How patterns work}
637 Patterns mimic the user's selection in two steps. The first one
638 selects roots (subterms) of the sequent, using the
639 $\NT{sequent\_path}$, while the second
640 one searches the $\NT{wanted}$ term starting from these roots. Both are
641 optional steps, and by convention the empty pattern selects the whole
646 concerns only the $[~\verb+in+~\NT{sequent\_path}~]$
647 part of the syntax. $\NT{ident}$ is an hypothesis name and
648 selects the assumption where the following optional $\NT{multipath}$
649 will operate. \verb+\vdash+ can be considered the name for the goal.
650 If the whole pattern is omitted, the whole goal will be selected.
651 If one or more hypotheses names are given the selection is restricted to
652 these assumptions. If a $\NT{multipath}$ is omitted the whole
653 assumption is selected. Remember that the user can be mostly
654 unaware of this syntax, since the system is able to write down a
655 $\NT{sequent\_path}$ starting from a visual selection.
656 \NOTE{Questo ancora non va in matita}
658 A $\NT{multipath}$ is a CiC term in which a special constant $\%$
660 The roots of discharged subterms are marked with $?$, while $\%$
661 is used to select roots. The default $\NT{multipath}$, the one that
662 selects the whole term, is simply $\%$.
663 Valid $\NT{multipath}$ are, for example, $(?~\%~?)$ or $\%~\verb+\to+~(\%~?)$
664 that respectively select the first argument of an application or
665 the source of an arrow and the head of the application that is
666 found in the arrow target.
668 The first phase selects not only terms (roots of subterms) but also
669 their context that will be eventually used in the second phase.
672 plays a role only if the $[~\verb+in match+~\NT{wanted}~]$
673 part is specified. From the first phase we have some terms, that we
674 will see as subterm roots, and their context. For each of these
675 contexts the $\NT{wanted}$ term is disambiguated in it and the
676 corresponding root is searched for a subterm $\alpha$-equivalent to
677 $\NT{wanted}$. The result of this search is the selection the
683 Since the first step is equipotent to the composition of the two
684 steps, the system uses it to represent each visual selection.
685 The second step is only meant for the
686 experienced user that writes patterns by hand, since it really
687 helps in writing concise patterns as we will see in the
690 \subsubsection{Examples}
691 To explain how the first step works let's give an example. Consider
692 you want to prove the uniqueness of the identity element $0$ for natural
693 sum, and that you can relay on the previously demonstrated left
694 injectivity of the sum, that is $inj\_plus\_l:\forall x,y,z.x+y=z+y \to x =z$.
697 theorem valid_name: \forall n,m. m + n = n \to m = O.
701 leads you to the following sequent
709 where you want to change the right part of the equivalence of the $H$
710 hypothesis with $O + n$ and then use $inj\_plus\_l$ to prove $m=O$.
712 change in H:(? ? ? %) with (O + n).
715 This pattern, that is a simple instance of the $\NT{sequent\_path}$
716 grammar entry, acts on $H$ that has type (without notation) $(eq~nat~(m+n)~n)$
717 and discharges the head of the application and the first two arguments with a
718 $?$ and selects the last argument with $\%$. The syntax may seem uncomfortable,
719 but the user can simply select with the mouse the right part of the equivalence
720 and left to the system the burden of writing down in the script file the
721 corresponding pattern with $?$ and $\%$ in the right place (that is not
722 trivial, expecially where implicit arguments are hidden by the notation, like
723 the type $nat$ in this example).
725 Changing all the occurrences of $n$ in the hypothesis $H$ with $O+n$
726 works too and can be done, by the experienced user, writing directly
727 a simpler pattern that uses the second phase.
729 change in match n in H with (O + n).
732 In this case the $\NT{sequent\_path}$ selects the whole $H$, while
733 the second phase searches the wanted $n$ inside it by
734 $\alpha$-equivalence. The resulting
735 equivalence will be $m+(O+n)=O+n$ since the second phase found two
736 occurrences of $n$ in $H$ and the tactic changed both.
738 Just for completeness the second pattern is equivalent to the
739 following one, that is less readable but uses only the first phase.
741 change in H:(? ? (? ? %) %) with (O + n).
745 \subsubsection{Tactics supporting patterns}
746 In \MATITA{} all the tactics that can be restricted to subterm of the working
747 sequent accept the pattern syntax. In particular these tactics are: simplify,
748 change, fold, unfold, generalize, replace and rewrite.
750 \NOTE{attualmente rewrite e fold non supportano phase 2. per
751 supportarlo bisogna far loro trasformare il pattern phase1+phase2
752 in un pattern phase1only come faccio nell'ultimo esempio. lo si fa
753 con una pattern\_of(select(pattern))}
755 \subsubsection{Comparison with Coq}
756 Coq has a two diffrent ways of restricting the application of tactis to
757 subterms of the sequent, both relaying on the same special syntax to identify
760 The first way is to use this special syntax to specify directly to the
761 tactic the occurrnces of a wanted term that should be affected, while
762 the second is to prepare the sequent with another tactic called
763 pattern and the apply the real tactic. Note that the choice is not
764 left to the user, since some tactics needs the sequent to be prepared
765 with pattern and do not accept directly this special syntax.
767 The base idea is that to identify a subterm of the sequent we can
768 write it and say that we want, for example, the third and the fifth
769 occurce of it (counting from left to right). In our previous example,
770 to change only the left part of the equivalence, the correct command
773 change n at 2 in H with (O + n)
776 meaning that in the hypothesis $H$ the $n$ we want to change is the
777 second we encounter proceeding from left toright.
779 The tactic pattern computes a
780 $\beta$-expansion of a part of the sequent with respect to some
781 occurrences of the given term. In the previous example the following
787 would have resulted in this sequent
791 H : (fun n0 : nat => m + n = n0) n
792 ============================
796 where $H$ is $\beta$-expanded over the second $n$
797 occurrence. This is a trick to make the unification algorithm ignore
798 the head of the application (since the unification is essentially
799 first-order) but normally operate on the arguments.
800 This works for some tactics, like rewrite and replace,
801 but for example not for change and other tactics that do not relay on
804 The idea behind this way of identifying subterms in not really far
805 from the idea behind patterns, but really fails in extending to
806 complex notation, since it relays on a mono-dimensional sequent representation.
807 Real math notation places arguments upside-down (like in indexed sums or
808 integrations) or even puts them inside a bidimensional matrix.
809 In these cases using the mouse to select the wanted term is probably the
810 only way to tell the system exactly what you want to do.
812 One of the goals of \MATITA{} is to use modern publishing techiques, and
813 adopting a method for restricting tactics application domain that discourages
814 using heavy math notation, would definitively be a bad choice.
816 \subsection{Tacticals}
817 There are mainly two kinds of languages used by proof assistants to recorder
818 proofs: tactic based and declarative. We will not investigate the philosophy
819 aroud the choice that many proof assistant made, \MATITA{} included, and we
820 will not compare the two diffrent approaches. We will describe the common
821 issues of the tactic-based language approach and how \MATITA{} tries to solve
824 \subsubsection{Tacticals overview}
826 Tacticals first appeared in LCF and can be seen as programming
827 constructs, like looping, branching, error recovery or sequential composition.
828 The following simple example shows three tacticals in action
832 A = B \to ((A \to B) \land (B \to A)).
835 [ rewrite < H. assumption.
836 | rewrite > H. assumption.
841 The first is ``\texttt{;}'' that combines the tactic \texttt{split}
842 with \texttt{intro}, applying the latter to each goal opened by the
843 former. Then we have ``\texttt{[}'' that branches on the goals (here
844 we have two goals, the two sides of the logic and).
845 The first goal $B$ (with $A$ in the context)
846 is proved by the first sequence of tactics
847 \texttt{rewrite} and \texttt{assumption}. Then we move to the second
848 goal with the separator ``\texttt{|}''. The last tactical we see here
849 is ``\texttt{.}'' that is a sequential composition that selects the
850 first goal opened for the following tactic (instead of applying it to
851 them all like ``\texttt{;}''). Note that usually ``\texttt{.}'' is
852 not considered a tactical, but a sentence terminator (i.e. the
853 delimiter of commands the proof assistant executes).
855 Giving serious examples here is rather difficult, since they are hard
856 to read without the interactive tool. To help the reader in
857 understanding the following considerations we just give few common
858 usage examples without a proof context.
861 elim z; try assumption; [ ... | ... ].
862 elim z; first [ assumption | reflexivity | id ].
865 The first example goes by induction on a term \texttt{z} and applies
866 the tactic \texttt{assumption} to each opened goal eventually recovering if
867 \texttt{assumption} fails. Here we are asking the system to close all
868 trivial cases and then we branch on the remaining with ``\texttt{[}''.
869 The second example goes again by induction on \texttt{z} and tries to
870 close each opened goal first with \texttt{assumption}, if it fails it
871 tries \texttt{reflexivity} and finally \texttt{id}
872 that is the tactic that leaves the goal untouched without failing.
874 Note that in the common implementation of tacticals both lines are
875 compositions of tacticals and in particular they are a single
876 statement (i.e. derived from the same non terminal entry of the
877 grammar) ended with ``\texttt{.}''. As we will see later in \MATITA{}
878 this is not true, since each atomic tactic or punctuation is considered
881 \subsubsection{Common issues of tactic(als)-based proof languages}
882 We will examine the two main problems of tactic(als)-based proof script:
883 maintainability and readability.
885 Huge libraries of formal mathematics have been developed, and backward
886 compatibility is a really time consuming task. \\
887 A real-life example in the history of \MATITA{} was the reordering of
888 goals opened by a tactic application. We noticed that some tactics
889 were not opening goals in the expected order. In particular the
890 \texttt{elim} tactic on a term of an inductive type with constructors
891 $c_1, \ldots, c_n$ used to open goals in order $g_1, g_n, g_{n-1}
892 \ldots, g_2$. The library of \MATITA{} was still in an embryonic state
893 but some theorems about integers were there. The inductive type of
894 $\mathcal{Z}$ has three constructors: $zero$, $pos$ and $neg$. All the
895 induction proofs on this type where written without tacticals and,
896 obviously, considering the three induction cases in the wrong order.
897 Fixing the behavior of the tactic broke the library and two days of
898 work were needed to make it compile again. The whole time was spent in
899 finding the list of tactics used to prove the third induction case and
900 swap it with the list of tactics used to prove the second case. If
901 the proofs was structured with the branch tactical this task could
902 have been done automatically.
904 From this experience we learned that the use of tacticals for
905 structuring proofs gives some help but may have some drawbacks in
906 proof script readability. We must highlight that proof scripts
907 readability is poor by itself, but in conjunction with tacticals it
908 can be nearly impossible. The main cause is the fact that in proof
909 scripts there is no trace of what you are working on. It is not rare
910 for two different theorems to have the same proof script (while the
911 proof is completely different).\\
912 Bad readability is not a big deal for the user while he is
913 constructing the proof, but is considerably a problem when he tries to
914 reread what he did or when he shows his work to someone else. The
915 workaround commonly used to read a script is to execute it again
916 step-by-step, so that you can see the proof goal changing and you can
917 follow the proof steps. This works fine until you reach a tactical. A
918 compound statement, made by some basic tactics glued with tacticals,
919 is executed in a single step, while it obviously performs lot of proof
920 steps. In the fist example of the previous section the whole branch
921 over the two goals (respectively the left and right part of the logic
922 and) result in a single step of execution. The workaround doesn't work
923 anymore unless you de-structure on the fly the proof, putting some
924 ``\texttt{.}'' where you want the system to stop.\\
926 Now we can understand the tradeoff between script readability and
927 proof structuring with tacticals. Using tacticals helps in maintaining
928 scripts, but makes it really hard to read them again, cause of the way
931 \MATITA{} uses a language of tactics and tacticals, but tries to avoid
932 this tradeoff, alluring the user to write structured proof without
933 making it impossible to read them again.
935 \subsubsection{The \MATITA{} approach: Tinycals}
938 \caption{\label{tab:tacsyn} Concrete syntax of \MATITA{} tacticals.\strut}
941 \begin{array}{@{}rcll@{}}
943 ::= & \SEMICOLON \quad|\quad \DOT \quad|\quad \SHIFT \quad|\quad \BRANCH \quad|\quad \MERGE \quad|\quad \POS{\mathrm{NUMBER}~} & \\
945 ::= & \verb+focus+ ~|~ \verb+try+ ~|~ \verb+solve+ ~|~ \verb+first+ ~|~ \verb+repeat+ ~|~ \verb+do+~\mathrm{NUMBER} & \\
946 \NT{block\_delimiter} &
947 ::= & \verb+begin+ ~|~ \verb+end+ & \\
949 ::= & \verb+skip+ ~|~ \NT{tactic} ~|~ \NT{block\_delimiter} ~|~ \NT{block\_kind} ~|~ \NT{punctuation} ~|~& \\
955 \MATITA{} tacticals syntax is reported in table \ref{tab:tacsyn}.
956 While one would expect to find structured constructs like
957 $\verb+do+~n~\NT{tactic}$ the syntax allows pieces of tacticals to be written.
958 This is essential for base idea behind matita tacticals: step-by-step execution.
960 The low-level tacticals implementation of \MATITA{} allows a step-by-step
961 execution of a tactical, that substantially means that a $\NT{block\_kind}$ is
962 not executed as an atomic operation. This has two major benefits for the user,
963 even being a so simple idea:
965 \item[Proof structuring]
966 is much easier. Consider for example a proof by induction, and imagine you
967 are using classical tacticals in one of the state of the
968 art graphical interfaces for proof assistant like Proof General or Coq Ide.
969 After applying the induction principle you have to choose: structure
970 the proof or not. If you decide for the former you have to branch with
971 ``\texttt{[}'' and write tactics for all the cases separated by
972 ``\texttt{|}'' and then close the tactical with ``\texttt{]}''.
973 You can replace most of the cases by the identity tactic just to
974 concentrate only on the first goal, but you will have to go one step back and
975 one further every time you add something inside the tactical. Again this is
976 caused by the one step execution of tacticals and by the fact that to modify
977 the already executed script you have to undo one step.
978 And if you are board of doing so, you will finish in giving up structuring
979 the proof and write a plain list of tactics.\\
980 With step-by-step tacticals you can apply the induction principle, and just
981 open the branching tactical ``\texttt{[}''. Then you can interact with the
982 system reaching a proof of the first case, without having to specify any
983 tactic for the other goals. When you have proved all the induction cases, you
984 close the branching tactical with ``\texttt{]}'' and you are done with a
986 While \MATITA{} tacticals help in structuring proofs they allow you to
987 choose the amount of structure you want. There are no constraints imposed by
988 the system, and if the user wants he can even write completely plain proofs.
991 is possible. Going on step by step shows exactly what is going on. Consider
992 again a proof by induction, that starts applying the induction principle and
993 suddenly branches with a ``\texttt{[}''. This clearly separates all the
994 induction cases, but if the square brackets content is executed in one single
995 step you completely loose the possibility of rereading it and you have to
996 temporary remove the branching tactical to execute in a satisfying way the
997 branches. Again, executing step-by-step is the way you would like to review
998 the demonstration. Remember that understanding the proof from the script is
999 not easy, and only the execution of tactics (and the resulting transformed
1000 goal) gives you the feeling of what is going on.
1003 \section{Content level terms}
1005 \subsection{Disambiguation}
1007 Software applications that involve input of mathematical content should strive
1008 to require the user as less drift from informal mathematics as possible. We
1009 believe this to be a fundamental aspect of such applications user interfaces.
1010 Being that drift in general very large when inputing
1011 proofs~\cite{debrujinfactor}, in \MATITA{} we achieved good results for
1012 mathematical formulae which can be input using a \TeX-like encoding (the
1013 concrete syntax corresponding to presentation level terms) and are then
1014 translated (in multiple steps) to partially specified terms as sketched in
1015 Sect.~\ref{sec:contentintro}.
1017 The key component of the translation is the generic disambiguation algorithm
1018 implemented in the \texttt{disambiguation} library of Fig.~\ref{fig:libraries}
1019 and presented in~\cite{disambiguation}. In this section we present how to use
1020 such an algorithm in the context of the development of a library of formalized
1021 mathematics. We proceed by examples took from the \MATITA{} standard library.
1023 \subsubsection{Disambiguation aliases}
1025 Let's start with the definition of the ``strictly greater then'' notion over
1026 (Peano) natural numbers.
1029 include "nat/nat.ma".
1031 definition gt: nat \to nat \to Prop \def
1032 \lambda n, m. m < n.
1035 The \texttt{include} statement adds the requirement that the part of the library
1036 defining the notion of (Peano) natural numbers should be defined before
1037 processing the following definition. Note indeed that the algorithm presented
1038 in~\cite{disambiguation} does not describe where interpretations for ambiguous
1039 expressions come from, since it is application-specific. As a first
1040 approximation, we will assume that in \MATITA{} they come from the library (i.e.
1041 all interpretations available in the library are used) and the \texttt{include}
1042 statements are used to ensure the availability of required library slices (see
1043 Sect.~\ref{sec:libmanagement}).
1045 While processing the \texttt{gt} definition, \MATITA{} has to disambiguate two
1046 terms: its type and its body. Being available in the required library only one
1047 interpretation both for the unbound identifier \texttt{nat} and for the
1048 \texttt{<} operator, and being the resulting partially specified term refinable,
1049 both type and body are easily disambiguated.
1051 Now suppose we have defined integers as signed Peano numbers, and that we want
1052 to prove a theorem about an order relationship already defined on them (which of
1053 course overload the \texttt{<} operator):
1059 \forall x, y, z. x < y \to y < z \to x < z.
1062 Since integers are defined on top of Peano numbers, the part of the library
1063 concerning the latters is available when disambiguating \texttt{Zlt\_compat}'s
1064 type. Thus, according to the disambiguation algorithm, two different partially
1065 specified terms could be associated to it. At first, this might not be seen as a
1066 problem, since the user is asked and can choose interactively which of the two
1067 she had in mind. However in the long run it has the drawbacks of inhibiting
1068 batch compilation of the library (a technique used in \MATITA{} for behind the
1069 scene compilation when needed, e.g. when an \texttt{include} is issued) and
1070 yields to poor user interaction (imagine how tedious would be to be asked for a
1071 choice each time you re-evaluate \texttt{Zlt\_compat}!).
1073 For this reason we added to \MATITA{} the concept of \emph{disambiguation
1074 aliases}. Disambiguation aliases are one-to-many mappings from ambiguous
1075 expressions to partially specified terms, which are part of the runtime status
1076 of \MATITA. They can be provided by users with the \texttt{alias} statement, but
1077 are usually automatically added when evaluating \texttt{include} statements
1078 (\emph{implicit aliases}). Moreover, \MATITA{} does it best to ensure that
1079 terms which require interactive choice are saved in batch compilable format.
1080 Thus, after evaluating the above theorem the script will be changed to the
1081 following snippet (assuming that the interpretation of \texttt{<} over integers
1085 alias symbol "lt" (instance 0) = "integer 'less than'".
1087 \forall x, y, z. x < y \to y < z \to x < z.
1090 But how are disambiguation aliases used? Since they come from the parts of the
1091 library explicitely included we may be tempted of using them as the only
1092 available interpretations. This would speed up the disambiguation, but may fail.
1093 Consider for example:
1096 theorem lt_mono: \forall x, y, k. x < y \to x < y + k.
1099 and suppose that the \texttt{+} operator is defined only on Peano numbers. If
1100 the alias for \texttt{<} points to the integer version of the operator, no
1101 refinable partially specified term matching the term could be found.
1103 For this reason we choosed to attempt \emph{multiple disambiguation passes}. A
1104 first pass attempt to disambiguate using the last available disambiguation
1105 aliases, in case of failure the next pass try again the disambiguation
1106 forgetting the aliases and using the whole library to retrieve interpretation
1107 for ambiguous expressions. Since the latter pass may lead to too many choices we
1108 intertwined an additional pass among the two which use as interpretations all
1109 the aliases coming for included parts of the library (this is the reason why
1110 aliases are \emph{one-to-many} mappings instead of one-to-one). This choice
1111 turned out to be a well-balanced trade-off among performances (earlier passes
1112 fail quickly) and degree of ambiguity supported for presentation level terms.
1114 \subsubsection{Operator instances}
1117 We would like to thank all the students that during the past
1118 five years collaborated in the \HELM{} project and contributed to
1119 the development of Matita, and in particular
1120 A.~Griggio, F.~Guidi, P.~Di~Lena, L.~Padovani, I.~Schena, M.~Selmi,
1125 \bibliography{matita}