changeset 530:c2f9f94ea709

Kinding
author Adam Chlipala <adamc@hcoop.net>
date Sat, 29 Nov 2008 09:34:11 -0500
parents 4df69124e9c5
children e47eff8c9037
files doc/manual.tex
diffstat 1 files changed, 90 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/doc/manual.tex	Thu Nov 27 16:55:30 2008 -0500
+++ b/doc/manual.tex	Sat Nov 29 09:34:11 2008 -0500
@@ -68,14 +68,14 @@
 \emph{Constructors} are the main class of compile-time-only data.  They include proper types and are classified by kinds.
 $$\begin{array}{rrcll}
   \textrm{Constructors} & c, \tau &::=& (c) :: \kappa & \textrm{kind annotation} \\
-  &&& x & \textrm{constructor variable} \\
+  &&& \hat{x} & \textrm{constructor variable} \\
   \\
   &&& \tau \to \tau & \textrm{function type} \\
   &&& x \; ? \; \kappa \to \tau & \textrm{polymorphic function type} \\
   &&& \$ c & \textrm{record type} \\
   \\
   &&& c \; c & \textrm{type-level function application} \\
-  &&& \lambda x \; ? \; \kappa \Rightarrow c & \textrm{type-level function abstraction} \\
+  &&& \lambda x \; :: \; \kappa \Rightarrow c & \textrm{type-level function abstraction} \\
   \\
   &&& () & \textrm{type-level unit} \\
   &&& \#X & \textrm{field name} \\
@@ -91,6 +91,9 @@
   \\
   &&& \_ :: \kappa & \textrm{wildcard} \\
   &&& (c) & \textrm{explicit precedence} \\
+  \\
+  \textrm{Qualified uncapitalized variables} & \hat{x} &::=& x & \textrm{not from a module} \\
+  &&& M.x & \textrm{projection from a module} \\
 \end{array}$$
 
 Modules of the module system are described by \emph{signatures}.
@@ -162,9 +165,6 @@
   \\
   \textrm{Local declarations} & ed &::=& \cd{val} \; x : \tau = e & \textrm{non-recursive value} \\
   &&& \cd{val} \; \cd{rec} \; (x : \tau = e \; \cd{and})^+ & \textrm{mutually-recursive values} \\
-  \\
-  \textrm{Qualified uncapitalized variables} & \hat{x} &::=& x & \textrm{not from a module} \\
-  &&& M.x & \textrm{projection from a module} \\
 \end{array}$$
 
 \emph{Declarations} primarily bring new symbols into context.
@@ -229,4 +229,89 @@
 
 A signature item $\mt{table} \; x : c$ is shorthand for $\mt{val} \; x : \mt{Basis}.\mt{sql\_table} \; c$.  $\mt{sequence} \; x$ is short for $\mt{val} \; x : \mt{Basis}.\mt{sql\_sequence}$, and $\mt{cookie} \; x : \tau$ is shorthand for $\mt{val} \; x : \mt{Basis}.\mt{http\_cookie} \; \tau$.
 
+
+\section{Static Semantics}
+
+In this section, we give a declarative presentation of Ur's typing rules and related judgments.  Inference is the subject of the next section; here, we assume that an oracle has filled in all wildcards with concrete values.
+
+Since there is significant mutual recursion among the judgments, we introduce them all before beginning to give rules.  We use the same variety of contexts throughout this section, implicitly introducing new sorts of context entries as needed.
+\begin{itemize}
+\item $\Gamma \vdash c :: \kappa$ assigns a kind to a constructor in a context.
+\item $\Gamma \vdash c \sim c$ proves the disjointness of two record constructors; that is, that they share no field names.  We overload the judgment to apply to pairs of field names as well.
+\item $\Gamma \vdash c \hookrightarrow \overline{c}$ proves that record constructor $c$ decomposes into set $\overline{c}$ of field names and record constructors.
+\item $\Gamma \vdash c \equiv c$ proves the computational equivalence of two constructors.  This is often called a \emph{definitional equality} in the world of type theory.
+\item $\Gamma \vdash e : \tau$ is a standard typing judgment.
+\item $\Gamma \vdash M : S$ is the module signature checking judgment.
+\item $\mt{proj}(M, S, V)$ is a partial function for projecting a signature item from a signature $S$, given the module $M$ that we project from.  $V$ may be $\mt{con} \; x$, $\mt{val} \; x$, $\mt{signature} \; X$, or $\mt{structure} \; X$.  The parameter $M$ is needed because the projected signature item may refer to other items of $S$.
+\end{itemize}
+
+\subsection{Kinding}
+
+$$\infer{\Gamma \vdash (c) :: \kappa :: \kappa}{
+  \Gamma \vdash c :: \kappa
+}
+\quad \infer{\Gamma \vdash x :: \kappa}{
+  x :: \kappa \in \Gamma
+}
+\quad \infer{\Gamma \vdash x :: \kappa}{
+  x :: \kappa = c \in \Gamma
+}$$
+
+$$\infer{\Gamma \vdash M.x :: \kappa}{
+  \Gamma \vdash M : S
+  & \mt{proj}(M, S, \mt{con} \; x) = \kappa
+}
+\quad \infer{\Gamma \vdash M.x :: \kappa}{
+  \Gamma \vdash M : S
+  & \mt{proj}(M, S, \mt{con} \; x) = (\kappa, c)
+}$$
+
+$$\infer{\Gamma \vdash \tau_1 \to \tau_2 :: \mt{Type}}{
+  \Gamma \vdash \tau_1 :: \mt{Type}
+  & \Gamma \vdash \tau_2 :: \mt{Type}
+}
+\quad \infer{\Gamma \vdash x \; ? \: \kappa \to \tau :: \mt{Type}}{
+  \Gamma, x :: \kappa \vdash \tau :: \mt{Type}
+}
+\quad \infer{\Gamma \vdash \$c :: \mt{Type}}{
+  \Gamma \vdash c :: \{\mt{Type}\}
+}$$
+
+$$\infer{\Gamma \vdash c_1 \; c_2 :: \kappa_2}{
+  \Gamma \vdash c_1 :: \kappa_1 \to \kappa_2
+  & \Gamma \vdash c_2 :: \kappa_1
+}
+\quad \infer{\Gamma \vdash \lambda x \; :: \; \kappa_1 \Rightarrow c :: \kappa_1 \to \kappa_2}{
+  \Gamma, x :: \kappa_1 \vdash c :: \kappa_2
+}$$
+
+$$\infer{\Gamma \vdash () :: \mt{Unit}}{}
+\quad \infer{\Gamma \vdash \#X :: \mt{Name}}{}$$
+
+$$\infer{\Gamma \vdash [\overline{c_i = c'_i}] :: \{\kappa\}}{
+  \forall i: \Gamma \vdash c_i : \mt{Name}
+  & \Gamma \vdash c'_i :: \kappa
+  & \forall i \neq j: \Gamma \vdash c_i \sim c_j
+}
+\quad \infer{\Gamma \vdash c_1 \rc c_2 :: \{\kappa\}}{
+  \Gamma \vdash c_1 :: \{\kappa\}
+  & \Gamma \vdash c_2 :: \{\kappa\}
+  & \Gamma \vdash c_1 \sim c_2
+}$$
+
+$$\infer{\Gamma \vdash \mt{fold} :: ((\mt{Name} \to \kappa_1 \to \kappa_2 \to \kappa_2) \to \kappa_2 \to \{\kappa_1\} \to \kappa_2}{}$$
+
+$$\infer{\Gamma \vdash (\overline c) :: (k_1 \times \ldots \times k_n)}{
+  \forall i: \Gamma \vdash c_i :: k_i
+}
+\quad \infer{\Gamma \vdash c.i :: k_i}{
+  \Gamma \vdash c :: (k_1 \times \ldots \times k_n)
+}$$
+
+$$\infer{\Gamma \vdash \lambda [c_1 \sim c_2] \Rightarrow c :: \kappa}{
+  \Gamma \vdash c_1 :: \{\kappa'\}
+  & \Gamma \vdash c_2 :: \{\kappa'\}
+  & \Gamma, c_1 \sim c_2 \vdash c :: \kappa
+}$$
+
 \end{document}
\ No newline at end of file