--- a/handouts/ho09.tex Mon Jun 05 10:50:36 2023 +0100
+++ b/handouts/ho09.tex Wed Jul 05 16:12:40 2023 +0100
@@ -19,29 +19,31 @@
Reflecting on our two tiny compilers targetting the JVM, the code
generation part was actually not so hard, no? Pretty much just some
-post-traversal of the abstract syntax tree, yes? One of the reasons
+post-traversal of the abstract syntax tree. Yes? One of the reasons
for this ease is that the JVM is a stack-based virtual machine and it
is therefore not hard to translate deeply-nested arithmetic
expressions into a sequence of instructions manipulating the
-stack. The problem is that ``real'' CPUs, although supporting stack
-operations, are not really designed to be \emph{stack machines}. The
-design of CPUs is more like: Here are some instructions and a chunk of
+stack. That is pretty much the whole point of the JVM. The problem is
+that ``real'' CPUs, although supporting stack operations, are not
+really designed to be \emph{stack machines}. The design of CPUs is
+more like: Here are some instructions and a chunk of
memory---compiler, or better compiler writers, do something with
them. Consequently, modern compilers need to go the extra mile in
order to generate code that is much easier and faster to process by
actual CPUs, rather than running code on virtual machines that
introduce an additional layer of indirection. To make this all
-tractable for this module, we target the LLVM Intermediate
-Language. In this way we can take advantage of the tools coming with
-LLVM.\footnote{\url{http://llvm.org}} For example we do not have to
-worry about things like register allocations. By using the LLVM-IR,
-however, we also have to pay price in the sense that generating code
-gets harder\ldots{}unfor\-tunately.
+tractable for this module, we target the \emph{LLVM Intermediate
+ Language} (LLVM-IR). In this way we can take advantage of the tools
+coming with LLVM.\footnote{\url{http://llvm.org}} For example we do
+not have to worry about things like register allocations or peephole
+optimisations. By using the LLVM-IR, however, we also have to pay
+price in the sense that generating code gets
+harder\ldots{}unfor\-tunately nothing comes for free in life.
\subsection*{LLVM and the LLVM-IR}
\noindent LLVM is a beautiful example
-that projects from Academia can make a difference in the World. LLVM
+that projects from Academia can make a difference in the Real World. LLVM
started in 2000 as a project by two researchers at the University of
Illinois at Urbana-Champaign. At the time the behemoth of compilers was
gcc with its myriad of front-ends for different programming languages (C++, Fortran,
@@ -73,14 +75,36 @@
reason why LLVM uses the SSA-format, rather than JVM-like stack
instructions, is that stack instructions are difficult to
optimise---you cannot just re-arrange instructions without messing
-about with what is calculated on the stack. Also it is hard to find
-out if all the calculations on the stack are actually necessary and
-not by chance dead code. The JVM has for all these obstacles
-sophisticated machinery to make such ``high-level'' code still run
-fast, but let's say that for the sake of argument we do not want to
-rely on it. We want to generate fast code ourselves. This means we
-have to work around the intricacies of what instructions CPUs can
-actually process fast. This is what the SSA format is designed for.
+about with what is calculated on the stack. Have a look at the
+expression $((a + b) * 4) - (3 * (a + b))$ and the corresponding JVM
+instructions:
+
+\begin{lstlisting}[language=JVMIS, numbers=none,mathescape]
+iload a
+iload b
+iadd
+ldc 4
+imul
+ldc 3
+iload a
+iload b
+iadd
+imul
+isub
+\end{lstlisting}
+
+\noindent
+and try to reorganise the code such that you calculate the expression
+$(a + b)$ only once. This requires either quite a bit of
+math-understanding from the compiler or you need to add ``copy-and-fetch''
+of a result from a local variable. Also it is hard to find out if all
+the calculations on the stack are actually necessary and not by chance
+dead code. The JVM has for all these obstacles sophisticated machinery
+to make such ``high-level'' code still run fast, but let's say that
+for the sake of argument we do not want to rely on it. We want to
+generate fast code ourselves. This means we have to work around the
+intricacies of what instructions CPUs can actually process fast. This
+is what the SSA format is designed for.
The main idea behind the SSA-format is to have sequences of very
@@ -105,10 +129,12 @@
example, not write \texttt{tmp1 = add tmp2 tmp3} in Line 5 even if
this would not change the overall result). At the end we have a
return-instruction wich contains the final result of the
-expression. As can be seen, the task we have to solve is to take apart
-compound expressions as shown above and transfrom them into a sequence
-of simple assignments. Note that this for example means we have to
-fix the order in which the expression is calculated.
+expression. As can be seen the task we have to solve for generating
+SSA-code is to take apart compound expressions into its most basic
+''particles'' and transfrom them into a sequence of simple assignments
+that calculates the desired result. Note that this means we have to
+fix the order in which the expression is calculated, like from the
+left to right.
There are sophisticated algorithms for imperative languages, like C,
that efficiently transform high-level programs into SSA-format. But
@@ -355,14 +381,14 @@
\end{lstlisting}
\noindent
-By having in \texttt{KLet} taking first a string (standing for a
+By having \texttt{KLet} taking first a string (standing for a
tmp-variable) and second a value, we can fulfil the SSA constraint in
assignments ``by con\-struction''---there is no way we could write
anything else than a K-value. Note that the third argument of a
\texttt{KLet} is again a K-expression, meaning either another
\texttt{KLet} or a \texttt{KReturn}. In this way we can construct a
-sequence of computations and indicate what is the final result of the
-computations. According to the SSA-format, we also have to ensure
+sequence of computations and indicate what the final result of the
+computations is. According to the SSA-format, we also have to ensure
that all intermediary computations are given (fresh) names---we will
use an (ugly) counter for this.
@@ -371,7 +397,7 @@
it is easy to generate the SSA-format for the LLVM-IR. What remains to
be done is a translation of our Fun-language into the K-language. The
main difficulty is that we need to order the computation---in the
-K-language we only have linear sequence of instructions. Before we
+K-language we only have linear sequences of instructions. Before we
explain this, we have a look at some programs in CPS-style.
@@ -479,20 +505,21 @@
Let us now come back to the CPS-translations for the Fun-language.
Though we will start with a simpler subset containing only numbers,
-arithmetic expressions and function calls. The main difficulty of
-generating instructions in SSA-format is that large compound
-expressions need to be broken up into smaller pieces and intermediate
-results need to be chained into later instructions. To do this
-conveniently, we use the CPS-translation mechanism. What continuations
-essentially solve is the following problem: Given an expressions
+arithmetic expressions and function calls---no variables for the
+moment. The main difficulty of generating instructions in SSA-format
+is that large compound expressions need to be broken up into smaller
+pieces and intermediate results need to be chained into later
+instructions. To do this conveniently, we use the CPS-translation
+mechanism. What the continuations essentially solve is the following
+problem: Given an expressions
\begin{equation}\label{exp}
(1 + 2) * (3 + 4)
\end{equation}
\noindent
-which of the subexpressions should be calculated first? We just
-arbitrarily going to decide that the calculation will be from left to
+which of the subexpressions should be calculated first? We are going
+arbitrarily to decide that the calculation will be from left to
right. Other languages make different choices---C famously is right to
left. In our case this means we have to tear the expression shown in
\eqref{exp} apart as follows:
@@ -569,7 +596,7 @@
be compiled. The result of the function is a K-expression, which later
can be compiled into LLVM-IR code.
-In case we have numbers, then we can just pass them in CPS-translation
+In case we have numbers, then we can just pass them in the CPS-translation
to the continuations because numbers need not be further teared apart
as they are already primitive. Passing the number to the continuation
means we apply the continuation like
@@ -595,7 +622,7 @@
\noindent
What we essentially have to do in this case is the following: compile
the subexpressions \texttt{e1} and \texttt{e2}. They will produce some
-result that is stored in two temporary variables (assuming they are more
+result that is stored in two temporary variables (assuming \texttt{e1} and \texttt{e2} are more
complicated than just numbers). We need to use these two temporary
variables and feed them into a new assignment of the form
@@ -621,11 +648,13 @@
the result of the computation of the arithmetic expression is stored
in \texttt{z} to the computations that follow. In this way we apply
the continuation \texttt{k} with this new variable (essentially we are
-plugging in a hole further down the line). Hope this makes sense.
+plugging in a hole further down the line). Hope this makes sense!? If not,
+play with the given code yourself.
The last case we need to consider in our small expression language are
function calls. For them remember each argument of the function
-call can in SSA-format only be a variable or a number.
+call can in SSA-format only be a variable or a number. Here is the
+complete code for this case:
\begin{lstlisting}[language=Scala,numbers=left,xleftmargin=0mm]
case Call(fname, args) => {
@@ -641,7 +670,7 @@
\end{lstlisting}
\noindent
-For this case we introduce an auxiliary function that compiles first all
+As can be seen, we introduce an auxiliary function that compiles first all
function arguments---remember in our source language we can have calls
such as $foo(3 + 4, g(3))$ where we first have to create temporary
variables (and computations) for each argument. Therefore \texttt{aux}
@@ -649,7 +678,7 @@
argument \texttt{a} on the front of the list (the case \texttt{a::as}
in Line 7), we call CPS recursively for the corresponding
subexpression. The temporary variable containing the result for this
-argument we add to the end of the K-values we have already analysed
+argument, we add to the end of the K-values we have already analysed
before. Again very conveniently we can use the recursive call to
\texttt{aux} as the continuation for the computations that
follow. When we reach the end of the argument list (the
@@ -703,19 +732,23 @@
\section*{Next Steps}
Having obtained a K-expression, it is relatively straightforward to
-generate a valid program for the LLVM-IR. We leave this to the
-attentive reader. What else can we do? Well it should be relatively
-easy to apply some common optimisations to the K-expressions. One
-optimisations is called constant folding---for example if we have an
-expression $3 + 4$ then we can replace it by just $5$ instead of
-generating code to compute $5$. Now this information needs to be
-propagated to the next computation step to see whether any further
-constant foldings are possible. Another useful technique is common
-subexpression elimination, meaning if you have twice a calculation of
-a function $foo(a)$, then we want to call it only once and store the
-result in a temporary variable that can be used instead of the second,
-or third, call to $foo(a)$. Again I leave this to the attentive reader
-to work out and implement.
+generate a valid program for the LLVM-IR---remember the K-language
+already enforces the SSA convention of a linear sequence of primitive
+instructions involving only unique temporary variables.
+We leave this step to the attentive reader.
+
+What else can we do? Well it should be relatively easy to apply some
+common optimisations to the K-expressions. One optimisations is called
+constant folding---for example if we have an expression $3 + 4$ then
+we can replace it by just $5$ instead of generating code to compute
+$5$. Now this information needs to be propagated to the next
+computation step to see whether any further constant foldings are
+possible. Another useful technique is common subexpression
+elimination, meaning if you have twice a calculation of a function
+$foo(a)$, then we want to call it only once and store the result in a
+temporary variable that can be used instead of the second, or third,
+call to $foo(a)$. Again I leave this to the attentive reader to work
+out and implement.
\begin{figure}[p]\small
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slides/ssy.tex Wed Jul 05 16:12:40 2023 +0100
@@ -0,0 +1,742 @@
+% !TEX program = xelatex
+\documentclass[dvipsnames,14pt,t,xelatex,xcolor={table}]{beamer}
+\usepackage{../slides}
+\usepackage{../graphicss}
+\usepackage{../langs}
+\usepackage{../data}
+\usetikzlibrary{cd}
+
+
+\usepackage{tcolorbox}
+\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+
+
+
+\hfuzz=220pt
+
+\lstset{language=Scala,
+ style=mystyle,
+ numbersep=0pt,
+ numbers=none,
+ xleftmargin=0mm}
+
+\pgfplotsset{compat=1.17}
+
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
+
+% beamer stuff
+\renewcommand{\slidecaption}{SSY, King's College London}
+
+
+
+\begin{document}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{%
+ \begin{tabular}{@ {}c@ {}}
+ \\[8mm]
+ \LARGE Derivative-Based\\
+ \LARGE Regular Expression Matching\\[5mm]
+ \normalsize\textcolor{gray}{Christian Urban, SSY Group}
+ \end{tabular}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{A Bit of Background}
+
+\begin{textblock}{10}(2,2.5)
+\includegraphics[scale=0.4]{../pics/phd-1.jpg}
+\end{textblock}
+
+\begin{textblock}{11}(1.7,10)
+\begin{bubble}[9.6cm]
+ PhD thesis on a particular term-rewriting system:\medskip\\
+ Proved that all rewriting sequences are strongly normalising (terminate).
+\end{bubble}
+\end{textblock}
+
+\only<2->{%
+\begin{textblock}{3}(10,2.5)
+\begin{bubble}[3cm]
+\begin{tabular}{rcl}
+ \bl{$t$} & \bl{::=} & \bl{$x$}\\
+ & \bl{|} & \bl{$\lambda x.\,t$}\\
+ & \bl{|} & \bl{$t_1\;t_2$}\\
+ & \bl{|} & \bl{...}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\end{frame}
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 1}
+\begin{bubble}[10cm]\it
+ There are many, many regular expression libraries.\bigskip\\
+
+ \textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
+ difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
+\end{bubble}
+
+\begin{textblock}{12}(2,9)
+\begin{tikzpicture}
+ \draw(0,0) node[rotate=20]{linear};
+ \draw(3,0) node[rotate=-20]{\bl{$O(n \log n)$}};
+ \draw(3,-2) node[rotate=10]{quadratic};
+ \draw(6,0) node[rotate=20]{P};
+ \draw(7,0) node[rotate=-20]{NP};
+ \draw(7,-1) node[rotate=0]{\bl{$O(2^n)$}};
+\end{tikzpicture}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 2}
+
+\begin{textblock}{12}(2,2.5)
+A regular expression for (some) email addresses:
+\begin{center}
+ ($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\_\!\!\_\,.-]^+}}_{\textrm{name}}$)\bl{$\,@\,$}
+ ($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\,-]^+}}_{\textrm{domain}}$) \bl{$\,.\,$}
+ ($\underbrace{\bl{[a\mbox{-}z\,.]^{\{2..5\}}}}_{\textrm{top-level domain}}$)
+\end{center}
+\end{textblock}
+
+\only<2>{
+\begin{textblock}{10}(4,8)
+bounded regular expressions:\medskip\\
+\begin{tabular}{ll}
+ \bl{$r^{\{n\}}$} & exactly n-times \bl{$r$}\\
+ \bl{$r^{\{n..m\}}$} & between n and m-times\\
+ \bl{$r^{\{n..\}}$} & from n-times\\
+ \bl{$r^{\{..m\}}$} & upto m-times\\
+\end{tabular}\smallskip\\
+\footnotesize\hfill ${}^*$ in some applications the counters can be in the millions
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 2}
+
+
+\begin{textblock}{12}(2,2.5)
+ \onslide<1->{Thompson construction: By recursion we are given two NFAs for $r_1$ and $r_2$.\medskip\\
+ \onslide<2->{For $r_1\cdot r_2$:}\bigskip}
+\end{textblock}
+
+\begin{textblock}{12}(2,6)
+\onslide<1>{
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20}]
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
+\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
+\node (R_1) [right=of Q_0] {$\ldots$};
+\node[state, accepting] (T_1) [right=of R_1] {$\mbox{}$};
+\node[state, accepting] (T_2) [above=of T_1] {$\mbox{}$};
+\node[state, accepting] (T_3) [below=of T_1] {$\mbox{}$};
+
+\node (A_0) [right=2.5cm of T_1] {$\mbox{}$};
+\node[state, initial] (A_01) [above=1mm of A_0] {$\mbox{}$};
+\node[state, initial] (A_02) [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1) [right=of A_0] {$\ldots$};
+\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
+\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
+\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
+\begin{pgfonlayer}{background}
+ \node (1) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_3)] {};
+ \node (2) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
+\node [yshift=2mm] at (1.north) {$r_1$};
+\node [yshift=2mm] at (2.north) {$r_2$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\end{textblock}
+
+\begin{textblock}{12}(2,6)
+\onslide<2>{
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
+\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
+\node (r_1) [right=of Q_0] {$\ldots$};
+\node[state] (t_1) [right=of r_1] {$\mbox{}$};
+\node[state] (t_2) [above=of t_1] {$\mbox{}$};
+\node[state] (t_3) [below=of t_1] {$\mbox{}$};
+
+\node (A_0) [right=2.5cm of t_1] {$\mbox{}$};
+\node[state] (A_01) [above=1mm of A_0] {$\mbox{}$};
+\node[state] (A_02) [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1) [right=of A_0] {$\ldots$};
+\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
+\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
+\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
+\path[->] (t_1) edge (A_01);
+\path[->] (t_2) edge node [above] {$\varepsilon$\footnotesize{}s} (A_01);
+\path[->] (t_3) edge (A_01);
+\path[->] (t_1) edge (A_02);
+\path[->] (t_2) edge (A_02);
+\path[->] (t_3) edge node [below] {$\varepsilon$\footnotesize{}s} (A_02);
+
+\begin{pgfonlayer}{background}
+ \node (3) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
+\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\end{textblock}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 2}
+
+\begin{textblock}{12}(2,2.5)
+ \onslide<1->{Thompson construction: By recursion we have a NFA for $r$.\medskip\\
+ \onslide<2->{For $r^*$:\bigskip}}
+\end{textblock}
+
+\begin{textblock}{12}(4,6)
+\onslide<1>{
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.north)]
+\node (2) {$\mbox{}$};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots$};
+\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
+\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
+\begin{pgfonlayer}{background}
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
+\node [yshift=3mm] at (1.north) {$r$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\end{textblock}
+
+\begin{textblock}{12}(2,6)
+\onslide<2->{
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.north)]
+\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
+\node (2) [right=16mm of 1] {$\mbox{}$};
+\node[state] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state] (5) [below=1mm of 2] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots$};
+\node[state] (a1) [right=of a] {$\mbox{}$};
+\node[state] (a2) [above=of a1] {$\mbox{}$};
+\node[state] (a3) [below=of a1] {$\mbox{}$};
+\path[->] (1) edge node [below] {$\varepsilon$} (4);
+\path[->] (1) edge node [below] {$\varepsilon$} (5);
+\path[->] (a1) edge [bend left=45] node [below] {$\varepsilon$} (1);
+\path[->] (a2) edge [bend right] node [below] {$\varepsilon$} (1);
+\path[->] (a3) edge [bend left=45] node [below] {$\varepsilon$} (1);
+\begin{pgfonlayer}{background}
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
+\node [yshift=3mm] at (2.north) {$r^*$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\end{textblock}
+
+\begin{textblock}{12}(2,12)
+\onslide<3->{
+ \begin{bubble}[9.5cm]\it
+ Quiz:\smallskip\\
+ \textbf{What is the Thompson Construction for \bl{$r^{\{n\}}$} ?}
+\end{bubble}}
+\end{textblock}
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+ \frametitle{Quiz 3}
+
+Hierarchy of Languages:
+
+\begin{center}
+\begin{tikzpicture}
+[rect/.style={draw=black!50,
+ top color=white,
+ bottom color=black!20,
+ rectangle,
+ very thick,
+ rounded corners}, scale=1.2]
+
+\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
+\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
+\draw (0,-0.85) node [rect, text depth=17mm] {\;\;context sensitive languages\;\;};
+\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
+\draw (0,-1.4) node [rect] {regular languages};
+\end{tikzpicture}
+\end{center}
+
+\begin{textblock}{12}(2,11.5)
+\onslide<2->{
+ \begin{bubble}[9.5cm]\it
+ Quiz:\smallskip\\
+
+ \textbf{Can we use standard parsing algorithms for matching / lexing\,?}
+ Say CYK, LL, LR(k), PEG, \ldots
+\end{bubble}}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\defverbatim{\foo}{\footnotesize%
+\begin{verbatim}
+(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
+null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
+| -|~|!|{}|\|\||\+)*.*(?:.*=.*)))
+\end{verbatim}
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{Quiz 4}
+
+\begin{textblock}{12}(2,2.5)
+\begin{bubble}[9.5cm]\it
+ Quiz:\smallskip\\
+ Do regular expressions have any security relevance\,?
+\end{bubble}
+\end{textblock}
+
+\only<2->{
+\begin{textblock}{2}(1,6)
+\includegraphics[scale=0.8]{../pics/zeek.png}
+\includegraphics[scale=0.17]{../pics/snort.png}
+\end{textblock}}
+
+\only<3->{
+\begin{textblock}{7}(7,5.6)
+ \includegraphics[scale=0.14]{../pics/cloudflare.png}\\
+ \footnotesize
+ It serves more web traffic than Twitter, Amazon, Apple,
+ Instagram, Bing \& Wikipedia combined.\medskip\\
+ Web Application Firewall filters out
+ SQL injection attacks, XSS attacks etc
+\end{textblock}}
+
+\only<3->{
+ \begin{textblock}{13}(4,12.3)
+ \footnotesize
+ \hspace{1.5cm}a global outage on 2 July 2019 (first one for six years)
+ \color{blue}\foo\color{black}
+ \end{textblock}
+}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+ \frametitle{Quiz 3}
+
+\begin{textblock}{12}(2,2)
+ \begin{bubble}[9.5cm]\it
+ Quiz:\smallskip\\
+
+ \textbf{Can we use standard parsing algorithms for matching / lexing\,?}
+ Say CYK, LL, LR(k), PEG, \ldots
+\end{bubble}
+\end{textblock}
+
+
+\begin{textblock}{12}(1,7)
+\textbf{POSIX lexing}
+
+\begin{tabular}{@ {}ll}
+ Assume you have: & \bl{$r_{key} \dn \texttt{if} + \texttt{then} + \texttt{while} \ldots$}\\
+ & \bl{$r_{id\;} \,\dn \texttt{[a-z]} \cdot \texttt{[a-z0-9\_]}^*$}\medskip\\
+
+ Lexing a string with & \bl{$(r_{key} + r_{id})^*$}\medskip\\
+
+ What should be & \\
+ the result for: & \bl{\texttt{"iffoo"}} \;\;\; \bl{\texttt{"if"}}\\
+\end{tabular}
+\end{textblock}
+
+\only<2->{
+\begin{textblock}{13.5}(1.5,4)
+ \begin{mybox3}{POSIX rules}
+ \begin{itemize}
+ \item \textbf{The Longest Match Rule:} The longest initial
+ substring matched by any regular expression is taken as next token.
+ \item \textbf{Priority Rule:} For a particular longest initial
+ substring, the first (leftmost) regular expression that can match
+ determines the token.
+ \item \ldots
+ \end{itemize}
+ \begin{center}
+ \bl{$(a + ab) \cdot (bc + c)$} \;\;and\;\; \bl{\texttt{"}$abc$\texttt{"}}
+ \end{center}
+ \end{mybox3}
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 1}
+\begin{bubble}[10cm]\it
+ There are many, many regular expression libraries.\bigskip\\
+
+ \textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
+ difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
+\end{bubble}
+
+\begin{textblock}{12}(1,9)
+ \begin{tabular}{p{4cm}|p{4cm}|p{2cm}}
+ atrociously slow (s't) & pretty lazy (s't) & \textcolor{gray}{OTBT}\medskip\\
+ Python, Ruby, Swift, Dart, JavaScript & Rust, Go, RE2 & \textcolor{gray}{Snort, .Net7}\\
+ \end{tabular}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
+\mbox{}\\[10mm]
+
+\begin{columns}[t,onlytextwidth]
+\begin{column}{.2\textwidth}
+\raisebox{-10mm}{
+\begin{tikzpicture}
+ \begin{axis}[
+ xlabel={\bl{$n$} \pcode{a}s},
+ %%x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,10,...,30},
+ xmax=35,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5cm,
+ height=5cm,
+ legend entries={Python,JavaScript,Swift,Dart},
+ legend style={font=\small,at={(0.5,-0.39)},anchor=north},
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
+\end{axis}
+\end{tikzpicture}}
+\end{column}
+
+\begin{column}{.2\textwidth}
+\begin{tikzpicture}
+ \begin{axis}[
+ xlabel={\bl{$n$} \pcode{a}s},
+ %ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,10,...,30},
+ xmax=35,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5cm,
+ height=5cm,
+ legend entries={Python,Ruby},
+ legend style={font=\small,at={(0.5,-0.39)},anchor=north},
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
+\end{axis}
+\end{tikzpicture}
+\end{column}
+\end{columns}
+
+\begin{textblock}{4}(9,1.7)
+\textbf{\bl{\texttt{(a?)\boldmath$^{\{n\}}\cdot$(a)\boldmath$^{\{n\}}$}}}
+\end{textblock}
+
+\begin{textblock}{4}(4,1.7)
+\textbf{\bl{\texttt{(a*)*$\cdot$b}}}
+\end{textblock}
+
+\begin{textblock}{3.4}(0.3,10)
+\small{}\textbf{matching with strings}
+\textbf{\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Quiz 1}
+\begin{bubble}[10cm]\it
+ \textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
+ difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
+\end{bubble}
+
+\begin{textblock}{12}(1.7,7)
+For \textbf{Perl-style} regular expression matchers (say Python, JavaScript, etc), the
+answer is:
+\only<2->{\begin{center}
+\fontspec{Hoefler Text Black}\textcolor{ProcessBlue}{\huge{}NP}
+\end{center}}
+\end{textblock}
+
+\begin{textblock}{12}(1.7,12)
+\only<3->{Backreferences: \bl{(\ldots)$\,\ldots{}\backslash{}n$}}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}
+\frametitle{Quiz 2}
+
+\begin{textblock}{12}(2,2)
+\onslide<1->{
+ \begin{bubble}[9.5cm]\it
+ Quiz:\smallskip\\
+ \textbf{What is the Thompson Construction for \bl{$r^{\{n\}}$} ?}
+\end{bubble}}
+\end{textblock}
+
+\only<2->{
+\begin{textblock}{12}(1,6)
+\begin{tabular}{ll}
+ Google's RE2 lib & $\Rightarrow$ \bl{$a^{\{1001\}}$} is too big\\
+ \onslide<3->{Rust Regex lib} & \onslide<5->{$\Rightarrow$ \bl{$a^{\{1000\}\{100\}\{5\}}$} too big}\\
+ & \onslide<6->{$\Rightarrow$ \bl{$a^{\{0\}\{4294967295\}}$} ?}
+\end{tabular}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{13.5}(1.5,4)
+ \begin{mybox3}{From Rust's Regex Description}\it
+ ``\ldots [the] syntax is similar to Perl-style regular expressions, but lacks a few features like look
+ around and backreferences. In exchange, all searches execute in linear time with respect
+ to the size of the regular expression and search text. \ldots''
+ \end{mybox3}
+\end{textblock}}
+
+
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Regular Expressions}
+
+\begin{textblock}{6}(2,5)
+ \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
+ & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} \\
+ & \bl{$\mid$} & \bl{$c, d, \ldots$} & characters\\
+ & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
+ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+ & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
+ \end{tabular}
+ \end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{l}The Derivative of a Rexp\end{tabular}}
+
+\large
+If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular
+expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
+
+\small
+\bl{$\der\,c\,r$} gives the answer, Brzozowski 1964\medskip\\
+(lost in the sands of time, re-appeared in 2009)
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{l}The Derivative of a Rexp\end{tabular}}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
+ \bl{$\der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$\der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
+ \bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\
+ \bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
+ & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\
+ & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\
+ \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\
+ \end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\begin{tabular}{l}Brzozowski matcher\end{tabular}}
+
+Does \bl{$r_1$} match \bl{"$abc$"}?
+\begin{center}
+\begin{tabular}{@{}rl@{}l@{}}
+Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\
+Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\
+Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\
+Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\
+ & test whether \bl{$r_4$} can recognise\\
+ & the empty string\medskip\\
+Output: & result of the test\\
+ & $\Rightarrow \bl{\textit{true}} \,\text{or}\,
+ \bl{\textit{false}}$\\
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{Nullable}}
+
+
+\ldots{}whether a regular expression can match the empty string:
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$nullable(\ZERO)$} & \bl{$\dn$} & \bl{\textit{false}}\\
+\bl{$nullable(\ONE)$} & \bl{$\dn$} & \bl{\textit{true}}\\
+\bl{$nullable (c)$} & \bl{$\dn$} & \bl{\textit{false}}\\
+\bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\
+\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
+\bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{\textit{true}}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\begin{tabular}{l}Extensions\end{tabular}}
+
+\begin{center}
+\begin{tabular}{@ {\hspace{-4mm}}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
+ \bl{$\der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;\ZERO\;else\; (der\,c\,r)\cdot r^{\{n-1\}}$} & \\
+ \bl{$\der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;\ZERO\;else\; (der\,c\,r)\cdot r^{\{n-1\}}$} & \\
+ \bl{$\der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;(der\,c\,r)\cdot r^*$} \\
+ & & \bl{$else\; (der\,c\,r)\cdot r^{\{n-1\}}$} & \\
+ \bl{$\der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & \bl{$if\;n=0 \wedge m=0\;then\;\ZERO\;else$} & \\
+ & & \bl{$if \;n=0 \wedge 0<m\; then\;(der\,c\,r)\cdot r^{\{..m-1\}}$} & \\
+ & & \bl{$else\; (der\,c\,r)\cdot r^{\{n-1..m-1\}}$} & \\
+ \bl{$\der\, c\, (\neg{}r)$} & \bl{$\dn$} & \bl{$\neg(der\,c\,r)$}\\
+ \end{tabular}
+\end{center}
+
+also works for lookarounds, various anchors, etc, but \textbf{not} for backreferences
+
+\begin{textblock}{3}(11,13)
+\onslide<2>{
+ \begin{bubble}[3cm]
+ \bl{$a^{\{0\}\{4294967295\}}$}
+\end{bubble}}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\mbox{Problems with Ders}}
+
+\textcolor{blue}{
+\small
+\def\ll{\stackrel{der\,a}{\longrightarrow}}
+\begin{center}
+\begin{tabular}{@{\hspace{-5mm}}rll}
+$(a + aa)^*$ & $\ll$ & $(\ONE + \ONE{}a) \cdot (a + aa)^*$\\
+& $\ll$ & $(\ZERO + \ZERO{}a + \ONE) \cdot (a + aa)^* \;+\; (\ONE + \ONE{}a) \cdot (a + aa)^*$\\
+& $\ll$ & $(\ZERO + \ZERO{}a + \ZERO) \cdot (a + aa)^* + (\ONE + \ONE{}a) \cdot (a + aa)^* \;+\; $\\
+& & $\qquad(\ZERO + \ZERO{}a + \ONE) \cdot (a + aa)^* + (\ONE + \ONE{}a) \cdot (a + aa)^*$\\
+& $\ll$ & \ldots\\ \hspace{15mm}
+\end{tabular}
+\end{center}}
+
+\begin{textblock}{13.5}(1.5,12)
+(regular expressions of sizes 98, 169, 283, 468, 767, \ldots)
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{Conclusion}}
+
+\begin{itemize}
+\item The beauty is that this only involves functional programs that can be conveniently reasoned about in theorem provers
+\item POSIX lexing can be done via an extension by Sulzmann and Lu, 2014 (our current work)\medskip\pause
+\item How surprising that one can still do new work on regular expressions.
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}<1-10>
+\end{frame}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
+