+\hrule
+\end{table}
+
+\begin{table}
+\caption{\label{tab:wfl2} Well-formedness rules for level 2 patterns.\strut}
+\hrule
+\[
+\renewcommand{\arraystretch}{3.5}
+\begin{array}{@{}c@{}}
+ \inference[\sc Constr]
+ {P_i :: D_i}
+ {\BLOB[P_1,\dots,P_n] :: D_i \oplus \cdots \oplus D_j} \\
+ \inference[\sc TermVar]
+ {}
+ {\mathtt{term}~x :: x : \mathtt{Term}}
+ \quad
+ \inference[\sc NumVar]
+ {}
+ {\mathtt{number}~x :: x : \mathtt{Number}}
+ \\
+ \inference[\sc IdentVar]
+ {}
+ {\mathtt{ident}~x :: x : \mathtt{String}}
+ \quad
+ \inference[\sc FreshVar]
+ {}
+ {\mathtt{fresh}~x :: x : \mathtt{String}}
+ \\
+ \inference[\sc Success]
+ {}
+ {\mathtt{anonymous} :: \emptyset}
+ \\
+ \inference[\sc Fold]
+ {P_1 :: D_1 & P_2 :: D_2 \oplus (x : \mathtt{Term}) & \DOMAIN(D_2)\ne\emptyset & \DOMAIN(D_1)\cap\DOMAIN(D_2)=\emptyset}
+ {\mathtt{fold}~P_1~\mathtt{rec}~x~P_2 :: D_1 \oplus D_2~\mathtt{List}}
+ \\
+ \inference[\sc Default]
+ {P_1 :: D \oplus D_1 & P_2 :: D & \DOMAIN(D_1) \ne \emptyset & \DOMAIN(D) \cap \DOMAIN(D_1) = \emptyset}
+ {\mathtt{default}~P_1~P_2 :: D \oplus D_1~\mathtt{Option}}
+ \\
+ \inference[\sc If]
+ {P_1 :: \emptyset & P_2 :: D & P_3 :: D }
+ {\mathtt{if}~P_1~\mathtt{then}~P_2~\mathtt{else}~P_3 :: D}
+ \qquad
+ \inference[\sc Fail]
+ {}
+ {\mathtt{fail} :: \emptyset}
+%% & | & \verb+if+~\NT{meta}~\verb+then+~\NT{meta}~\verb+else+~\NT{meta} \\
+%% & | & \verb+fail+
+\end{array}
+\]
+\hrule
+\end{table}
+
+\begin{table}
+ \caption{\label{tab:il2f1} Instantiation of level 2 patterns from level 1.
+ \strut}
+\hrule
+\[
+\begin{array}{rcll}
+
+\IOT{C[t_1,\dots,t_n]}{\mathcal{E}} & =
+& C[\IOT{t_1}{\mathcal{E}},\dots,\IOT{t_n}{\mathcal{E}}] \\
+
+\IOT{\mathtt{term}~x}{\mathcal{E}} & = & t & \mathcal{E}(x) = \mathtt{Term}~t \\
+
+\IOT{\mathtt{number}~x}{\mathcal{E}} & =
+& n & \mathcal{E}(x) = \mathtt{Number}~n \\
+
+\IOT{\mathtt{ident}~x}{\mathcal{E}} & =
+& y & \mathcal{E}(x) = \mathtt{String}~y \\
+
+\IOT{\mathtt{fresh}~x}{\mathcal{E}} & = & y & \mathcal{E}(x) = \mathtt{String}~y \\
+
+\IOT{\mathtt{default}~P_1~P_2}{\mathcal{E}} & =
+& \IOT{P_1}{\UPDATE{\mathcal{E}}{x_i|->v_i}}
+& \mathcal{E}(x_i)=\mathtt{Some}~v_i \\
+& & & \NAMES(P_1)\setminus\NAMES(P_2)=\{x_1,\dots,x_n\} \\
+
+\IOT{\mathtt{default}~P_1~P_2}{\mathcal{E}} & =
+& \IOT{P_2}{\UPDATE{\mathcal{E}}{x_i|->\bot}}
+& \mathcal{E}(x_i)=\mathtt{None} \\
+& & & \NAMES(P_1)\setminus\NAMES(P_2)=\{x_1,\dots,x_n\} \\
+
+\IOT{\mathtt{fold}~\mathtt{right}~P_1~\mathtt{rec}~x~P_2}{\mathcal{E}}
+& =
+& \IOT{P_1}{\mathcal{E}'}
+& \mathcal{E}(\NAMES(P_2)\setminus\{x\}) = \{[],\dots,[]\} \\
+& & \multicolumn{2}{l}{\mathcal{E}'=\UPDATE{\mathcal{E}}{\NAMES(P_2)\setminus\{x\}|->\bot}}
+\\
+
+\IOT{\mathtt{fold}~\mathtt{right}~P_1~\mathtt{rec}~x~P_2}{\mathcal{E}}
+& =
+& \IOT{P_2}{\mathcal{E}'}
+& \mathcal{E}(y_i) = [v_{i1},\dots,v_{in}] \\
+& & & \NAMES(P_2)\setminus\{x\}=\{y_1,\dots,y_m\} \\
+& & \multicolumn{2}{l}{\mathcal{E}'(y) =
+ \left\{
+ \begin{array}{@{}ll}
+ \IOT{\mathtt{fold}~\mathtt{right}~P_1~\mathtt{rec}~x~P_e}{\mathcal{E}''}
+ & y=x \\
+ v_{i1} & y=y_i \\
+ \mathcal{E}(y) & \mbox{otherwise} \\
+ \end{array}
+ \right.} \\
+& & \multicolumn{2}{l}{\mathcal{E}''(y) =
+ \left\{
+ \begin{array}{@{}ll}
+ [v_{i2};\dots;v_{in}] & y=y_i \\
+ \mathcal{E}(y) & \mbox{otherwise} \\
+ \end{array}
+ \right.} \\
+
+\IOT{\mathtt{fold}~\mathtt{left}~P_1~\mathtt{rec}~x~P_2}{\mathcal{E}}
+& =
+& \mathit{eval\_fold}(x,P_2,\mathcal{E}')
+& \\
+& & \multicolumn{2}{l}{\mathcal{E}' = \UPDATE{\mathcal{E}}{x|->
+\IOT{P_1}{\UPDATE{\mathcal{E}}{\NAMES(P_2)|->\bot}}}} \\
+
+\mathit{eval\_fold}(x,P,\mathcal{E})
+& =
+& \mathcal{E}(x)
+& \mathcal{E}(\NAMES(P)\setminus\{x\})=\{[],\dots,[]\} \\
+
+\mathit{eval\_fold}(x,P,\mathcal{E})
+& =
+& \mathit{eval\_fold}(x,P,\mathcal{E}')
+& \mathcal{E}(y_i) = [v_{i1},\dots,v_{in}] \\
+& & & \NAMES(P)\setminus{x}=\{y_1,\dots,y_m\} \\
+&
+& \multicolumn{2}{l}{\mathcal{E}' = \UPDATE{\mathcal{E}}{x|->\IOT{P}{\mathcal{E}''}; ~ y_i |-> [v_{i2};\dots;v_{in_i}]}}
+\\
+&
+& \multicolumn{2}{l}{\mathcal{E}''(y) =
+\left\{
+\begin{array}{ll}
+ v_1 & y\in \NAMES(P)\setminus\{x\} \\
+ \mathcal{E}(x) & y=x \\
+ \bot & \mathit{otherwise} \\
+\end{array}
+\right.
+}
+\\
+
+\end{array} \\
+\]
+\end{table}
+
+\begin{table}
+\caption{\label{tab:l2match} Pattern matching of level 2 terms.\strut}
+\hrule
+\[
+\renewcommand{\arraystretch}{3.5}
+\begin{array}{@{}c@{}}
+ \inference[\sc Constr]
+ {t_i \in P_i ~> \mathcal E_i & i\ne j => \DOMAIN(\mathcal E_i)\cap\DOMAIN(\mathcal E_j)=\emptyset}
+ {C[t_1,\dots,t_n] \in C[P_1,\dots,P_n] ~> \mathcal E_1 \oplus \cdots \oplus \mathcal E_n}
+ \\
+ \inference[\sc TermVar]
+ {}
+ {t \in [\mathtt{term}]~x ~> [x |-> \mathtt{Term}~t]}
+ \quad
+ \inference[\sc NumVar]
+ {}
+ {n \in \mathtt{number}~x ~> [x |-> \mathtt{Number}~n]}
+ \\
+ \inference[\sc IdentVar]
+ {}
+ {x \in \mathtt{ident}~x ~> [x |-> \mathtt{String}~x]}
+ \quad
+ \inference[\sc FreshVar]
+ {}
+ {x \in \mathtt{fresh}~x ~> [x |-> \mathtt{String}~x]}
+ \\
+ \inference[\sc Success]
+ {}
+ {t \in \mathtt{anonymous} ~> \emptyset}
+ \\
+ \inference[\sc DefaultT]
+ {t \in P_1 ~> \mathcal E}
+ {t \in \mathtt{default}~P_1~P_2 ~> \mathcal E'}
+ \quad
+ \mathcal E'(x) = \left\{
+ \renewcommand{\arraystretch}{1}
+ \begin{array}{ll}
+ \mathtt{Some}~\mathcal{E}(x) & x \in \NAMES(P_1) \setminus \NAMES(P_2) \\
+ \mathcal{E}(x) & \mbox{otherwise}
+ \end{array}
+ \right.
+ \\
+ \inference[\sc DefaultF]
+ {t \not\in P_1 & t \in P_2 ~> \mathcal E}
+ {t \in \mathtt{default}~P_1~P_2 ~> \mathcal E'}
+ \quad
+ \mathcal E'(x) = \left\{
+ \renewcommand{\arraystretch}{1}
+ \begin{array}{ll}
+ \mathtt{None} & x \in \NAMES(P_1) \setminus \NAMES(P_2) \\
+ \mathcal{E}(x) & \mbox{otherwise}
+ \end{array}
+ \right.
+ \\
+ \inference[\sc IfT]
+ {t \in P_1 ~> \mathcal E' & t \in P_2 ~> \mathcal E}
+ {t \in \mathtt{if}~P_1~\mathtt{then}~P_2~\mathtt{else}~P_3 ~> \mathcal E}
+ \quad
+ \inference[\sc IfF]
+ {t \not\in P_1 & t \in P_3 ~> \mathcal E}
+ {t \in \mathtt{if}~P_1~\mathtt{then}~P_2~\mathtt{else}~P_3 ~> \mathcal E}
+ \\
+ \inference[\sc FoldRec]
+ {t \in P_2 ~> \mathcal E & \mathcal{E}(x) \in \mathtt{fold}~d~P_1~\mathtt{rec}~x~P_2 ~> \mathcal E'}
+ {t \in \mathtt{fold}~d~P_1~\mathtt{rec}~x~P_2 ~> \mathcal E''}
+ \\
+ \mbox{where}~\mathcal{E}''(y) = \left\{
+ \renewcommand{\arraystretch}{1}
+ \begin{array}{ll}
+ \mathcal{E}(y)::\mathcal{E}'(y) & y \in \NAMES(P_2) \setminus \{x\} \wedge d = \mathtt{right} \\
+ \mathcal{E}'(y)@[\mathcal{E}(y)] & y \in \NAMES(P_2) \setminus \{x\} \wedge d = \mathtt{left} \\
+ \mathcal{E}'(y) & \mbox{otherwise}
+ \end{array}
+ \right.
+ \\
+ \inference[\sc FoldBase]
+ {t \not\in P_2 & t \in P_1 ~> \mathcal E}
+ {t \in \mathtt{fold}~P_1~\mathtt{rec}~x~P_2 ~> \mathcal E'}
+ \quad
+ \mathcal E'(y) = \left\{
+ \renewcommand{\arraystretch}{1}
+ \begin{array}{ll}
+ [] & y \in \NAMES(P_2) \setminus \{x\} \\
+ \mathcal{E}(y) & \mbox{otherwise}
+ \end{array}
+ \right.
+\end{array}
+\]
+\hrule
+\end{table}
+
+\begin{table}
+ \caption{\label{tab:synl3} Abstract syntax of level 3 terms and patterns.}
+ \hrule
+ \[
+ \begin{array}{@{}ll@{}}
+ \begin{array}[t]{rcll}
+ T & : := & & \mbox{(\bf terms)} \\
+ & & u & \mbox{(uri)} \\
+ & | & \lambda x.T & \mbox{($\lambda$-abstraction)} \\
+ & | & (T_1 \dots T_n) & \mbox{(application)} \\
+ & | & \dots \\[2ex]
+ \end{array} &
+ \begin{array}[t]{rcll}
+ P & : := & & \mbox{(\bf patterns)} \\
+ & & u & \mbox{(uri)} \\
+ & | & V & \mbox{(variable)} \\
+ & | & (P_1 \dots P_n) & \mbox{(application)} \\[2ex]
+ V & : := & & \mbox{(\bf variables)} \\
+ & & \TVAR{x} & \mbox{(term variable)} \\
+ & | & \IMPVAR & \mbox{(implicit variable)} \\
+ \end{array} \\
+ \end{array}
+ \]
+ \hrule
+\end{table}
+
+\begin{table}
+\caption{\label{tab:wfl3} Well-formedness rules for level 3 patterns.\strut}
+\hrule
+\[
+\renewcommand{\arraystretch}{3.5}
+\begin{array}{@{}c@{}}
+ \inference[\sc Uri] {} {u :: \emptyset} \quad
+ \inference[\sc ImpVar] {} {\TVAR{x} :: \emptyset} \quad
+ \inference[\sc TermVar] {} {\TVAR{x} :: x:\mathtt{Term}} \\
+ \inference[\sc Appl]
+ {P_i :: D_i
+ \quad \forall i,j,i\neq j=>\DOMAIN(D_i)\cap\DOMAIN(D_j)=\emptyset}
+ {P_1\cdots P_n :: D_1\oplus\cdots\oplus D_n} \\
+\end{array}
+\]
+\hrule
+\end{table}
+
+\begin{table}
+ \caption{\label{tab:synargp} Abstract syntax of applicative symbol patterns.}
+ \hrule
+ \[
+ \begin{array}{rcll}
+ P & : := & & \mbox{(\bf patterns)} \\
+ & & s ~ \{ \mathit{arg} \} & \mbox{(symbol pattern)} \\[2ex]
+ \mathit{arg} & : := & & \mbox{(\bf argument)} \\
+ & & \TVAR{x} & \mbox{(term variable)} \\
+ & | & \eta.\mathit{arg} & \mbox{($\eta$-abstraction)} \\
+ \end{array}
+ \]
+ \hrule
+\end{table}
+
+\begin{table}
+\caption{\label{tab:wfargp} Well-formedness rules for applicative symbol
+patterns.\strut}
+\hrule
+\[
+\renewcommand{\arraystretch}{3.5}
+\begin{array}{@{}c@{}}
+ \inference[\sc Pattern]
+ {\mathit{arg}_i :: D_i
+ \quad \forall i,j,i\neq j=>\DOMAIN(D_i)\cap\DOMAIN(D_j)=\emptyset}
+ {s~\mathit{arg}_1\cdots\mathit{arg}_n :: D_1\oplus\cdots\oplus D_n} \\
+ \inference[\sc TermVar]
+ {}
+ {\TVAR{x} :: x : \mathtt{Term}}
+ \quad
+ \inference[\sc EtaAbs]
+ {\mathit{arg} :: D}
+ {\eta.\mathit{arg} :: D}
+ \\
+\end{array}
+\]
+\hrule
+\end{table}
+
+\begin{table}
+\caption{\label{tab:l3match} Pattern matching of level 3 terms.\strut}
+\hrule
+\[
+\renewcommand{\arraystretch}{3.5}
+\begin{array}{@{}c@{}}
+ \inference[\sc Uri] {} {u\in u ~> []} \quad
+ \inference[\sc Appl] {t_i\in P_i ~> \mathcal{E}_i}
+ {(t_1\dots t_n)\in(P_1\dots P_n) ~>
+ \mathcal{E}_1\oplus\cdots\oplus\mathcal{E}_n} \\
+ \inference[\sc TermVar] {} {t\in \TVAR{x} ~> [x |-> \mathtt{Term}~t]} \quad
+ \inference[\sc ImpVar] {} {t\in \IMPVAR ~> []} \\
+\end{array}
+\]
+\hrule
+\end{table}
+
+\begin{table}
+\caption{\label{tab:iapf3} Instantiation of applicative symbol patterns (from
+level 3).\strut}
+\hrule
+\[
+\begin{array}{rcll}
+ \IAP{s~a_1\cdots a_n}{\mathcal{E}} & = &
+ (s~\IAPP{a_1}{\mathcal{E}}{0}\cdots\IAPP{a_n}{\mathcal{E}}{0}) & \\
+ \IAPP{\TVAR{x}}{\mathcal{E}}{0} & = & t & \mathcal{E}(x)=\mathtt{Term}~t \\
+ \IAPP{\TVAR{x}}{\mathcal{E}}{i+1} & = & \lambda y.\IAPP{t}{\mathcal{E}}{i}
+ & \mathcal{E}(x)=\mathtt{Term}~\lambda y.t \\
+ \IAPP{\TVAR{x}}{\mathcal{E}}{i+1} & =
+ & \lambda y_1.\cdots.\lambda y_{i+1}.t~y_1\cdots y_{i+1}
+ & \mathcal{E}(x)=\mathtt{Term}~t\wedge\forall y,t\neq\lambda y.t \\
+ \IAPP{\eta.a}{\mathcal{E}}{i} & = & \IAPP{a}{\mathcal{E}}{i+1} \\
+\end{array}
+\]
+\hrule
+\end{table}
+
+\section{Type checking}
+
+\subsection{Level 1 $<->$ Level 2}
+
+\newcommand{\GUARDED}{\mathit{guarded}}
+\newcommand{\TRUE}{\mathit{true}}
+\newcommand{\FALSE}{\mathit{false}}
+
+\newcommand{\TN}{\mathit{tn}}
+
+\begin{table}
+\caption{\label{tab:guarded} Guarded condition of level 2
+pattern. Note that the recursive case of the \texttt{fold} magic is
+not explicitly required to be guarded. The point is that it must
+contain at least two distinct names, and this guarantees that whatever
+is matched by the recursive pattern, the terms matched by those two
+names will be smaller than the whole matched term.\strut} \hrule
+\[
+\begin{array}{rcll}
+ \GUARDED(C(M(P))) & = & \GUARDED(P) \\
+ \GUARDED(C(t_1,\dots,t_n)) & = & \TRUE \\
+ \GUARDED(\mathtt{term}~x) & = & \FALSE \\
+ \GUARDED(\mathtt{number}~x) & = & \FALSE \\
+ \GUARDED(\mathtt{ident}~x) & = & \FALSE \\
+ \GUARDED(\mathtt{fresh}~x) & = & \FALSE \\
+ \GUARDED(\mathtt{anonymous}) & = & \TRUE \\
+ \GUARDED(\mathtt{default}~P_1~P_2) & = & \GUARDED(P_1) \wedge \GUARDED(P_2) \\
+ \GUARDED(\mathtt{if}~P_1~\mathtt{then}~P_2~\mathtt{else}~P_3) & = & \GUARDED(P_2) \wedge \GUARDED(P_3) \\
+ \GUARDED(\mathtt{fail}) & = & \TRUE \\
+ \GUARDED(\mathtt{fold}~d~P_1~\mathtt{rec}~x~P_2) & = & \GUARDED(P_2)
+\end{array}
+\]
+\hrule