Paper/Paper.thy
changeset 2156 029f8aabed12
parent 2141 b9292bbcffb6
child 2163 5dc48e1af733
--- a/Paper/Paper.thy	Tue May 18 11:47:29 2010 +0200
+++ b/Paper/Paper.thy	Tue May 18 14:40:05 2010 +0100
@@ -922,30 +922,33 @@
   ``\isacommand{bind}-part'' will be called \emph{binders}. 
 
   In contrast to Ott, we allow multiple labels in binders and bodies. For example
-  we have binding clauses of the form:
+  we allow binding clauses of the form:
 
   \begin{center}
-  \begin{tabular}{ll}
-  @{text "Foo x::name y::name t::lam s::lam"} &  
-      \isacommand{bind} @{text "x y"} \isacommand{in} @{text "t s"}  
+  \begin{tabular}{@ {}ll@ {}}
+  @{text "Foo\<^isub>1 x::name y::name t::lam s::lam"} &  
+      \isacommand{bind} @{text "x y"} \isacommand{in} @{text "t s"}\\
+  @{text "Foo\<^isub>2 x::name y::name t::lam s::lam"} &  
+      \isacommand{bind} @{text "x y"} \isacommand{in} @{text "t"}, 
+      \isacommand{bind} @{text "x y"} \isacommand{in} @{text "s"}\\
   \end{tabular}
   \end{center}
 
   \noindent
-  Similarly for the other binding modes.
+  Similarly for the other binding modes. Interestingly, in case of \isacommand{bind\_set}
+  and \isacommand{bind\_res} the binding clauses will make a difference in
+  terms of the corresponding alpha-equivalence. We will show this later with an example.
   
-
-  There are a few restrictions we need to impose: First, a body can only occur in
-  \emph{one} binding clause of a term constructor. 
-  For binders we distinguish between \emph{shallow} and \emph{deep} binders.
-  Shallow binders are just labels. The
-  restriction we need to impose on them is that in case of
-  \isacommand{bind\_set} and \isacommand{bind\_res} the labels must
-  either refer to atom types or to sets of atom types; in case of
-  \isacommand{bind} the labels must refer to atom types or lists of atom types. 
-  Two examples for the use of shallow binders are the specification of
-  lambda-terms, where a single name is bound, and type-schemes, where a finite
-  set of names is bound:
+  There are some restrictions we need to impose: First, a body can only occur
+  in \emph{one} binding clause of a term constructor. For binders we
+  distinguish between \emph{shallow} and \emph{deep} binders.  Shallow binders
+  are just labels. The restriction we need to impose on them is that in case
+  of \isacommand{bind\_set} and \isacommand{bind\_res} the labels must either
+  refer to atom types or to sets of atom types; in case of \isacommand{bind}
+  the labels must refer to atom types or lists of atom types. Two examples for
+  the use of shallow binders are the specification of lambda-terms, where a
+  single name is bound, and type-schemes, where a finite set of names is
+  bound:
 
   \begin{center}
   \begin{tabular}{@ {}cc@ {}}
@@ -967,23 +970,25 @@
   \end{center}
 
   \noindent
-  Note that for @{text lam} it does not matter which binding mode we use. The reason is that 
-  we bind only a single @{text name}. However, having \isacommand{bind\_set} or 
-  \isacommand{bind} in the second
-  case changes the semantics of the specification. 
-  Note also that in these specifications @{text "name"} refers to an atom type, and
-  @{text "fset"} to the type of finite sets. 
+  Note that for @{text lam} it does not matter which binding mode we use. The
+  reason is that we bind only a single @{text name}. However, having
+  \isacommand{bind\_set} or \isacommand{bind} in the second case again makes a
+  difference to the underlying notion of alpha-equivalence. Note also that in
+  these specifications @{text "name"} refers to an atom type, and @{text
+  "fset"} to the type of finite sets.
+
 
   A \emph{deep} binder uses an auxiliary binding function that ``picks'' out
-  the atoms in one argument of the term-constructor, which can be bound in  
-  other arguments and also in the same argument (we will
-  call such binders \emph{recursive}, see below). 
-  The corresponding binding functions are expected to return either a set of atoms
-  (for \isacommand{bind\_set} and \isacommand{bind\_res}) or a list of atoms
-  (for \isacommand{bind}). They can be defined by primitive recursion over the
-  corresponding type; the equations must be given in the binding function part of
-  the scheme shown in \eqref{scheme}. For example a term-calculus containing @{text "Let"}s 
-  with tuple patterns might be specified as:
+  the atoms in one argument of the term-constructor, which can be bound in
+  other arguments and also in the same argument (we will call such binders
+  \emph{recursive}, see below). The corresponding binding functions are
+  expected to return either a set of atoms (for \isacommand{bind\_set} and
+  \isacommand{bind\_res}) or a list of atoms (for \isacommand{bind}). They can
+  be defined by primitive recursion over the corresponding type; the equations
+  must be given in the binding function part of the scheme shown in
+  \eqref{scheme}. For example a term-calculus containing @{text "Let"}s with
+  tuple patterns might be specified as:
+
   %
   \begin{equation}\label{letpat}
   \mbox{%
@@ -1065,9 +1070,7 @@
 
   \noindent
   The reason why we must exclude such specifications is that they cannot be
-  represented by the general binders described in Section
-  \ref{sec:binders}. Unlike shallow binders, we restrict deep binders to occur
-  in only one binding clause.
+  represented by the general binders described in Section~\ref{sec:binders}. 
 
   We also need to restrict the form of the binding functions. As will shortly
   become clear, we cannot return an atom in a binding function that is also
@@ -1084,7 +1087,7 @@
   (case @{text PTup}). This restriction will simplify some automatic proofs
   later on.
   
-  In order to simplify later definitions, we shall assume specifications 
+  In order to simplify our definitions, we shall assume specifications 
   of term-calculi are \emph{completed}. By this we mean that  
   for every argument of a term-constructor that is \emph{not} 
   already part of a binding clause, we add implicitly a special \emph{empty} binding