\documentclass{beamer}
\usepackage{listings}
\usepackage{ulem}
\usepackage{lmodern}
\usepackage[T1]{fontenc}

\title{Iteratees in C}
\subtitle{or how to invert the basement plumbing}

\author{pesco \texttt{\color{gray}@khjk.org}}
\date{HushCon, Seattle, Dec 16 2013 \\[\medskipamount]
      \tiny{\alert{*updated Dec 18 2013}}}

\begin{document}
\begin{frame}\titlepage\end{frame}

%=====
\begin{frame}{Wat?}
\begin{itemize}
\item Iteratees are \emph{stream processors}.
\item Programming model / API
  \begin{itemize}
  \item to allow reasoning about I/O
  \end{itemize}
\item Origin: functional programming
\item Challenge: Do it without first-class functions!
  \begin{itemize}
  \item cf. Hammer
  \end{itemize}
\end{itemize}
\end{frame}

%=====
\begin{frame}{About Me}{(Context)}
\begin{itemize}
\item Programming
\item Mathematics
\item Cryptography
\end{itemize}
\end{frame}

%=====
\begin{frame}{Motivation}
\begin{itemize}
\item Apply formal thinking
\item \dots to program construction
\item \dots to achieve security properties.
\end{itemize}
\end{frame}

% - hammer
%   - use iteratees as an outward api
%     - allows to use hammer parsers inside iteratees
%     - inherit hammer's restriction to byte streams
%     - e.g. context-free parts of protocol/file format
%     - e.g. xml/json after encoding switch
%   - use iteratees as internal interface to consume input stream
%     - aleviates byte stream restriction
%     - stack hammer with decoders, lexers etc.

%=====
\begin{frame}{Iteratees}
\begin{itemize}
\item \emph{Not} my idea
\item Oleg Kiselyov in Haskell, 2008
\item Pretty far-out, even for the Haskellers
  \begin{itemize}
  \item cf. proliferation of alternative libraries
  \end{itemize}
\end{itemize}

\begin{itemize}
\item A \emph{model} for input processing
\item The model gives rise to a library/implementation.
\end{itemize}
\end{frame}

%=====
\begin{frame}{Iteratees}{(cont.)}
\begin{itemize}
\item Represent stream processing
\item Modular, composable
\end{itemize}

\begin{itemize}
\item Breaking procedures over chunks
  \begin{itemize}
  \item compose without worry of the boundaries
  \end{itemize}
\end{itemize}

\begin{itemize}
\item Inversion of the common representation of input processing
  \begin{itemize}
  \item ``FILE/read $\rightarrow$ file/READ''
  \item data as data $\rightarrow$ procedure as data
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Security}
\begin{itemize}
\item High level
\item ``Declarative''
\item Be formal about accepted input
\item Modular: reduce unmapped interactions
\end{itemize}

\begin{itemize}
\item[$\Rightarrow$] Avoid weird machines
\item Cf. langsec
\end{itemize}
\end{frame}

%=====
\begin{frame}[fragile]{How It Works}{(in Pseudohaskell)}
\lstset{escapeinside={\%(}{)}}
\begin{lstlisting}[language=Haskell]
data Iteratee %($\alpha$) =
    CONT (Stream %($\rightarrow$) (Stream, Iteratee %($\alpha$)))
  | STOP Error
  | DONE (%($\alpha$), Stream)
\end{lstlisting}
\end{frame}

%=====
\begin{frame}{Functional Programming in C}
\begin{itemize}
\item Lambda expressions
\item Partial application
\item Lexical closures
\end{itemize}

vs.

\begin{itemize}
\item Lambda lifting
\item Environment structs
\end{itemize}
\end{frame}

%=====
\begin{frame}[fragile]{Functional Programming in C}{(cont.)}
\lstset{escapeinside={\%(}{)}}
\begin{lstlisting}[language=Haskell]
f(x,y,z) = %(\dots)

g(a,xs) = map (%($\lambda$)y %($\rightarrow$) f(a,y,0)) xs

g%($_\lambda$)(a) = %($\lambda$)y %($\rightarrow$) f(a,y,0)
g(a,xs) = map g%($_\lambda$)(a) xs
\end{lstlisting}
\end{frame}

%=====
\begin{frame}[fragile]{Functional Programming in C}{(cont. 2)}
\setbeamercolor{alerted text}{fg=black}
\begin{semiverbatim}\color{gray}
\alert<1>{int f(int x, int y, int z);}

\alert<2>{struct Env\_gl \{int a; }\alert<>{/*...*/}\alert<2>{\};
int gl(void *env_, int y) \{
    struct Env_gl *env = env_;
    return {\color{red}f(env->a, y, 0)};
\}}

\alert<3>{list_t g(int a, list_t xs) \{
    struct Env_gl env = \{a\};
    return map({\color{red}gl, &env}, xs);
\}}
\end{semiverbatim}
\end{frame}

%=====
\begin{frame}[fragile]{How It Works}{(in C)}
\setbeamercolor{alerted text}{fg=black}
\begin{semiverbatim}\color{gray}
\alert<1>{struct Iteratee_ \{}
\alert<1>{  enum \{DONE, CONT, STOP\} state;}

\alert<1>{  union \{}
\alert<2>{    void *result;         // DONE}

\alert<3>{    struct \{              // CONT,STOP}
\alert<3>{      Iteratee (*cont)(void *env, Stream *input);}
\alert<3>{      void *env;}
\alert<4>{      const char *error;  // STOP only}
\alert<3>{    \};}
\alert<1>{  \};}
\alert<1>{\};}
\end{semiverbatim}
\end{frame}

%=====
\begin{frame}[fragile]{Case Study: Word Count}
\uncover<1,4>{} % make 3 pages
\begin{semiverbatim}
Iteratee word_ = \alert<3>{bind_}(\alert<2>{dropws}, \alert<2>{dropword});
Iteratee countwords = \alert<3>{wrap}(\alert<3>{decode}(word_), \alert<2>{count});

Iteratee it = \alert<3>{apply}(\alert<3>{enumf}(stdin), countwords);
uintptr_t nwords = (uintptr_t)\alert<3>{finish}(it);
\end{semiverbatim}
\end{frame}

%=====
\begin{frame}{Case Study: Word Count}{(cont.)}
\begin{itemize}
\item Benchmark: "rockyou" password list 
  \begin{itemize}
  \item 14.344.392 lines
  \item \textasciitilde{}14.44M words
  \end{itemize}
\end{itemize}

\begin{itemize}
\item \texttt{wc -w}
  \begin{itemize}
  \item 3.8s real 3.6s user 0.1s sys
  \item ignores non-ASCII
  \end{itemize}
\end{itemize}

\begin{itemize}
\item \texttt{./iter} (\texttt{main} = \texttt{test4})
  \begin{itemize}
  \item \sout{9.2s real 8.5s user 0.7s sys}
  \item \sout{total allocation: 600MB}
  \item \sout{peak memory use: 4MB}
  \item 3.7s real 3.6s user 0.1s sys
  \item total allocation: 3MB
  \end{itemize}
\end{itemize}
\end{frame}

%=====
\begin{frame}[fragile]{Example: JSON and character encoding}
\setbeamercolor{alerted text}{fg=black}
\begin{semiverbatim}\color{gray}
\alert<1->{Iteratee utf8;  // decodes a single UTF-8 character}
\alert<1->{Iteratee json;  // consumes Unicode code points}
\alert<2->{Iteratee it;}

\alert<3->{it = wrap(decode(utf8), json);  // attach decoder}
\alert<4->{it = apply(enumf(stdin, it);    // feed input}

\alert<5>{JSON *j = finish(it);           // extract result}
\alert<5>{if(j) \{}
\alert<5>{    // ...}
\alert<5>{\}}
\end{semiverbatim}
\end{frame}

%=====
\begin{frame}{Example: XML and character encoding}
\begin{itemize}
\item \texttt{<?xml>} directive may specify encoding for the file.
  \begin{itemize}
  \item guess encoding from initial bytes at first.
  \item switch to proper decoder for rest of file.
  \end{itemize}
\item This is easy with iteratees (\texttt{bind}).
\item[$\Rightarrow$] One iteratee to process the entire file
\end{itemize}

\begin{itemize}
\item Also cf. \texttt{Content-Type} header, BOM, \dots
\end{itemize}
\end{frame}

%=====
\begin{frame}[fragile]{Example: XML and character encoding}{(cont.)}
\setbeamercolor{alerted text}{fg=black}
\begin{semiverbatim}\color{gray}
\alert<1->{Iteratee xml_decl;      // returns encoding name}
\alert<1->{Iteratee xml_unicode;   // consumes Unicode code points}

\alert<2->{Iteratee f_xml(void *, void *result) \{}
\alert<2->{  const char *encoding = result;}
\alert<3->{  Enumeratee decoder = find_decoder(encoding);}
\alert<3->{  return wrap(decoder, xml_unicode);}
\alert<2->{\}}

\alert<1->{Iteratee xml = bind(xml_decl, f_xml,} \alert<>{NULL}\alert<1->{);}
\end{semiverbatim}
\end{frame}

%=====
\begin{frame}{PoC Implementation}
\begin{itemize}
\item Basic iteratees
\item Input from file descriptor
\item ``\texttt{decode}'' combinator
\item UTF-8 decoder
\item Several simple test examples
  \begin{itemize}
  \item word count, line count, UTF-8 character count, \dots
  \end{itemize}
\end{itemize}

\begin{itemize}
\item Automatic memory management
  \begin{itemize}
  \item uses standard \texttt{malloc}/\texttt{free} for arenas
  \item x86 (32-bit) only right now (needs to know registers)
  \end{itemize}
\end{itemize}

\begin{itemize}
\item \textasciitilde{}1500 lines alltogether
\end{itemize}
\end{frame}

%=====
\begin{frame}{Future Work}
\begin{itemize}
\item \sout{Memory management (garbage collection?!)}
\item Speed optimization
\item A larger case study
\item Flesh out a proper library/API
\item Recursive-descent parser combinators
\item Iteratee API for Hammer
\item \dots
\end{itemize}
\end{frame}

%=====
\begin{frame}{Pointers}
\begin{itemize}
\item Feedback: \alert{\texttt{pesco@khjk.org}}
\end{itemize}

\begin{itemize}
\item PoC code:
  \alert{\texttt{http://code.khjk.org/citer/}}
\end{itemize}

\begin{itemize}
\item Iteratee home (Oleg): \\
  \texttt{http://okmij.org/ftp/Streams.html\#iteratee}
\item Introductory paper (Oleg): \\
  \texttt{http://okmij.org/ftp/Haskell/Iteratee/describe.pdf}
\end{itemize}
\end{frame}

\end{document}
