<commit_before>\documentclass{beamer}
\usepackage[latin1]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Processing List Elements in Reverse Order}

\author{<NAME> and <NAME>}
\institute{
LaBRI, University of Bordeaux
}
\date{April, 2015}

%\inputtex{macros.tex}


\begin{document}
\frame{
\resizebox{3cm}{!}{\includegraphics{Logobx.pdf}}
\hfill
\resizebox{1.5cm}{!}{\includegraphics{labri-logo.pdf}}
\titlepage
\vfill
\small{European Lisp Symposium, London, UK \hfill ELS2015}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Context: The \sicl{} project}

https://github.com/robert-strandh/SICL

Several objectives:

\begin{itemize}
\item Create high-quality \emph{modules} for implementors of
  \commonlisp{} systems.
\item Improve existing techniques with respect to algorithms and data
  structures where possible.
\item Improve readability and maintainability of code.
\item Improve documentation.
\item Ultimately, create a new implementation based on these modules.
\end{itemize}
}

\frame{
\frametitle{Processing list elements in reverse order}

\begin{itemize}
\item Several \commonlisp{} operators accept the \texttt{:from-end}
  keyword argument.
\item In most cases, an implementation is still allowed to process
  from beginning to end, but the result will typically be different.
\item Two operators are \emph{required} to process from the end, namely
  \texttt{count} and \texttt{reduce}.
\end{itemize}

In this talk, we will exclusively refer to the \texttt{count}
operator, but the same argument is true for \texttt{reduce}.
}

\frame[containsverbatim]{
\frametitle{The \commonlisp{} \texttt{count} operator}

\begin{verbatim}
count item sequence
      &key from-end start end key test test-not => n
\end{verbatim}


\begin{quotation}
  The from-end has no direct effect on the result.
  However, if from-end is true, the elements of sequence
  will be supplied as arguments to the test, test-not,
  and key in reverse order, which may change the side-effects,
  if any, of those functions.
\end{quotation}
  
}

\frame{
\frametitle{Existing implementations of \texttt{count}}

\sbcl{}, \ccl{}, and \lispworks{} all implement the behavior of
\texttt{count} by first calling \texttt{reverse} on the list.

Inconveniences:

\begin{itemize}
\item For long lists, an unreasonable amount of heap space is used,
  and it is possible to run out of space.
\item Allocating list elements \emph{may} be costly.
\item The garbage collector will run more often.
\end{itemize}

}

\frame{
\frametitle{Basis of our technique}

\begin{itemize}
\item Use available stack space.
\item Traverse the list multiple times if necessary.
\end{itemize}

Most of the talk will discuss near-portable techniques.
\vskip 0.25cm
Toward the end, more efficient non-portable techniques.
\vskip 0.25cm
The main performance factor of our technique is the number of
\texttt{cdr} operations.  For that reason, we will consider that
\texttt{:test} is \texttt{eq} and that \texttt{:key} is
\texttt{identity}.  Other cases will be more favorable to our
technique.
}

\frame[containsverbatim]{
\frametitle{Basic recursive technique}

\begin{verbatim}
(defun recursive-count (x list)
  (if (endp list)
      0
      (+ (recursive-count x (cdr list))
         (if (eq (car list) x) 1 0))))
\end{verbatim}

This technique uses \emph{stack} space rather than heap space.\\
Problem: stack space is limited, so it may fail.
\vskip 0.25cm
Otherwise, it is very fast and does not solicit the garbage
collector.

}

\frame[containsverbatim]{
\frametitle{Avoiding stack overflow}

\begin{verbatim}
(defun count-from-end (x list)
  (labels ((aux (x list n)
             (cond ((= n 0) 0)
                   ((= n 1)
                    (if (eq x (car list)) 1 0))
                   (t (let* ((n/2 (ash n -1))
                             (half (nthcdr n/2 list)))
                        (+ (aux x half (- n n/2))
                           (aux x list n/2)))))))
    (aux x list (length list))))))
\end{verbatim}

Number of \texttt{cdr} operations $F(n)$ on a list of length $n$ is
approximately $F(n) \approx n\thinspace (1 +
\frac{1}{2}\mathsf{lb}\thinspace n)$.
\vskip 0.25cm
Unacceptable when $n$ is very large.
\vskip 0.25cm
Stack depth is only $\mathsf{lb}\thinspace n$.
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m (ash n -1))
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (aux x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (aux x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (recursive x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

{\small
\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             ...)
           (aux1 (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux1 x suffix (- n m))
                      (recursive x list m)))))
           (aux2 (x list n)
             (if (<= n 100000000)
                 (aux1 x list n)
                 (let* ((m (ash n -1))
                        (suffix (nthcdr m list)))
                   (+ (aux2 x suffix (- n m))
                      (aux2 x list m))))))
    (aux2 x list (length list))))
\end{verbatim}
}
}

\frame{
  \frametitle{Benchmark of three versions}

  \begin{itemize}
  \item v0 Native \texttt{count} with \texttt{:from-end t}.
  \item v1 Using \texttt{reverse} then \texttt{count}.
  \item v7 Our best version.
  \end{itemize}
}

\frame{
  \frametitle{Comparison of the behavior of the three versions}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{System characteristics}  & \multicolumn{3}{|c|}{Time in ms}\\ \hline
Impl & Version        & Processor  & v0   & v1   & v7   \\ \hline
LispWorks  & 6.1.1    & Intel Core & 0.20 & 0.18 & 0.14 \\ \hline
Clozure CL & 1.10     & Intel Xeon & 1.93 & 1.79 & 0.15 \\ \hline
Clozure CL & 1.10-dev & AMD FX     & 1.77 & 1.63 & 0.15 \\ \hline
SBCL       & 1.2.8    & Intel Xeon & 0.51 & 0.27 & 0.22 \\ \hline
ABCL       & 1.3.1    & Intel Xeon & 1.13 & 0.22 & 0.34 \\ \hline
CLISP      & 2.49     & X86\_64    & 1.15 & 1.14 & 0.87 \\ \hline
ECL        & 13.5.1   & ?          & 0.69 & 0.41 & 0.36 \\ \hline
SBCL       & 1.2.7    & Intel Core & 0.36 & 0.38 & 0.25 \\ \hline
\end{tabular}
}

\frame{
  \frametitle{Comparison of the behavior of the three versions}
  \begin{center}
    \includegraphics{v0-v1-v7.eps}
  \end{center}
}

\frame{
  \frametitle{Acknowledgments}

We would like to thank <NAME> for reading and commenting
on an early draft of this paper.  We would also like to thank Alastair
Bridgewater for helping us with the foreign-function interface of
\sbcl{}.  Also, we would like to thank <NAME>, Alastair
Bridgewater, <NAME>, <NAME>, <NAME>, and <NAME> for helping us run benchmarks on platforms that are unavailable
to us.  Finally, we would like to thank <NAME> at \lispworks{}
technical support for giving us the information we needed in order to
explain the performance of our technique on the \lispworks{}
\commonlisp{} implementation.
}

\frame{
\frametitle{Future work}

\begin{itemize}
\item Apply our technique to operators where the implementation has a
  choice of direction of traversal, in particular \texttt{find} and
  \texttt{position}.
\item Devise benchmarks for these operators.  Additional parameters
  are necessary, such as expected position of last element that
  \emph{passes the test}.
\item Apply the idea of using available stack space to other domains.
\end{itemize}

}

\frame{
\frametitle{Conclusion and Perspectives}<commit_msg>New frame introducing implementation-specific techniques.<commit_after>\documentclass{beamer}
\usepackage[latin1]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Processing List Elements in Reverse Order}

\author{<NAME> and <NAME>}
\institute{
LaBRI, University of Bordeaux
}
\date{April, 2015}

%\inputtex{macros.tex}


\begin{document}
\frame{
\resizebox{3cm}{!}{\includegraphics{Logobx.pdf}}
\hfill
\resizebox{1.5cm}{!}{\includegraphics{labri-logo.pdf}}
\titlepage
\vfill
\small{European Lisp Symposium, London, UK \hfill ELS2015}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Context: The \sicl{} project}

https://github.com/robert-strandh/SICL

Several objectives:

\begin{itemize}
\item Create high-quality \emph{modules} for implementors of
  \commonlisp{} systems.
\item Improve existing techniques with respect to algorithms and data
  structures where possible.
\item Improve readability and maintainability of code.
\item Improve documentation.
\item Ultimately, create a new implementation based on these modules.
\end{itemize}
}

\frame{
\frametitle{Processing list elements in reverse order}

\begin{itemize}
\item Several \commonlisp{} operators accept the \texttt{:from-end}
  keyword argument.
\item In most cases, an implementation is still allowed to process
  from beginning to end, but the result will typically be different.
\item Two operators are \emph{required} to process from the end, namely
  \texttt{count} and \texttt{reduce}.
\end{itemize}

In this talk, we will exclusively refer to the \texttt{count}
operator, but the same argument is true for \texttt{reduce}.
}

\frame[containsverbatim]{
\frametitle{The \commonlisp{} \texttt{count} operator}

\begin{verbatim}
count item sequence
      &key from-end start end key test test-not => n
\end{verbatim}


\begin{quotation}
  The from-end has no direct effect on the result.
  However, if from-end is true, the elements of sequence
  will be supplied as arguments to the test, test-not,
  and key in reverse order, which may change the side-effects,
  if any, of those functions.
\end{quotation}
  
}

\frame{
\frametitle{Existing implementations of \texttt{count}}

\sbcl{}, \ccl{}, and \lispworks{} all implement the behavior of
\texttt{count} by first calling \texttt{reverse} on the list.

Inconveniences:

\begin{itemize}
\item For long lists, an unreasonable amount of heap space is used,
  and it is possible to run out of space.
\item Allocating list elements \emph{may} be costly.
\item The garbage collector will run more often.
\end{itemize}

}

\frame{
\frametitle{Basis of our technique}

\begin{itemize}
\item Use available stack space.
\item Traverse the list multiple times if necessary.
\end{itemize}

Most of the talk will discuss near-portable techniques.
\vskip 0.25cm
Toward the end, more efficient non-portable techniques.
\vskip 0.25cm
The main performance factor of our technique is the number of
\texttt{cdr} operations.  For that reason, we will consider that
\texttt{:test} is \texttt{eq} and that \texttt{:key} is
\texttt{identity}.  Other cases will be more favorable to our
technique.
}

\frame[containsverbatim]{
\frametitle{Basic recursive technique}

\begin{verbatim}
(defun recursive-count (x list)
  (if (endp list)
      0
      (+ (recursive-count x (cdr list))
         (if (eq (car list) x) 1 0))))
\end{verbatim}

This technique uses \emph{stack} space rather than heap space.\\
Problem: stack space is limited, so it may fail.
\vskip 0.25cm
Otherwise, it is very fast and does not solicit the garbage
collector.

}

\frame[containsverbatim]{
\frametitle{Avoiding stack overflow}

\begin{verbatim}
(defun count-from-end (x list)
  (labels ((aux (x list n)
             (cond ((= n 0) 0)
                   ((= n 1)
                    (if (eq x (car list)) 1 0))
                   (t (let* ((n/2 (ash n -1))
                             (half (nthcdr n/2 list)))
                        (+ (aux x half (- n n/2))
                           (aux x list n/2)))))))
    (aux x list (length list))))))
\end{verbatim}

Number of \texttt{cdr} operations $F(n)$ on a list of length $n$ is
approximately $F(n) \approx n\thinspace (1 +
\frac{1}{2}\mathsf{lb}\thinspace n)$.
\vskip 0.25cm
Unacceptable when $n$ is very large.
\vskip 0.25cm
Stack depth is only $\mathsf{lb}\thinspace n$.
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m (ash n -1))
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (aux x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (aux x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             (if (zerop n)
                 0
                 (+ (recursive x (cdr list) (1- n))
                    (if (eq x (car list)) 1 0))))
           (aux (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux x suffix (- n m))
                      (recursive x list m))))))
    (aux x list (length list))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Using more stack space}

{\small
\begin{verbatim}
(defun count-from-end-2 (x list)
  (labels ((recursive (x list n)
             ...)
           (aux1 (x list n)
             (if (<= n 10000)
                 (recursive x list n)
                 (let* ((m 10000)
                        (suffix (nthcdr m list)))
                   (+ (aux1 x suffix (- n m))
                      (recursive x list m)))))
           (aux2 (x list n)
             (if (<= n 100000000)
                 (aux1 x list n)
                 (let* ((m (ash n -1))
                        (suffix (nthcdr m list)))
                   (+ (aux2 x suffix (- n m))
                      (aux2 x list m))))))
    (aux2 x list (length list))))
\end{verbatim}
}
}

\frame{
  \frametitle{Benchmark of three versions}

  \begin{itemize}
  \item v0 Native \texttt{count} with \texttt{:from-end t}.
  \item v1 Using \texttt{reverse} then \texttt{count}.
  \item v7 Our best version.
  \end{itemize}
}

\frame{
  \frametitle{Comparison of the behavior of the three versions}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{System characteristics}  & \multicolumn{3}{|c|}{Time in ms}\\ \hline
Impl & Version        & Processor  & v0   & v1   & v7   \\ \hline
LispWorks  & 6.1.1    & Intel Core & 0.20 & 0.18 & 0.14 \\ \hline
Clozure CL & 1.10     & Intel Xeon & 1.93 & 1.79 & 0.15 \\ \hline
Clozure CL & 1.10-dev & AMD FX     & 1.77 & 1.63 & 0.15 \\ \hline
SBCL       & 1.2.8    & Intel Xeon & 0.51 & 0.27 & 0.22 \\ \hline
ABCL       & 1.3.1    & Intel Xeon & 1.13 & 0.22 & 0.34 \\ \hline
CLISP      & 2.49     & X86\_64    & 1.15 & 1.14 & 0.87 \\ \hline
ECL        & 13.5.1   & ?          & 0.69 & 0.41 & 0.36 \\ \hline
SBCL       & 1.2.7    & Intel Core & 0.36 & 0.38 & 0.25 \\ \hline
\end{tabular}
}

\frame{
  \frametitle{Comparison of the behavior of the three versions}
  \begin{center}
    \includegraphics{v0-v1-v7.eps}
  \end{center}
}

\frame{
  \frametitle{Doing better with implementation-specific techniques}

So far, our technique is mostly portable (aside from computing
available stack space).
\vskip 0.25cm
Observations:

\begin{itemize}
\item Each recursive call takes many words in each stack frame for
  frame pointer, return address, saved registers, etc.
\item We use \texttt{nthcdr} which must test for \texttt{cons} cells,
  but no such test is needed.
\end{itemize}

}

\frame{
  \frametitle{Acknowledgments}

We would like to thank <NAME> for reading and commenting
on an early draft of this paper.  We would also like to thank Alastair
Bridgewater for helping us with the foreign-function interface of
\sbcl{}.  Also, we would like to thank <NAME>, Alastair
Bridgewater, <NAME>, <NAME>, <NAME>, and <NAME> for helping us run benchmarks on platforms that are unavailable
to us.  Finally, we would like to thank <NAME> at \lispworks{}
technical support for giving us the information we needed in order to
explain the performance of our technique on the \lispworks{}
\commonlisp{} implementation.
}

\frame{
\frametitle{Future work}

\begin{itemize}
\item Apply our technique to operators where the implementation has a
  choice of direction of traversal, in particular \texttt{find} and
  \texttt{position}.
\item Devise benchmarks for these operators.  Additional parameters
  are necessary, such as expected position of last element that
  \emph{passes the test}.
\item Apply the idea of using available stack space to other domains.
\end{itemize}

}

\frame{
\frametitle{Conclusion and Perspectives}
{'fraction_non_alphanumeric': 0.14384011920936143, 'fraction_numerical': 0.02774247271771048, 'mean_word_length': 2.8278812279818824, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 23, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5375740', 'n_tokens_mistral': 8122, 'n_tokens_neox': 7592, 'n_words': 2312}