type-parameterization/talk.tex

% 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}