christiaan/recursion.lhs

   1 \subsection{Recursion}
   2 %include talk.fmt
   3 \frame{
   4 \frametitle{Future Work: Recursion}
   5 \begin{itemize}
   6   \item The most pressing future work is to support recursive functions.
   7   \item Partially explored solution: static loop unrolling
   8   \item Unexplored solution: Haskell language extensions, new source language
   9 \end{itemize}
  10 }
  11
  12 \subsubsection{Static loop unrolling}
  13 \frame{
  14 \frametitle{Static loop unrolling}
  15 \begin{itemize}
  16   \item Unroll, and simplify recursive definitions at compile time.
  17   \item Explored solution: Unrolling number-guided recursive functions using Template Haskell
  18 \end{itemize}
  19 }
  20
  21 \frame{
  22 \frametitle{Template Haskell}
  23 \begin{itemize}
  24   \item Template Haskell allows for compile-time inspection, construction, and manipulation of Haskell code.
  25   \item All these functions are expressible in normal Haskell
  26 \end{itemize}
  27 }
  28
  29 \frame{
  30 \frametitle{Tree Adder}
  31 \begin{verbatim}
  32 $(do
  33   [typ, _] <- [d|{
  34 treeSum :: Vector D8 (SizedWord D8) -> SizedWord D8;
  35 treeSum xs = undefined
  36   }|]
  37   [func] <- [d|{
  38 treeSum i xs | i < 1     = head xs
  39              | otherwise = let (a,b) = split xs
  40                            in (treeSum (i-1) a) +
  41                               (treeSum (i-1) b)
  42   }|]
  43   let func' = unroll Nothing 0 (IntegerL 3) funct
  44   return [typ,func']
  45 )
  46 \end{verbatim}
  47 }
  48
  49 \begin{frame}
  50    \frametitle{Unrolled tree adder}
  51    \begin{figure}
  52       \includegraphics[height=5cm]{treeadder}
  53     \end{figure}
  54 \end{frame}
  55
  56 \subsubsection{Input Language}
  57 \frame{
  58 \frametitle{Input Language}
  59 \begin{itemize}
  60   \item New source language: One of the problems is that Haskell does not properly support dependent types. Investigate languages with dependent type systems.
  61   \item Haskell extentions: Invariant descriptions at the type-level.
  62 \end{itemize}
  63 }