Changeset 48 for docs

Legend:

Unmodified

Added

Removed

• docs/branches/200711-tock-seminars/neil-split/200711-A-tock-slides.tex

  r47	r48
  41	41
  42	42	\title{Tock}
  43	\subtitle{A Swift Kick in the Monads}
  44	% FIXME: Ahem...
  45	% "Our quest to use as many Haskell libraries as possible in one
  46	% project"
  43	\subtitle{Every compilation begins with a single pass}
  47	44
  48	45	\author{Neil Brown and Adam Sampson}
  …	…
  152	149	\tableofcontents
  153	150	\end{frame}
  151	(追記) (追記ここまで)
  152	(追記) (追記ここまで)
  153	(追記) \begin{frame} (追記ここまで)
  154	(追記) \frametitle{Talk Abstract (TEMP slide)} (追記ここまで)
  155	(追記) Nanopass compilation is a way of structuring a compiler as many small passes, (追記ここまで)
  156	(追記) each performing only one simple action. In the first of two talks, we will (追記ここまで)
  157	(追記) introduce Tock, our nanopass compiler for concurrent languages, written in (追記ここまで)
  158	(追記) Haskell. We will explain nanopass compilation, and how we have implemented (追記ここまで)
  159	(追記) it with the help of Haskell generics. We will then go on to demonstrate (追記ここまで)
  160	(追記) a novel use for Haskell generics in our testing framework. (追記ここまで)
  161	(追記) \end{frame} (追記ここまで)
  154	162	%}}}
  155	163
  156	164	%{{{ introduction
  157	165	\section{Introduction}
  158	(削除) (削除ここまで)
  159	(削除) \begin{frame} (削除ここまで)
  160	(削除) \frametitle{What we're assuming you know} (削除ここまで)
  161	(削除) \begin{itemize} (削除ここまで)
  162	(削除) \item Haskell syntax (削除ここまで)
  163	(削除) \item Monads (削除ここまで)
  164	(削除) \end{itemize} (削除ここまで)
  165	(削除) \end{frame} (削除ここまで)
  166	(削除) (削除ここまで)
  167	(削除) %Tempting to add a joke "What we're not assuming you know" slide here (削除ここまで)
  168	(削除) %Suggestions for items: P=NP, the price of a loaf of bread, how to fix the university parking problem, etc etc (削除ここまで)
  169	166
  170	167	\begin{frame}
  …	…
  674	671	%}}}
  675	672
  676	(削除) %{{{ code analysis (削除ここまで)
  677	(削除) \section{Code analysis} (削除ここまで)
  678	(削除) (削除ここまで)
  679	(削除) \subsection{Tree navigation} (削除ここまで)
  680	(削除) (削除ここまで)
  681	(削除) \begin{frame} (削除ここまで)
  682	(削除) \frametitle{Control-flow graphs} (削除ここまで)
  683	(削除) \begin{itemize} (削除ここまで)
  684	(削除) \item We need to analyse the AST for various purposes (削除ここまで)
  685	(削除) \begin{itemize} (削除ここまで)
  686	(削除) \item Parallel usage checking (削除ここまで)
  687	(削除) \item Definedness checking (削除ここまで)
  688	(削除) \item Type optimisation (削除ここまで)
  689	(削除) \end{itemize} (削除ここまで)
  690	(削除) \item Many algorithms are easier to express on a CFG than on the (削除ここまで)
  691	(削除) AST directly (削除ここまで)
  692	(削除) \item Generating the CFG from the AST is easy (削除ここまで)
  693	(削除) \end{itemize} (削除ここまで)
  694	(削除) \end{frame} (削除ここまで)
  695	(削除) (削除ここまで)
  696	(削除) \begin{frame} (削除ここまで)
  697	(削除) \frametitle{Modifying the AST} (削除ここまで)
  698	(削除) \begin{itemize} (削除ここまで)
  699	(削除) \item Once we've made a decision based on the CFG, we need to go (削除ここまで)
  700	(削除) and change the AST (削除ここまで)
  701	(削除) \item But how? (削除ここまで)
  702	(削除) \begin{itemize} (削除ここまで)
  703	(削除) \item No unique identifiers in AST (削除ここまで)
  704	(削除) \item Only unique thing is the position in the tree (削除ここまで)
  705	(削除) \item No easy way to find \emph{and modify} a particular spot (削除ここまで)
  706	(削除) in a tree (削除ここまで)
  707	(削除) \end{itemize} (削除ここまで)
  708	(削除) \end{itemize} (削除ここまで)
  709	(削除) \end{frame} (削除ここまで)
  710	(削除) (削除ここまで)
  711	(削除) \begin{frame} (削除ここまで)
  712	(削除) \frametitle{Navigating the AST} (削除ここまで)
  713	(削除) \begin{columns} (削除ここまで)
  714	(削除) \column{.5\textwidth} (削除ここまで)
  715	(削除) \begin{itemize} (削除ここまで)
  716	(削除) \item Remember the route (削除ここまで)
  717	(削除) \begin{itemize} (削除ここまで)
  718	(削除) \item 1st child, 1st child, 2nd child (削除ここまで)
  719	(削除) \end{itemize} (削除ここまで)
  720	(削除) \item Not quite as easy as that in Haskell (the types vary!) (削除ここまで)
  721	(削除) \end{itemize} (削除ここまで)
  722	(削除) \column{.5\textwidth} (削除ここまで)
  723	(削除) \includegraphics[height=55mm]{Tock-Navigate-AST.png} (削除ここまで)
  724	(削除) \end{columns} (削除ここまで)
  725	(削除) \end{frame} (削除ここまで)
  726	(削除) (削除ここまで)
  727	(削除) \begin{frame}[fragile] (削除ここまで)
  728	(削除) \frametitle{A hop, a skip and a jump} (削除ここまで)
  729	(削除) \begin{columns} (削除ここまで)
  730	(削除) \column{.35\textwidth} (削除ここまで)
  731	(削除) \begin{itemize} (削除ここまで)
  732	(削除) \item Compose ``routes'' as we descend the tree (削除ここまで)
  733	(削除) \end{itemize} (削除ここまで)
  734	(削除) \begin{lstlisting} (削除ここまで)
  735	(削除) type F a = a -> m a (削除ここまで)
  736	(削除) append :: (削除ここまで)
  737	(削除) (F outer -> F Root) (削除ここまで)
  738	(削除) -> (F inner -> F outer) (削除ここまで)
  739	(削除) -> (F inner -> F Root) (削除ここまで)
  740	(削除) \end{lstlisting} (削除ここまで)
  741	(削除) %Old/alternate versions of the above code: (削除ここまで)
  742	(削除) %append :: ((outer -> m outer) -> (Root -> m Root)) (削除ここまで)
  743	(削除) % -> ((inner -> m inner) -> (outer -> m outer)) (削除ここまで)
  744	(削除) % -> ((inner -> m inner) -> (Root -> m Root)) (削除ここまで)
  745	(削除) (削除ここまで)
  746	(削除) (削除ここまで)
  747	(削除) %type Mod inner outer = (inner -> m inner) -> (outer -> m outer) (削除ここまで)
  748	(削除) %append :: Mod outer Root -> Mod inner outer -> Mod inner Root (削除ここまで)
  749	(削除) \column{.65\textwidth} (削除ここまで)
  750	(削除) \only<1>{\includegraphics[height=40mm]{Tock-Navigate-AST-1.png}} (削除ここまで)
  751	(削除) \only<2>{\includegraphics[height=40mm]{Tock-Navigate-AST-2.png}} (削除ここまで)
  752	(削除) \only<3>{\includegraphics[height=40mm]{Tock-Navigate-AST-3.png}} (削除ここまで)
  753	(削除) \only<4>{\includegraphics[height=40mm]{Tock-Navigate-AST-4.png}} (削除ここまで)
  754	(削除) \end{columns} (削除ここまで)
  755	(削除) \end{frame} (削除ここまで)
  756	(削除) (削除ここまで)
  757	(削除) (削除ここまで)
  758	(削除) \begin{frame}[fragile] (削除ここまで)
  759	(削除) \frametitle{$\sum \lambda_n = $Tedium} (削除ここまで)
  760	(削除) \begin{itemize} (削除ここまで)
  761	(削除) \item Writing it out long-hand is tiresome: (削除ここまで)
  762	(削除) \end{itemize} (削除ここまで)
  763	(削除) \begin{lstlisting} (削除ここまで)
  764	(削除) buildNode (While e s) route (削除ここまで)
  765	(削除) = do addNode (label e) (append route (削除ここまで)
  766	(削除) -- (Expr -> m Expr) -> (Statement -> m Statement) (削除ここまで)
  767	(削除) (\f (While e s) -> do {e' <- f e ; return (While e' s)})) (削除ここまで)
  768	(削除) buildNode p (append route (削除ここまで)
  769	(削除) -- (Statement -> m Statement) -> (Statement -> m Statement) (削除ここまで)
  770	(削除) (\f (While e s) -> f s >>= While e)) (削除ここまで)
  771	(削除) ... (削除ここまで)
  772	(削除) \end{lstlisting} (削除ここまで)
  773	(削除) \end{frame} (削除ここまで)
  774	(削除) (削除ここまで)
  775	(削除) \begin{frame}[fragile] (削除ここまで)
  776	(削除) \frametitle{Generic Route-Building} (削除ここまで)
  777	(削除) \begin{itemize} (削除ここまで)
  778	(削除) \item First-class patterns would help here, again (削除ここまで)
  779	(削除) \item We turn to generics again (削除ここまで)
  780	(削除) \end{itemize} (削除ここまで)
  781	(削除) \begin{lstlisting} (削除ここまで)
  782	(削除) buildNode (While e s) route (削除ここまで)
  783	(削除) = do addNode (label e) (route12 route While) (削除ここまで)
  784	(削除) buildNode s (route22 route While) (削除ここまで)
  785	(削除) ... (削除ここまで)
  786	(削除) route12 route con f = append route (decomp2 con f return) (削除ここまで)
  787	(削除) route22 route con f = append route (decomp2 con return f) (削除ここまで)
  788	(削除) (削除ここまで)
  789	(削除) decomp2 :: Monad m => (削除ここまで)
  790	(削除) (a0 -> a1 -> a) -> (a0 -> m a0) -> (a1 -> m a1) -> a -> m a (削除ここまで)
  791	(削除) \end{lstlisting} (削除ここまで)
  792	(削除) \end{frame} (削除ここまで)
  793	(削除) %The types of route12 and route22 (TODO might be worth having on a spare slide): (削除ここまで)
  794	(削除) %route12 :: (Monad m, Typeable a0, Typeable a1, Data a) => (削除ここまで)
  795	(削除) % ((a -> m a) -> (Root -> m Root)) -> (a0 -> a1 -> a) -> ((a0 -> m a0) -> (Root -> m root)) (削除ここまで)
  796	(削除) %route22 :: (Monad m, Typeable a0, Typeable a1, Data a) => (削除ここまで)
  797	(削除) % ((a -> m a) -> (Root -> m Root)) -> (a0 -> a1 -> a) -> ((a1 -> m a1) -> (Root -> m root)) (削除ここまで)
  798	(削除) (削除ここまで)
  799	(削除) \subsection{Usage checking} (削除ここまで)
  800	(削除) (削除ここまで)
  801	(削除) \begin{frame}[fragile] (削除ここまで)
  802	(削除) \frametitle{Usage checking} (削除ここまで)
  803	(削除) \begin{itemize} (削除ここまで)
  804	(削除) \item Detect parallel usage of objects (削除ここまで)
  805	(削除) \item Use generics to label CFG nodes with variables read/written to (削除ここまで)
  806	(削除) \end{itemize} (削除ここまで)
  807	(削除) \begin{lstlisting} (削除ここまで)
  808	(削除) type UsedVars = ([String], [String]) -- written, read (削除ここまで)
  809	(削除) (削除ここまで)
  810	(削除) getUsedVars (Assign _ (VarList lhvs) rhs) (削除ここまで)
  811	(削除) = (lhvs, map getJustVar (listify isJustVar rhs)) (削除ここまで)
  812	(削除) (削除ここまで)
  813	(削除) getJustVar (JustVar v) = v (削除ここまで)
  814	(削除) isJustVar (JustVar _) = True (削除ここまで)
  815	(削除) isJustVar _ = False (削除ここまで)
  816	(削除) \end{lstlisting} (削除ここまで)
  817	(削除) %FIXME: "The code snippet is short, but I worry that it is not very (削除ここまで)
  818	(削除) %understandable" (削除ここまで)
  819	(削除) \end{frame} (削除ここまで)
  820	(削除) (削除ここまで)
  821	(削除) \begin{frame} (削除ここまで)
  822	(削除) \frametitle{Usage checking} (削除ここまで)
  823	(削除) \begin{itemize} (削除ここまで)
  824	(削除) \item As in other occam compilers, array indexing makes usage checking hard (削除ここまで)
  825	(削除) \item For now, this problem has been skipped (削除ここまで)
  826	(削除) \end{itemize} (削除ここまで)
  827	(削除) \end{frame} (削除ここまで)
  828	(削除) (削除ここまで)
  829	(削除) %FIXME: multipass checking (削除ここまで)
  830	(削除) %FIXME: flesh out this section (削除ここまで)
  831	(削除) %}}} (削除ここまで)
  832	(削除) (削除ここまで)
  833	(削除) %{{{ parsing (削除ここまで)
  834	(削除) \section{Parsing} (削除ここまで)
  835	(削除) (削除ここまで)
  836	(削除) \begin{frame}[fragile] (削除ここまで)
  837	(削除) \frametitle{Parsec} (削除ここまで)
  838	(削除) \begin{itemize} (削除ここまで)
  839	(削除) \item Combinator-based parsing library (削除ここまで)
  840	(削除) \begin{itemize} (削除ここまで)
  841	(削除) \item Parser monad (削除ここまで)
  842	(削除) \item Productions are monadic operations that return the thing they parsed (削除ここまで)
  843	(削除) \begin{itemize} (削除ここまで)
  844	(削除) \item \lstinline|reserved :: String -> Parser String| (削除ここまで)
  845	(削除) \end{itemize} (削除ここまで)
  846	(削除) \item Operators combine productions into bigger productions (削除ここまで)
  847	(削除) \begin{itemize} (削除ここまで)
  848	(削除) \item \lstinline$<|> :: Parser a -> Parser a -> Parser a -- choice$ (削除ここまで)
  849	(削除) \end{itemize} (削除ここまで)
  850	(削除) \end{itemize} (削除ここまで)
  851	(削除) \end{itemize} (削除ここまで)
  852	(削除) \end{frame} (削除ここまで)
  853	(削除) (削除ここまで)
  854	(削除) \begin{frame} (削除ここまで)
  855	(削除) \frametitle{What makes Parsec cool} (削除ここまで)
  856	(削除) \begin{itemize} (削除ここまで)
  857	(削除) \item Does Prolog-style backtracking (削除ここまで)
  858	(削除) \begin{itemize} (削除ここまで)
  859	(削除) \item No lookahead needed (削除ここまで)
  860	(削除) \item \lstinline|try| lets you decide when to commit to a particular branch (like Prolog cut) (削除ここまで)
  861	(削除) \end{itemize} (削除ここまで)
  862	(削除) \item Can pass state around for awkward languages (削除ここまで)
  863	(削除) \begin{itemize} (削除ここまで)
  864	(削除) \item occam parser uses this to track types of symbols (削除ここまで)
  865	(削除) \begin{itemize} (削除ここまで)
  866	(削除) \item e.g. "expected integer constant" (削除ここまで)
  867	(削除) \end{itemize} (削除ここまで)
  868	(削除) \item But we probably want to avoid this in the future (削除ここまで)
  869	(削除) \end{itemize} (削除ここまで)
  870	(削除) \end{itemize} (削除ここまで)
  871	(削除) \end{frame} (削除ここまで)
  872	(削除) (削除ここまで)
  873	(削除) \begin{frame}[fragile] (削除ここまで)
  874	(削除) \frametitle{What makes Parsec \emph{really} cool} (削除ここまで)
  875	(削除) \begin{itemize} (削除ここまで)
  876	(削除) \item Productions are more-or-less BNF with Haskell syntax (削除ここまで)
  877	(削除) \end{itemize} (削除ここまで)
  878	(削除) \begin{lstlisting} (削除ここまで)
  879	(削除) statement (削除ここまで)
  880	(削除) = while <|> communication <|> assignment (削除ここまで)
  881	(削除) (削除ここまで)
  882	(削除) while (削除ここまで)
  883	(削除) = do reserved "while" (削除ここまで)
  884	(削除) reserved "(" (削除ここまで)
  885	(削除) e <- expression (削除ここまで)
  886	(削除) reserved ")" (削除ここまで)
  887	(削除) s <- statement (削除ここまで)
  888	(削除) return (While e s) (削除ここまで)
  889	(削除) \end{lstlisting} (削除ここまで)
  890	(削除) \end{frame} (削除ここまで)
  891	(削除) (削除ここまで)
  892	(削除) \begin{frame} (削除ここまで)
  893	(削除) \frametitle{Nanopass parsing} (削除ここまで)
  894	(削除) \begin{itemize} (削除ここまで)
  895	(削除) \item Our frontends are nanopass-based too (削除ここまで)
  896	(削除) \item For occam: (削除ここまで)
  897	(削除) \begin{itemize} (削除ここまで)
  898	(削除) \item Preprocess (削除ここまで)
  899	(削除) \item Tokenise (based on Alex) (削除ここまで)
  900	(削除) \item Join continuation lines (削除ここまで)
  901	(削除) \item Convert indentation to markers (削除ここまで)
  902	(削除) \item Parse (削除ここまで)
  903	(削除) \item Resolve grammar ambiguities (削除ここまで)
  904	(削除) \end{itemize} (削除ここまで)
  905	(削除) \item Can use QuickCheck to generate test code (削除ここまで)
  906	(削除) \end{itemize} (削除ここまで)
  907	(削除) \end{frame} (削除ここまで)
  908	(削除) %}}} (削除ここまで)
  909	(削除) (削除ここまで)
  910	(削除) %{{{ backends (削除ここまで)
  911	(削除) \section{Backends} (削除ここまで)
  912	(削除) (削除ここまで)
  913	(削除) \begin{frame} (削除ここまで)
  914	(削除) \frametitle{Why compile to C/C++?} (削除ここまで)
  915	(削除) \begin{itemize} (削除ここまで)
  916	(削除) \item Going via bytecode throws away a lot of useful information for optimisation (削除ここまで)
  917	(削除) \item Want to support multiple platforms (削除ここまで)
  918	(削除) \begin{itemize} (削除ここまで)
  919	(削除) \item IA32, x86-64, PowerPC, Cell, ARM\ldots (削除ここまで)
  920	(削除) \item Writing code generators is boring! (削除ここまで)
  921	(削除) \end{itemize} (削除ここまで)
  922	(削除) \item Existing compilers are very mature and generate good code (削除ここまで)
  923	(削除) \end{itemize} (削除ここまで)
  924	(削除) \end{frame} (削除ここまで)
  925	(削除) (削除ここまで)
  926	(削除) \begin{frame} (削除ここまで)
  927	(削除) \frametitle{Generating code} (削除ここまで)
  928	(削除) \begin{itemize} (削除ここまで)
  929	(削除) \item Generate idiomatic code -- as a human would (削除ここまで)
  930	(削除) \begin{itemize} (削除ここまで)
  931	(削除) \item That's what compilers are designed to handle (削除ここまで)
  932	(削除) \end{itemize} (削除ここまで)
  933	(削除) \item For C, use CCSP via the CIF interface (削除ここまで)
  934	(削除) \item For C++, use C++CSP (削除ここまで)
  935	(削除) \item Result: Tock's output is \emph{8x faster} than tranx86's for numeric code (削除ここまで)
  936	(削除) \end{itemize} (削除ここまで)
  937	(削除) \end{frame} (削除ここまで)
  938	(削除) (削除ここまで)
  939	(削除) \begin{frame} (削除ここまで)
  940	(削除) \frametitle{Sharing backend code} (削除ここまで)
  941	(削除) \begin{itemize} (削除ここまで)
  942	(削除) \item C and C++ structure is very similar (削除ここまで)
  943	(削除) \item Share functions for common constructs (削除ここまで)
  944	(削除) \begin{itemize} (削除ここまで)
  945	(削除) \item Must support recursion (削除ここまで)
  946	(削除) \begin{itemize} (削除ここまで)
  947	(削除) \item \lstinline|genWhile| calls (削除ここまで)
  948	(削除) \lstinline|genProcess|, which calls (削除ここまで)
  949	(削除) \lstinline|cppGenCall| (削除ここまで)
  950	(削除) \end{itemize} (削除ここまで)
  951	(削除) \item Use "virtual function tables" (削除ここまで)
  952	(削除) \begin{itemize} (削除ここまで)
  953	(削除) \item We're not reinventing OO, honest (削除ここまで)
  954	(削除) \end{itemize} (削除ここまで)
  955	(削除) \item Can override functions with stubs for unit testing (削除ここまで)
  956	(削除) \end{itemize} (削除ここまで)
  957	(削除) \end{itemize} (削除ここまで)
  958	(削除) \end{frame} (削除ここまで)
  959	(削除) (削除ここまで)
  960	(削除) \begin{frame}[fragile] (削除ここまで)
  961	(削除) \frametitle{Sharing backend code} (削除ここまで)
  962	(削除) \begin{lstlisting} (削除ここまで)
  963	(削除) type GenOps = GenOps { ... (削除ここまで)
  964	(削除) genWhile :: GenOps -> Expression -> Statement -> CodeGenM (), (削除ここまで)
  965	(削除) genExpression :: GenOps -> Expression -> CodeGenM (), (削除ここまで)
  966	(削除) genStatement :: GenOps -> Statement -> CodeGenM (), (削除ここまで)
  967	(削除) ... (削除ここまで)
  968	(削除) } (削除ここまで)
  969	(削除) (削除ここまで)
  970	(削除) genWhileC :: GenOps -> Expression -> Statement -> CodeGenM () (削除ここまで)
  971	(削除) genWhileC ops exp body (削除ここまで)
  972	(削除) = do tell ["while("] (削除ここまで)
  973	(削除) genExpression ops ops exp (削除ここまで)
  974	(削除) tell [")"] (削除ここまで)
  975	(削除) genStatement ops ops body (削除ここまで)
  976	(削除) \end{lstlisting} (削除ここまで)
  977	(削除) \end{frame} (削除ここまで)
  978	(削除) (削除ここまで)
  979	(削除) \begin{frame}[fragile] (削除ここまで)
  980	(削除) \frametitle{Testing backend code} (削除ここまで)
  981	(削除) \begin{lstlisting} (削除ここまで)
  982	(削除) -- genWhile :: GenOps -> Expression -> Statement -> CodeGenM () (削除ここまで)
  983	(削除) -- genExpression :: GenOps -> Expression -> CodeGenM () (削除ここまで)
  984	(削除) -- genStatement :: GenOps -> Statement -> CodeGenM () (削除ここまで)
  985	(削除) (削除ここまで)
  986	(削除) testgenWhile (削除ここまで)
  987	(削除) = assertEqual "testgenWhile" (削除ここまで)
  988	(削除) "while(@@@)###" (削除ここまで)
  989	(削除) (runCodeGen (genWhileC whileOps undefined undefined)) (削除ここまで)
  990	(削除) where (削除ここまで)
  991	(削除) whileOps = GenOps { genExpression = (\_ _ -> tell ["@@@"]), (削除ここまで)
  992	(削除) genStatement = (\_ _ -> tell ["###"]) } (削除ここまで)
  993	(削除) \end{lstlisting} (削除ここまで)
  994	(削除) Using \lstinline|undefined| saves constructing a value, \\ (削除ここまで)
  995	(削除) and makes sure it's not evaluated! (削除ここまで)
  996	(削除) \end{frame} (削除ここまで)
  997	(削除) (削除ここまで)
  998	(削除) \begin{frame} (削除ここまで)
  999	(削除) \frametitle{Stack allocation} (削除ここまで)
  1000	(削除) \begin{itemize} (削除ここまで)
  1001	(削除) \item When starting a process, must allocate stack for it (削除ここまで)
  1002	(削除) \item But how much? (削除ここまで)
  1003	(削除) \begin{itemize} (削除ここまで)
  1004	(削除) \item Can't tell directly, because we're not doing the code generation (削除ここまで)
  1005	(削除) \item Could use a size that's ``always big enough'' -- but that's inefficient (削除ここまで)
  1006	(削除) \begin{itemize} (削除ここまで)
  1007	(削除) \item C++CSP has to do this (削除ここまで)
  1008	(削除) \end{itemize} (削除ここまで)
  1009	(削除) \end{itemize} (削除ここまで)
  1010	(削除) \end{itemize} (削除ここまで)
  1011	(削除) \end{frame} (削除ここまで)
  1012	(削除) (削除ここまで)
  1013	(削除) \begin{frame} (削除ここまで)
  1014	(削除) \frametitle{Stack usage analysis} (削除ここまで)
  1015	(削除) \begin{itemize} (削除ここまで)
  1016	(削除) \item Run the C/C++ compiler, then analyse the generated assembler code (削除ここまで)
  1017	(削除) \begin{itemize} (削除ここまで)
  1018	(削除) \item Look for stack adjustment instructions (削除ここまで)
  1019	(削除) \item Compute an upper bound per function (削除ここまで)
  1020	(削除) \item Relink the program with the computed sizes inserted (削除ここまで)
  1021	(削除) \end{itemize} (削除ここまで)
  1022	(削除) \item Some things are hard to analyse (削除ここまで)
  1023	(削除) \begin{itemize} (削除ここまで)
  1024	(削除) \item Recursion, alloca, exceptions, virtual functions\ldots (削除ここまで)
  1025	(削除) \item But we can control when we generate these (or (削除ここまで)
  1026	(削除) avoid them entirely) (削除ここまで)
  1027	(削除) \end{itemize} (削除ここまで)
  1028	(削除) \end{itemize} (削除ここまで)
  1029	(削除) \end{frame} (削除ここまで)
  1030	(削除) %}}} (削除ここまで)
  1031	(削除) (削除ここまで)
  1032	(削除) %{{{ language features (削除ここまで)
  1033	(削除) \section{occam language features} (削除ここまで)
  1034	(削除) (削除ここまで)
  1035	(削除) \occamsettings (削除ここまで)
  1036	(削除) (削除ここまで)
  1037	(削除) \begin{frame} (削除ここまで)
  1038	(削除) \frametitle{What makes occam interesting to compile} (削除ここまで)
  1039	(削除) \begin{itemize} (削除ここまで)
  1040	(削除) \item Parallelism! (削除ここまで)
  1041	(削除) \item Indentation-based syntax (削除ここまで)
  1042	(削除) \item Parser needs lots of lookahead (削除ここまで)
  1043	(削除) \item Compile-time usage checks (削除ここまで)
  1044	(削除) \begin{itemize} (削除ここまで)
  1045	(削除) \item Parallel safety (削除ここまで)
  1046	(削除) \item Definedness (削除ここまで)
  1047	(削除) \end{itemize} (削除ここまで)
  1048	(削除) \item Abbreviations (削除ここまで)
  1049	(削除) \end{itemize} (削除ここまで)
  1050	(削除) \end{frame} (削除ここまで)
  1051	(削除) (削除ここまで)
  1052	(削除) \begin{frame} (削除ここまで)
  1053	(削除) \frametitle{Runtime checks} (削除ここまで)
  1054	(削除) \begin{itemize} (削除ここまで)
  1055	(削除) \item Various things are checked at runtime in occam (削除ここまで)
  1056	(削除) \begin{itemize} (削除ここまで)
  1057	(削除) \item Over/underflow on arithmetic operations (削除ここまで)
  1058	(削除) \item Array bounds (削除ここまで)
  1059	(削除) \item Data type conversions (e.g. INT32 $\rightarrow$ INT16) (削除ここまで)
  1060	(削除) \end{itemize} (削除ここまで)
  1061	(削除) \item Can compile out these checks when statically proven safe (削除ここまで)
  1062	(削除) \end{itemize} (削除ここまで)
  1063	(削除) \end{frame} (削除ここまで)
  1064	(削除) (削除ここまで)
  1065	(削除) \begin{frame}[fragile] (削除ここまで)
  1066	(削除) \frametitle{Abbreviations} (削除ここまで)
  1067	(削除) \begin{itemize} (削除ここまで)
  1068	(削除) \item occam doesn't have pointers (削除ここまで)
  1069	(削除) \item Instead, it has a very powerful reference (``abbreviation'') system (削除ここまで)
  1070	(削除) \end{itemize} (削除ここまで)
  1071	(削除) \begin{lstlisting} (削除ここまで)
  1072	(削除) INT x: -- declares variable (削除ここまで)
  1073	(削除) INT y IS x: -- declares reference to variable (削除ここまで)
  1074	(削除) VAL INT y2 IS y: (削除ここまで)
  1075	(削除) -- declares read-only reference to variable (削除ここまで)
  1076	(削除) (削除ここまで)
  1077	(削除) PROC foo (INT z) -- procedure that takes a reference (削除ここまで)
  1078	(削除) z := 42 (削除ここまで)
  1079	(削除) : (削除ここまで)
  1080	(削除) \end{lstlisting} (削除ここまで)
  1081	(削除) \end{frame} (削除ここまで)
  1082	(削除) (削除ここまで)
  1083	(削除) \begin{frame}[fragile] (削除ここまで)
  1084	(削除) \frametitle{Array abbreviations} (削除ここまで)
  1085	(削除) \begin{itemize} (削除ここまで)
  1086	(削除) \item occam's arrays have some interesting features (削除ここまで)
  1087	(削除) \begin{itemize} (削除ここまで)
  1088	(削除) \item slicing (削除ここまで)
  1089	(削除) \item compile-time and run-time bounds checks (削除ここまで)
  1090	(削除) \end{itemize} (削除ここまで)
  1091	(削除) \end{itemize} (削除ここまで)
  1092	(削除) \begin{lstlisting} (削除ここまで)
  1093	(削除) [10]INT xs: -- declares an array (削除ここまで)
  1094	(削除) SEQ (削除ここまで)
  1095	(削除) xs[15] := 42 -- would fail at compile time (削除ここまで)
  1096	(削除) xs[n] := 42 -- would fail at runtime if n >= 10 (削除ここまで)
  1097	(削除) (削除ここまで)
  1098	(削除) n := SIZE xs -- get size of the array (削除ここまで)
  1099	(削除) (削除ここまで)
  1100	(削除) INT y IS xs[4]: -- abbreviate a member of the array (削除ここまで)
  1101	(削除) y := 42 (削除ここまで)
  1102	(削除) (削除ここまで)
  1103	(削除) [4]INT ys IS [xs FROM 4 FOR 5]: (削除ここまで)
  1104	(削除) -- abbreviate a slice of the array (削除ここまで)
  1105	(削除) ys[2] := 42 (削除ここまで)
  1106	(削除) \end{lstlisting} (削除ここまで)
  1107	(削除) \end{frame} (削除ここまで)
  1108	(削除) (削除ここまで)
  1109	(削除) \begin{frame} (削除ここまで)
  1110	(削除) \frametitle{Implementing arrays} (削除ここまで)
  1111	(削除) \begin{itemize} (削除ここまで)
  1112	(削除) \item In C\ldots (削除ここまで)
  1113	(削除) \begin{itemize} (削除ここまで)
  1114	(削除) \item Pointer for data (削除ここまで)
  1115	(削除) \item Array of sizes (one for each dimension) (削除ここまで)
  1116	(削除) \item Insert bounds checks into C code that accesses arrays (削除ここまで)
  1117	(削除) \end{itemize} (削除ここまで)
  1118	(削除) \item In C++\ldots (削除ここまで)
  1119	(削除) \begin{itemize} (削除ここまで)
  1120	(削除) \item Can't just use the STL vector class -- no slicing! (削除ここまで)
  1121	(削除) \item Wrote our own class to provide the occam array semantics (削除ここまで)
  1122	(削除) \end{itemize} (削除ここまで)
  1123	(削除) \end{itemize} (削除ここまで)
  1124	(削除) \end{frame} (削除ここまで)
  1125	(削除) (削除ここまで)
  1126	(削除) \begin{frame}[fragile] (削除ここまで)
  1127	(削除) \frametitle{Retyping} (削除ここまで)
  1128	(削除) \begin{lstlisting} (削除ここまで)
  1129	(削除) INT32 i: (削除ここまで)
  1130	(削除) [4]BYTE bs RETYPES i: (削除ここまで)
  1131	(削除) \end{lstlisting} (削除ここまで)
  1132	(削除) \begin{itemize} (削除ここまで)
  1133	(削除) \item Data retyping (削除ここまで)
  1134	(削除) \begin{itemize} (削除ここまで)
  1135	(削除) \item Reinterprets data as a different type (削除ここまで)
  1136	(削除) \item Like a C pointer cast, but with safety checks (削除ここまで)
  1137	(削除) \item Straightforward for C or C++\ldots (削除ここまで)
  1138	(削除) \end{itemize} (削除ここまで)
  1139	(削除) \item Arrays can be reshaped (削除ここまで)
  1140	(削除) \end{itemize} (削除ここまで)
  1141	(削除) \begin{lstlisting} (削除ここまで)
  1142	(削除) [4][3]INT xs: (削除ここまで)
  1143	(削除) [2][6]INT ys RESHAPES xs: (削除ここまで)
  1144	(削除) \end{lstlisting} (削除ここまで)
  1145	(削除) \begin{itemize} (削除ここまで)
  1146	(削除) \item Channels can also be retyped (削除ここまで)
  1147	(削除) \begin{itemize} (削除ここまで)
  1148	(削除) \item Very awkward for the C++CSP backend (削除ここまで)
  1149	(削除) \item Can't use templated channels\ldots (削除ここまで)
  1150	(削除) \end{itemize} (削除ここまで)
  1151	(削除) \end{itemize} (削除ここまで)
  1152	(削除) \end{frame} (削除ここまで)
  1153	(削除) (削除ここまで)
  1154	(削除) \begin{frame} (削除ここまで)
  1155	(削除) \frametitle{Mobile data} (削除ここまで)
  1156	(削除) \begin{itemize} (削除ここまで)
  1157	(削除) \item A \emph{mobile} is a reference to a piece of data (削除ここまで)
  1158	(削除) \begin{itemize} (削除ここまで)
  1159	(削除) \item Only one process can use any particular mobile (削除ここまで)
  1160	(削除) \item \ldots but ownership can be transferred -- e.g. by (削除ここまで)
  1161	(削除) sending the mobile down a channel (削除ここまで)
  1162	(削除) \end{itemize} (削除ここまで)
  1163	(削除) \item Not just a pointer (削除ここまで)
  1164	(削除) \begin{itemize} (削除ここまで)
  1165	(削除) \item Requires either reference counting or garbage collection (削除ここまで)
  1166	(削除) \end{itemize} (削除ここまで)
  1167	(削除) \end{itemize} (削除ここまで)
  1168	(削除) \end{frame} (削除ここまで)
  1169	(削除) (削除ここまで)
  1170	(削除) \haskellsettings (削除ここまで)
  1171	(削除) (削除ここまで)
  1172	(削除) %}}} (削除ここまで)
  1173	(削除) (削除ここまで)
  1174	(削除) %{{{ reflections (削除ここまで)
  1175	(削除) \section{Reflections} (削除ここまで)
  1176	(削除) (削除ここまで)
  1177	(削除) \subsection{How we use Haskell} (削除ここまで)
  1178	(削除) (削除ここまで)
  1179	(削除) \begin{frame} (削除ここまで)
  1180	(削除) \frametitle{How're you gonna get your day's work done?} (削除ここまで)
  1181	(削除) % OK, nobody is going to get the reference... (削除ここまで)
  1182	(削除) \begin{itemize} (削除ここまで)
  1183	(削除) \item Laziness isn't very useful (削除ここまで)
  1184	(削除) \begin{itemize} (削除ここまで)
  1185	(削除) \item Nothing uses infinite data structures (削除ここまで)
  1186	(削除) \item Really want strict evaluation in most places (削除ここまで)
  1187	(削除) \begin{itemize} (削除ここまで)
  1188	(削除) \item Force errors sooner! (削除ここまで)
  1189	(削除) \end{itemize} (削除ここまで)
  1190	(削除) \item Except: some utility in using ``undefined'' when testing (削除ここまで)
  1191	(削除) \end{itemize} (削除ここまで)
  1192	(削除) \end{itemize} (削除ここまで)
  1193	(削除) \end{frame} (削除ここまで)
  1194	(削除) (削除ここまで)
  1195	(削除) \begin{frame}[fragile] (削除ここまで)
  1196	(削除) \frametitle{Monads in disguise} (削除ここまで)
  1197	(削除) \begin{itemize} (削除ここまで)
  1198	(削除) \item Tock is a \emph{practical} system, therefore\ldots (削除ここまで)
  1199	(削除) \item Monads, monads, monads (削除ここまで)
  1200	(削除) \item Not a lot of pure functional code (削除ここまで)
  1201	(削除) \item Heavy use of monad transformers (削除ここまで)
  1202	(削除) \end{itemize} (削除ここまで)
  1203	(削除) \begin{lstlisting} (削除ここまで)
  1204	(削除) type PassM = ErrorT ErrorReport (StateT CompilerState IO) (削除ここまで)
  1205	(削除) type CodeGenM = WriterT [String] PassM (削除ここまで)
  1206	(削除) \end{lstlisting} (削除ここまで)
  1207	(削除) \end{frame} (削除ここまで)
  1208	(削除) (削除ここまで)
  1209	(削除) \begin{frame} (削除ここまで)
  1210	(削除) \frametitle{A fistful of dollars} (削除ここまで)
  1211	(削除) \begin{itemize} (削除ここまで)
  1212	(削除) \item Use the \lstinline|$| operator to avoid nested brackets (削除ここまで)
  1213	(削除) \begin{itemize} (削除ここまで)
  1214	(削除) \item \lstinline|liftIO $ putStr $ "quux is " ++ (fmt $ get quux)| (削除ここまで)
  1215	(削除) \item Adam got this from John Meacham's code\ldots (削除ここまで)
  1216	(削除) \end{itemize} (削除ここまで)
  1217	(削除) \item Define some helper operators for common tasks (削除ここまで)
  1218	(削除) \begin{itemize} (削除ここまで)
  1219	(削除) \item e.g. applying a pure function to the result of a monadic (削除ここまで)
  1220	(削除) operation \\ (削除ここまで)
  1221	(削除) \lstinline|(>>*) :: m a -> (a -> b) -> m b| \\ (削除ここまで)
  1222	(削除) \lstinline|v <- getFoo >>* fromMaybe| (削除ここまで)
  1223	(削除) \end{itemize} (削除ここまで)
  1224	(削除) \end{itemize} (削除ここまで)
  1225	(削除) \end{frame} (削除ここまで)
  1226	(削除) (削除ここまで)
  1227	(削除) %FIXME: slide on the GHC extensions we use? (削除ここまで)
  1228	(削除) (削除ここまで)
  1229	(削除) \subsection{Haskell frustrations} (削除ここまで)
  1230	(削除) (削除ここまで)
  1231	(削除) \begin{frame} (削除ここまで)
  1232	(削除) \frametitle{Debugging is hard} (削除ここまで)
  1233	(削除) \begin{itemize} (削除ここまで)
  1234	(削除) \item Tracing does not generally do what you expect (owing to laziness) (削除ここまで)
  1235	(削除) \item Existing tools often have limitations that make them unworkable with Tock code (削除ここまで)
  1236	(削除) \begin{itemize} (削除ここまで)
  1237	(削除) \item e.g. no GHC extensions, no higher-order types, \ldots (削除ここまで)
  1238	(削除) \end{itemize} (削除ここまで)
  1239	(削除) \item Unit tests do help to narrow down problems (削除ここまで)
  1240	(削除) \item We often resort to printf debugging (that's why (削除ここまで)
  1241	(削除) \lstinline|IO| is in \lstinline|PassM|) (削除ここまで)
  1242	(削除) \end{itemize} (削除ここまで)
  1243	(削除) %FIXME: example of a nasty type error with solution? (削除ここまで)
  1244	(削除) \end{frame} (削除ここまで)
  1245	(削除) (削除ここまで)
  1246	(削除) \begin{frame} (削除ここまで)
  1247	(削除) \frametitle{Deciphering type errors} (削除ここまで)
  1248	(削除) \begin{itemize} (削除ここまで)
  1249	(削除) \item GHC's errors are usually enormous and hard to understand (削除ここまで)
  1250	(削除) \begin{itemize} (削除ここまで)
  1251	(削除) \item The line number is usually the most useful bit! (削除ここまで)
  1252	(削除) \end{itemize} (削除ここまで)
  1253	(削除) \item Sometimes GHC can infer the right type, but a human can't~ (削除ここまで)
  1254	(削除) \begin{itemize} (削除ここまで)
  1255	(削除) \item Would be nice to be able to ask GHCI about (削除ここまで)
  1256	(削除) definitions in \lstinline|where| clauses\ldots (削除ここまで)
  1257	(削除) \end{itemize} (削除ここまで)
  1258	(削除) \item We often resort to trial and error (削除ここまで)
  1259	(削除) \end{itemize} (削除ここまで)
  1260	(削除) \end{frame} (削除ここまで)
  1261	(削除) (削除ここまで)
  1262	(削除) \begin{frame} (削除ここまで)
  1263	(削除) \frametitle{Going in circles} (削除ここまで)
  1264	(削除) \begin{itemize} (削除ここまで)
  1265	(削除) \item Haskell disallows mutually recursive modules (削除ここまで)
  1266	(削除) \begin{itemize} (削除ここまで)
  1267	(削除) \item \lstinline|A.foo| calls \lstinline|B.bar|, which (削除ここまで)
  1268	(削除) calls \lstinline|A.baz| (削除ここまで)
  1269	(削除) \end{itemize} (削除ここまで)
  1270	(削除) \item But we want to do this quite often (削除ここまで)
  1271	(削除) \begin{itemize} (削除ここまで)
  1272	(削除) \item e.g. evaluating constant expressions (削除ここまで)
  1273	(削除) \end{itemize} (削除ここまで)
  1274	(削除) \item Some awkward code organisation at the moment\ldots (削除ここまで)
  1275	(削除) \end{itemize} (削除ここまで)
  1276	(削除) \end{frame} (削除ここまで)
  1277	(削除) (削除ここまで)
  1278	(削除) \begin{frame} (削除ここまで)
  1279	(削除) \frametitle{A pain in the monads} (削除ここまで)
  1280	(削除) \begin{itemize} (削除ここまで)
  1281	(削除) \item Monad transformers aren't available for all monads (削除ここまで)
  1282	(削除) \begin{itemize} (削除ここまで)
  1283	(削除) \item e.g. Parsec, QuickCheck (削除ここまで)
  1284	(削除) \item You can't have a parser or test that does IO (safely!) (削除ここまで)
  1285	(削除) \end{itemize} (削除ここまで)
  1286	(削除) \item Monad transformer typeclass instances (e.g. \lstinline|MonadState|) aren't (削除ここまで)
  1287	(削除) derived automatically (削除ここまで)
  1288	(削除) \end{itemize} (削除ここまで)
  1289	(削除) \end{frame} (削除ここまで)
  1290	(削除) (削除ここまで)
  1291	673	\begin{frame}[fragile]
  1292	674	\frametitle{\dag~Insert generic swear-word here}

Note: See TracChangeset for help on using the changeset viewer.