Context Navigation


Ignore:
Timestamp:
Dec 5, 2007, 10:54:32 AM (18 years ago)
Author:
ats
Message:

Redo retyping and usage checking, add a slide on GHC extensions, and tweak a
few minor bits.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • docs/trunk/200711-tock-seminars/200711-B-tock-slides.tex

    r94 r95
    204204\begin{frame}[fragile]
    205205\frametitle{Retyping}
    206(追記) An unusually low-level feature\ldots (追記ここまで)
    206207\begin{lstlisting}
    207208INT32 i:
    208209[4]BYTE bs RETYPES i:
    209\end{lstlisting}
    210\begin{itemize}
    211 \item Data retyping
    212 \begin{itemize}
    213 \item Reinterprets data as a different type
    214 \item Like a C pointer cast, but with safety checks
    215 \item Straightforward for C or C++\ldots
    216 \end{itemize}
    217 \item Arrays can be reshaped
    218\end{itemize}
    219\begin{lstlisting}
    210
    220211[4][3]INT xs:
    221212[2][6]INT ys RESHAPES xs:
    222213\end{lstlisting}
    223214\begin{itemize}
    215(追記) \item Reinterprets data as a different type (追記ここまで)
    216(追記) \item Like a C pointer cast, but with safety checks (追記ここまで)
    217(追記) \item Straightforward for C or C++\ldots (追記ここまで)
    218(追記) \item Arrays can be reshaped (追記ここまで)
    219(追記) \end{itemize} (追記ここまで)
    220(追記) \end{frame} (追記ここまで)
    221(追記) (追記ここまで)
    222(追記) \begin{frame}[fragile] (追記ここまで)
    223(追記) \frametitle{More retyping} (追記ここまで)
    224(追記) \begin{lstlisting} (追記ここまで)
    225(追記) CHAN INT ci: (追記ここまで)
    226(追記) CHAN [4]BYTE cb RETYPES ci: (追記ここまで)
    227(追記) \end{lstlisting} (追記ここまで)
    228(追記) \begin{itemize} (追記ここまで)
    224229 \item Channels can also be retyped
    225230 \begin{itemize}
    226 \item Very awkward for the C++CSP backend(削除) (削除ここまで)
    227 \item Can't use templated channels(削除) \ldots (削除ここまで)
    228 \end{itemize}(削除) (削除ここまで)
    229 %TODO: Maybe put this on its own slide
    230\end{(削除) itemiz (削除ここまで)e}
    231\end{frame}
    232
    233\(削除) begin{frame (削除ここまで)}
    234\(削除) frametitle{Mobile data (削除ここまで)}
    235\begin{itemize}
    236 \item (削除) A \emph{mobile} is a reference to a piece of data (削除ここまで)
    231 \item Very awkward for the C++CSP backend(追記) ! (追記ここまで)
    232 \item Can't use templated channels(追記) (追記ここまで)
    233 \end{itemize}(追記) (追記ここまで)
    234\end{itemize}
    235\end{(追記) fram (追記ここまで)e}
    236
    237\begin{frame}
    238\(追記) frametitle{Mobiles (追記ここまで)}
    239\(追記) begin{itemize (追記ここまで)}
    240 \item A \emph{mobile} is a safe reference
    241 \item (追記) Regular mobiles (追記ここまで)
    237242 \begin{itemize}
    238243 \item Only one process can use any particular mobile
    239244 \item \ldots but ownership can be transferred -- e.g. by
    240245 sending the mobile down a channel
    241 \end{itemize}
    242 \item Not just a pointer
    243 \begin{itemize}
    246 \item Can be smart about allocation -- recycling,
    247 relocating
    248 \end{itemize}
    249 \item Shared mobiles
    250 \begin{itemize}
    251 \item Protected by a lock
    244252 \item Requires either reference counting or garbage collection
    245253 \end{itemize}
    246(削除) %FIXME: Mobile data can just be a pointer; either re-title slide or remove last point (削除ここまで)
    247254\end{itemize}
    248255\end{frame}
    … …
    264271\begin{itemize}
    265272 \item Combinator-based parsing library
    266 \begin{itemize}
    267 \item Parser monad
    268 \item Productions are monadic operations that return the thing they parsed
    269 \begin{itemize}
    270 \item \lstinline|reserved :: String -> Parser String|
    271 \end{itemize}
    272 \item Operators combine productions into bigger productions
    273 \begin{itemize}
    274 \item \lstinline$<|> :: Parser a -> Parser a -> Parser a -- choice$
    275 \end{itemize}
    276 \end{itemize}
    277\end{itemize}
    273 \item Productions are monadic operations that return the thing they parsed
    274\end{itemize}
    275
    276\begin{lstlisting}
    277reserved :: String -> Parser String
    278reserved "CHAN" -- matches and returns "CHAN"
    279\end{lstlisting}
    280
    281\begin{itemize}
    282 \item Operators combine productions
    283\end{itemize}
    284
    285\begin{lstlisting}
    286dataType = reserved "INT" <|> reserved "BYTE"
    287channelType = reserved "CHAN" >> dataType
    288\end{lstlisting}
    278289\end{frame}
    279290
    … …
    429440\frametitle{$\sum \lambda_n = $Tedium}
    430441\begin{itemize}
    431 \item Writing it out (削除) long- (削除ここまで)hand is tiresome:
    442 \item Writing it out (追記) by (追記ここまで)hand is tiresome:
    432443\end{itemize}
    433444\begin{lstlisting}
    … …
    447458\begin{itemize}
    448459 \item First-class patterns would help here, again
    449 \item (削除) We turn to generics again (削除ここまで)
    460 \item (追記) Another use for generics (追記ここまで)
    450461\end{itemize}
    451462\begin{lstlisting}
    … …
    469480\subsection{Usage checking}
    470481
    471(削除) \begin{frame}[fragile] (削除ここまで)
    472(削除) \frametitle{Usage checking} (削除ここまで)
    473(削除) \begin{itemize} (削除ここまで)
    474(削除) \item Detect parallel usage of objects (削除ここまで)
    475(削除) \item Use generics to label CFG nodes with variables read/written to (削除ここまで)
    476(削除) \begin{itemize} (削除ここまで)
    477(削除) \item For example, getting all variables read in an expression (削除ここまで)
    478(削除) \end{itemize} (削除ここまで)
    479(削除) \end{itemize} (削除ここまで)
    480(削除) \begin{lstlisting} (削除ここまで)
    481(削除) getVariable :: Variable -> Bool (削除ここまで)
    482(削除) getVariable _ = True (削除ここまで)
    483(削除) (削除ここまで)
    484(削除) getAllVariables :: Expression -> [Variable] (削除ここまで)
    485(削除) getAllVariables = listify getVariable (削除ここまで)
    486(削除) \end{lstlisting} (削除ここまで)
    487(削除) \end{frame} (削除ここまで)
    488(削除) (削除ここまで)
    489482\occamsettings
    490483
    491484\begin{frame}
    492\frametitle{Usage checking}
    493\begin{itemize}
    494 \item As in other occam compilers, array indexing makes usage checking hard
    495 \begin{itemize}
    496 \item E.g. can we be sure \lstinline|xs[y]| is distinct from \lstinline|xs[z]| at compile-time?
    497 \end{itemize}
    498 \item For now, this problem has been skipped
    485\frametitle{Definedness checking}
    486\begin{itemize}
    487 \item Compiler must detect use of undefined objects
    488 \begin{itemize}
    489 \item e.g. using a mobile you've communicated away
    490 \end{itemize}
    491 \item Reasonably straightforward to do with the CFG
    492 \item Must be conservative -- if you can't tell it's safe, it
    493 isn't!
    494 \item Same type of analysis can be used for optimisations
    495 \begin{itemize}
    496 \item e.g. Rain's automatic demobilisation
    497 \end{itemize}
    498\end{itemize}
    499\end{frame}
    500
    501\begin{frame}[fragile]
    502\frametitle{Parallel usage checking}
    503\begin{itemize}
    504 \item Compiler must detect and disallow parallel usage of objects
    505 \item Annotate AST/CFG nodes with objects used
    506 \begin{itemize}
    507 \item e.g. "reads \lstinline|x|,
    508 writes \lstinline|y, z|"
    509 \end{itemize}
    510 \item Check for consistency at \lstinline|PAR| blocks
    511\end{itemize}
    512\end{frame}
    513
    514\begin{frame}[fragile]
    515\frametitle{But it's not that simple\ldots}
    516\begin{lstlisting}
    517[11]CHAN INT cs:
    518PAR i = 0 FOR 10
    519 pipeline.cell (cs[i]?, cs[i + 1]!)
    520\end{lstlisting}
    521\begin{itemize}
    522 \item Array elements can be indexed by an arbitrary expression
    523 \item Can't just reason about the whole array
    524 \item Need to prove that \lstinline|i| and \lstinline|i + 1|
    525 don't overlap, or that \lstinline|a[i]| is defined
    526 \begin{itemize}
    527 \item Existing compiler brute-forces it!
    528 \item Could use a proper solver (e.g. the Omega test)
    529 \item Could do simple pattern matching --
    530 \lstinline|(i + C) \ N| covers 99\% of cases
    531 \end{itemize}
    532 \item Again, must be conservative by default
    499533\end{itemize}
    500534\end{frame}
    501535
    502536\haskellsettings
    503(削除) (削除ここまで)
    504(削除) %FIXME: multipass checking (削除ここまで)
    505(削除) %FIXME: flesh out this section (削除ここまで)
    506537%}}}
    507538
    … …
    539570 \item For C, use CCSP via the CIF interface
    540571 \item For C++, use C++CSP
    541 \item Result: Tock's output is (削除) \emph{8x faster} (削除ここまで) than tranx86's for numeric code
    572 \item Result: Tock's output is (追記) $\approx8ドルx faster (追記ここまで) than tranx86's for numeric code
    542573\end{itemize}
    543574\end{frame}
    … …
    693724\end{frame}
    694725
    695%FIXME: slide on the GHC extensions we use?
    726\begin{frame}
    727\frametitle{Go Go Gadget Extensions!}
    728\begin{itemize}
    729 \item \lstinline|forall| -- functions to apply operators to
    730 numeric types in evaluator
    731 \item Undecidable instances -- typeclass synonyms
    732% TODO: any more?
    733\end{itemize}
    734\end{frame}
    696735
    697736\subsection{Haskell frustrations}
    … …
    703742 \item Existing tools often have limitations that make them unworkable with Tock code
    704743 \begin{itemize}
    705 \item e.g. no GHC extensions, no (削除) higher-order types, \ldot (削除ここまで)s
    744 \item e.g. no GHC extensions, no (追記) parametric/higher-order type (追記ここまで)s
    706745 \end{itemize}
    707746 \item Unit tests do help to narrow down problems
    … …
    709748 \lstinline|IO| is in \lstinline|PassM|)
    710749\end{itemize}
    711(削除) %FIXME: example of a nasty type error with solution? (削除ここまで)
    712750\end{frame}
    713751
    … …
    722760 \begin{itemize}
    723761 \item Would be nice to be able to ask GHCI about
    724 definitions in \lstinline|where| clauses(削除) \ldots (削除ここまで)
    762 definitions in \lstinline|where| clauses(追記) (追記ここまで)
    725763 \end{itemize}
    726764 \item We often resort to trial and error
    … …
    742780 \item e.g. evaluating constant expressions
    743781 \end{itemize}
    744 \item Some awkward code organisation at the moment\ldots
    782 \item (Yes, there's the hs-boot mechanism\ldots yuck!)
    783 \item Some of our modules are a bit arbitrary at the moment
    745784\end{itemize}
    746785\column{.3\textwidth}
Note: See TracChangeset for help on using the changeset viewer.

AltStyle によって変換されたページ (->オリジナル) /