<commit_before>TODO: Implementation of all 9 compiler-parts


\subsection{Preprocessor}

The preprocessor in Kite is almost identical to the \code{C} language preprocessor. We use a library called \code{cpphs}\footnote{\url{http://projects.haskell.org/cpphs}} that mimics the \code{C} version, and provides an embeddable Haskell library. This is the reason for the \code{\#include "file.kite"} syntax. Preprocessing is the first step of the compilation, and generates a single source code file which is a recursive concatenation of all included source files referenced from the main file.

\subsection{Lexer}
The lexer is implemented with the lexical generator Alex \cite{dornan01}. The lexer splits in

\subsection{Parser}
The parser is implemented with the LALR-parser generator Happy \cite{marlow01}. Happy automatically generates Haskell code from the file `src/Kite/Parser.y', which we have written in partially Haskell and partially Backus-Naur Form\footnote{This is a well known notation technique for specifying context-free grammars, which the more popular parser generator ANTLR also makes use of.}.

When a(/a combination of) tokens are matched in the parser, it is transformed into Haskell data-structures, from which we build the parse tree. Some matches are first transformed into temporary syntactic sugaring structures before being inserted into the parse tree. This is described further in section \ref{sec:imp-sugar}

The current parser generates more than 2,000 lines of quite unreadable Haskell code, which is used in the compilation of the compiler. Fortunately Happy allows setting a --info flag when it is used, which also generates a .info-file about the parser. For instance it yields very useful information about shift-reduce and reduce-reduce conflicts, which has been a great throughout the development.


\subsection{Syntactic sugar}
\label{sec:imp-sugar}
We have implemented a desugaring module which receives the matched tokens and converts them into the parse tree data-structures. We have implemented the following syntactic sugar:

\begin{itemize}
  \item Infix operators
  \item Strings
  \item List comprehensions
    
    As list comprehensions are composed of an output expression, draws and guards, the desugaring is implemented as follows (for an example of a list comprehension, and its desugared version,  please see section \ref{sec:ex-listcomp}):
    \begin{description}
      \item[First] the identifiers from the draws are extracted as these will be used as arguments to the various functions.
      \item[Secondly,] a flatMap\footnote{flatMaps takes as arguments a lambda-expression and a list, maps the function to the list, and flattens the result} is generated for each of the draws, with the function taking as argument the identifier of the current draw and the list-expression as defined right-hand-side of the ` \texttt{<-}', e.g. `\texttt{x <- [1, 2, 3]}' or `\texttt{x <- range(1,3)}'. The body of the lambda expression is either a nested flatMap or an if-expression (TODO: the final step?).
        \item[Thirdly,] the guards are inserted as bodies to functions which take all the extracted identifiers as arguments. These lambda-expressions are then combined as conjunctions in the condition of the \textbf{if}-expression.
      \item[Finally,] the \textbf{then}-branch of the \textbf{if}-expression is the output expression, and the \textbf{else}-branch is simply an empty list. This implies that only the elements that pass the guards are outputted, as flatMap gets rid of empty elements.
    \end{description}

    
\end{itemize}

TODO: infix

TODO: strings<commit_msg>Something darkside on implementation of desugaring<commit_after>TODO: Implementation of all 9 compiler-parts


\subsection{Preprocessor}

The preprocessor in Kite is almost identical to the \code{C} language preprocessor. We use a library called \code{cpphs}\footnote{\url{http://projects.haskell.org/cpphs}} that mimics the \code{C} version, and provides an embeddable Haskell library. This is the reason for the \code{\#include "file.kite"} syntax. Preprocessing is the first step of the compilation, and generates a single source code file which is a recursive concatenation of all included source files referenced from the main file.

\subsection{Lexer}
The lexer is implemented with the lexical generator Alex \cite{dornan01}. The lexer splits in

\subsection{Parser}
The parser is implemented with the LALR-parser generator Happy \cite{marlow01}. Happy automatically generates Haskell code from the file `src/Kite/Parser.y', which we have written in partially Haskell and partially Backus-Naur Form\footnote{This is a well known notation technique for specifying context-free grammars, which the more popular parser generator ANTLR also makes use of.}.

When a(/a combination of) tokens are matched in the parser, it is transformed into Haskell data-structures, from which we build the parse tree. Some matches are first transformed into temporary syntactic sugaring structures before being inserted into the parse tree. This is described further in section \ref{sec:imp-sugar}

The current parser generates more than 2,000 lines of quite unreadable Haskell code, which is used in the compilation of the compiler. Fortunately Happy allows setting a --info flag when it is used, which also generates a .info-file about the parser. For instance it yields very useful information about shift-reduce and reduce-reduce conflicts, which has been a great throughout the development.


\subsection{Syntactic sugar}
\label{sec:imp-sugar}
We have implemented a desugaring module which receives the matched tokens and converts them into the parse tree data-structures. We have implemented the following syntactic sugar:

\begin{itemize}
  \item \textbf{Infix function application}
    
    This is implemented in the parser, as it simply takes the two arguments of the application and parses it as a normal function call with two arguments.

  \item \textbf{Multiple parameters and arguments}

    \texttt{foo(a,b,c)} (TODO: args) TODO: se LambdaSignatur i parser.y

    \texttt{bar = |x,y,z| -> { ... }} (TODO: params) TODO: se i parser under mkCalls



  \item \textbf{Strings}

    As the representation of `strings' outputted from the lexer is a Haskell-list, where each element is a letter, we just map each element to a `PChar' and wrap it within a `PList'. Thus it has become a list of characters in the parse tree.

  \item \textbf{List comprehensions}
    
    As list comprehensions are composed of an output expression, draws and guards, the desugaring is implemented as follows (for an example of a list comprehension, and its desugared version,  please see section \ref{sec:ex-listcomp}):
    \begin{description}
      \item[First] the identifiers from the draws are extracted as these will be used as arguments to the various functions.
      \item[Secondly,] a flatMap\footnote{flatMaps takes as arguments a lambda-expression and a list, maps the function to the list, and flattens the result} is generated for each of the draws, with the function taking as argument the identifier of the current draw and the list-expression as defined right-hand-side of the ` \texttt{<-}', e.g. `\texttt{[1, 2, 3]}' in `\texttt{x <- [1, 2, 3]}'. The body of the lambda expression is either a nested flatMap or the final if-expression.
        \item[Thirdly,] the guards are inserted as bodies into functions which take all the extracted identifiers as arguments. These lambda-expressions are then conjoined in the condition of the \textbf{if}-expression.
      \item[Finally,] the \textbf{then}-branch of the \textbf{if}-expression is a function with the output expression as its body and the extracted identifiers as its arguments. The \textbf{else}-branch is simply an empty list. This implies that only the elements that pass the guards are outputted, as flatMap gets rid of empty elements.
    \end{description}

    
\end{itemize}

TODO: infix

TODO: strings
{'fraction_non_alphanumeric': 0.06282853566958699, 'fraction_numerical': 0.0036295369211514395, 'mean_word_length': 4.428668478260869, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, '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': '6242391', 'n_tokens_mistral': 2060, 'n_tokens_neox': 1971, 'n_words': 1085}