deliverables/p2/p2.tex

   1 %&p2
   2 \begin{document}
   3 \frame{\titlepage}
   4
   5 \begin{frame}[fragile]
   6         \frametitle{\textsc{SPLS}}
   7         \begin{block}{Features}
   8                 \begin{itemize}
   9                         \item Implementation language:
  10                                 Clean ({\tiny\url{http://clean.cs.ru.nl}})
  11                         \pause%
  12                         \item State transformer monad\pause%
  13                                 \begin{CleanCode}
  14 :: Gamma :== (Map String Type, [String])
  15 :: Env a :== StateT Gamma (Either SemError) a
  16                                 \end{CleanCode}
  17                         \item Preferably we want to have an \CI{Either} monad transformer
  18                                 but clean does not have that\ldots
  19                 \end{itemize}
  20         \end{block}
  21 \end{frame}
  22
  23 \begin{frame}[fragile]
  24         \frametitle{Grammar changes}
  25
  26         \begin{itemize}
  27                 \item Function type:\pause%
  28                         \begin{CleanCode}
  29 <FunType>  ::= <VoidType> ['->' <FunType>]
  30 <VoidType> ::= <Void> | Type
  31                         \end{CleanCode}
  32                 \pause Example%
  33                         \begin{CleanCode}
  34 append(l1, l2) :: [t] -> [t] -> [t] {
  35     ...
  36 }
  37                         \end{CleanCode}
  38                 \pause\item We check in the semantic analysis that \CI{Void} is only in
  39                         the last type.
  40                 \pause\item This is for future higher-order functions
  41         \end{itemize}
  42 \end{frame}
  43
  44 \begin{frame}[fragile]
  45         \frametitle{What do we analyze exactly?}
  46         \begin{CleanCode}
  47 :: Pos = {line :: Int, col :: Int}
  48 :: SemOutput :== Either [SemError] (AST, Gamma)
  49 :: SemError
  50     = ParseError Pos String                     // Post-parse errors
  51     | UnifyError Pos Type Type                  // Unification
  52     | FieldSelectorError Pos Type FieldSelector // hd, tail, fst, snd
  53     | OperatorError Pos Op2 Type                // 'a' == 5
  54     | UndeclaredVariableError Pos String        // Variable ordering
  55     | Error String
  56
  57 sem :: AST -> SemOutput
  58         \end{CleanCode}
  59 \end{frame}
  60
  61 \begin{frame}[fragile]
  62         \frametitle{Analyses}
  63         \pause%
  64         \begin{block}{Scoping?}
  65                 Local variables get a new name and are changed in the function body.
  66         \end{block}
  67         \pause%
  68         \begin{block}{Order?}
  69                 Does matter for variables, not for functions.
  70                 \pause
  71                 \begin{itemize}
  72                         \item Note that this means that \texttt{ones=1:ones} is
  73                                         not allowed.
  74                 \end{itemize}
  75         \end{block}
  76         \pause%
  77         \begin{block}{Mutual recursion?}
  78                 Yep!
  79         \end{block}
  80         \pause%
  81         \begin{block}{Higher order functions?}
  82                 Would be an interesting idea for assignment 4
  83         \end{block}
  84 \end{frame}
  85
  86 \begin{frame}[fragile]
  87         \frametitle{Mutual Recursion}
  88         \begin{itemize}
  89                 \item Mutual recursion is allowed and type checked, however inference is
  90                 not complete.
  91                 \pause
  92                 \begin{CleanCode}
  93 flip(n, l) :: Int -> [Int] -> [Int] {
  94   if( n <= 0 ) {return l;}
  95   else {return flop(n-1, 0:l);}
  96 }
  97
  98 flop(n, l) :: Int -> [Int] -> [Int] {
  99   return flip(n, 1:l);
 100 }
 101                 \end{CleanCode}
 102                 \pause
 103                 \item Completely typed specifications are checked correctly.
 104         \end{itemize}
 105 \end{frame}
 106
 107 \begin{frame}[fragile]
 108         \frametitle{Mutual Recursion}
 109         \begin{itemize}
 110                 \item Mutual recursion is allowed and type checked, however inference is
 111                 not complete.
 112                 \begin{CleanCode}
 113 flip(n, l) :: Int -> [Int] -> [Int] {
 114   if( n <= 0 ) {return l;}
 115   else {return flop(n-1, 0:l);}
 116 }
 117
 118 flop(n, l) :: Int -> [Int] -> Bool {
 119   return flip(n, 1:l);
 120 }
 121                 \end{CleanCode}
 122                 \pause
 123                 \item It is also correctly determined that \texttt{Bool} and the return
 124                 type of \texttt{flop(n,l)} don't match.
 125         \end{itemize}
 126 \end{frame}
 127
 128 \begin{frame}[fragile]
 129         \frametitle{Mutual Recursion}
 130         \begin{itemize}
 131                 \item Mutual recursion is allowed and type checked, however inference is
 132                 not complete.
 133                 \pause
 134                 \begin{CleanCode}
 135 flip(n, l) {
 136   if( n <= 0 ) {return l;}
 137   else {return flop(n-1, 0:l);}
 138 }
 139
 140 flop(n, l) {
 141   return flip(n, 1:l);
 142 }
 143                 \end{CleanCode}
 144         \end{itemize}
 145 \end{frame}
 146
 147
 148 \begin{frame}[fragile]
 149         \frametitle{Mutual Recursion}
 150         \begin{itemize}
 151                 \item Mutual recursion is allowed and type checked, however inference is
 152                 not complete.
 153                 \begin{CleanCode}
 154 flip(n, l) :: Int -> [Int] -> vTqhp {
 155   if( n <= 0 ) {return l;}
 156   else {return flop(n-1, 0:l);}
 157 }
 158
 159 flop(n, l) :: Int -> [Int] -> HSWdn {
 160   return flip(n, 1:l);
 161 }
 162                 \end{CleanCode}
 163                 \item However when no type information is given at all our algorithm
 164                 fails to correctly infer the result type of the two function.
 165         \end{itemize}
 166 \end{frame}
 167
 168 % - Can functions that are defined later in a file call earlier defined functions?
 169 % - Can local variables be defined in terms of other local variables?
 170 % - How do you deal with assignments?
 171 % - Tell us if and how you include the value restriction.
 172 %- How do you deal with recursion?
 173 %- How do you deal with multiple recursion?
 174 %- If you forbid multiple recursion, how do you do so?
 175 % - Does your language support higher-order functions?
 176 % - How do you deal with polymorphism?
 177 % - How do you deal with overloading?
 178 % - How does the absence/presence of type signatures influence your type
 179 %  checker?
 180 \end{document}