From 27a7e0c9b99110ef41e0ff03bff744fbb6fa7f57 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Mon, 21 Mar 2016 21:41:46 +0100 Subject: [PATCH] up --- .gitignore | 1 + long1/clean.sty | 70 ++++++++++++++++++ long1/long.tex | 190 +++++++++++++++++++++++++++++++++++++++++++++--- long1/pre.tex | 7 +- 4 files changed, 257 insertions(+), 11 deletions(-) create mode 100644 long1/clean.sty diff --git a/.gitignore b/.gitignore index 95dcd9b..21411d2 100644 --- a/.gitignore +++ b/.gitignore @@ -6,3 +6,4 @@ *.pdf *.nav *.snm +*.vrb diff --git a/long1/clean.sty b/long1/clean.sty new file mode 100644 index 0000000..ca04091 --- /dev/null +++ b/long1/clean.sty @@ -0,0 +1,70 @@ +\usepackage{listings} + +\lstdefinelanguage{Clean}{% + alsoletter={ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_`1234567890}, + alsoletter={~!@\#$\%^\&*-+=?<>:|\\.}, + morekeywords={generic,implementation,definition,dynamic,module,import,from,where,in,of,case,let,infix,infixr,infixl,class,instance,with,if,derive,Void}, + sensitive=true, + morecomment=[l]{//}, + morecomment=[n]{/*}{*/}, + morestring=[b]", + morestring=[b]', + emptylines=1, + basicstyle=\small, + identifierstyle=\small\ttfamily, + commentstyle=\itshape, + keywordstyle=\bfseries, + stringstyle=\ttfamily, + numbers=none, + showstringspaces=false, + basewidth=0.45em, + columns=[c]fixed, + keepspaces=true, + breaklines=false, + tabsize=4, + texcl=true, + escapeinside={(\#}{\#)}, + literate=% + % Basic Clean constructs + {\\}{{$\lambda\:$}}1 + {A.}{{$\forall\;\,$}}1 + {E.}{{$\exists\;\,$}}1 + {>}{{$>$}}1 + {<}{{$<$}}1 + {<=}{{$\leq$}}1 + {>=}{{$\geq$}}1 + {<>}{{$\neq$}}1 + {->}{{$\rightarrow$}}2 + {<-}{{$\leftarrow$}}1 + {=}{{$=$}}1 + {~}{{$\sim$}}1 + {\#}{{$\sharp$}}1 + {\{|}{{$\{\!|\!$}}1 + {|\}}{{$\!|\!\}$}}1 + {:=}{{$:=$}}2 + {==}{{$==$}}2 + {++}{{$+\!\!+$}}2 + {+++}{{$+\!\!\!\!+\!\!\!\!+$}}2 + {:==}{{$:==$}}3 + {\{|*|\}}{{$\{\!|\!\!\star\!\!|\!\}$}}3 + % + % Basic iTask constructs + {>||>}{{$\triangleright\triangleright$}}2 + {>>=}{{\texttt{>>=}}}3 + {>>|}{{\texttt{>>|}}}3 + {?>>}{{\texttt{?>>}}}3 + {!>>}{{\texttt{!>>}}}3 + {-||-}{{\texttt{-||-}}}4 + {.||.}{{\texttt{.||.}}}4 + {.&&.}{{\texttt{.\&\&.}}}4 +} + +\newcommand{\CleanInline}[1]{\lstinline[language=Clean]¦#1¦} +\newcommand{\CI}[1]{\CleanInline{#1}} + +\lstdefinestyle{numbers}{numbers=left, stepnumber=1, numberstyle=\tiny, numbersep=5pt} + +\lstnewenvironment{CleanCode}{\lstset{language=Clean,identifierstyle=\ttfamily}}{} +\lstnewenvironment{CleanCodeN}{\lstset{language=Clean,style=numbers}}{} +\lstnewenvironment{CleanCodeB}{\lstset{language=Clean,frame=single}}{} +\lstnewenvironment{CleanCodeNB}{\lstset{language=Clean,style=numbers,frame=single}}{} diff --git a/long1/long.tex b/long1/long.tex index ab65bb8..c0e603e 100644 --- a/long1/long.tex +++ b/long1/long.tex @@ -5,12 +5,14 @@ \section{Introduction} \begin{frame} \frametitle{Scientific Impact} - \begin{itemize} - \item Cited $676$ times in $23$ years - \item $\pm 30$ cites per year - \item Cited as de-facto monad introducing paper - \item Monads in computer science: Moggi et al.\ in $1989$ - \end{itemize} + \begin{block}{Metrics} + \begin{itemize}[<+->] + \item Cited $676$ times in $23$ years + \item $\pm 30$ cites per year + \item Cited as de-facto monad introducing paper + \item Monads in computer science: Moggi et al.\ in $1989$ + \end{itemize} + \end{block} \end{frame} \begin{frame} @@ -24,23 +26,193 @@ \pause% \begin{block}{Current state of the art} - \begin{itemize} + \begin{itemize}[<+->] \item $2016$: $2$ papers citing Wadler \item $2015$: $24$ papers citing Wadler \item Ranging from - \pause% - \begin{itemize} + \begin{itemize}[<+->] \item Introducing new monad types \item Generic programming \item Designing modular DSL's \item Concurrency frameworks in functional languages + \item\ldots \end{itemize} \end{itemize} \end{block} \end{frame} \section{Contents} +\subsection{Introduction} +\begin{frame} + \frametitle{Introduction} + \begin{itemize} + \item Monads (Moggi et al.) + \item Integrate the impure in the pure + \item Wadler shows \textsc{Haskell} examples + \item Following samples are in \textsc{Clean} + \end{itemize} +\end{frame} + +\subsection{Naive approach} +\begin{frame}[fragile] + \frametitle{Case study (1)} + \framesubtitle{Evaluator} + \begin{CleanCode} +:: Term = Con Int | Div Term Term + +eval :: Term -> Int +eval (Con a) = a +eval (Div t u) = eval t / eval u + +//Examples +answer :: Term +answer = (Div (Div (Con 1972) (Con 2)) (Con 23)) + +error :: Term +error = (Div (Con 1) (Con 0)) + \end{CleanCode} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Case study (2)} + \framesubtitle{Exceptions} + \begin{CleanCode} +:: M a = Raise Exception | Return a +:: Exception :== String + +eval :: Term -> M Int +eval (Con a) = Return a +eval (Div t u) = case eval t of + Raise e = Raise e + Return a = case eval u of + Raise e = Raise e + Return b = if (b == 0) + (Raise "Divide by zero") + (Return (a / b)) + \end{CleanCode} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Case study (3)} + \framesubtitle{State, count divisions} + \begin{CleanCode} +:: M a :== State -> (a, State) +:: State :== Int + +eval :: Term -> M Int +eval (Con a) x = (a, x) +eval (Div t u) +# (a, y) = eval t x +# (b, z) = eval u y += (a/b, z+1) + \end{CleanCode} +\end{frame} + +\subsection{Monadic approach} +\begin{frame}[fragile] + \frametitle{Monadic (1)} + Monad is a triple: $(M, unit, \star)$ + \pause% + \begin{block}{Signatures} + \begin{CleanCode} +:: M a = ... +unit :: a -> M a +((#$\star$#)) :: (M a) (a -> M b) -> M b + \end{CleanCode} + \end{block} + \pause% + \begin{block}{Evaluator (Identity monad)} + \begin{CleanCode} +:: M a :== a +unit :: a -> I a +unit a = a +((#$\star$#)) :: (M a) (a -> M b) -> M b +a (#$\star$#) k = k a + \end{CleanCode} + \end{block} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Monadic (2)} + \framesubtitle{Exceptions} + \pause% + \begin{CleanCode} +:: M a = Raise Exception | Return a +:: Exception :== String + \end{CleanCode} + \pause% + \begin{CleanCode} +unit :: a -> M a +unit a = Return a + +((#$\star$#)) :: (M a) (a -> M b) -> M b +m (#$\star$#) k = case m of + Raise e = Raise e + Return a = k a + \end{CleanCode} + \pause% + \begin{CleanCode} +raise :: Exception -> M a +raise e = Raise e + \end{CleanCode} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Monadic (3)} + \framesubtitle{State} + \pause% + \begin{CleanCode} +:: M a = State -> (a, State) +:: State :== Int + \end{CleanCode} + \pause% + \begin{CleanCode} +unit :: a -> M a +unit a = \x.(a, x) + +((#$\star$#)) :: (M a) (a -> M b) -> M b +m (#$\star$#) k = \x.let (a, y) = m x in + let (b, z) = k a y in + (b, z) + \end{CleanCode} + \pause% + \begin{CleanCode} +tick :: M Void +tick = \x.(Void, x + 1) + \end{CleanCode} +\end{frame} + +\subsection{Laws} +\begin{frame}[fragile] + \frametitle{Laws} + \begin{block}{Monoid} + \begin{itemize} + \item Left unit: + \begin{CleanCode} +unit a (#$\star$#) \b.n = n[a/b] + \end{CleanCode} + \item Right unit + \begin{CleanCode} +m (#$\star$#) \a.unit a = m + \end{CleanCode} + \item Associativity + \begin{CleanCode} +m (#$\star$#) (\a.n (#$\star$#) \b.o) = (m (#$\star$#) \a.n) (#$\star$#) \b.o + \end{CleanCode} + \end{itemize} + \end{block} +\end{frame} + +\subsection{Further evidence} +\begin{frame}[fragile] + \frametitle{Further examples} + \begin{itemize}[<+->] + \item Array %TODO + \end{itemize} +\end{frame} \section{Discussion} +\begin{frame} +\end{frame} \end{document} diff --git a/long1/pre.tex b/long1/pre.tex index 077a09b..ada3c0b 100644 --- a/long1/pre.tex +++ b/long1/pre.tex @@ -1,10 +1,13 @@ \documentclass{beamer} +\usepackage{clean} + \usecolortheme{dove} \usetheme{Singapore} -\title[RSSS]{Monads for functional programming} -%\subtitle{A review} +\title[RSSS]{Monads for functional programming\\P.\ Wadler} +\subtitle{Originally published in Springer's \emph{Program Design Calculi} in + $1993$} \author[Lubbers]{M.~Lubbers~\inst{1}} \institute[Radboud University]{% \inst{1}% -- 2.20.1