1 \documentclass[]{kluwer}
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{\component}{component}
17 \newcommand{\components}{components}
19 \newcommand{\AUTO}{\textsc{Auto}}
20 \newcommand{\COQ}{Coq}
21 \newcommand{\ELIM}{\textsc{Elim}}
22 \newcommand{\GDOME}{Gdome}
23 \newcommand{\HELM}{Helm}
24 \newcommand{\HINT}{\textsc{Hint}}
25 \newcommand{\IN}{\ensuremath{\dN}}
26 \newcommand{\INSTANCE}{\textsc{Instance}}
27 \newcommand{\IR}{\ensuremath{\dR}}
28 \newcommand{\IZ}{\ensuremath{\dZ}}
29 \newcommand{\LIBXSLT}{LibXSLT}
30 \newcommand{\LOCATE}{\textsc{Locate}}
31 \newcommand{\MATCH}{\textsc{Match}}
32 \newcommand{\MATITA}{Matita}
33 \newcommand{\METAHEADING}{Symbol & Position \\ \hline\hline}
34 \newcommand{\MOWGLI}{MoWGLI}
35 \newcommand{\NAT}{\ensuremath{\mathit{nat}}}
36 \newcommand{\NATIND}{\mathit{nat\_ind}}
37 \newcommand{\NUPRL}{NuPRL}
38 \newcommand{\OCAML}{OCaml}
39 \newcommand{\PROP}{\mathit{Prop}}
40 \newcommand{\REF}[3]{\ensuremath{\mathit{Ref}_{#1}(#2,#3)}}
41 \newcommand{\TEXMACRO}[1]{\texttt{\char92 #1}}
42 \newcommand{\UWOBO}{UWOBO}
43 \newcommand{\GETTER}{Getter}
44 \newcommand{\WHELP}{Whelp}
45 \newcommand{\DOT}{\ensuremath{\mbox{\textbf{.}}}}
46 \newcommand{\SEMICOLON}{\ensuremath{\mbox{\textbf{;}}}}
47 \newcommand{\BRANCH}{\ensuremath{\mbox{\textbf{[}}}}
48 \newcommand{\SHIFT}{\ensuremath{\mbox{\textbf{\textbar}}}}
49 \newcommand{\POS}[1]{\ensuremath{#1\mbox{\textbf{:}}}}
50 \newcommand{\MERGE}{\ensuremath{\mbox{\textbf{]}}}}
51 \newcommand{\FOCUS}[1]{\ensuremath{\mathtt{focus}~#1}}
52 \newcommand{\UNFOCUS}{\ensuremath{\mathtt{unfocus}}}
53 \newcommand{\SKIP}{\MATHTT{skip}}
54 \newcommand{\TACTIC}[1]{\ensuremath{\mathtt{tactic}~#1}}
56 \definecolor{gray}{gray}{0.85} % 1 -> white; 0 -> black
57 \newcommand{\NT}[1]{\langle\mathit{#1}\rangle}
58 \newcommand{\URI}[1]{\texttt{#1}}
59 \newcommand{\OP}[1]{``\texttt{#1}''}
61 %{\end{SaveVerbatim}\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{2mm}%
62 \newenvironment{grafite}{\VerbatimEnvironment
63 \begin{SaveVerbatim}{boxtmp}}%
64 {\end{SaveVerbatim}\setlength{\fboxsep}{3mm}%
66 \fcolorbox{black}{gray}{\BUseVerbatim[boxwidth=0.9\linewidth]{boxtmp}}
70 \newenvironment{example}{\stepcounter{example}\vspace{0.5em}\noindent\emph{Example} \arabic{example}.}
72 \newcommand{\ASSIGNEDTO}[1]{\textbf{Assigned to:} #1}
73 \newcommand{\FILE}[1]{\texttt{#1}}
74 % \newcommand{\NOTE}[1]{\ifodd \arabic{page} \else \hspace{-2cm}\fi\ednote{#1}}
75 \newcommand{\NOTE}[1]{\ednote{#1}{foo}}
76 \newcommand{\TODO}[1]{\textbf{TODO: #1}}
79 \newcommand{\PASS}{\stepcounter{pass}\arabic{pass}}
82 \newcommand{\sequent}[2]{
83 \savebox{\tmpxyz}[0.9\linewidth]{
84 \begin{minipage}{0.9\linewidth}
88 \end{minipage}}\setlength{\fboxsep}{3mm}%
90 \fcolorbox{black}{gray}{\usebox{\tmpxyz}}
93 \bibliographystyle{plain}
99 \title{The \MATITA{} Proof Assistant}
101 \author{Andrea \surname{Asperti} \email{asperti@cs.unibo.it}}
102 \author{Claudio \surname{Sacerdoti Coen} \email{sacerdot@cs.unibo.it}}
103 \author{Enrico \surname{Tassi} \email{tassi@cs.unibo.it}}
104 \author{Stefano \surname{Zacchiroli} \email{zacchiro@cs.unibo.it}}
105 \institute{Department of Computer Science, University of Bologna\\
106 Mura Anteo Zamboni, 7 --- 40127 Bologna, ITALY}
108 \runningtitle{The Matita proof assistant}
109 \runningauthor{Asperti, Sacerdoti Coen, Tassi, Zacchiroli}
114 ``We are nearly bug-free'' -- \emph{CSC, Oct 2005}
121 \keywords{Proof Assistant, Mathematical Knowledge Management, XML, Authoring,
127 \section{Introduction}
129 \MATITA{} is the Proof Assistant under development by the \HELM{} team
130 \cite{mkm-helm} at the University of Bologna, under the direction of
132 The paper describes the overall architecture of
133 the system, focusing on its most distintive and innovative
136 \subsection{Historical Perspective}
137 The origins of \MATITA{} go back to 1999. At the time we were mostly
138 interested to develop tools and techniques to enhance the accessibility
139 via Web of formal libraries of mathematics. Due to its dimension, the
140 library of the \COQ~\cite{CoqManual} proof assistant (of the order of 35'000 theorems)
141 was choosed as a privileged test bench for our work, although experiments
142 have been also conducted with other systems, and notably
143 with \NUPRL{}\cite{nuprl-book}.
144 The work, mostly performed in the framework of the recently concluded
145 European project IST-33562 \MOWGLI{}~\cite{pechino}, mainly consisted in the
148 \item exporting the information from the internal representation of
149 \COQ{} to a system and platform independent format. Since XML was at the
150 time an emerging standard, we naturally adopted this technology, fostering
151 a content-centric architecture\cite{content-centric} where the documents
152 of the library were the the main components around which everything else
154 \item developing indexing and searching techniques supporting semantic
155 queries to the library;
156 %these efforts gave birth to our \WHELP{}
157 %search engine, described in~\cite{whelp};
158 \item developing languages and tools for a high-quality notational
159 rendering of mathematical information\footnote{We have been
160 active in the MathML Working group since 1999.};
161 %and developed inside
162 %\HELM{} a MathML-compliant widget for the GTK graphical environment
163 %which can be integrated in any application.
166 According to our content-centric commitment, the library exported from
167 Coq was conceived as being distributed and most of the tools were developed
168 as Web services. The user could interact with the library and the tools by
169 means of a Web interface that orchestrates the Web services.
171 The Web services and the other tools have been implemented as front-ends
172 to a set of software libraries, collectively called the \HELM{} libraries.
173 At the end of the \MOWGLI{} project we already disposed of the following
174 tools and software libraries:
176 \item XML specifications for the Calculus of Inductive Constructions,
177 with libraries for parsing and saving mathematical objects in such a format
178 \cite{exportation-module};
179 \item metadata specifications with libraries for indexing and querying the
181 \item a proof checker library (i.e. the {\em kernel} of a proof assistant),
182 implemented to check that we exported form the \COQ{} library all the
183 logically relevant content;
184 \item a sophisticated parser (used by the search engine), able to deal
185 with potentially ambiguous and incomplete information, typical of the
186 mathematical notation \cite{disambiguation};
187 \item a {\em refiner} library, i.e. a type inference system, based on
188 partially specified terms, used by the disambiguating parser;
189 \item complex transformation algorithms for proof rendering in natural
190 language \cite{remathematization};
191 \item an innovative, MathML-compliant rendering widget for the GTK
192 graphical environment\cite{padovani}, supporting
193 high-quality bidimensional
194 rendering, and semantic selection, i.e. the possibility to select semantically
195 meaningful rendering expressions, and to past the respective content into
196 a different text area.
198 Starting from all this, developing our own proof assistant was not
199 too far away: essentially, we ``just'' had to
200 add an authoring interface, and a set of functionalities for the
201 overall management of the library, integrating everything into a
202 single system. \MATITA{} is the result of this effort.
204 \subsection{The System}
205 DESCRIZIONE DEL SISTEMA DAL PUNTO DI VISTA ``UTENTE''
208 \item scelta del sistema fondazionale
209 \item sistema indipendente (da Coq)
210 \item compatibilit\`a con sistemi legacy
213 \subsection{Relationship with \COQ{}}
215 At first sight, \MATITA{} looks as (and partly is) a \COQ{} clone. This is
216 more the effect of the circumstances of its creation described
217 above than the result of a deliberate design. In particular, we
218 (essentially) share the same foundational dialect of \COQ{} (the
219 Calculus of (Co)Inductive Constructions), the same implementative
220 language (\OCAML{}), and the same (script based) authoring philosophy.
221 However, the analogy essentially stops here and no code is shared by the
224 In a sense; we like to think of \MATITA{} as the way \COQ{} would
225 look like if entirely rewritten from scratch: just to give an
226 idea, although \MATITA{} currently supports almost all functionalities of
227 \COQ{}, it links 60'000 lines of \OCAML{} code, against the 166'000 lines linked
228 by \COQ{} (and we are convinced that, starting from scratch again,
229 we could furtherly reduce our code in sensible way).
231 Moreover, the complexity of the code of \MATITA{} is greatly reduced with
232 respect to \COQ. For instance, the API of the libraries of \MATITA{} comprise
233 989 functions, to be compared with the 4'286 functions of \COQ.
235 Finally, \MATITA{} has several innovatives features over \COQ{} that derive
236 from the integration of Mathematical Knowledge Management tools with proof
237 assistants. Among them, the advanced indexing tools over the library and
238 the parser for ambiguous mathematical notation.
240 The size and complexity improvements over \COQ{} must be understood
241 historically. \COQ{} is a quite old
242 system whose development started 15\NOTE{Verificare} years ago. Since then
243 several developers have took over the code and several new research ideas
244 that were not considered in the original architecture have been experimented
245 and integrated in the system. Moreover, there exists a lot of developments
246 for \COQ{} that require backward compatibility between each pair of releases;
247 since many central functionalities of a proof assistant are based on heuristics
248 or arbitrary choices to overcome undecidability (e.g. for higher order
249 unification), changing these functionalities mantaining backward compatibility
250 is very difficult. Finally, the code of \COQ{} has been greatly optimized
251 over the years; optimization reduces maintenability and rises the complexity
254 In writing \MATITA{} we have not been hindered by backward compatibility and
255 we have took advantage of the research results and experiences previously
256 developed by others, comprising the authors of \COQ. Moreover, starting from
257 scratch, we have designed in advance the architecture and we have splitted
258 the code in coherent minimally coupled libraries.
260 In the future we plan to exploit \MATITA{} as a test bench for new ideas and
261 extensions. Keeping the single libraries and the whole architecture as
262 simple as possible is thus crucial to foster future experiments and to
263 allow other developers to quickly understand our code and contribute.
265 %For direct experience of the authors, the learning curve to understand and
266 %be able to contribute to \COQ{}'s code is quite steep and requires direct
267 %and frequent interactions with \COQ{} developers.
271 \includegraphics[width=0.9\textwidth]{librariesCluster.ps}
272 \caption{\MATITA{} libraries}
273 \label{fig:libraries}
277 \section{Architecture}
278 Fig.~\ref{fig:libraries} shows the architecture of the \emph{\components}
279 (circle nodes) and \emph{applications} (squared nodes) developed in the HELM
282 Applications and \components{} depend over other \components{} forming a
283 directed acyclic graph (DAG). Each \component{} can be decomposed in
284 a a set of \emph{modules} also forming a DAG.
286 Modules and \components{} provide coherent sets of functionalities
287 at different scales. Applications that require only a few functionalities
288 depend on a restricted set of \components{}.
290 Only the proof assistant \MATITA{} and the \WHELP{} search engine are
291 applications meant to be used directly by the user. All the other applications
292 are Web services developed in the HELM and MoWGLI projects and already described
293 elsewhere. In particular:
295 \item The \emph{Getter} is a Web service to retrieve an (XML) document
296 from a physical location (URL) given its logical name (URI). The Getter is
297 responsible of updating a table that maps URIs to URLs. Thanks to the Getter
298 it is possible to work on a logically monolithic library that is physically
299 distributed on the network. More information on the Getter can be found
300 in~\cite{zack-master}.
301 \item \emph{Whelp} is a search engine to index and locate mathematical
302 notions (axioms, theorems, definitions) in the logical library managed
303 by the Getter. Typical examples of a query to Whelp are queries that search
304 for a theorem that generalize or instantiate a given formula, or that
305 can be immediately applied to prove a given goal. The output of Whelp is
306 an XML document that lists the URIs of a complete set of candidates that
307 are likely to satisfy the given query. The set is complete in the sense
308 that no notion that actually satisfies the query is thrown away. However,
309 the query is only approssimated in the sense that false matches can be
310 returned. Whelp has been described in~\cite{whelp}.
311 \item \emph{Uwobo} is a Web service that, given the URI of a mathematical
312 notion in the distributed library, renders it according to the user provided
313 two dimensional mathematical notation. Uwobo may also embed the rendering
314 of mathematical notions into arbitrary documents before returning them.
315 The Getter is used by Uwobo to retrieve the document to be rendered.
316 Uwobo has been described in~\cite{zack-master}.
317 \item The \emph{Proof Checker} is a Web service that, given the URI of
318 notion in the distributed library, checks its correctness. Since the notion
319 is likely to depend in an acyclic way over other notions, the proof checker
320 is also responsible of building in a top-down way the DAG of all
321 dependencies, checking in turn every notion for correctness.
322 The proof checker has been described in~\cite{zack-master}.
323 \item The \emph{Dependency Analyzer} is a Web service that can produce
324 a textual or graphical representation of the dependecies of an object.
325 The dependency analyzer has been described in~\cite{zack-master}.
328 The dependency of a \component{} or application over another \component{} can
329 be satisfied by linking the \component{} in the same executable.
330 For those \components{} whose functionalities are also provided by the
331 aforementioned Web services, it is also possible to link stub code that
332 forwards the request to a remote Web service. For instance, the Getter
333 is just a wrapper to the \texttt{getter} \component{} that allows the
334 \component{} to be used as a Web service. \MATITA{} can directly link the code
335 of the \texttt{getter} \component, or it can use a stub library with the same
336 API that forwards every request to the Getter.
338 To better understand the architecture of \MATITA{} and the role of each
339 \component, we can focus on the representation of the mathematical information.
340 \MATITA{} is based on (a variant of) the Calculus of (Co)Inductive
341 Constructions (CIC). In CIC terms are used to represent mathematical
342 expressions, types and proofs. \MATITA{} is able to handle terms at
343 four different levels of specification. On each level it is possible to provide
344 a different set of functionalities. The four different levels are:
345 fully specified terms; partially specified terms;
346 content level terms; presentation level terms.
348 \subsection{Fully specified terms}
349 \emph{Fully specified terms} are CIC terms where no information is
350 missing or left implicit. A fully specified term should be well-typed.
351 The mathematical notions (axioms, definitions, theorems) that are stored
352 in our mathematical library are fully specified and well-typed terms.
353 Fully specified terms are extremely verbose (to make type-checking
354 decidable). Their syntax is fixed and does not resemble the usual
355 extendible mathematical notation. They are not meant for direct user
358 The \texttt{cic} \component{} defines the data type that represents CIC terms
359 and provides a parser for terms stored in an XML format.
361 The most important \component{} that deals with fully specified terms is
362 \texttt{cic\_proof\_checking}. It implements the procedure that verifies
363 if a fully specified term is well-typed. It also implements the
364 \emph{conversion} judgement that verifies if two given terms are
365 computationally equivalent (i.e. they share the same normal form).
367 Terms may reference other mathematical notions in the library.
368 One commitment of our project is that the library should be physically
369 distributed. The \texttt{getter} \component{} manages the distribution,
370 providing a mapping from logical names (URIs) to the physical location
371 of a notion (an URL). The \texttt{urimanager} \component{} provides the URI
372 data type and several utility functions over URIs. The
373 \texttt{cic\_proof\_checking} \component{} calls the \texttt{getter}
374 \component{} every time it needs to retrieve the definition of a mathematical
375 notion referenced by a term that is being type-checked.
377 The Proof Checker is the Web service that provides an interface
378 to the \texttt{cic\_proof\_checking} \component.
380 We use metadata and a sort of crawler to index the mathematical notions
381 in the distributed library. We are interested in retrieving a notion
382 by matching, instantiation or generalization of a user or system provided
383 mathematical expression. Thus we need to collect metadata over the fully
384 specified terms and to store the metadata in some kind of (relational)
385 database for later usage. The \texttt{hmysql} \component{} provides
387 interface to a (possibly remote) MySql database system used to store the
388 metadata. The \texttt{metadata} \component{} defines the data type of the
390 we are collecting and the functions that extracts the metadata from the
391 mathematical notions (the main functionality of the crawler).
392 The \texttt{whelp} \component{} implements a search engine that performs
393 approximated queries by matching/instantiation/generalization. The queries
394 operate only on the metadata and do not involve any actual matching
395 (that will be described later on and that is implemented in the
396 \texttt{cic\_unification} \component). Not performing any actual matching
397 the query only returns a complete and hopefully small set of matching
398 candidates. The process that has issued the query is responsible of
399 actually retrieving from the distributed library the candidates to prune
400 out false matches if interested in doing so.
402 The Whelp search engine is the Web service that provides an interface to
403 the \texttt{whelp} \component.
405 According to our vision, the library is developed collaboratively so that
406 changing or removing a notion can invalidate other notions in the library.
407 Moreover, changing or removing a notion requires a corresponding change
408 in the metadata database. The \texttt{library} \component{} is responsible
409 of preserving the coherence of the library and the database. For instance,
410 when a notion is removed, all the notions that depend on it and their
411 metadata are removed from the library. This aspect will be better detailed
412 in Sect.~\ref{decompilazione}.
414 \subsection{Partially specified terms}
415 \emph{Partially specified terms} are CIC terms where subterms can be omitted.
416 Omitted subterms can bear no information at all or they may be associated to
417 a sequent. The formers are called \emph{implicit terms} and they occur only
418 linearly. The latters may occur multiple times and are called
419 \emph{metavariables}. An \emph{explicit substitution} is applied to each
420 occurrence of a metavariable. A metavariable stand for a term whose type is
421 given by the conclusion of the sequent. The term must be closed in the
422 context that is given by the ordered list of hypotheses of the sequent.
423 The explicit substitution instantiates every hypothesis with an actual
424 value for the term bound by the hypothesis.
426 Partially specified terms are not required to be well-typed. However a
427 partially specified term should be \emph{refinable}. A \emph{refiner} is
428 a type-inference procedure that can instantiate implicit terms and
429 metavariables and that can introduce \emph{implicit coercions} to make a
430 partially specified term be well-typed. The refiner of \MATITA{} is implemented
431 in the \texttt{cic\_unification} \component. As the type checker is based on
432 the conversion check, the refiner is based on \emph{unification} that is
433 a procedure that makes two partially specified term convertible by instantiating
434 as few as possible metavariables that occur in them.
436 Since terms are used in CIC to represent proofs, correct incomplete
437 proofs are represented by refinable partially specified terms. The metavariables
438 that occur in the proof correspond to the conjectures still to be proved.
439 The sequent associated to the metavariable is the conjecture the user needs to
442 \emph{Tactics} are the procedures that the user can apply to progress in the
443 proof. A tactic proves a conjecture possibly creating new (and hopefully
444 simpler) conjectures. The implementation of tactics is given in the
445 \texttt{tactics} \component. It is heavily based on the refinement and
446 unification procedures of the \texttt{cic\_unification} \component.
448 The \texttt{grafite} \component{} defines the abstract syntax tree (AST) for the
449 commands of the \MATITA{} proof assistant. Most of the commands are tactics.
450 Other commands are used to give definitions and axioms or to state theorems
451 and lemmas. The \texttt{grafite\_engine} \component{} is the core of \MATITA{}.
452 It implements the semantics of each command in the grafite AST as a function
453 from status to status. It implements also an undo function to go back to
454 previous statuses. \TODO{parlare di disambiguazione lazy \& co?}
456 As fully specified terms, partially specified terms are not well suited
457 for user consumption since their syntax is not extendible and it is not
458 possible to adopt the usual mathematical notation. However they are already
459 an improvement over fully specified terms since they allow to omit redundant
460 information that can be inferred by the refiner.
462 \subsection{Content level terms}
463 \label{sec:contentintro}
465 The language used to communicate proofs and expecially expressions with the
466 user does not only needs to be extendible and accomodate the usual mathematical
467 notation. It must also reflect the comfortable degree of imprecision and
468 ambiguity that the mathematical language provides.
470 For instance, it is common practice in mathematics to speak of a generic
471 equality that can be used to compare any two terms. However, it is well known
472 that several equalities can be distinguished as soon as we care for decidability
473 or for their computational properties. For instance equality over real
474 numbers is well known to be undecidable, whereas it is decidable over
477 Similarly, we usually speak of natural numbers and their operations and
478 properties without caring about their representation. However the computational
479 properties of addition over the binary representation are very different from
480 those of addition over the unary representation. And addition over two natural
481 numbers is definitely different from addition over two real numbers.
483 Formal mathematics cannot hide these differences and obliges the user to be
484 very precise on the types he is using and their representation. However,
485 to communicate formulae with the user and with external tools, it seems good
486 practice to stick to the usual imprecise mathematical ontology. In the
487 Mathematical Knowledge Management community this imprecise language is called
488 the \emph{content level} representation of expressions.
490 In \MATITA{} we provide two translations: from partially specified terms
491 to content level terms and the other way around. The first translation can also
492 be applied to fully specified terms since a fully specified term is a special
493 case of partially specified term where no metavariable or implicit term occurs.
495 The translation from partially specified terms to content level terms must
496 discriminate between terms used to represent proofs and terms used to represent
497 expressions. The firsts are translated to a content level representation of
498 proof steps that can easily be rendered in natural language. The latters
499 are translated to MathML Content formulae. MathML Content~\cite{mathml} is a W3C
501 for the representation of content level expressions in an XML extensible format.
503 The translation to content level is implemented in the
504 \texttt{acic\_content} \component. Its input are \emph{annotated partially
505 specified terms}, that are maximally unshared
506 partially specified terms enriched with additional typing information for each
507 subterm. This information is used to discriminate between terms that represent
508 proofs and terms that represent expressions. Part of it is also stored at the
509 content level since it is required to generate the natural language rendering
510 of proofs. The terms need to be maximally unshared (i.e. they must be a tree
511 and not a DAG). The reason is that to the occurrences of a subterm in
512 two different positions we need to associate different typing informations.
513 This association is made easier when the term is represented as a tree since
514 it is possible to label each node with an unique identifier and associate
515 the typing information using a map on the identifiers.
516 The \texttt{cic\_acic} \component{} unshares and annotates terms. It is used
517 by the \texttt{library} \component{} since fully specified terms are stored
518 in the library in their annotated form.
520 We do not provide yet a reverse translation from content level proofs to
521 partially specified terms. But in \texttt{cic\_disambiguation} we do provide
522 the reverse translation for expressions. The mapping from
523 content level expressions to partially specified terms is not unique due to
524 the ambiguity of the content level. As a consequence the translation
525 is guided by an \emph{interpretation}, that is a function that chooses for
526 every ambiguous expression one partially specified term. The
527 \texttt{cic\_disambiguation} \component{} implements the
528 disambiguation algorithm we presented in~\cite{disambiguation} that is
529 responsible of building in an efficicent way the set of all ``correct''
530 interpretations. An interpretation is correct if the partially specified term
531 obtained using the interpretation is refinable.
533 \subsection{Presentation level terms}
535 Content level terms are a sort of abstract syntax trees for mathematical
536 expressions and proofs. The concrete syntax given to these abstract trees
537 is called \emph{presentation level}.
539 The main important difference between the content level language and the
540 presentation level language is that only the former is extendible. Indeed,
541 the presentation level language is a finite language that comprises all
542 the usual mathematical symbols. Mathematicians invent new notions every
543 single day, but they stick to a set of symbols that is more or less fixed.
545 The fact that the presentation language is finite allows the definition of
546 standard languages. In particular, for formulae we have adopt MathML
547 Presentation~\cite{mathml} that is an XML dialect standardized by the W3C. To
549 represent proofs it is enough to embed formulae in plain text enriched with
550 formatting boxes. Since the language of formatting boxes is very simple,
551 many equivalent specifications exist and we have adopted our own, called
554 The \texttt{content\_pres} \component{} contains the implementation of the
555 translation from content level terms to presentation level terms. The
556 rendering of presentation level terms is left to the application that uses
557 the \component. However, in the \texttt{hgdome} \component{} we provide a few
558 utility functions to build a \GDOME~\cite{gdome2} MathML+BoxML tree from our
560 level terms. \GDOME{} MathML+BoxML trees can be rendered by the GtkMathView
561 widget developed by Luca Padovani \cite{padovani}. The widget is
562 particularly interesting since it allows to implement \emph{semantic
565 Semantic selection is a technique that consists in enriching the presentation
566 level terms with pointers to the content level terms and to the partially
567 specified terms they correspond to. Highlight of formulae in the widget is
568 constrained to selection of meaningful expressions, i.e. expressions that
569 correspond to a lower level term, that is a content term or a partially or
570 fully specified term.
571 Once the rendering of a lower level term is
572 selected it is possible for the application to retrieve the pointer to the
573 lower level term. An example of applications of semantic selection is
574 \emph{semantic cut\&paste}: the user can select an expression and paste it
575 elsewhere preserving its semantics (i.e. the partially specified term),
576 possibly performing some semantic transformation over it (e.g. renaming
577 variables that would be captured or lambda-lifting free variables).
579 The reverse translation from presentation level terms to content level terms
580 is implemented by a parser that is also found in \texttt{content\_pres}.
581 Differently from the translation from content level terms to partially
582 refined terms, this translation is not ambiguous. The reason is that the
583 parsing tool we have adopted (CamlP4) is not able to parse ambiguous
584 grammars. Thus we require the mapping from presentation level terms
585 (concrete syntax) to content level terms (abstract syntax) to be unique.
586 This means that the user must fix once and for all the associativity and
587 precedence level of every operator he is using. In practice this limitation
588 does not seem too strong. The reason is that the target of the
589 translation is an ambiguous language and the user is free to associate
590 to every content level term several different interpretations (as a
591 partially specified term).
593 Both the direct and reverse translation from presentation to content level
594 terms are parameterized over the user provided mathematical notation.
595 The \texttt{lexicon} \component{} is responsible of managing the lexicon,
596 that is the set of active notations. It defines an abstract syntax tree
597 of commands to declare and activate new notations and it implements the
598 semantics of these commands. It also implements undoing of the semantic
599 actions. Among the commands there are hints to the
600 disambiguation algorithm that are used to control and speed up disambiguation.
601 These mechanisms will be further discussed in Sect.~\ref{disambiguazione}.
603 Finally, the \texttt{grafite\_parser} \component{} implements a parser for
604 the concrete syntax of the commands of \MATITA. The parser process a stream
605 of characters and returns a stream of abstract syntax trees (the ones
606 defined by the \texttt{grafite} component and whose semantics is given
607 by \texttt{grafite\_engine}). When the parser meets a command that changes
608 the lexicon, it invokes the \texttt{lexicon} \component{} to immediately
609 process the command. When the parser needs to parse a term at the presentation
610 level, it invokes the already described parser for terms contained in
611 \texttt{content\_pres}.
613 The \MATITA{} proof assistant and the \WHELP{} search engine are both linked
614 against the \texttt{grafite\_parser} \components{}
615 since they provide an interface to the user. In both cases the formulae
616 written by the user are parsed using the \texttt{content\_pres} \component{} and
617 then disambiguated using the \texttt{cic\_disambiguation} \component.
618 However, only \MATITA{} is linked against the \texttt{grafite\_engine} and
619 \texttt{tactics} components since \WHELP{} can only execute those ASTs that
620 correspond to queries (implemented in the \texttt{whelp} component).
622 The \UWOBO{} Web service wraps the \texttt{content\_pres} \component,
623 providing a rendering service for the documents in the distributed library.
624 To render a document given its URI, \UWOBO{} retrieves it using the
625 \GETTER{} obtaining a document with fully specified terms. Then it translates
626 it to the presentation level passing through the content level. Finally
627 it returns the result document to be rendered by the user's
628 browser.\footnote{\TODO{manca la passata verso HTML}}
631 The \components{} not yet described (\texttt{extlib}, \texttt{xml},
632 \texttt{logger}, \texttt{registry} and \texttt{utf8\_macros}) are
633 minor \components{} that provide a core of useful functions and basic
634 services missing from the standard library of the programming language.
635 In particular, the \texttt{xml} \component{} is used
636 to easily represent, parse and pretty-print XML files.
638 \section{Using \MATITA (boh \ldots cambiare titolo)}
642 % \includegraphics[width=0.9\textwidth]{a.eps}
643 \caption{\MATITA{} screenshot}
644 \label{fig:screenshot}
648 \MATITA{} has a script based user interface. As can be seen in Fig.~... it is
649 split in two main windows: on the left a textual widget is used to edit the
650 script, on the right the list of open goal is shown using a MathML rendering
651 widget. A distinguished part of the script (shaded in the screenshot) represent
652 the commands already executed and can't be edited without undoing them. The
653 remaining part can be freely edited and commands from that part can be executed
654 moving down the execution point. An additional window --- the ``cicBrowser'' ---
655 can be used to browse the library, including the proof being developed, and
656 enable content based search on it. In the cicBrowser proofs are rendered in
657 natural language, automatically generated from the low-level $\lambda$-terms
658 using techniques inspired by \cite{natural,YANNTHESIS}.
660 In the \MATITA{} philosophy the script is not relevant \emph{per se}, but is
661 only seen as a convenient way to create mathematical objects. The universe of
662 all these objects makes up the \HELM{} library, which is always completely
663 visible to the user. The mathematical library is thus conceived as a global
664 hypertext, where objects may freely reference each other. It is a duty of
665 the system to guide the user through the relevant parts of the library.
667 This methodological assumption has many important consequences
668 which will be discussed in the next section.
671 %it requires functionalities for the overall management of the library,
672 %%%%%comprising efficient indexing techniques to retrieve and filter the
674 %on the other it introduces overloading in the use of
675 %identifiers and mathematical notation, requiring sophisticated disambiguation
676 %techniques for interpreting the user inputs.
677 %In the next two sections we shall separately discuss the two previous
680 %In order to maximize accessibility mathematical objects are encoded in XML. (As%discussed in the introduction,) the modular architecture of \MATITA{} is
681 %organized in components which work on data in this format. For instance the
682 %rendering engine, which transform $\lambda$-terms encoded as XML document to
683 %MathML Presentation documents, can be used apart from \MATITA{} to print ...
686 A final section is devoted to some innovative aspects
687 of the authoring system, such as a step by step tactical execution,
688 content selection and copy-paste.
690 \section{Library Management}
692 \subsection{Indexing and searching}
694 \subsection{Developments}
696 \subsection{Automation}
698 \subsection{Matita's naming convention}
699 A minor but not entirely negligible aspect of Matita is that of
700 adopting a (semi)-rigid naming convention for identifiers, derived by
701 our studies about metadata for statements.
702 The convention is only applied to identifiers for theorems
703 (not definitions), and relates the name of a proof to its statement.
704 The basic rules are the following:
706 \item each identifier is composed by an ordered list of (short)
707 names occurring in a left to right traversal of the statement;
708 \item all identifiers should (but this is not strictly compulsory)
709 separated by an underscore,
710 \item identifiers in two different hypothesis, or in an hypothesis
711 and in the conlcusion must be separated by the string ``\verb+_to_+'';
712 \item the identifier may be followed by a numerical suffix, or a
713 single or duoble apostrophe.
716 Take for instance the theorem
717 \[\forall n:nat. n = plus \; n\; O\]
718 Possible legal names are: \verb+plus_n_O+, \verb+plus_O+,
719 \verb+eq_n_plus_n_O+ and so on.
720 Similarly, consider the theorem
721 \[\forall n,m:nat. n<m \to n \leq m\]
722 In this case \verb+lt_to_le+ is a legal name,
723 while \verb+lt_le+ is not.\\
724 But what about, say, the symmetric law of equality? Probably you would like
725 to name such a theorem with something explicitly recalling symmetry.
726 The correct approach,
727 in this case, is the following. You should start with defining the
728 symmetric property for relations
730 \[definition\;symmetric\;= \lambda A:Type.\lambda R.\forall x,y:A.R x y \to R y x \]
732 Then, you may state the symmetry of equality as
733 \[ \forall A:Type. symmetric \;A\;(eq \; A)\]
734 and \verb+symmetric_eq+ is valid Matita name for such a theorem.
735 So, somehow unexpectedly, the introduction of semi-rigid naming convention
736 has an important benefical effect on the global organization of the library,
737 forcing the user to define abstract notions and properties before
738 using them (and formalizing such use).
740 Two cases have a special treatment. The first one concerns theorems whose
741 conclusion is a (universally quantified) predicate variable, i.e.
742 theorems of the shape
743 $\forall P,\dots.P(t)$.
744 In this case you may replace the conclusion with the word
745 ``elim'' or ``case''.
746 For instance the name \verb+nat_elim2+ is a legal name for the double
749 The other special case is that of statements whose conclusion is a
751 A typical example is the following
755 [ true \Rightarrow n = m
756 | false \Rightarrow n \neq m]
758 where $eqb$ is boolean equality.
759 In this cases, the name can be build starting from the matched
760 expression and the suffix \verb+_to_Prop+. In the above example,
761 \verb+eqb_to_Prop+ is accepted.
763 \section{The \MATITA{} user interface}
767 \subsection{Disambiguation}
769 Software applications that involve input of mathematical content should strive
770 to require the user as less drift from informal mathematics as possible. We
771 believe this to be a fundamental aspect of such applications user interfaces.
772 Being that drift in general very large when inputing
773 proofs~\cite{debrujinfactor}, in \MATITA{} we achieved good results for
774 mathematical formulae which can be input using a \TeX-like encoding (the
775 concrete syntax corresponding to presentation level terms) and are then
776 translated (in multiple steps) to partially specified terms as sketched in
777 Sect.~\ref{sec:contentintro}.
779 The key component of the translation is the generic disambiguation algorithm
780 implemented in the \texttt{disambiguation} library of Fig.~\ref{fig:libraries}
781 and presented in~\cite{disambiguation}. In this section we present how to use
782 such an algorithm in the context of the development of a library of formalized
783 mathematics. We will see that using multiple passes of the algorithm, varying
784 some of its parameters, helps in keeping the input terse without sacrificing
787 \subsubsection{Disambiguation aliases}
789 Let's start with the definition of the ``strictly greater then'' notion over
790 (Peano) natural numbers.
793 include "nat/nat.ma".
795 definition gt: nat \to nat \to Prop \def
799 The \texttt{include} statement adds the requirement that the part of the library
800 defining the notion of natural numbers should be defined before
801 processing the following definition. Note indeed that the algorithm presented
802 in~\cite{disambiguation} does not describe where interpretations for ambiguous
803 expressions come from, since it is application-specific. As a first
804 approximation, we will assume that in \MATITA{} they come from the library (i.e.
805 all interpretations available in the library are used) and the \texttt{include}
806 statements are used to ensure the availability of required library slices (see
807 Sect.~\ref{sec:libmanagement}).
809 While processing the \texttt{gt} definition, \MATITA{} has to disambiguate two
810 terms: its type and its body. Being available in the required library only one
811 interpretation both for the unbound identifier \texttt{nat} and for the
812 \OP{<} operator, and being the resulting partially specified term refinable,
813 both type and body are easily disambiguated.
815 Now suppose we have defined integers as signed natural numbers, and that we want
816 to prove a theorem about an order relationship already defined on them (which of
817 course overload the \OP{<} operator):
823 \forall x, y, z. x < y \to y < z \to x < z.
826 Since integers are defined on top of natural numbers, the part of the library
827 concerning the latters is available when disambiguating \texttt{Zlt\_compat}'s
828 type. Thus, according to the disambiguation algorithm, two different partially
829 specified terms could be associated to it. At first, this might not be seen as a
830 problem, since the user is asked and can choose interactively which of the two
831 she had in mind. However in the long run it has the drawbacks of inhibiting
832 batch compilation of the library (a technique used in \MATITA{} for behind the
833 scene compilation when needed, e.g. when an \texttt{include} is issued) and
834 yields to poor user interaction (imagine how tedious would be to be asked for a
835 choice each time you re-evaluate \texttt{Zlt\_compat}!).
837 For this reason we added to \MATITA{} the concept of \emph{disambiguation
838 aliases}. Disambiguation aliases are one-to-many mappings from ambiguous
839 expressions to partially specified terms, which are part of the runtime status
840 of \MATITA. They can be provided by users with the \texttt{alias} statement, but
841 are usually automatically added when evaluating \texttt{include} statements
842 (\emph{implicit aliases}). Aliases implicitely inferred during disambiguation
843 are remembered as well. Moreover, \MATITA{} does it best to ensure that terms
844 which require interactive choice are saved in batch compilable format. Thus,
845 after evaluating the above theorem the script will be changed to the following
846 snippet (assuming that the interpretation of \OP{<} over integers has been
850 alias symbol "lt" = "integer 'less than'".
852 \forall x, y, z. x < y \to y < z \to x < z.
855 But how are disambiguation aliases used? Since they come from the parts of the
856 library explicitely included we may be tempted of using them as the only
857 available interpretations. This would speed up the disambiguation, but may fail.
858 Consider for example:
861 theorem lt_mono: \forall x, y, k. x < y \to x < y + k.
864 and suppose that the \OP{+} operator is defined only on natural numbers. If
865 the alias for \OP{<} points to the integer version of the operator, no
866 refinable partially specified term matching the term could be found.
868 For this reason we choosed to attempt \emph{multiple disambiguation passes}. A
869 first pass attempt to disambiguate using the last available disambiguation
870 aliases (\emph{mono aliases} pass), in case of failure the next pass try again
871 the disambiguation forgetting the aliases and using the whole library to
872 retrieve interpretation for ambiguous expressions (\emph{library aliases} pass).
873 Since the latter pass may lead to too many choices we intertwined an additional
874 pass among the two which use as interpretations all the aliases coming for
875 included parts of the library (\emph{multi aliases} phase). This is the reason
876 why aliases are \emph{one-to-many} mappings instead of one-to-one. This choice
877 turned out to be a well-balanced trade-off among performances (earlier passes
878 fail quickly) and degree of ambiguity supported for presentation level terms.
880 \subsubsection{Operator instances}
882 Let's suppose now we want to define a theorem relating ordering relations on
883 natural and integer numbers. The way we would like to write such a theorem (as
884 we can read it in the \MATITA{} standard library) is:
888 include "nat/orders.ma".
890 theorem lt_to_Zlt_pos_pos:
891 \forall n, m: nat. n < m \to pos n < pos m.
894 Unfortunately, none of the passes described above is able to disambiguate its
895 type, no matter how aliases are defined. This is because the \OP{<} operator
896 occurs twice in the content level term (it has two \emph{instances}) and two
897 different interpretation for it have to be used in order to obtain a refinable
898 partially specified term. To address this issue, we have the ability to consider
899 each instance of a single symbol as a different ambiguous expression in the
900 content level term, and thus we can assign a different interpretation to each of
901 them. A disambiguation pass which exploit this feature is said to be using
902 \emph{fresh instances}.
904 Fresh instances lead to a non negligible performance loss (since the choice of
905 an interpretation for one instances does not constraint the choice for the
906 others). For this reason we always attempt a fresh instances pass only after
907 attempting a non-fresh one.
909 \subsubsection{Implicit coercions}
911 Let's now consider a (rather hypothetical) theorem about derivation:
915 \forall n: nat, x: R. d x ^ n dx = n * x ^ (n - 1).
918 and suppose there exists a \texttt{R \TEXMACRO{to} nat \TEXMACRO{to} R}
919 interpretation for \OP{\^}, and a real number interpretation for \OP{*}.
920 Mathematichians would write the term that way since it is well known that the
921 natural number \texttt{n} could be ``injected'' in \IR{} and considered a real
922 number for the purpose of real multiplication. The refiner of \MATITA{} supports
923 \emph{implicit coercions} for this reason: given as input the above content
924 level term, it will return a partially specified term where in place of
925 \texttt{n} the application of a coercion from \texttt{nat} to \texttt{R} appears
926 (assuming it has been defined as such of course).
928 Nonetheless coercions are not always desirable. For example, in disambiguating
929 \texttt{\TEXMACRO{forall} x: nat. n < n + 1} we don't want the term which uses
930 two coercions from \texttt{nat} to \texttt{R} around \OP{<} arguments to show up
931 among the possible partially specified term choices. For this reason in
932 \MATITA{} we always try first a disambiguation pass which require the refiner
933 not to use the coercions and only in case of failure we attempt a
934 coercion-enabled pass.
936 It is interesting to observe also the relationship among operator instances and
937 implicit coercions. Consider again the theorem \texttt{lt\_to\_Zlt\_pos\_pos},
938 which \MATITA{} disambiguated using fresh instances. In case there exists a
939 coercion from natural numbers to (positive) integers (which indeed does, it is
940 the \texttt{pos} constructor itself), the theorem can be disambiguated using
941 twice that coercion on the left hand side of the implication. The obtained
942 partially specified term however would not probably be the expected one, being a
943 theorem which prove a trivial implication. For this reason we choose to always
944 prefer fresh instances over implicit coercion, i.e. we always attempt
945 disambiguation passes with fresh instances before attempting passes with
948 \subsubsection{Disambiguation passes}
950 \TODO{spiegazione della tabella}
953 \begin{tabular}{c|c|c|c}
954 \multicolumn{1}{p{1.5cm}|}{\centering\raisebox{-1.5ex}{\textbf{Pass}}}
955 & \multicolumn{1}{p{2.5cm}|}{\centering\textbf{Operator instances}}
956 & \multicolumn{1}{p{3.1cm}|}{\centering\textbf{Disambiguation aliases}}
957 & \multicolumn{1}{p{2.5cm}}{\centering\textbf{Implicit coercions}} \\
959 \PASS & Normal & Mono & Disabled \\
960 \PASS & Normal & Multi & Disabled \\
961 \PASS & Fresh & Mono & Disabled \\
962 \PASS & Fresh & Multi & Disabled \\
963 \PASS & Fresh & Mono & Enabled \\
964 \PASS & Fresh & Multi & Enabled \\
965 \PASS & Fresh & Library & Enabled
969 \TODO{alias one shot}
977 \subsection{Patterns}
979 serve una intro che almeno cita il widget (per i patterns) e che fa
980 il resoconto delle cose che abbiamo e che non descriviamo,
981 sottolineando che abbiamo qualcosa da dire sui pattern e sui
984 Patterns are the textual counterpart of the MathML widget graphical
987 Matita benefits of a graphical interface and a powerful MathML rendering
988 widget that allows the user to select pieces of the sequent he is working
989 on. While this is an extremely intuitive way for the user to
990 restrict the application of tactics, for example, to some subterms of the
991 conclusion or some hypothesis, the way this action is recorded to the text
992 script is not obvious.\\
993 In \MATITA{} this issue is addressed by patterns.
995 \subsubsection{Pattern syntax}
996 A pattern is composed of two terms: a $\NT{sequent\_path}$ and a
998 The former mocks-up a sequent, discharging unwanted subterms with $?$ and
999 selecting the interesting parts with the placeholder $\%$.
1000 The latter is a term that lives in the context of the placeholders.
1002 The concrete syntax is reported in table \ref{tab:pathsyn}
1003 \NOTE{uso nomi diversi dalla grammatica ma che hanno + senso}
1005 \caption{\label{tab:pathsyn} Concrete syntax of \MATITA{} patterns.\strut}
1008 \begin{array}{@{}rcll@{}}
1010 ::= & [~\verb+in match+~\NT{wanted}~]~[~\verb+in+~\NT{sequent\_path}~] & \\
1011 \NT{sequent\_path} &
1012 ::= & \{~\NT{ident}~[~\verb+:+~\NT{multipath}~]~\}~
1013 [~\verb+\vdash+~\NT{multipath}~] & \\
1014 \NT{wanted} & ::= & \NT{term} & \\
1015 \NT{multipath} & ::= & \NT{term\_with\_placeholders} & \\
1021 \subsubsection{How patterns work}
1022 Patterns mimic the user's selection in two steps. The first one
1023 selects roots (subterms) of the sequent, using the
1024 $\NT{sequent\_path}$, while the second
1025 one searches the $\NT{wanted}$ term starting from these roots. Both are
1026 optional steps, and by convention the empty pattern selects the whole
1031 concerns only the $[~\verb+in+~\NT{sequent\_path}~]$
1032 part of the syntax. $\NT{ident}$ is an hypothesis name and
1033 selects the assumption where the following optional $\NT{multipath}$
1034 will operate. \verb+\vdash+ can be considered the name for the goal.
1035 If the whole pattern is omitted, the whole goal will be selected.
1036 If one or more hypotheses names are given the selection is restricted to
1037 these assumptions. If a $\NT{multipath}$ is omitted the whole
1038 assumption is selected. Remember that the user can be mostly
1039 unaware of this syntax, since the system is able to write down a
1040 $\NT{sequent\_path}$ starting from a visual selection.
1041 \NOTE{Questo ancora non va in matita}
1043 A $\NT{multipath}$ is a CiC term in which a special constant $\%$
1045 The roots of discharged subterms are marked with $?$, while $\%$
1046 is used to select roots. The default $\NT{multipath}$, the one that
1047 selects the whole term, is simply $\%$.
1048 Valid $\NT{multipath}$ are, for example, $(?~\%~?)$ or $\%~\verb+\to+~(\%~?)$
1049 that respectively select the first argument of an application or
1050 the source of an arrow and the head of the application that is
1051 found in the arrow target.
1053 The first phase selects not only terms (roots of subterms) but also
1054 their context that will be eventually used in the second phase.
1057 plays a role only if the $[~\verb+in match+~\NT{wanted}~]$
1058 part is specified. From the first phase we have some terms, that we
1059 will see as subterm roots, and their context. For each of these
1060 contexts the $\NT{wanted}$ term is disambiguated in it and the
1061 corresponding root is searched for a subterm $\alpha$-equivalent to
1062 $\NT{wanted}$. The result of this search is the selection the
1068 Since the first step is equipotent to the composition of the two
1069 steps, the system uses it to represent each visual selection.
1070 The second step is only meant for the
1071 experienced user that writes patterns by hand, since it really
1072 helps in writing concise patterns as we will see in the
1075 \subsubsection{Examples}
1076 To explain how the first step works let's give an example. Consider
1077 you want to prove the uniqueness of the identity element $0$ for natural
1078 sum, and that you can relay on the previously demonstrated left
1079 injectivity of the sum, that is $inj\_plus\_l:\forall x,y,z.x+y=z+y \to x =z$.
1082 theorem valid_name: \forall n,m. m + n = n \to m = O.
1086 leads you to the following sequent
1094 where you want to change the right part of the equivalence of the $H$
1095 hypothesis with $O + n$ and then use $inj\_plus\_l$ to prove $m=O$.
1097 change in H:(? ? ? %) with (O + n).
1100 This pattern, that is a simple instance of the $\NT{sequent\_path}$
1101 grammar entry, acts on $H$ that has type (without notation) $(eq~nat~(m+n)~n)$
1102 and discharges the head of the application and the first two arguments with a
1103 $?$ and selects the last argument with $\%$. The syntax may seem uncomfortable,
1104 but the user can simply select with the mouse the right part of the equivalence
1105 and left to the system the burden of writing down in the script file the
1106 corresponding pattern with $?$ and $\%$ in the right place (that is not
1107 trivial, expecially where implicit arguments are hidden by the notation, like
1108 the type $nat$ in this example).
1110 Changing all the occurrences of $n$ in the hypothesis $H$ with $O+n$
1111 works too and can be done, by the experienced user, writing directly
1112 a simpler pattern that uses the second phase.
1114 change in match n in H with (O + n).
1117 In this case the $\NT{sequent\_path}$ selects the whole $H$, while
1118 the second phase searches the wanted $n$ inside it by
1119 $\alpha$-equivalence. The resulting
1120 equivalence will be $m+(O+n)=O+n$ since the second phase found two
1121 occurrences of $n$ in $H$ and the tactic changed both.
1123 Just for completeness the second pattern is equivalent to the
1124 following one, that is less readable but uses only the first phase.
1126 change in H:(? ? (? ? %) %) with (O + n).
1130 \subsubsection{Tactics supporting patterns}
1131 In \MATITA{} all the tactics that can be restricted to subterm of the working
1132 sequent accept the pattern syntax. In particular these tactics are: simplify,
1133 change, fold, unfold, generalize, replace and rewrite.
1135 \NOTE{attualmente rewrite e fold non supportano phase 2. per
1136 supportarlo bisogna far loro trasformare il pattern phase1+phase2
1137 in un pattern phase1only come faccio nell'ultimo esempio. lo si fa
1138 con una pattern\_of(select(pattern))}
1140 \subsubsection{Comparison with Coq}
1141 Coq has a two diffrent ways of restricting the application of tactis to
1142 subterms of the sequent, both relaying on the same special syntax to identify
1145 The first way is to use this special syntax to specify directly to the
1146 tactic the occurrnces of a wanted term that should be affected, while
1147 the second is to prepare the sequent with another tactic called
1148 pattern and the apply the real tactic. Note that the choice is not
1149 left to the user, since some tactics needs the sequent to be prepared
1150 with pattern and do not accept directly this special syntax.
1152 The base idea is that to identify a subterm of the sequent we can
1153 write it and say that we want, for example, the third and the fifth
1154 occurce of it (counting from left to right). In our previous example,
1155 to change only the left part of the equivalence, the correct command
1158 change n at 2 in H with (O + n)
1161 meaning that in the hypothesis $H$ the $n$ we want to change is the
1162 second we encounter proceeding from left toright.
1164 The tactic pattern computes a
1165 $\beta$-expansion of a part of the sequent with respect to some
1166 occurrences of the given term. In the previous example the following
1172 would have resulted in this sequent
1176 H : (fun n0 : nat => m + n = n0) n
1177 ============================
1181 where $H$ is $\beta$-expanded over the second $n$
1182 occurrence. This is a trick to make the unification algorithm ignore
1183 the head of the application (since the unification is essentially
1184 first-order) but normally operate on the arguments.
1185 This works for some tactics, like rewrite and replace,
1186 but for example not for change and other tactics that do not relay on
1189 The idea behind this way of identifying subterms in not really far
1190 from the idea behind patterns, but really fails in extending to
1191 complex notation, since it relays on a mono-dimensional sequent representation.
1192 Real math notation places arguments upside-down (like in indexed sums or
1193 integrations) or even puts them inside a bidimensional matrix.
1194 In these cases using the mouse to select the wanted term is probably the
1195 only way to tell the system exactly what you want to do.
1197 One of the goals of \MATITA{} is to use modern publishing techiques, and
1198 adopting a method for restricting tactics application domain that discourages
1199 using heavy math notation, would definitively be a bad choice.
1202 \subsection{Tacticals}
1203 There are mainly two kinds of languages used by proof assistants to recorder
1204 proofs: tactic based and declarative. We will not investigate the philosophy
1205 aroud the choice that many proof assistant made, \MATITA{} included, and we
1206 will not compare the two diffrent approaches. We will describe the common
1207 issues of the tactic-based language approach and how \MATITA{} tries to solve
1210 \subsubsection{Tacticals overview}
1212 Tacticals first appeared in LCF and can be seen as programming
1213 constructs, like looping, branching, error recovery or sequential composition.
1214 The following simple example shows three tacticals in action
1218 A = B \to ((A \to B) \land (B \to A)).
1221 [ rewrite < H. assumption.
1222 | rewrite > H. assumption.
1227 The first is ``\texttt{;}'' that combines the tactic \texttt{split}
1228 with \texttt{intro}, applying the latter to each goal opened by the
1229 former. Then we have ``\texttt{[}'' that branches on the goals (here
1230 we have two goals, the two sides of the logic and).
1231 The first goal $B$ (with $A$ in the context)
1232 is proved by the first sequence of tactics
1233 \texttt{rewrite} and \texttt{assumption}. Then we move to the second
1234 goal with the separator ``\texttt{|}''. The last tactical we see here
1235 is ``\texttt{.}'' that is a sequential composition that selects the
1236 first goal opened for the following tactic (instead of applying it to
1237 them all like ``\texttt{;}''). Note that usually ``\texttt{.}'' is
1238 not considered a tactical, but a sentence terminator (i.e. the
1239 delimiter of commands the proof assistant executes).
1241 Giving serious examples here is rather difficult, since they are hard
1242 to read without the interactive tool. To help the reader in
1243 understanding the following considerations we just give few common
1244 usage examples without a proof context.
1247 elim z; try assumption; [ ... | ... ].
1248 elim z; first [ assumption | reflexivity | id ].
1251 The first example goes by induction on a term \texttt{z} and applies
1252 the tactic \texttt{assumption} to each opened goal eventually recovering if
1253 \texttt{assumption} fails. Here we are asking the system to close all
1254 trivial cases and then we branch on the remaining with ``\texttt{[}''.
1255 The second example goes again by induction on \texttt{z} and tries to
1256 close each opened goal first with \texttt{assumption}, if it fails it
1257 tries \texttt{reflexivity} and finally \texttt{id}
1258 that is the tactic that leaves the goal untouched without failing.
1260 Note that in the common implementation of tacticals both lines are
1261 compositions of tacticals and in particular they are a single
1262 statement (i.e. derived from the same non terminal entry of the
1263 grammar) ended with ``\texttt{.}''. As we will see later in \MATITA{}
1264 this is not true, since each atomic tactic or punctuation is considered
1267 \subsubsection{Common issues of tactic(als)-based proof languages}
1268 We will examine the two main problems of tactic(als)-based proof script:
1269 maintainability and readability.
1271 Huge libraries of formal mathematics have been developed, and backward
1272 compatibility is a really time consuming task. \\
1273 A real-life example in the history of \MATITA{} was the reordering of
1274 goals opened by a tactic application. We noticed that some tactics
1275 were not opening goals in the expected order. In particular the
1276 \texttt{elim} tactic on a term of an inductive type with constructors
1277 $c_1, \ldots, c_n$ used to open goals in order $g_1, g_n, g_{n-1}
1278 \ldots, g_2$. The library of \MATITA{} was still in an embryonic state
1279 but some theorems about integers were there. The inductive type of
1280 $\mathcal{Z}$ has three constructors: $zero$, $pos$ and $neg$. All the
1281 induction proofs on this type where written without tacticals and,
1282 obviously, considering the three induction cases in the wrong order.
1283 Fixing the behavior of the tactic broke the library and two days of
1284 work were needed to make it compile again. The whole time was spent in
1285 finding the list of tactics used to prove the third induction case and
1286 swap it with the list of tactics used to prove the second case. If
1287 the proofs was structured with the branch tactical this task could
1288 have been done automatically.
1290 From this experience we learned that the use of tacticals for
1291 structuring proofs gives some help but may have some drawbacks in
1292 proof script readability. We must highlight that proof scripts
1293 readability is poor by itself, but in conjunction with tacticals it
1294 can be nearly impossible. The main cause is the fact that in proof
1295 scripts there is no trace of what you are working on. It is not rare
1296 for two different theorems to have the same proof script (while the
1297 proof is completely different).\\
1298 Bad readability is not a big deal for the user while he is
1299 constructing the proof, but is considerably a problem when he tries to
1300 reread what he did or when he shows his work to someone else. The
1301 workaround commonly used to read a script is to execute it again
1302 step-by-step, so that you can see the proof goal changing and you can
1303 follow the proof steps. This works fine until you reach a tactical. A
1304 compound statement, made by some basic tactics glued with tacticals,
1305 is executed in a single step, while it obviously performs lot of proof
1306 steps. In the fist example of the previous section the whole branch
1307 over the two goals (respectively the left and right part of the logic
1308 and) result in a single step of execution. The workaround doesn't work
1309 anymore unless you de-structure on the fly the proof, putting some
1310 ``\texttt{.}'' where you want the system to stop.\\
1312 Now we can understand the tradeoff between script readability and
1313 proof structuring with tacticals. Using tacticals helps in maintaining
1314 scripts, but makes it really hard to read them again, cause of the way
1317 \MATITA{} uses a language of tactics and tacticals, but tries to avoid
1318 this tradeoff, alluring the user to write structured proof without
1319 making it impossible to read them again.
1321 \subsubsection{The \MATITA{} approach: Tinycals}
1324 \caption{\label{tab:tacsyn} Concrete syntax of \MATITA{} tacticals.\strut}
1327 \begin{array}{@{}rcll@{}}
1329 ::= & \SEMICOLON \quad|\quad \DOT \quad|\quad \SHIFT \quad|\quad \BRANCH \quad|\quad \MERGE \quad|\quad \POS{\mathrm{NUMBER}~} & \\
1331 ::= & \verb+focus+ ~|~ \verb+try+ ~|~ \verb+solve+ ~|~ \verb+first+ ~|~ \verb+repeat+ ~|~ \verb+do+~\mathrm{NUMBER} & \\
1332 \NT{block\_delimiter} &
1333 ::= & \verb+begin+ ~|~ \verb+end+ & \\
1335 ::= & \verb+skip+ ~|~ \NT{tactic} ~|~ \NT{block\_delimiter} ~|~ \NT{block\_kind} ~|~ \NT{punctuation} ~|~& \\
1341 \MATITA{} tacticals syntax is reported in table \ref{tab:tacsyn}.
1342 While one would expect to find structured constructs like
1343 $\verb+do+~n~\NT{tactic}$ the syntax allows pieces of tacticals to be written.
1344 This is essential for base idea behind matita tacticals: step-by-step execution.
1346 The low-level tacticals implementation of \MATITA{} allows a step-by-step
1347 execution of a tactical, that substantially means that a $\NT{block\_kind}$ is
1348 not executed as an atomic operation. This has two major benefits for the user,
1349 even being a so simple idea:
1351 \item[Proof structuring]
1352 is much easier. Consider for example a proof by induction, and imagine you
1353 are using classical tacticals in one of the state of the
1354 art graphical interfaces for proof assistant like Proof General or Coq Ide.
1355 After applying the induction principle you have to choose: structure
1356 the proof or not. If you decide for the former you have to branch with
1357 ``\texttt{[}'' and write tactics for all the cases separated by
1358 ``\texttt{|}'' and then close the tactical with ``\texttt{]}''.
1359 You can replace most of the cases by the identity tactic just to
1360 concentrate only on the first goal, but you will have to go one step back and
1361 one further every time you add something inside the tactical. Again this is
1362 caused by the one step execution of tacticals and by the fact that to modify
1363 the already executed script you have to undo one step.
1364 And if you are board of doing so, you will finish in giving up structuring
1365 the proof and write a plain list of tactics.\\
1366 With step-by-step tacticals you can apply the induction principle, and just
1367 open the branching tactical ``\texttt{[}''. Then you can interact with the
1368 system reaching a proof of the first case, without having to specify any
1369 tactic for the other goals. When you have proved all the induction cases, you
1370 close the branching tactical with ``\texttt{]}'' and you are done with a
1371 structured proof. \\
1372 While \MATITA{} tacticals help in structuring proofs they allow you to
1373 choose the amount of structure you want. There are no constraints imposed by
1374 the system, and if the user wants he can even write completely plain proofs.
1377 is possible. Going on step by step shows exactly what is going on. Consider
1378 again a proof by induction, that starts applying the induction principle and
1379 suddenly branches with a ``\texttt{[}''. This clearly separates all the
1380 induction cases, but if the square brackets content is executed in one single
1381 step you completely loose the possibility of rereading it and you have to
1382 temporary remove the branching tactical to execute in a satisfying way the
1383 branches. Again, executing step-by-step is the way you would like to review
1384 the demonstration. Remember that understanding the proof from the script is
1385 not easy, and only the execution of tactics (and the resulting transformed
1386 goal) gives you the feeling of what is going on.
1389 \section{The Matita library}
1391 Matita is Coq compatible, in the sense that every theorem of Coq
1392 can be read, checked and referenced in further developments.
1393 However, in order to test the actual usability of the system, a
1394 new library of results has been started from scratch. In this case,
1395 of course, we wrote (and offer) the source script files,
1396 while, in the case of Coq, Matita may only rely on XML files of
1398 The current library just comprises about one thousand theorems in
1399 elementary aspects of arithmetics up to the multiplicative property for
1400 Eulers' totient function $\phi$.
1401 The library is organized in five main directories: $logic$ (connectives,
1402 quantifiers, equality, $\dots$), $datatypes$ (basic datatypes and type
1403 constructors), $nat$ (natural numbers), $Z$ (integers), $Q$ (rationals).
1404 The most complex development is $nat$, organized in 25 scripts, listed
1405 in Figure\ref{scripts}
1408 nat.ma & plus.ma & times.ma \\
1409 minus.ma & exp.ma & compare.ma \\
1410 orders.ma & le\_arith.ma & lt\_arith.ma \\
1411 factorial.ma & sigma\_and\_pi.ma & minimization.ma \\
1412 div\_and\_mod.ma & gcd.ma & congruence.ma \\
1413 primes.ma & nth\_prime.ma & ord.ma\\
1414 count.ma & relevant\_equations.ma & permutation.ma \\
1415 factorization.ma & chinese\_reminder.ma & fermat\_little\_th.ma \\
1418 \caption{\label{scripts}Matita scripts on natural numbers}
1421 We do not plan to maintain the library in a centralized way,
1422 as most of the systems do. On the contary we are currently
1423 developing wiki-technologies to support a collaborative
1424 development of the library, encouraging people to expand,
1425 modify and elaborate previous contributions.
1427 \section{Conclusions}
1430 We would like to thank all the students that during the past
1431 five years collaborated in the \HELM{} project and contributed to
1432 the development of Matita, and in particular
1433 M.~Galat\`a, A.~Griggio, F.~Guidi, P.~Di~Lena, L.~Padovani, I.~Schena, M.~Selmi,
1438 \bibliography{matita}