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                 \begin{CleanCode}
 134 flip(n, l) {
 135   if( n <= 0 ) {return l;}
 136   else {return flop(n-1, 0:l);}
 137 }
 138
 139 flop(n, l) {
 140   return flip(n, 1:l);
 141 }
 142                 \end{CleanCode}
 143         \end{itemize}
 144 \end{frame}
 145
 146
 147 \begin{frame}[fragile]
 148         \frametitle{Mutual Recursion}
 149         \begin{itemize}
 150                 \item Mutual recursion is allowed and type checked, however inference is
 151                 not complete.
 152                 \begin{CleanCode}
 153 flip(n, l) :: Int -> [Int] -> vTqhp {
 154   if( n <= 0 ) {return l;}
 155   else {return flop(n-1, 0:l);}
 156 }
 157
 158 flop(n, l) :: Int -> [Int] -> HSWdn {
 159   return flip(n, 1:l);
 160 }
 161                 \end{CleanCode}
 162                 \item However when no type information is given at all our algorithm
 163                 fails to correctly infer the result type of the two function.
 164         \end{itemize}
 165 \end{frame}
 166
 167 \begin{frame}[fragile]
 168         \frametitle{But wait, there is more!}
 169         \framesubtitle{Trouble that is}
 170         \begin{itemize}
 171                 \item Polymorphism is not working great either.
 172                 \begin{CleanCode}
 173 id(x) :: a -> a {
 174     return x;
 175 }
 176                 \end{CleanCode}
 177                 \pause
 178                 \item Is typed fun, but when we introduce:
 179                 \begin{CleanCode}
 180 var x = id(5);
 181 var y = id(True);
 182                 \end{CleanCode}
 183                 \pause
 184                 \begin{CleanCode}
 185 2:12 SemError: Cannot unify types. Expected: Int. Given: Bool
 186                 \end{CleanCode}
 187         \end{itemize}
 188 \end{frame}
 189
 190 \begin{frame}[fragile]
 191         \frametitle{But wait, there is more!}
 192         \framesubtitle{Trouble that is}
 193
 194         \begin
 195 \end{frame}
 196
 197 % - Can functions that are defined later in a file call earlier defined functions?
 198 % - Can local variables be defined in terms of other local variables?
 199 % - How do you deal with assignments?
 200 % - Tell us if and how you include the value restriction.
 201 %- How do you deal with recursion?
 202 %- How do you deal with multiple recursion?
 203 %- If you forbid multiple recursion, how do you do so?
 204 % - Does your language support higher-order functions?
 205 % - How do you deal with polymorphism?
 206 % - How do you deal with overloading?
 207 % - How does the absence/presence of type signatures influence your type
 208 %  checker?
 209 \end{document}