\documentclass{beamer}
\usetheme[style=plain]{uu}

%% unicode support, for text and code :)
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{autofe}

\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}


%% Haskell syntax highlighting - "Liewe style"
\newcommand{\colour}[2]{\textcolor{#1}{#2}}
\newcommand{\type}[1]{\textcolor{blue}{#1}}
\newcommand{\class}[1]{\textcolor{orange}{#1}}
\newcommand{\constr}[1]{\textcolor{red}{#1}}
\newcommand{\keyword}[1]{\textbf{#1}}


%% Metainformation
\title[GPandoc]{Generic and well-formed Pandoc}

\date{\today}

\author[Alpuim, Binsbergen, Pizani Flor]
{
    J.~Alpuim
    \and L.T. van~Binsbergen
    \and J.P.~Pizani Flor
}

\institute[Utrecht University]
{
    Department of Information and Computing Sciences,
    Utrecht University
}


%% The document itself
\begin{document}

    % Studying the Pandoc type
    % Studying the usage of Pandoc
    % Determining the errors we expected
    % Confirming the errors
    % Come up with the proposed solution
    % Work on XHTML parser and datatype
    % Obtain meta-information from the HTML type
    % Approach #1
    % Approach #2
    \begin{frame}
        \titlepage
    \end{frame}

    \begin{frame}
        \frametitle{Table of Contents}
        \tableofcontents
    \end{frame}

    \section{Pandoc overview}
        \subsection{What it does}
        \begin{frame}
            \frametitle{What it does}
            \begin{itemize}
                \item Pandoc converts between several markup languages.
                \item 6 input languages including \LaTeX, HTML and Markdown.
                \item More than 15 output languages.
            \end{itemize}
        \end{frame}

        \subsection{How it works}
        \begin{frame}
            \frametitle{How it works}
            \begin{itemize}
                \item Recognizes input language by the file extension (there is an option to override it).
                \item Parses language into a general \textcolor{blue}{Pandoc} datatype.
                \item All printers use the general datatype.
            \end{itemize}
        \end{frame}

        \subsection{How to break it}
        \begin{frame}
            \frametitle{How to break it} 
        
            In HTML:
            \begin{itemize}
                \item Parsing HTML with non-sensical tags (e.g. $<$bbl$>$some text$<$/bbl$>$);
                \item Parsing HTML with non-sensical nesting (e.g. \emph{head} tag inside a list);
                \item Mixed input and \emph{just plain wrong} input does not lead to error messages.
            \end{itemize}

            We concluded that the parser was too tolerant.
        \end{frame}

    \section{Proposed solution}
        \begin{frame}
            \frametitle{How do we improve it?}
            \begin{block}{Proposed Solution}
                \begin{itemize}
                    \item[1.] Implement specific datatypes for each input language
                    \item[2.] With a separate parser to provide us with error messages
                    \item[] Such that correct parsing gives us a well-formed type
                    \item[3.] Use generic programming for transforming these datatypes into the 
                          \textcolor{blue}{Pandoc} datatype;
                    \item Project Goal: Work this out for one input language  
                \end{itemize}
            \end{block}
        \end{frame}

        \subsection{Test-case: XHTML}
        \begin{frame}
            \frametitle{Test-case: XHTML}
            \begin{itemize}
                \item Defining a datatype corresponding with the XHTML 1.0 Strict language
                \item Defining a parser (using parsec) to parse into this type
                \item This gives us errors messages when parsing incorrect input (however the 
                messages are not really helpful yet)
            \end{itemize}
        \end{frame}

        \subsection{Obtaining Meta Information}
        \begin{frame}
            \frametitle{Obtaining Meta Information}

            Pandoc meta-data datatype has fields for title, authors and date:

            \keyword{data} \type{Meta} = \constr{Meta} \{ docTitle   :: \type{[Inline]} \\
            \hspace{3.2cm}    , docAuthors :: \type{[[Inline]]} \\
            \hspace{3.2cm}    , docDate    :: \type{[Inline]} \} \\

            \vfill

            Our generic function for fetching the title:

            gTitle :: (\class{GTitle} a) $\Rightarrow$ (a $\rightarrow$ \type{[Inline]}) 
                      $\rightarrow$ \type{GenericQ [Inline]} \\
            gTitle g = everything (++) (mkQ [] g)
        \end{frame}

        \begin{frame}
            \frametitle{Obtaining Meta Information (cont.)}

            Given these three classes:

            \keyword{class} (\class{Data} a, \class{Typeable} a) $\Rightarrow$ \class{GTitle} a \keyword{where} \\
            \hspace{0.5cm} gtitle :: a $\rightarrow$ \type{[Inline]}

            \keyword{class} (\class{Data} a, \class{Typeable} a) $\Rightarrow$ \class{GMeta} a \keyword{where} \\
            \hspace{0.5cm} gmeta :: a $\rightarrow$ \type{Meta}

            \keyword{class} (\class{Data} a, \class{Typeable} a) $\Rightarrow$ \class{GPandoc} a \keyword{where} \\
            \hspace{0.5cm} gpandoc :: a $\rightarrow$ \type{Pandoc}

            \vfill
            We may do the following with our HTML datatype:

            \keyword{instance} \class{GTitle} \type{Head} \keyword{where} \\
            \hspace{0.5cm} gtitle (\constr{Head} l) = ...
                                                      % maybe [] ($\lambda$x $\rightarrow$ [Str x]) (lookup Title l)

            \keyword{instance} \class{GMeta} \type{HTML} \keyword{where} \\
            \hspace{0.5cm} gmeta h = \constr{Meta} (gTitle (gtitle :: \type{Head} $\rightarrow$ \type{[Inline]}) 
                                     h) [] []

            \keyword{instance} \class{GPandoc} \type{HTML} \keyword{where} \\
            \hspace{0.5cm} gpandoc h = \constr{Pandoc} (gmeta h) (gblocks h) 
        \end{frame}

\AtBeginSection[]%
{%
\begin{frame}[plain]%
  \begin{center}%
    \usebeamerfont{section title}\insertsection%
  \end{center}%
\end{frame}%
}

    \section{Approach \#1}
    \begin{frame}
    \frametitle{Type Classes}
    
    The \type{Pandoc} datatype is defined in terms of: 
    
    \begin{itemize}
        \item \emph{Blocks}: The way in which the document is structured (e.g. tables, lists, etc) and contain
              \emph{inlines}.
        \item \emph{Inlines}: Specific formats for text (e.g. emph, bold, etc.) 
    \end{itemize}

    \vfill

    Following the same approach to Meta, two type classes were defined:
    \begin{itemize}
        \item \class{GBlocks}, with method \emph{gblocks}
        \item \class{GInlines}, with method \emph{ginlines}
    \end{itemize}

\end{frame}

\subsection{Mutual Recursion}
\begin{frame}
    \frametitle{Mutual Recursion}
    \begin{itemize}
        \item Pandoc has only top level blocks
        \item XHTML can have blocks inside inlines, which makes it mutually recursive
        \item The user has to make a decision on how to deal with it
    \end{itemize}
\end{frame}

\subsection{Instances}
\begin{frame}
    \frametitle{Instances for XHTML}

    \keyword{instance} \class{GBlocks} \type{BlockTags} \keyword{where} \\
    \hspace{0.5cm} gblocks (\constr{Paragraph} ts) = \constr{Para} (ginlines ts) : (gblocks ts) \\
    \hspace{0.5cm} gblocks (\constr{Div} ts) = \constr{Plain} (ginlines ts) : (gblocks ts) \\
    \hspace{0.5cm} gblocks (\constr{Header} (H1 blas)) = \constr{Header} 1 (ginlines blas) : \\ 
                   \hspace{5.5cm} (gblocks blas) \\
    \hspace{0.5cm} gblocks (\constr{BlockText} raw) = [\constr{Plain} [\constr{Str} raw]]

    \vfill

    \keyword{instance} \class{GInlines} \type{InlineTags} \keyword{where} \\
    \hspace{0.5cm} ginlines (\constr{Span} ias) = ginlines ias \\
    \hspace{0.5cm} ginlines (\constr{Em} str) = [(\constr{Emph} [\constr{Str} str])] \\
    \hspace{0.5cm} ginlines (\constr{InlineText} str) = [\constr{Str} str] \\

\end{frame}

\begin{frame}
    \frametitle{Characteristics}
    \begin{itemize}
        \item Genericity of transformation interface
        \begin{itemize}
            \item \textcolor{green}{Completely general!}
        \end{itemize}
        \pause
        \item Level of overhead
        \begin{itemize}
            \item \textcolor{red}{Potentially a lot of boilerplate code.}
        \end{itemize}
        \pause
        \item Level of understanding of Pandoc datatype
        \begin{itemize}
            \item \textcolor{red}{User needs to be Pandoc-aware.}
        \end{itemize}
        \pause
        \item Level of freedom for the user when defining transformation
        \begin{itemize}
            \item \textcolor{green}{Free implementation, but choice is required.} 
        \end{itemize}
    \end{itemize}

\end{frame}


\section{Approach \#2}
    \subsection{Concept}
        \begin{frame}
            \frametitle{A generic AST parser}

            \begin{block}{What it is}
                The transformation is implemented as a parser \emph{with an output of type Pandoc}.
                This parser is not an ordinary parser, because:

                \begin{enumerate}
                    \item It does \emph{not} parse a sequence of characters or tokens, but the AST of a
                    document (as a Haskell datatype).

                    \item It is generic over its input type, i.e, it does not know the structure of its input.
                \end{enumerate}
            \end{block}
        \end{frame}

        \begin{frame}
            \frametitle{A generic AST parser}

            \begin{block}{How it works}
                The parser is structured as a recursive-descent parser:

                \begin{itemize}
                    \item Each concept of Pandoc (one of the possible nodes in a Pandoc-typed value)
                    corresponds to a parsing function.

                    \item These parsing functions are organized in a hierarchy, like in a Parsec parser.

                    \item Each parsing function returns its result inside the \emph{Maybe} monad.

                    \item Each generic parsing function can be \emph{specialized} if necessary.
                \end{itemize}
            \end{block}
        \end{frame}

        \subsection{Implementation}
        \begin{frame}
            \frametitle{An example of generic parsing function}

            The gPandoc function, root of the parsing hierarchy, looks like:
            \newline

            gPandoc e m b = (combine . flat2 . gmapQ collect) \keyword{`extQ`} e\\
            \hspace{0.5cm} \keyword{where}\\
            \hspace{0.5cm} \hspace{0.5cm} collect child = (m child, b child)\\
            \hspace{0.5cm} \hspace{0.5cm} combine (m, b) = \keyword{if} isJust m \&\& isJust b\\
            \hspace{0.5cm} \hspace{0.5cm} \hspace{0.5cm} \keyword{then} \constr{Just} \$ \constr{Pandoc} (fromJust m) (fromJust b)\\
            \hspace{0.5cm} \hspace{0.5cm} \hspace{0.5cm} \keyword{else} \constr{Nothing}

            \begin{itemize}[<+->]
                \item We try to get all possible substructures, for each child.
                \item This \emph{collect and combine} behavior is widespread.
                \item Specialize behavior by using the \emph{e} parameter.
                \item The explicitly-passed parameters \emph{m} and \emph{b} ``tie the knot''.
            \end{itemize}
        \end{frame}

        \begin{frame}
            \frametitle{How to use the generic functions and specialize them}

            How to implement the conversion from a new input language to the Pandoc type?
            \vspace{0.4cm}
            \pause

            dummy :: \type{()} $\rightarrow$ \type{Maybe a}\\
            dummy = const \constr{Nothing}\\
            \vspace{0.3cm}
            \keyword{hPandoc} = \type{gPandoc} \class{dummy} \keyword{hMeta} \keyword{gBlocks}\\
            \keyword{hMeta} = \type{gMeta} \class{dummy} \keyword{hTitle} \keyword{hAuthors} \keyword{hDate}\\
            \keyword{hTitle} = \type{gTitle} \class{eHTMLTitle}\\
            \keyword{hAuthors} = \type{gAuthors} \class{eHTMLAuthors}\\
            \keyword{hDate} = \type{gDate} \class{eHTMLDate}\\

            \vspace{0.4cm}
            \pause

            \begin{itemize}
                \item By \emph{partially applying the generic parsing functions}
                \item Specializing when desired (minimal matching subtrees)
                \item ``Tying the knot elsewhere''
            \end{itemize}
        \end{frame}

        \begin{frame}
            \frametitle{Characteristics}

            \begin{itemize}
                \item Genericity of transformation interface
                \begin{itemize}
                    \item \textcolor{green}{Very general}.
                \end{itemize}
                \pause
                \item Level of overhead
                \begin{itemize}
                    \item \textcolor{green}{Less overhead than \#1}. The user writes code only for subtrees in
                    which he wants to override the generic behavior.
                \end{itemize}
                \pause
                \item Level of understanding of Pandoc datatype
                \begin{itemize}
                    \item \textcolor{red}{The same as approach \#1, complete}.
                \end{itemize}
                \pause
                \item Level of freedom for the user when defining transformation
                \begin{itemize}
                    \item \textcolor{green}{Customization is possible, but \textbf{not} needed}.
                \end{itemize}
            \end{itemize}
        \end{frame}

\end{document}
