1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
\documentclass{article}
\usepackage{fullpage,amsmath,amssymb,proof}
\newcommand{\cd}[1]{\texttt{#1}}
\newcommand{\mt}[1]{\mathsf{#1}}
\newcommand{\rc}{+ \hspace{-.075in} + \;}
\begin{document}
\title{The Ur/Web Manual}
\author{Adam Chlipala}
\maketitle
\section{Syntax}
\subsection{Lexical Conventions}
We give the Ur language definition in \LaTeX $\;$ math mode, since that is prettier than monospaced ASCII. The corresponding ASCII syntax can be read off directly. Here is the key for mapping math symbols to ASCII character sequences.
\begin{center}
\begin{tabular}{rl}
\textbf{\LaTeX} & \textbf{ASCII} \\
$\to$ & \cd{->} \\
$\times$ & \cd{*} \\
$\lambda$ & \cd{fn} \\
$\Rightarrow$ & \cd{=>} \\
$\rc$ & \cd{++} \\
\\
$x$ & Normal textual identifier, not beginning with an uppercase letter \\
$X$ & Normal textual identifier, beginning with an uppercase letter \\
\end{tabular}
\end{center}
We often write syntax like $e^*$ to indicate zero or more copies of $e$, $e^+$ to indicate one or more copies, and $e,^*$ and $e,^+$ to indicate multiple copies separated by commas. Another separator may be used in place of a comma. The $e$ term may be surrounded by parentheses to indicate grouping; those parentheses should not be included in the actual ASCII.
\subsection{Core Syntax}
\emph{Kinds} classify types and other compile-time-only entities. Each kind in the grammar is listed with a description of the sort of data it classifies.
$$\begin{array}{rrcll}
\textrm{Kinds} & \kappa &::=& \mt{Type} & \textrm{proper types} \\
&&& \mt{Unit} & \textrm{the trivial constructor} \\
&&& \mt{Name} & \textrm{field names} \\
&&& \kappa \to \kappa & \textrm{type-level functions} \\
&&& \{\kappa\} & \textrm{type-level records} \\
&&& (\kappa\times^+) & \textrm{type-level tuples} \\
&&& (\kappa) & \textrm{explicit precedence} \\
\end{array}$$
Ur supports several different notions of functions that take types as arguments. These arguments can be either implicit, causing them to be inferred at use sites; or explicit, forcing them to be specified manually at use sites. There is a common explicitness annotation convention applied at the definitions of and in the types of such functions.
$$\begin{array}{rrcll}
\textrm{Explicitness} & ? &::=& :: & \textrm{explicit} \\
&&& \; ::: & \textrm{implicit}
\end{array}$$
\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} \\
\\
&&& \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} \\
\\
&&& () & \textrm{type-level unit} \\
&&& \#X & \textrm{field name} \\
\\
&&& [(c = c)^*] & \textrm{known-length type-level record} \\
&&& c \rc c & \textrm{type-level record concatenation} \\
&&& \mt{fold} & \textrm{type-level record fold} \\
\\
&&& (c^+) & \textrm{type-level tuple} \\
&&& c.n & \textrm{type-level tuple projection ($n \in \mathbb N^+$)} \\
\\
&&& \lambda [c \sim c] \Rightarrow c & \textrm{guarded constructor} \\
\\
&&& (c) & \textrm{explicit precedence} \\
\end{array}$$
Modules of the module system are described by \emph{signatures}.
$$\begin{array}{rrcll}
\textrm{Signatures} & S &::=& \mt{sig} \; s^* \; \mt{end} & \textrm{constant} \\
&&& X & \textrm{variable} \\
&&& \mt{functor}(X : S) : S & \textrm{functor} \\
&&& S \; \mt{where} \; x = c & \textrm{concretizing an abstract constructor} \\
&&& M.X & \textrm{projection from a module} \\
\\
\textrm{Signature items} & s &::=& \mt{con} \; x :: \kappa & \textrm{abstract constructor} \\
&&& \mt{con} \; x :: \kappa = c & \textrm{concrete constructor} \\
&&& \mt{datatype} \; x \; x^* = dc\mid^+ & \textrm{algebraic datatype declaration} \\
&&& \mt{datatype} \; x = M.x & \textrm{algebraic datatype import} \\
&&& \mt{val} \; x : \tau & \textrm{value} \\
&&& \mt{structure} \; X : S & \textrm{sub-module} \\
&&& \mt{signature} \; X = S & \textrm{sub-signature} \\
&&& \mt{include} \; S & \textrm{signature inclusion} \\
&&& \mt{constraint} \; c \sim c & \textrm{record disjointness constraint} \\
&&& \mt{class} \; x & \textrm{abstract type class} \\
&&& \mt{class} \; x = c & \textrm{concrete type class} \\
\\
\textrm{Datatype constructors} & dc &::=& X & \textrm{nullary constructor} \\
&&& X \; \mt{of} \; \tau & \textrm{unary constructor} \\
\end{array}$$
\end{document}
|
