From 5f216c089cf607cab359f5bc8d5b4ec76bc15a25 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Wed, 13 Apr 2016 19:21:48 +0200 Subject: [PATCH] oops, eerste presentatie weggegooid --- deliverables/p1/p1.tex | 221 ------------------------------ deliverables/p2/.chktexrc | 1 + deliverables/{p1 => p2}/Makefile | 4 +- deliverables/{p1 => p2}/clean.sty | 0 deliverables/p2/p2.tex | 93 +++++++++++++ deliverables/{p1 => p2}/pre.tex | 11 +- 6 files changed, 98 insertions(+), 232 deletions(-) delete mode 100644 deliverables/p1/p1.tex create mode 100644 deliverables/p2/.chktexrc rename deliverables/{p1 => p2}/Makefile (79%) rename deliverables/{p1 => p2}/clean.sty (100%) create mode 100644 deliverables/p2/p2.tex rename deliverables/{p1 => p2}/pre.tex (64%) diff --git a/deliverables/p1/p1.tex b/deliverables/p1/p1.tex deleted file mode 100644 index 27c30d1..0000000 --- a/deliverables/p1/p1.tex +++ /dev/null @@ -1,221 +0,0 @@ -%&p1 -\begin{document} -\frame{\titlepage} - -\section{Introduction} -\begin{frame} - \frametitle{\textsc{SPL}} - \begin{block}{Features} - \begin{itemize} - \item Implementation language: - Clean ({\tiny\url{http://clean.cs.ru.nl}}) - \pause - \begin{itemize} - \item Pure language - \item Higher order functions - \item Monads - \item Using parser combinator library \textsc{Yard} - \end{itemize} - \pause - \item Positional data available for easy locating of errors. - \pause - \item Standardized parser errors. This means you can set it as - \texttt{buildprg} in \texttt{vim} and you can then use the - quickfix window! - \end{itemize} - \end{block} -\end{frame} - -\begin{frame}[fragile] - \frametitle{\textsc{YARD}} - \framesubtitle{A minimal home grown monadic parser combinator library} - \begin{itemize} - \item Inspired by \textsc{parsec}: $1pc=3.375\cdot10^{16}yd$~\footnote{ - A yard is exactly $36$ inch and an inch is exactly the length - of $3$ barleycorns}. - \item Definitons: - \begin{CleanCode} -:: Error = PositionalError Int Int String | Error String -:: Parser a b = Parser ([a] -> (Either Error b, [a])) - \end{CleanCode} - \pause - \item Result is either Error or \texttt{b}, not a \texttt{[b]} as - described Hutton \& Meijer \footnote{G. Hutton and E. Meijer. - Monadic parser combinators. 1996.} - \pause - \item Matches longest left-most parser - \pause - \item Stops immediately on error\pause\\ - By design! - \end{itemize} -\end{frame} - -\begin{frame}[fragile] - \frametitle{\textsc{YARD} Combinators} - \framesubtitle{Designed to be minimal, just 14 parsers/combinators} - YARD is designed to be minimal and defines just 14 primitives: - \begin{columns}[t] - \begin{column}{0.5\textwidth} - \begin{CleanCode} -top :: Parser a a -peek :: Parser a a -fail :: Parser a b -eof :: Parser a Void -(until) :: (Parser a b) - (Parser a c) - -> Parser a [b] -satisfy :: (a -> Bool) - -> Parser a a -check :: (a -> Bool) - -> Parser a a -item :: a -> Parser a a -list :: [a] -> Parser a [a] - \end{CleanCode} - \end{column} - \begin{column}{0.5\textwidth} - \begin{CleanCode} -(>>=) :: (Parser a b) - (b -> Parser a c) - -> Parser a c -(<|>) :: (Parser a b) - (Parser a b) - -> Parser a b -some :: (Parser a b) - -> Parser a [b] -many :: (Parser a b) - -> Parser a [b] -optional :: (Parser a b) - -> Parser a (Maybe b) - \end{CleanCode} - \end{column} - \end{columns} -\end{frame} - -\begin{frame}[fragile] - \frametitle{\textsc{YARD} Combinators} - \framesubtitle{Designed to be minimal, just \textbf{7} parsers/combinators} - Actually, scrap that, just \textbf{7} primitives: - \begin{columns}[t] - \begin{column}{0.5\textwidth} - \begin{CleanCode} -top :: Parser a a -peek :: Parser a a -fail :: Parser a b -eof :: Parser a Void - \end{CleanCode} - \end{column} - \begin{column}{0.5\textwidth} - \begin{CleanCode} -(>>=) :: (Parser a b) - (b -> Parser a c) - -> Parser a c -(<|>) :: (Parser a b) - (Parser a b) - -> Parser a b - \end{CleanCode} - \end{column} - \end{columns} - All others can be (and are) derived from these. e.g. - \begin{lstlisting} -satisfy :: (a -> Bool) -> Parser a a -satisfy f = top >>= \c -> if (f c) (return c) fail - \end{lstlisting} -\end{frame} - -\section{Design choices} -\begin{frame} - \frametitle{Adapting the grammar} - \begin{itemize} - \item Remove left recursion - \item Fixing associativity - \item Added small features such as escape characters \texttt{ - \textbackslash n\textbackslash b} - \pause - \item Show grammar now\ldots - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Two-phase design} - \framesubtitle{Lexing} - Also done with \textsc{YARD} because - \begin{itemize} - \item Multiline comments - \item Alternatives - \item Positions - \end{itemize} -\end{frame} - -\begin{frame}[fragile] - \frametitle{Two-phase design} - \framesubtitle{Parsing} - Read from stdin, write to stdout\\ - Added some handy primitives - \begin{CleanCode} -parseBlock :: Parser Token [Stmt] - -parseOpR :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr -parseOpL :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr - -trans2 :: TokenValue (TokenValue -> a) -> Parser Token a -trans1 :: TokenValue a -> Parser Token a - -peekPos :: Parser Token Pos - \end{CleanCode} -\end{frame} - -\begin{frame}[fragile] - \frametitle{Statistics} - \framesubtitle{Lines of code} - \lstinputlisting{|"wc -l ../../*.[di]cl"} - \pause - \begin{block}{} - \emph{``Measuring programming progress by lines of code is like - measuring aircraft building progress by weight.''}\\ - {---} Bill Gates - \end{block} -\end{frame} - -\begin{frame} - \frametitle{Statistics} - \framesubtitle{Hours of work} - We have no clue how much time we have worked on it\ldots - \pause - \begin{block}{} - \emph{``Choose a job you love, and you will never have to work a day in - your life.''}\\ - {---} Confucius - \end{block} -\end{frame} - -\section{Examples} -\begin{frame} - \frametitle{Weird inputs} - \begin{itemize} - \item \pause Heap full - \pause\ldots Increase heap\\ - \texttt{\$ ./spl -h 2000M} - \item \pause Stack full - \pause\ldots Increase stack\\ - \texttt{\$ ./spl -s 200M} - \item \pause Segmentation fault - \pause\ldots Enable memory overcommitting\\ - \texttt{\# echo 1 > /proc/sys/vm/overcommit\_memory} - \item \pause Still segmentation fault - \pause\ldots Buy more \textsc{RAM} - \item \pause Still segmentation fault? - \pause\ldots Divide into modules and parse separatly~\footnote{To be - implemented} - \item \pause Thus, we are only limited by hardware\ldots - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Learned lessons} - \begin{itemize} - \item \pause Parser combinators are elegant! - \item \pause Positional errors are a must! - \item \ldots - \end{itemize} -\end{frame} -\end{document} diff --git a/deliverables/p2/.chktexrc b/deliverables/p2/.chktexrc new file mode 100644 index 0000000..7d63431 --- /dev/null +++ b/deliverables/p2/.chktexrc @@ -0,0 +1 @@ +VerbEnvir { CleanCode } diff --git a/deliverables/p1/Makefile b/deliverables/p2/Makefile similarity index 79% rename from deliverables/p1/Makefile rename to deliverables/p2/Makefile index c2f8c38..98517ce 100644 --- a/deliverables/p1/Makefile +++ b/deliverables/p2/Makefile @@ -1,6 +1,6 @@ LATEX:=pdflatex LATEXFLAGS:=-shell-escape -DOCUMENT:=p1 +DOCUMENT:=p2 .PHONY: all clean .SECONDARY: $(DOCUMENT).fmt @@ -15,4 +15,4 @@ all: $(DOCUMENT).pdf $(LATEX) $(LATEXFLAGS) -ini -jobname="$(basename $@)" "&$(LATEX) $<\dump" clean: - $(RM) -v $(addprefix $(DOCUMENT).,aux fmt log nav out snm toc) + $(RM) -v $(addprefix $(DOCUMENT).,aux fmt log nav out snm toc vrb) diff --git a/deliverables/p1/clean.sty b/deliverables/p2/clean.sty similarity index 100% rename from deliverables/p1/clean.sty rename to deliverables/p2/clean.sty diff --git a/deliverables/p2/p2.tex b/deliverables/p2/p2.tex new file mode 100644 index 0000000..0399d8d --- /dev/null +++ b/deliverables/p2/p2.tex @@ -0,0 +1,93 @@ +%&p2 +\begin{document} +\frame{\titlepage} + +\begin{frame}[fragile] + \frametitle{\textsc{SPLS}} + \begin{block}{Features} + \begin{itemize} + \item Implementation language: + Clean ({\tiny\url{http://clean.cs.ru.nl}}) + \pause% + \item State transformer monad\pause% + \begin{CleanCode} +:: Gamma :== (Map String Type, [String]) +:: Env a :== StateT Gamma (Either SemError) a + \end{CleanCode} + \item Preferably we want to have an \CI{Either} monad transformer + but clean does not have that\ldots + \end{itemize} + \end{block} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Grammar changes} + + \begin{itemize} + \item Function type:\pause% + \begin{CleanCode} + ::= ['->' ] + ::= | Type + \end{CleanCode} + \pause Example% + \begin{CleanCode} +append(l1, l2) :: [t] -> [t] -> [t] { + ... +} + \end{CleanCode} + \pause\item We check in the semantic analysis that \CI{Void} is only in + the last type. + \pause\item This is for future higher-order functions + \end{itemize} +\end{frame} + +\begin{frame}[fragile] + \frametitle{What do we analyze exactly?} + \begin{CleanCode} +:: Pos = {line :: Int, col :: Int} +:: SemOutput :== Either [SemError] (AST, Gamma) +:: SemError + = ParseError Pos String // Post-parse errors + | UnifyError Pos Type Type // Unification + | FieldSelectorError Pos Type FieldSelector // hd, tail, fst, snd + | OperatorError Pos Op2 Type // 'a' == 5 + | UndeclaredVariableError Pos String // Variable ordering + | Error String + +sem :: AST -> SemOutput + \end{CleanCode} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Analyses} + \pause% + \begin{block}{Scoping?} + Local variables get a new name and are changed in the function body. + \end{block} + \pause% + \begin{block}{Order?} + Does matter for variables, not for functions. + \end{block} + \pause% + \begin{block}{Mutual recursion?} + Yep! + \end{block} + \pause% + \begin{block}{Higher order functions?} + Hopefully in the future + \end{block} +\end{frame} + +% - Can functions that are defined later in a file call earlier defined functions? +% - Can local variables be defined in terms of other local variables? +% - How do you deal with assignments? +% - Tell us if and how you include the value restriction. +%- How do you deal with recursion? +%- How do you deal with multiple recursion? +%- If you forbid multiple recursion, how do you do so? +% - Does your language support higher-order functions? +% - How do you deal with polymorphism? +% - How do you deal with overloading? +% - How does the absence/presence of type signatures influence your type +% checker? +\end{document} diff --git a/deliverables/p1/pre.tex b/deliverables/p2/pre.tex similarity index 64% rename from deliverables/p1/pre.tex rename to deliverables/p2/pre.tex index 5cc364c..59c31d6 100644 --- a/deliverables/p1/pre.tex +++ b/deliverables/p2/pre.tex @@ -4,8 +4,8 @@ \usepackage{listings} \usepackage{clean} -\title[cc1516: Lexing \& Parsing]{SPL} -\subtitle{\texttt{ ::= 'and' }} +\title[cc1516: Semantic analysis]{SPLT} +\subtitle{\texttt{~::= `,' `and' }} \author[P. Jager, M. Lubbers]{Pim Jager\inst{1}\and Mart Lubbers\inst{1}} \institute[Radboud University]{% \inst{1}% @@ -15,13 +15,6 @@ \subject{Parser} \date{\today} -\AtBeginSection[]{% - \begin{frame} - \frametitle{Table of Contents} - \tableofcontents[currentsection] - \end{frame} -} - \lstset{% basicstyle=\ttfamily\footnotesize, breaklines -- 2.20.1