\chapter{Defining Logics} \label{Defining-Logics}

\section{Mixfix declarations} \label{sec:mixfix}

\index{mixfix declarations|(}

When defining a theory, you declare new constants by giving their names,

their type, and an optional {\bf mixfix annotation}.  Mixfix annotations

allow you to extend Isabelle's basic $\lambda$-calculus syntax with

readable notation.  They can express any context-free priority grammar.

Isabelle syntax definitions are inspired by \OBJ~\cite{OBJ}; they are more

general than the priority declarations of \ML\ and Prolog.

A mixfix annotation defines a production of the priority grammar.  It

describes the concrete syntax, the translation to abstract syntax, and the

pretty printing.  Special case annotations provide a simple means of

specifying infix operators and binders.

\subsection{The general mixfix form}

Here is a detailed account of mixfix declarations.  Suppose the following

line occurs within a {\tt consts} or {\tt syntax} section of a {\tt .thy}

file:

\begin{center}

  {\tt $c$ ::\ "$\sigma$" ("$template$" $ps$ $p$)}

\end{center}

This constant declaration and mixfix annotation are interpreted as follows:

\begin{itemize}\index{productions}

\item The string {\tt $c$} is the name of the constant associated with the

  production; unless it is a valid identifier, it must be enclosed in

  quotes.  If $c$ is empty (given as~{\tt ""}) then this is a copy

  production.\index{productions!copy} Otherwise, parsing an instance of the

  phrase $template$ generates the \AST{} {\tt ("$c$" $a@1$ $\ldots$

    $a@n$)}, where $a@i$ is the \AST{} generated by parsing the $i$-th

  argument.

  \item The constant $c$, if non-empty, is declared to have type $\sigma$

    ({\tt consts} section only).

  \item The string $template$ specifies the right-hand side of

    the production.  It has the form

    \[ w@0 \;_\; w@1 \;_\; \ldots \;_\; w@n, \]

    where each occurrence of {\tt_} denotes an argument position and

    the~$w@i$ do not contain~{\tt _}.  (If you want a literal~{\tt _} in

    the concrete syntax, you must escape it as described below.)  The $w@i$

    may consist of \rmindex{delimiters}, spaces or

    \rmindex{pretty printing} annotations (see below).

  \item The type $\sigma$ specifies the production's nonterminal symbols

    (or name tokens).  If $template$ is of the form above then $\sigma$

    must be a function type with at least~$n$ argument positions, say

    $\sigma = [\tau@1, \dots, \tau@n] \To \tau$.  Nonterminal symbols are

    derived from the types $\tau@1$, \ldots,~$\tau@n$, $\tau$ as described

    below.  Any of these may be function types.

  \item The optional list~$ps$ may contain at most $n$ integers, say {\tt

      [$p@1$, $\ldots$, $p@m$]}, where $p@i$ is the minimal

    priority\indexbold{priorities} required of any phrase that may appear

    as the $i$-th argument.  Missing priorities default to~0.

  \item The integer $p$ is the priority of this production.  If

    omitted, it defaults to the maximal priority.  Priorities range

    between 0 and \ttindexbold{max_pri} (= 1000).

\end{itemize}

%

The resulting production is \[ A^{(p)}= w@0\, A@1^{(p@1)}\, w@1\,

A@2^{(p@2)}\, \dots\, A@n^{(p@n)}\, w@n \] where $A$ and the $A@i$ are the

nonterminals corresponding to the types $\tau$ and $\tau@i$ respectively.

The nonterminal symbol associated with a type $(\ldots)ty$ is {\tt logic}, if

this is a logical type (namely one of class {\tt logic} excluding {\tt

prop}).  Otherwise it is $ty$ (note that only the outermost type constructor

is taken into account).  Finally, the nonterminal of a type variable is {\tt

any}.

\begin{warn}

  Theories must sometimes declare types for purely syntactic purposes ---

  merely playing the role of nonterminals.  One example is \tydx{type}, the

  built-in type of types.  This is a `type of all types' in the syntactic

  sense only.  Do not declare such types under {\tt arities} as belonging to

  class {\tt logic}\index{*logic class}, for that would make them useless as

  separate nonterminal symbols.

\end{warn}

Associating nonterminals with types allows a constant's type to specify

syntax as well.  We can declare the function~$f$ to have type $[\tau@1,

\ldots, \tau@n]\To \tau$ and, through a mixfix annotation, specify the layout

of the function's $n$ arguments.  The constant's name, in this case~$f$, will

also serve as the label in the abstract syntax tree.

You may also declare mixfix syntax without adding constants to the theory's

signature, by using a {\tt syntax} section instead of {\tt consts}.  Thus a

production need not map directly to a logical function (this typically

requires additional syntactic translations, see also

Chapter~\ref{chap:syntax}).

\medskip

As a special case of the general mixfix declaration, the form

\begin{center}

  {\tt $c$ ::\ "$\sigma$" ("$template$")}

\end{center}

specifies no priorities.  The resulting production puts no priority

constraints on any of its arguments and has maximal priority itself.

Omitting priorities in this manner is prone to syntactic ambiguities unless

the production's right-hand side is fully bracketed, as in

\verb|"if _ then _ else _ fi"|.

Omitting the mixfix annotation completely, as in {\tt $c$ ::\ "$\sigma$"},

is sensible only if~$c$ is an identifier.  Otherwise you will be unable to

write terms involving~$c$.

\subsection{Example: arithmetic expressions}

\index{examples!of mixfix declarations}

This theory specification contains a {\tt syntax} section with mixfix

declarations encoding the priority grammar from

\S\ref{sec:priority_grammars}:

\begin{ttbox}

ExpSyntax = Pure +

types

  exp

syntax

  "0" :: exp                 ("0"      9)

  "+" :: [exp, exp] => exp   ("_ + _"  [0, 1] 0)

  "*" :: [exp, exp] => exp   ("_ * _"  [3, 2] 2)

  "-" :: exp => exp          ("- _"    [3] 3)

end

\end{ttbox}

Executing {\tt Syntax.print_gram} reveals the productions derived from the

above mixfix declarations (lots of additional information deleted):

\begin{ttbox}

Syntax.print_gram (syn_of ExpSyntax.thy);

{\out exp = "0"  => "0" (9)}

{\out exp = exp[0] "+" exp[1]  => "+" (0)}

{\out exp = exp[3] "*" exp[2]  => "*" (2)}

{\out exp = "-" exp[3]  => "-" (3)}

\end{ttbox}

Note that because {\tt exp} is not of class {\tt logic}, it has been

retained as a separate nonterminal.  This also entails that the syntax

does not provide for identifiers or paranthesized expressions.

Normally you would also want to add the declaration {\tt arities

  exp::logic} after {\tt types} and use {\tt consts} instead of {\tt

  syntax}.  Try this as an exercise and study the changes in the

grammar.

\subsection{Infixes}

\indexbold{infixes}

Infix operators associating to the left or right can be declared using

{\tt infixl} or {\tt infixr}.  Basically, the form {\tt $c$ ::\ 

  $\sigma$ (infixl $p$)} abbreviates the mixfix declarations

\begin{ttbox}

"op \(c\)" :: \(\sigma\)   ("(_ \(c\)/ _)" [\(p\), \(p+1\)] \(p\))

"op \(c\)" :: \(\sigma\)   ("op \(c\)")

\end{ttbox}

and {\tt $c$ ::\ $\sigma$ (infixr $p$)} abbreviates the mixfix declarations

\begin{ttbox}

"op \(c\)" :: \(\sigma\)   ("(_ \(c\)/ _)" [\(p+1\), \(p\)] \(p\))

"op \(c\)" :: \(\sigma\)   ("op \(c\)")

\end{ttbox}

The infix operator is declared as a constant with the prefix {\tt op}.

Thus, prefixing infixes with \sdx{op} makes them behave like ordinary

function symbols, as in \ML.  Special characters occurring in~$c$ must be

escaped, as in delimiters, using a single quote.

A slightly more general form of infix declarations allows constant

names to be independent from their concrete syntax, namely \texttt{$c$

  ::\ $\sigma$\ (infixl "$sy$" $p$)}, the same for \texttt{infixr}.  As

an example consider:

\begin{ttbox}

and :: [bool, bool] => bool  (infixr "&" 35)

\end{ttbox}

The internal constant name will then be just \texttt{and}, without any

\texttt{op} prefixed.

\subsection{Binders}

\indexbold{binders}

\begingroup

\def\Q{{\cal Q}}

A {\bf binder} is a variable-binding construct such as a quantifier.  The

constant declaration

\begin{ttbox}

\(c\) :: \(\sigma\)   (binder "\(\Q\)" [\(pb\)] \(p\))

\end{ttbox}

introduces a constant~$c$ of type~$\sigma$, which must have the form

$(\tau@1 \To \tau@2) \To \tau@3$.  Its concrete syntax is $\Q~x.P$, where

$x$ is a bound variable of type~$\tau@1$, the body~$P$ has type $\tau@2$

and the whole term has type~$\tau@3$.  The optional integer $pb$

specifies the body's priority, by default~$p$.  Special characters

in $\Q$ must be escaped using a single quote.

The declaration is expanded internally to something like

\begin{ttbox}

\(c\)\hskip3pt    :: (\(\tau@1\) => \(\tau@2\)) => \(\tau@3\)

"\(\Q\)"  :: [idts, \(\tau@2\)] => \(\tau@3\)   ("(3\(\Q\)_./ _)" [0, \(pb\)] \(p\))

\end{ttbox}

Here \ndx{idts} is the nonterminal symbol for a list of identifiers with

\index{type constraints}

optional type constraints (see Fig.\ts\ref{fig:pure_gram}).  The

declaration also installs a parse translation\index{translations!parse}

for~$\Q$ and a print translation\index{translations!print} for~$c$ to

translate between the internal and external forms.

A binder of type $(\sigma \To \tau) \To \tau$ can be nested by giving a

list of variables.  The external form $\Q~x@1~x@2 \ldots x@n. P$

corresponds to the internal form

\[ c(\lambda x@1. c(\lambda x@2. \ldots c(\lambda x@n. P) \ldots)). \]

\medskip

For example, let us declare the quantifier~$\forall$:\index{quantifiers}

\begin{ttbox}

All :: ('a => o) => o   (binder "ALL " 10)

\end{ttbox}

This lets us write $\forall x.P$ as either {\tt All(\%$x$.$P$)} or {\tt ALL

  $x$.$P$}.  When printing, Isabelle prefers the latter form, but must fall

back on ${\tt All}(P)$ if $P$ is not an abstraction.  Both $P$ and {\tt ALL

  $x$.$P$} have type~$o$, the type of formulae, while the bound variable

can be polymorphic.

\endgroup

\index{mixfix declarations|)}

\section{*Alternative print modes} \label{sec:prmodes}

\index{print modes|(}

%

Isabelle's pretty printer supports alternative output syntaxes.  These

may be used independently or in cooperation.  The currently active

print modes (with precedence from left to right) are determined by a

reference variable.

\begin{ttbox}\index{*print_mode}

print_mode: string list ref

\end{ttbox}

Initially this may already contain some print mode identifiers,

depending on how Isabelle has been invoked (e.g.\ by some user

interface).  So changes should be incremental --- adding or deleting

modes relative to the current value.

Any \ML{} string is a legal print mode identifier, without any predeclaration

required.  The following names should be considered reserved, though:

\texttt{""} (the empty string), \texttt{symbols}, \texttt{xsymbols}, and

\texttt{latex}.

There is a separate table of mixfix productions for pretty printing

associated with each print mode.  The currently active ones are

conceptually just concatenated from left to right, with the standard

syntax output table always coming last as default.  Thus mixfix

productions of preceding modes in the list may override those of later

ones.  Also note that token translations are always relative to some

print mode (see \S\ref{sec:tok_tr}).

\medskip The canonical application of print modes is optional printing

of mathematical symbols from a special screen font instead of {\sc

  ascii}.  Another example is to re-use Isabelle's advanced

$\lambda$-term printing mechanisms to generate completely different

output, say for interfacing external tools like \rmindex{model

  checkers} (see also \texttt{HOL/Modelcheck}).

\index{print modes|)}

\section{Ambiguity of parsed expressions} \label{sec:ambiguity}

\index{ambiguity!of parsed expressions}

To keep the grammar small and allow common productions to be shared

all logical types (except {\tt prop}) are internally represented

by one nonterminal, namely {\tt logic}.  This and omitted or too freely

chosen priorities may lead to ways of parsing an expression that were

not intended by the theory's maker.  In most cases Isabelle is able to

select one of multiple parse trees that an expression has lead

to by checking which of them can be typed correctly.  But this may not

work in every case and always slows down parsing.

The warning and error messages that can be produced during this process are

as follows:

If an ambiguity can be resolved by type inference the following

warning is shown to remind the user that parsing is (unnecessarily)

slowed down.  In cases where it's not easily possible to eliminate the

ambiguity the frequency of the warning can be controlled by changing

the value of {\tt Syntax.ambiguity_level} which has type {\tt int

ref}.  Its default value is 1 and by increasing it one can control how

many parse trees are necessary to generate the warning.

\begin{ttbox}

{\out Ambiguous input "\dots"}

{\out produces the following parse trees:}

{\out \dots}

{\out Fortunately, only one parse tree is type correct.}

{\out You may still want to disambiguate your grammar or your input.}

\end{ttbox}

The following message is normally caused by using the same

syntax in two different productions:

\begin{ttbox}

{\out Ambiguous input "..."}

{\out produces the following parse trees:}

{\out \dots}

{\out More than one term is type correct:}

{\out \dots}

\end{ttbox}

Ambiguities occuring in syntax translation rules cannot be resolved by

type inference because it is not necessary for these rules to be type

correct.  Therefore Isabelle always generates an error message and the

ambiguity should be eliminated by changing the grammar or the rule.

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: "ref"

%%% End: