123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471 |
- % Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>
- % This work is licensed under the Creative Commons Attribution-ShareAlike 4.0
- % International License. To view a copy of this license, visit
- % http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative
- % Commons, PO Box 1866, Mountain View, CA 94042, USA.
- \documentclass{beamer}
- \usepackage[utf8]{inputenc}
- \usecolortheme{seahorse}
- \usefonttheme{professionalfonts}
- \usepackage{fontspec}
- \setmainfont{DejaVu Sans}
- \setbeamertemplate{navigation symbols}{}
- \usepackage{caption}
- \usepackage[font=itshape, begintext=``, endtext='']{quoting}
- \title{Type parameterization}
- \subtitle{Or: reason \#213 why Java is terrible at everything}
- \titlegraphic{\includegraphics[scale=0.5]{logo.eps}}
- \author{Koz Ross}
- \date{4th May, 2017}
- \begin{document}
- \begin{frame}[c]
- \titlepage{}
- \end{frame}
- \begin{frame}[c]
- \frametitle{Outline}
- \tableofcontents
- \end{frame}
- \section{What is this, and why should I care?}
- \begin{frame}[fragile,c]
- \frametitle{Example 1}
- Consider the following function:\pause{}
-
- \bigskip
- \begin{verbatim}
- int add () {
- return 2 + 3;
- }
- \end{verbatim}\pause{}
- \bigskip
- This function is \alert{very} inflexible --- it might as well be a constant!
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Example 1}
- We can make the function more flexible (and thus, do more work) by {\em
- parameterizing\/} its arguments.\pause{} That way, the {\em user\/} can decide
- what numbers it gets to add instead of us:\pause{}
- \bigskip
- \begin{verbatim}
- int add (int x, int y) {
- return x + y;
- }
- \end{verbatim}\pause{}
- We call this {\em argument parameterization}, and it is a very useful thing
- to have (in fact, programming would be pretty pointless without it).\pause{}
- But then, what if our user wants to add two {\tt float}s instead?
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Example 2}
- Consider this (partial) definition of a (singly) linked list:\pause{}
- \begin{verbatim}
- struct node {
- int data;
- node* next;
- };
- struct list {
- node* first;
- };
- list* list_new ();
- \end{verbatim}\pause{}
- What if our user wanted a list of {\tt float}s instead?\pause{} Does it really
- matter for list operations what kind of data we're storing?
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{The problem}
- These are both examples of {\em type restrictions}.\pause{} Normally, these
- are a {\em good\/} thing, as we wouldn't want something like this to
- compile:\pause{}
- \begin{verbatim}
- /* this won't compile */
- sqrt("10");
- /* but will *run* in JavaScript, sigh... */
- \end{verbatim}\pause{}
- However, in our two examples, type restrictions get in our way.\pause{}
- Wouldn't it be nice if we could parameterize over {\em types\/} as well?
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{What would this look like?}
- \pause{}
- \begin{verbatim}
- struct node <T> {
- T data;
- node <T>* next;
- };
- struct list <T> {
- node <T>* first;
- };
- list <T>* list_new ();
- \end{verbatim}\pause{}
- So now, if the user wants a list of {\tt int}s, they will write
- \verb!list <int>* foo = list_new();!.\linebreak
- If they prefer a list of {\tt float}s, they can write
- \verb!list <float>* bar = list_new();!.
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Why do we care?}
- \pause{}
- \begin{itemize}
- \item Write the code for a list {\em once}, and it will be able to store
- anything a user could want.\pause{}
- \item Still have protection against things like this:
- \begin{verbatim}
- list <int>* foo = list_new();
- /* won't compile */
- list_insert(foo, "bar");
- \end{verbatim}\pause{}
- \item Can write very useful things:
- \begin{verbatim}
- struct pair <T,U> {
- T left;
- U right;
- }; /* a pair of anything! */
- \end{verbatim}
- \end{itemize}\pause{}
- \alert{In short:} Type parameterization makes our code more flexible, more
- concise, and generally better.
- \end{frame}
- \section{How do we implement this?}
- \begin{frame}[c,fragile]
- \frametitle{Some terminology}
- A {\em type parameter\/} is a placeholder type.\pause{} When we mention it in
- a definition (like a structure or a function), we call this a {\em
- declaration\/}:\pause{}
- \begin{verbatim}
- struct pair <T,U> { /* declaration */
- T left;
- U right;
- }
- \end{verbatim}\pause{}
- Later, when we actually use the structure of function, we have to provide an
- actual type for the type parameter ({\em instantiation\/}):\pause{}
- \begin{verbatim}
- pair <float, int> foo; /* instantiation */
- \end{verbatim}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Homogenous translation}
- \pause{}
- \begin{itemize}
- \item Type parameter {\em declarations\/} (and anything using them) get
- promoted to some specific type and compiled on the spot.\pause{}
- \item Type parameter {\em instantiations\/} are first checked for
- consistency; if no problems are found, their types are simply ignored
- where appropriate.\pause{}
- \end{itemize}
- Thus, at {\em runtime}, a \verb!pair <int, float>! is no different to
- a \verb!pair <float, char*>! --- might as well be
- \verb!pair <wtf, wtf>! for all we care.
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Heterogenous translation}
- \pause{}
- \begin{itemize}
- \item Type parameter {\em declarations\/} (and anything using them) get
- turned into a `template', with gaps where the type parameters should
- go. Nothing gets compiled yet.\pause{}
- \item When the compiler sees a type parameter {\em instantiation}, it
- copy-pastes the types into the template, compiles the result, and uses
- the result for all identical future cases.\pause{}
- \end{itemize}
- This, when the compiler sees \verb!pair<int, float>! for the first
- time, it will compile a special version for just those types; if it later sees
- \verb!pair<float, char*>!, it'll compile a special version for those
- types; and so on.
- \end{frame}
- \section{How good are these?}
- \begin{frame}[fragile,c]
- \frametitle{Tradeoffs for homogenous translation}
- \pause{}
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Simple:\pause{}
- \begin{itemize}
- \item Compiles faster\pause{}
- \item Simpler compiler logic\pause{}
- \end{itemize}
- \item Smaller binaries:\pause{}
- \begin{itemize}
- \item Less space required\pause{}
- \item Can use instruction cache effectively\pause{}
- \end{itemize}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item No type information at runtime\pause{}
- \item Indirection:\pause{}
- \begin{itemize}
- \item Overhead for a pointer to the data\pause{}
- \item Extra pointer chasing
- \end{itemize}
- \end{itemize}
- \end{block}
- \end{columns}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Tradeoffs for heterogenous translation}
- \pause{}
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Type information available at runtime\pause{}
- \item No extra indirection\pause{}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item Bigger binaries:\pause{}
- \begin{itemize}
- \item More space needed\pause{}
- \item No hope for instruction cache\pause{}
- \end{itemize}
- \item Complex:\pause{}
- \begin{itemize}
- \item Compiles slower\pause{}
- \item More complex compiler logic
- \end{itemize}
- \end{itemize}
- \end{block}
- \end{columns}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{So which is better?}
- \pause{}
- \begin{itemize}
- \item No single answer --- both have various tradeoffs in general\pause{}
- \item Need to be viewed in the context of a particular language\pause{}
- \item Let's see some examples!\pause{}
- \end{itemize}
- We will have rating indicators:\pause{}
-
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{center}
- \begin{figure}
- \includegraphics[scale=0.1]{yes.eps}
- \caption*{`This is good (or not a problem)!'}\pause{}
- \end{figure}
- \end{center}
-
- \column{.5\textwidth}
- \begin{center}
- \begin{figure}
- \includegraphics[scale=0.1]{no.eps}
- \caption*{`This is bad (or a {\em real\/} problem)!'}
- \end{figure}
- \end{center}
- \end{columns}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Homogenous translation done well: C}
- \pause{}
-
- Honesty note: C doesn't technically have homogenous translation built-in. We
- have to fake it with \verb!void*!.\pause{}
-
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Simple\pause{} \includegraphics[scale=0.03]{yes.eps} \pause{}
- \item Smaller binaries\pause{} \includegraphics[scale=0.03]{yes.eps}
- \pause{}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item No type information at runtime\pause{}
- \includegraphics[scale=0.03]{yes.eps}\pause{}
- \item Indirection\pause{} \includegraphics[scale=0.03]{no.eps}\pause{}
- \end{itemize}
- \end{block}
- \end{columns}
-
- \begin{center}
- \alert{Overall verdict:} $\frac{3}{4}$\pause{} (a B).
- \end{center}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Homogenous translation done badly: Java}
- \pause{}
-
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Simple\pause{} \includegraphics[scale=0.03]{no.eps} \pause{}
- \item Smaller binaries\pause{} \includegraphics[scale=0.03]{no.eps}
- \pause{}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item No type information at runtime\pause{}
- \includegraphics[scale=0.03]{no.eps}\pause{}
- \item Indirection\pause{} \includegraphics[scale=0.03]{yes.eps}\pause{}
- \end{itemize}
- \end{block}
- \end{columns}
- \begin{center}
- \alert{Overall verdict:} $\frac{1}{4}$\pause{} (drop out of university Java,
- you're drunk)
- \end{center}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Heterogenous translation done well: C\#}
- \pause{}
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Type information available at runtime\pause{}
- \includegraphics[scale=0.03]{yes.eps}\pause{}
- \item No extra indirection\pause{}
- \includegraphics[scale=0.03]{yes.eps}\pause{}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item Bigger binaries\pause{}
- \includegraphics[scale=0.03]{yes.eps}\pause{}
- \item Complex\pause{} \includegraphics[scale=0.03]{yes.eps}\pause{}
- \end{itemize}
- \end{block}
- \end{columns}
-
- \begin{center}
- \alert{Overall verdict:} $\frac{4}{4}$\pause{} (I swear that Microsoft
- didn't pay me!)
- \end{center}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Heterogenous translation done badly: C++}
- \pause{}
- \begin{columns}[t]
- \column{.5\textwidth}
- \begin{block}{Advantages}
- \begin{itemize}
- \item Type information available at runtime\pause{}
- \includegraphics[scale=0.03]{no.eps}\pause{}
- \item No extra indirection\pause{}
- \includegraphics[scale=0.03]{yes.eps}\pause{}
- \end{itemize}
- \end{block}
- \column{.5\textwidth}
- \begin{block}{Disadvantages}
- \begin{itemize}
- \item Bigger binaries\pause{}
- \includegraphics[scale=0.03]{no.eps}\pause{}
- \item Complex\pause{} \includegraphics[scale=0.03]{no.eps}\pause{}
- \end{itemize}
- \end{block}
- \end{columns}
-
- \begin{center}
- \alert{Overall verdict:} $\frac{1}{4}$\pause{} (bad idea in the 80s, bad
- idea now)
- \end{center}
- \end{frame}
- \begin{frame}[c]
- \frametitle{Conclusion}
- \pause{}
- \begin{itemize}
- \item Type parametrization is something we want (and language designers have
- obliged)\pause{}
- \item There's more than one way to do it, and it must be viewed in the
- context of the language they inhabit\pause{}
- \item More work is still being done on this!\pause{}
- \item Important to understand how something works (don't just blindly follow
- hype and buzzwords)\pause{}
- \end{itemize}
-
- \begin{quoting}
- In software development, abstraction is often used as a synonym for
- indirection. Not so in mathematics.
- \end{quoting}
- Susan Potter ({\tt @SusanPotter})
- \end{frame}
- \section{There's this one thing I don't get\ldots}
- \begin{frame}
- \frametitle{Question time!}
-
- \begin{center}
- \includegraphics[scale=0.5]{question.eps}
- \end{center}
- \end{frame}
- \end{document}
|