% Chapter Template

% Main chapter title

\chapter{Bit-coded Algorithm of Sulzmann and Lu}

\label{Bitcoded1} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

%Then we illustrate how the algorithm without bitcodes falls short for such aggressive 

%simplifications and therefore introduce our version of the bitcoded algorithm and 

%its correctness proof in 

%Chapter 3\ref{Chapter3}. 

\section{Bit-coded Algorithm}

The lexer algorithm in Chapter \ref{Inj}, as shown in \ref{InjFigure},

stores information of previous lexing steps

on a stack, in the form of regular expressions

and characters: $r_0$, $c_0$, $r_1$, $c_1$, etc.

\begin{ceqn}

\begin{equation}%\label{graph:injLexer}

\end{tikzcd}

\end{equation}

\end{ceqn}

\noindent

This is both inefficient and prone to stack overflow.

A natural question arises as to whether we can store lexing

information on the fly, while still using regular expression 

\begin{center}

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

         \nodepart{two} $\Seq(\ldots, \Seq(\Char(b), \Char(c)))$};

\end{tikzpicture}

\end{center}

\begin{center}

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={white!30,blue!20},]

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture}

\end{center}

\noindent

\begin{center}

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture}

\end{center}

\noindent

If we do this kind of "attachment"

and each time augment the attached partially

constructed value when taking off a 

character:

\begin{center}

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        {$\Seq(\Stars[\Char(a), \Char(a)], \Seq(\Char(b), \ldots))$

\end{tikzpicture}\\

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        {$\Seq(\Stars[\Char(a), \Char(a)], \Seq(\Char(b), \Char(c)))$

         \nodepart{two} EOF};

\end{tikzpicture}

\end{center}

\noindent

In the end we could recover the value without a backward phase.

But (partial) values are a bit clumsy to stick together with a regular expression, so 

we instead use bit-codes to encode them.

Bits and bitcodes (lists of bits) are defined as:

\begin{center}

		$b ::=   S \mid  Z \qquad

bs ::= [] \mid b::bs    

$

\end{center}

\noindent

Using $S$ and $Z$ rather than $1$ and $0$ is to avoid

confusion with the regular expressions $\ZERO$ and $\ONE$.

Bitcodes (or

bit-lists) can be used to encode values (or potentially incomplete values) in a

compact form. This can be straightforwardly seen in the following

coding function from values to bitcodes: 

\begin{center}

\begin{tabular}{lcl}

  $\textit{code}(\Empty)$ & $\dn$ & $[]$\\

  $\textit{code}(\Char\,c)$ & $\dn$ & $[]$\\

  $\textit{code}(\Left\,v)$ & $\dn$ & $Z :: code(v)$\\

  $\textit{code}(\Right\,v)$ & $\dn$ & $S :: code(v)$\\

  $\textit{code}(\Seq\,v_1\,v_2)$ & $\dn$ & $code(v_1) \,@\, code(v_2)$\\

  $\textit{code}(\Stars\,[])$ & $\dn$ & $[Z]$\\

  $\textit{code}(\Stars\,(v\!::\!vs))$ & $\dn$ & $S :: code(v) \;@\;

                                                 code(\Stars\,vs)$

\end{tabular}    

\end{center} 

\noindent

Here $\textit{code}$ encodes a value into a bit-code by converting

$\Left$ into $Z$, $\Right$ into $S$, and marks the start of any non-empty

star iteration by $S$. The border where a local star terminates

is marked by $Z$. 

This coding is lossy, as it throws away the information about

characters, and also does not encode the ``boundary'' between two

sequence values. Moreover, with only the bitcode we cannot even tell

whether the $S$s and $Z$s are for $\Left/\Right$ or $\Stars$. The

reason for choosing this compact way of storing information is that the

relatively small size of bits can be easily manipulated and ``moved

We define the reverse operation of $\code$, which is $\decode$.

As expected, $\decode$ not only requires the bit-codes,

but also a regular expression to guide the decoding and 

fill the gaps of characters:

%\begin{definition}[Bitdecoding of Values]\mbox{}

\begin{center}

\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}

  $\textit{decode}'\,bs\,(\ONE)$ & $\dn$ & $(\Empty, bs)$\\

  $\textit{decode}'\,bs\,(c)$ & $\dn$ & $(\Char\,c, bs)$\\

  $\textit{decode}'\,(Z\!::\!bs)\;(r_1 + r_2)$ & $\dn$ &

     $\textit{let}\,(v, bs_1) = \textit{decode}'\,bs\,r_1\;\textit{in}\;

       (\Left\,v, bs_1)$\\

  $\textit{decode}'\,(S\!::\!bs)\;(r_1 + r_2)$ & $\dn$ &

     $\textit{let}\,(v, bs_1) = \textit{decode}'\,bs\,r_2\;\textit{in}\;

       (\Right\,v, bs_1)$\\                           

  $\textit{decode}'\,bs\;(r_1\cdot r_2)$ & $\dn$ &

        $\textit{let}\,(v_1, bs_1) = \textit{decode}'\,bs\,r_1\;\textit{in}$\\

  & &   $\textit{let}\,(v_2, bs_2) = \textit{decode}'\,bs_1\,r_2$\\

  & &   \hspace{35mm}$\textit{in}\;(\Seq\,v_1\,v_2, bs_2)$\\

  $\textit{decode}'\,(Z\!::\!bs)\,(r^*)$ & $\dn$ & $(\Stars\,[], bs)$\\

  $\textit{decode}'\,(S\!::\!bs)\,(r^*)$ & $\dn$ & 

         $\textit{let}\,(v, bs_1) = \textit{decode}'\,bs\,r\;\textit{in}$\\

  & &   $\textit{let}\,(\Stars\,vs, bs_2) = \textit{decode}'\,bs_1\,r^*$\\

  & &   \hspace{35mm}$\textit{in}\;(\Stars\,v\!::\!vs, bs_2)$\bigskip\\

  $\textit{decode}\,bs\,r$ & $\dn$ &

     $\textit{let}\,(v, bs') = \textit{decode}'\,bs\,r\;\textit{in}$\\

  & & $\textit{if}\;bs' = []\;\textit{then}\;\textit{Some}\,v\;

       \textit{else}\;\textit{None}$                       

\end{tabular}    

\end{center} 

%\end{definition}

\noindent

$\decode'$ does most of the job while $\decode$ throws

away leftover bit-codes and returns the value only.

$\decode$ is terminating as $\decode'$ is terminating.

We have the property that $\decode$ and $\code$ are

reverse operations of one another:

\begin{lemma}

\[\vdash v : r \implies \decode \; (\code \; v) \; r = \textit{Some}(v) \]

\end{lemma}

\begin{proof}

By proving a more general version of the lemma, on $\decode'$:

\[\vdash v : r \implies \decode' \; ((\code \; v) @ ds) \; r = (v, ds) \]

Then setting $ds$ to be $[]$ and unfolding $\decode$ definition

we get the lemma.

\end{proof}

With the $\code$ and $\decode$ functions in hand, we know how to 

switch between bit-codes and value--the two different representations of 

lexing information. 

The next step is to integrate this information into the working regular expression.

Attaching bits to the front of regular expressions is the solution Sulzamann and Lu

gave for storing partial values on the fly:

\begin{center}

\begin{tabular}{lcl}

  $\textit{a}$ & $::=$  & $\ZERO$\\

                  & $\mid$ & $_{bs}\ONE$\\

                  & $\mid$ & $_{bs}{\bf c}$\\

                  & $\mid$ & $_{bs}\sum\,as$\\

                  & $\mid$ & $_{bs}a_1\cdot a_2$\\

                  & $\mid$ & $_{bs}a^*$

\end{tabular}    

\end{center}  

%(in \textit{ALTS})

\noindent

We call these regular expressions carrying bit-codes \emph{Annotated regular expressions}.

$bs$ stands for bit-codes, $a$  for $\mathbf{a}$nnotated regular

expressions and $as$ for a list of annotated regular expressions.

The alternative constructor ($\sum$) has been generalised to 

accept a list of annotated regular expressions rather than just 2.

The first thing we define related to bit-coded regular expressions

The operation $\fuse$ is just to attach bit-codes 

to the front of an annotated regular expression:

\begin{center}

\begin{tabular}{lcl}

  $\textit{fuse}\;bs \; \ZERO$ & $\dn$ & $\ZERO$\\

  $\textit{fuse}\;bs\; _{bs'}\ONE$ & $\dn$ &

     $_{bs @ bs'}\ONE$\\

  $\textit{fuse}\;bs\;_{bs'}{\bf c}$ & $\dn$ &

     $_{bs@bs'}{\bf c}$\\

  $\textit{fuse}\;bs\,_{bs'}\sum\textit{as}$ & $\dn$ &

     $_{bs@bs'}\sum\textit{as}$\\

  $\textit{fuse}\;bs\; _{bs'}a_1\cdot a_2$ & $\dn$ &

     $_{bs@bs'}a_1 \cdot a_2$\\

  $\textit{fuse}\;bs\,_{bs'}a^*$ & $\dn$ &

     $_{bs @ bs'}a^*$

\end{tabular}    

\end{center} 

\noindent

With that we are able to define $\internalise$.

To do lexing using annotated regular expressions, we shall first

transform the usual (un-annotated) regular expressions into annotated

regular expressions. This operation is called \emph{internalisation} and

defined as follows:

%\begin{definition}

\begin{center}

\begin{tabular}{lcl}

  $(\ZERO)^\uparrow$ & $\dn$ & $\ZERO$\\

  $(\ONE)^\uparrow$ & $\dn$ & $_{[]}\ONE$\\

  $(c)^\uparrow$ & $\dn$ & $_{[]}{\bf c}$\\

  $(r_1 + r_2)^\uparrow$ & $\dn$ &

  $_{[]}\sum[\textit{fuse}\,[Z]\,r_1^\uparrow,\,

  \textit{fuse}\,[S]\,r_2^\uparrow]$\\

  $(r_1\cdot r_2)^\uparrow$ & $\dn$ &

         $_{[]}r_1^\uparrow \cdot r_2^\uparrow$\\

  $(r^*)^\uparrow$ & $\dn$ &

         $_{[]}(r^\uparrow)^*$\\

\end{tabular}    

\end{center}    

%\end{definition}

\noindent

We use an up arrow with postfix notation

to denote the operation, 

for convenience. The $\textit{internalise} \; r$

notation is more cumbersome.

The opposite of $\textit{internalise}$ is

$\erase$, where all the bit-codes are removed,

and the alternative operator $\sum$ for annotated

regular expressions is transformed to the binary alternatives

for plain regular expressions.

\begin{center}

	\begin{tabular}{lcr}

		$\erase \; \ZERO$ & $\dn$ & $\ZERO$\\

		$\erase \; _{bs}\ONE$ & $\dn$ & $\ONE$\\

		$\erase \; _{bs}\mathbf{c}$ & $\dn$ & $\mathbf{c}$\\

		$\erase \; _{bs} a_1 \cdot a_2$ & $\dn$ & $\erase \; r_1\cdot\erase\; r_2$\\

		$\erase \; _{bs} [] $ & $\dn$ & $\ZERO$\\

		$\erase \; _{bs} [a] $ & $\dn$ & $\erase \; a$\\

		$\erase \; _{bs} \sum [a_1, \; a_2]$ & $\dn$ & $\erase \; a_1 +\erase \; a_2$\\

		$\erase \; _{bs} \sum (a :: as)$ & $\dn$ & $\erase \; a + \erase \; _{[]} \sum as$\\

		$\erase \; _{bs} a^*$ & $\dn$ & $(\erase \; a)^*$

	\end{tabular}

\end{center}

\noindent

We also abbreviate the $\erase\; a$ operation

as $a_\downarrow$, for conciseness.

For bit-coded regular expressions, as a different datatype, 

testing whether they contain empty string in their lauguage requires

a dedicated function $\bnullable$

which simply calls $\erase$ first before testing whether it is $\nullable$.

\begin{center}

	\begin{tabular}{lcr}

		$\bnullable \; a $ & $\dn$ & $\nullable \; (a_\downarrow)$

	\end{tabular}

\end{center}

The function for collecting the

bitcodes of a $\bnullable$ annotated regular expression

is a generalised version of the $\textit{mkeps}$ function

for annotated regular expressions, called $\textit{bmkeps}$:

%\begin{definition}[\textit{bmkeps}]\mbox{}

\begin{center}

\begin{tabular}{lcl}

  $\textit{bmkeps}\,(_{bs}\ONE)$ & $\dn$ & $bs$\\

  $\textit{bmkeps}\,(_{bs}\sum a::\textit{as})$ & $\dn$ &

     $\textit{if}\;\textit{bnullable}\,a$\\

  & &$\textit{then}\;bs\,@\,\textit{bmkeps}\,a$\\

  & &$\textit{else}\;bs\,@\,\textit{bmkeps}\,(_{[]}\sum \textit{as})$\\

  $\textit{bmkeps}\,(_{bs} a_1 \cdot a_2)$ & $\dn$ &

     $bs \,@\,\textit{bmkeps}\,a_1\,@\, \textit{bmkeps}\,a_2$\\

  $\textit{bmkeps}\,(_{bs}a^*)$ & $\dn$ &

     $bs \,@\, [Z]$

\end{tabular}    

\end{center}    

%\end{definition}

\noindent

This function completes the value information by travelling along the

path of the regular expression that corresponds to a POSIX value and

collecting all the bitcodes, and using $S$ to indicate the end of star

iterations. 

The most central question is how these partial lexing information

represented as bit-codes is augmented and carried around 

during a derivative is taken.

This is done by adding bitcodes to the 

derivatives, for example when one more star iteratoin is taken (we

call the operation of derivatives on annotated regular expressions $\bder$

we need to unfold it into a sequence,

and attach an additional bit $Z$ to the front of $r \backslash c$

to indicate one more star iteration. 

\begin{center}

  \begin{tabular}{@{}lcl@{}}

  $\bder \; c\; (_{bs}a^*) $ & $\dn$ &

      $_{bs}(\textit{fuse}\, [Z] \; \bder \; c \; a)\cdot

       (_{[]}a^*))$

\end{tabular}    

\end{center}    

\noindent

For most time we use the infix notation $\backslash$ to mean $\bder$ for brevity when

there is no danger of confusion with derivatives on plain regular expressions, 

for example, the above can be expressed as

\begin{center}

  \begin{tabular}{@{}lcl@{}}

  $(_{bs}a^*)\,\backslash c$ & $\dn$ &

      $_{bs}(\textit{fuse}\, [Z] \; a\,\backslash c)\cdot

       (_{[]}a^*))$

\end{tabular}    

\end{center}   

\noindent

Using the picture we used earlier to depict this, the transformation when 

taking a derivative w.r.t a star is like below:

\begin{tabular}{@{}l@{\hspace{1mm}}l@{\hspace{0mm}}c@{}}

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        {$bs$

         \nodepart{two} $a^*$ };

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture} 

&

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        {$v_{\text{previous iterations}}$

         \nodepart{two} $a^*$};

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture}

\\

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        { $bs$ + [Z]

         \nodepart{two}  $(a\backslash c )\cdot a^*$ };

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture}

&

\begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    \node [rectangle split, rectangle split horizontal, rectangle split parts=2, rectangle split part fill={red!30,blue!20},]

        {$v_{\text{previous iterations}}$ + 1 more iteration

         \nodepart{two} $(a\backslash c )\cdot a^*$ };

%\caption{term 1 \ref{term:1}'s matching configuration}

\end{tikzpicture}

\end{tabular}    

\noindent

Another place in the $\bder$ function where it differs

from normal derivatives (on un-annotated regular expressions)

is the sequence case:

\begin{center}

  \begin{tabular}{@{}lcl@{}}

  $(_{bs}\;a_1\cdot a_2)\,\backslash c$ & $\dn$ &

     $\textit{if}\;\textit{bnullable}\,a_1$\\

					       & &$\textit{then}\;_{bs}\sum\,[(_{[]}\,(a_1\,\backslash c)\cdot\,a_2),$\\

					       & &$\phantom{\textit{then},\;_{bs}\sum\,}(\textit{fuse}\,(\textit{bmkeps}\,a_1)\,(a_2\,\backslash c))]$\\

  & &$\textit{else}\;_{bs}\,(a_1\,\backslash c)\cdot a_2$

\end{tabular}    

\end{center}    

The difference is that (when $a_1$ is $\bnullable$)

we use $\bmkeps$ to store the lexing information

in $a_1$ before collapsing it (as it has been fully matched by string prior to $c$, 

and attach the collected bit-codes to the front of $a_2$

before throwing away $a_1$. We assume that $\bmkeps$ correctly extracts the bitcode for how $a_1$

matches the string prior to $c$ (more on this later).

The bitsequence $\textit{bs}$ which was initially attached to the first element of the sequence

$a_1 \cdot a_2$, has now been elevated to the top level of teh $\sum$. 

This is because this piece of information will be needed whichever way the sequence is matched,

regardless of whether $c$ belongs to $a_1$ or $a_2$.

In the injection-based lexing, $r_1$ is immediately thrown away in 

subsequent derivatives on the right branch (when $r_1$ is $\nullable$),

\begin{center}

	$(r_1 \cdot r_2 )\backslash c = (r_1 \backslash c) \cdot r_2 + r_2 \backslash c$

\end{center}

\noindent

as it knows $r_1$ is stored on stack and available once the recursive 

call to later derivatives finish.

Therefore, if the $\Right$ branch is taken in a $\POSIX$ match,

we construct back the sequence value once step back by

calling a on $\mkeps(r_1)$.

\begin{center}

	\begin{tabular}{lcr}

		$\ldots r_1 \cdot r_2$ & $\rightarrow$ & $r_1\cdot r_2 + r_2 \backslash c \ldots $\\

		$\ldots \Seq(v_1, v_2) (\Seq(\mkeps(r1), (\inj \; r_2 \; c\; v_{2c})))$ & $\leftarrow$ & $\Right(v_{2c})\ldots$

	\end{tabular}

\end{center}

\noindent

The rest of the clauses of $\bder$ is rather similar to

$\der$, and is put together here as a wholesome definition

for $\bder$:

\begin{center}

  \begin{tabular}{@{}lcl@{}}

  $(\ZERO)\,\backslash c$ & $\dn$ & $\ZERO$\\  

  $(_{bs}\ONE)\,\backslash c$ & $\dn$ & $\ZERO$\\  

  $(_{bs}{\bf d})\,\backslash c$ & $\dn$ &

        $\textit{if}\;c=d\; \;\textit{then}\;

         _{bs}\ONE\;\textit{else}\;\ZERO$\\  

  $(_{bs}\sum \;\textit{as})\,\backslash c$ & $\dn$ &

  $_{bs}\sum\;(\textit{map} \; (\_\backslash c) \; as )$\\

  $(_{bs}\;a_1\cdot a_2)\,\backslash c$ & $\dn$ &

     $\textit{if}\;\textit{bnullable}\,a_1$\\

					       & &$\textit{then}\;_{bs}\sum\,[(_{[]}\,(a_1\,\backslash c)\cdot\,a_2),$\\

					       & &$\phantom{\textit{then},\;_{bs}\sum\,}(\textit{fuse}\,(\textit{bmkeps}\,a_1)\,(a_2\,\backslash c))]$\\

  & &$\textit{else}\;_{bs}\,(a_1\,\backslash c)\cdot a_2$\\

  $(_{bs}a^*)\,\backslash c$ & $\dn$ &

      $_{bs}(\textit{fuse}\, [Z] \; r\,\backslash c)\cdot

       (_{[]}r^*))$

\end{tabular}    

\end{center}