Paper/Paper.thy
changeset 1587 b6da798cef68
parent 1579 5b0bdd64956e
child 1607 ac69ed8303cc
--- a/Paper/Paper.thy	Mon Mar 22 18:38:59 2010 +0100
+++ b/Paper/Paper.thy	Tue Mar 23 07:39:10 2010 +0100
@@ -54,8 +54,8 @@
   also there one would like to bind multiple variables at once.
 
   Binding multiple variables has interesting properties that cannot be captured
-  easily by iterating single binders. For example in the case of type-schemes we do not
-  like to make a distinction about the order of the bound variables. Therefore
+  easily by iterating single binders. For example in case of type-schemes we do not
+  want to make a distinction about the order of the bound variables. Therefore
   we would like to regard the following two type-schemes as alpha-equivalent
   %
   \begin{equation}\label{ex1}
@@ -63,14 +63,15 @@
   \end{equation}
 
   \noindent
-  but  the following two should \emph{not} be alpha-equivalent
+  but assuming that $x$, $y$ and $z$ are distinct variables,
+  the following two should \emph{not} be alpha-equivalent
   %
   \begin{equation}\label{ex2}
   \forall \{x, y\}. x \rightarrow y  \;\not\approx_\alpha\; \forall \{z\}. z \rightarrow z 
   \end{equation}
 
   \noindent
-  assuming that $x$, $y$ and $z$ are distinct. Moreover, we like to regard type-schemes as 
+  Moreover, we like to regard type-schemes as 
   alpha-equivalent, if they differ only on \emph{vacuous} binders, such as
   %
   \begin{equation}\label{ex3}
@@ -87,7 +88,7 @@
 
   However, the notion of alpha-equivalence that is preserved by vacuous binders is not
   always wanted. For example in terms like
-
+  %
   \begin{equation}\label{one}
   \LET x = 3 \AND y = 2 \IN x\,-\,y \END
   \end{equation}
@@ -96,7 +97,7 @@
   we might not care in which order the assignments $x = 3$ and $y = 2$ are
   given, but it would be unusual to regard \eqref{one} as alpha-equivalent 
   with
-
+  %
   \begin{center}
   $\LET x = 3 \AND y = 2 \AND z = loop \IN x\,-\,y \END$
   \end{center}
@@ -109,7 +110,7 @@
   However, we found that this is still not sufficient for dealing with
   language constructs frequently occurring in programming language
   research. For example in $\mathtt{let}$s containing patterns
-
+  %
   \begin{equation}\label{two}
   \LET (x, y) = (3, 2) \IN x\,-\,y \END
   \end{equation}
@@ -118,7 +119,7 @@
   we want to bind all variables from the pattern inside the body of the
   $\mathtt{let}$, but we also care about the order of these variables, since
   we do not want to regard \eqref{two} as alpha-equivalent with
-
+  %
   \begin{center}
   $\LET (y, x) = (3, 2) \IN x\,- y\,\END$
   \end{center}
@@ -131,7 +132,7 @@
   By providing these general binding mechanisms, however, we have to work around 
   a problem that has been pointed out by Pottier in \cite{Pottier06}: in 
   $\mathtt{let}$-constructs of the form
-
+  %
   \begin{center}
   $\LET x_1 = t_1 \AND \ldots \AND x_n = t_n \IN s \END$
   \end{center}
@@ -141,7 +142,7 @@
   which the $x_i = t_i$ are given, but we do care about the information that there are 
   as many $x_i$ as there are $t_i$. We lose this information if we represent the 
   $\mathtt{let}$-constructor by something like 
-
+  %
   \begin{center}
   $\LET [x_1,\ldots,x_n].s\;\; [t_1,\ldots,t_n]$
   \end{center}
@@ -154,7 +155,7 @@
   lists are of equal length. This can result into very messy reasoning (see
   for example~\cite{BengtsonParow09}). To avoid this, we will allow type specifications
   for $\mathtt{let}$s as follows
-
+  %
   \begin{center}
   \begin{tabular}{r@ {\hspace{2mm}}r@ {\hspace{2mm}}l}
   $trm$ & $::=$  & \ldots\\ 
@@ -385,10 +386,10 @@
 section {* General Binders *}
 
 text {*
-  In Nominal Isabelle the user is expected to write down a specification of a
-  term-calculus and a reasoning infrastructure is then automatically derived
+  In Nominal Isabelle, the user is expected to write down a specification of a
+  term-calculus and then a reasoning infrastructure is automatically derived
   from this specifcation (remember that Nominal Isabelle is a definitional
-  extension of Isabelle/HOL and cannot introduce new axioms).
+  extension of Isabelle/HOL, which does not introduce any new axioms).
 
 
   In order to keep our work manageable, we will wherever possible state
@@ -508,11 +509,50 @@
   \begin{proof}
   All properties are by unfolding the definitions and simple calculations. 
   \end{proof}
+
+
+  \begin{lemma}
+  $supp ([as]set. x) = supp x - as$ 
+  \end{lemma}
 *}
 
 section {* Alpha-Equivalence and Free Variables *}
 
 text {*
+  A specification of a term-calculus in Nominal Isabelle is a collection
+  of (possibly mutual recursive) type declarations, say $ty_1$, $ty_2$, \ldots $ty_n$ 
+  written as follows:
+
+  \begin{center}
+  \begin{tabular}{l}
+  \isacommand{nominal\_datatype} $ty_1 =$\\
+  \isacommand{and} $ty_2 =$\\
+  $\ldots$\\ 
+  \isacommand{and} $ty_n =$\\ 
+  $\ldots$\\
+  \isacommand{with}\\
+  $\ldots$\\
+  \end{tabular}
+  \end{center}
+
+  \noindent
+  The section below the \isacommand{with} are binding functions, which
+  will be explained below.
+  
+
+
+  A specification of a term-calculus in Nominal Isabell is very similar to 
+  the usual datatype definition of Isabelle/HOL: 
+
+
+  Because of the problem Pottier pointed out in \cite{Pottier06}, the general 
+  binders from the previous section cannot be used directly to represent w 
+  be used directly 
+*}
+
+
+
+text {*
   Restrictions
 
   \begin{itemize}