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 \note[itemize]{
  12 \item Afsluitend nog het meest voor de hand liggende future work: het ondersteunen van recursie.
  13 \item Er zijn al wat mogelijkheden onderzocht: static loop unrolling, waar ik zo wat over vertel.
  14 \item Andere mogelijkheden zijn het op zoek gaan naar een taal die wel echt ondersteuning heeft voor dependent types. Daar later meer over.
  15 \item Next sheet: static loop unrolling
  16 }
  17
  18 \subsubsection{Static loop unrolling}
  19 \frame{
  20 \frametitle{Static loop unrolling}
  21 \begin{itemize}
  22   \item Unroll, and simplify recursive definitions at compile time.
  23   \item Explored solution: Unrolling number-guided recursive functions using Template Haskell
  24 \end{itemize}
  25 }
  26 \note[itemize]{
  27 \item Static loop unrolling, is het op compile-time uitrollen van recursieve functies totdat er geen recursie meer is. Je moet de functies ook simplificeren omdat je de choice-logic die de recursie leidt wil verwijderen.
  28 \item Ik heb gekeken naar het uitrollen van number-guided recursive functies, met gehulp van Template Haskell.
  29 \item Next sheet: Template Haskell uitleg
  30 }
  31
  32 \frame{
  33 \frametitle{Template Haskell}
  34 \begin{itemize}
  35   \item Template Haskell allows for compile-time inspection, construction, and manipulation of Haskell code.
  36   \item All these functions are expressible in normal Haskell
  37 \end{itemize}
  38 }
  39 \note[itemize]{
  40 \item Ik heb vooral naar Template Haskell gekeken, omdat toekomstig gebruikes van \clash{} ook beschikking hebben om TH te kunnen gebruiken. Zonder dat ze direct de compiler in moeten duiken.
  41 \item TH staat het toe om code op compile-time te inspecteren, te creeeren en te veranderen.
  42 \item En dit kan allemaal met behulp van normale Haskell code
  43 \item Next sheet: voorbeeld uitrollen tree adder
  44 }
  45
  46 \frame{
  47 \frametitle{Tree Adder}
  48 \begin{code}
  49 $(do
  50   [typ, _] <- [d|{
  51 {-"{\color<2>[rgb]{1,0,0}"-}treeSum :: Vector D8 (SizedWord D8) -> SizedWord D8;{-"}"-}
  52 treeSum xs = undefined
  53   }|]
  54   [func] <- [d|{
  55 {-"{\color<3>[rgb]{1,0,0}"-}treeSum i xs | i < 1     = head xs{-"}"-}
  56 {-"{\color<3>[rgb]{1,0,0}"-}             | otherwise = let (a,b) = split xs{-"}"-}
  57 {-"{\color<3>[rgb]{1,0,0}"-}                           in (treeSum (i-1) a) +{-"}"-}
  58 {-"{\color<3>[rgb]{1,0,0}"-}                              (treeSum (i-1) b){-"}"-}
  59   }|]
  60 {-"{\color<4>[rgb]{1,0,0}"-}  let func' = unroll Nothing 0 (IntegerL 3) func{-"}"-}
  61 {-"{\color<5>[rgb]{1,0,0}"-}  return [typ,func']{-"}"-}
  62 )
  63 \end{code}
  64 }
  65 \note[itemize]{
  66 \item Zie hier een recursieve tree adder die ik uitroll naar 3 diep d.m.v. template haskell
  67 \item Zie de function signature bovenaan.
  68 \item Dan de de recursieve treeSum functie
  69 \item Dan de unroll functie die deze treeSum functie uitrolt
  70 \item En dan voegen we de uitegerolde functie weer in
  71 \item Next sheet: schema uitgerolde tree adder
  72 }
  73
  74 \begin{frame}
  75    \frametitle{Unrolled tree adder}
  76    \begin{figure}
  77       \includegraphics[height=5cm]{treeadder}
  78     \end{figure}
  79 \end{frame}
  80 \note[itemize]{
  81 \item Hier een schema van uitgerolde tree-adder voor 3 diep
  82 \item Volgende sheet: Aanpassingen input taal voor \clash{}
  83 }
  84
  85 \subsubsection{Input Language}
  86 \frame{
  87 \frametitle{Input Language}
  88 \begin{itemize}
  89   \item New source language: One of the problems is that Haskell does not properly support dependent types. Investigate languages with dependent type systems.
  90   \item Haskell extentions: Invariant descriptions at the type-level.
  91 \end{itemize}
  92 }
  93 \note[itemize]{
  94 \item Ondersteuning van dependent types is niet echt bestaand in Haskell. Is meer op een ad-hoc manier mogelijk, maar is bij ontwerp van het type-systeem nooit de bedoeling geweest.
  95 \item Daarom zou er gekeken moeten worden naar een echte dependently typed taal. Die het hopelijk makkelijker maakt om invarianten te specificeren, en is toe te voegen aan de code.
  96 \item Of er moet worden gekeken of er in Haskell de mogelijkheid bestaat om invarianten op type-niveau toe te voegen.
  97 \item Next sheet: vragen
  98 }