all.tex

% This is a borrowed LaTeX template file for lecture notes for CS267,
% Applications of Parallel Computing, UCBerkeley EECS Department.
% Now being used for CMU's 10725 Fall 2012 Optimization course
% taught by Geoff Gordon and Ryan Tibshirani.  When preparing 
% LaTeX notes for this class, please use this template.
%
% To familiarize yourself with this template, the body contains
% some examples of its use.  Look them over.  Then you can
% run LaTeX on this file.  After you have LaTeXed this file then
% you can look over the result either by printing it out with
% dvips or using xdvi. "pdflatex template.tex" should also work.
%

\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% ADD PACKAGES here:
%

\usepackage{amsmath,amsfonts,graphicx,dirtytalk,courier}
\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=haskell,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{black},
  commentstyle=\color{dkgreen},
  stringstyle=\color{red},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3
}


%
% The following commands set up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf Notes for Programming Languages (CSE 230)
	\hfill From Winter 2016} }
      \vspace{2mm}}
   }
   \end{center}

   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
% Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
        {[\arabic{equation}]}{\usecounter{equation}
         \setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
         \setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
			\vspace{#2}
			\begin{center}
			Figure \thelecnum.#1:~#3
			\end{center}
	}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\newcommand\E{\mathbb{E}}

\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1}{August 28}{Geoff Gordon/Ryan Tibshirani}{scribe-name1,2,3}
%\footnotetext{These notes are partially based on those of Nigel Mansell.}

% **** YOUR NOTES GO HERE:

\section{$\lambda$ calculus}

According to Landin, all programming languages can be traced back to the
$\lambda$-calculus. In general, there are only three kinds of expressions
(terms):

\begin{itemize}
    \item Variables of the form $e::=x$.
    \item Functions of the form $\lambda x.e$, where $x$ is an argument and
    $e$ is an expression.
    \item Application $e_i e_2$, means that $e_2$ is applied to $e_1$.
\end{itemize}

Consider the following examples:

\begin{itemize}
    \item An identitiy function $I=_{def} \lambda x.\ x$.
    \item A function that appilies its argument to the identity function
    $\lambda f.\ f\ (\lambda x.\ x)$.
\end{itemize}

\subsection{Free and bound variables}

A variable $x$ can belong to a scope $E$, for example $\lambda x.\ E$ binds
variable $x$ in $E$, in that example $x$ is the new variable being introduced
into the context or scope $E$, consequently $E$ is the scope of $x$, and $x$
is bound to the expression $\lambda x.\ E$. Finally consider another variable
$y$, this variable is gooing to be free in $E$ if it occurs not bound in $E$.

To determine the free variables of an expression see the following examples:

\begin{itemize}
    \item $Free(x)=\{x\}$.
    \item $Free(E_1\ E_2)=Free(E_1) \cup Free(E_2)$.
    \item $Free(\lambda x.\ E)=Free(E)-\{x\}$.
\end{itemize}

An example of these rules applied would be
$Free(\lambda x.\ x(\lambda y.\ x\ y\ z))=\{z\}$.

\subsection{$\alpha\textrm{-}renaming$}

The definition from the slides:

\say{$\lambda$-terms after renaming bound variables that are considered
identical to the original.}

The definition from Wikipedia:

\say{Alpha-conversion allows bound variable names to be changed. For example,
alpha-conversion of $\lambda x.\ x$ might yield $\lambda y.\ y$, terms that
differ only by alpha-conversion are called $\alpha$-equivalent. In frequent
uses of lambda calculus, $\alpha\textrm{-}equivalent$ terms are considered to be
equivalent.}

Some examples of these equivalences are:

\begin{itemize}
    \item $\lambda x.\ x == \lambda y.\ y == \lambda z.\ z$.
\end{itemize}

Notation $[E'/x]\ E$: Substitution of $E'$ for $x$ in $E$, means that we
uniquely rename bound variables en E and $E'$ and then do textual substitution
of $E'$ for $x$ in $E$.

Example $[y\ (\lambda x.\ x)/x]\ \lambda y.\ (\lambda x.\ x)\ y\ x$

\begin{itemize}
    \item After renaming: $[y (\lambda v.\ v)/x]\ \lambda z.\ (\lambda u.\ u)\ z\ x$
    \item After substitution: $\lambda z. (\lambda u.\ u)z\ (y\ (\lambda v.\ v))$
\end{itemize}


\subsection{$\beta\textrm{-}renaming$}

$$(\lambda x.\ e)\ e' \rightarrow [e'/x]e$$

The core idea is that we are substituting expressions, one at a time:

\begin{itemize}
    \item binds $x$ to $e'$.
    \item evaluates $e$ with the new binding.
    \item yields the result of this evaluation
\end{itemize}

In the following example we substitute:

$$ (\lambda f.\ f\ (f\ e))\ g \rightarrow g\ (g\ e)$$

Now lets see this applied to the identity function
$(\lambda x.\ x)\ E \rightarrow [E/x]x = E$, here we take an expression $E$,
then pass it as an argument to the identity function that takes an $x$ and
replace the $x$ with the expression $E$ thus yielding $E$.


Now this is an example that's a little bit more convoluted:

\begin{itemize}

    \item $(\lambda f.\ f\ (\lambda x.\ x))\ (\lambda x.\ x) \rightarrow [\lambda x.\ x/f]\ f\ (\lambda x.\ x)$
    \item $=[(\lambda x.\ x) / f] f (\lambda y.\ y)$
    \item $=(\lambda x.\ x) (\lambda y.\ y) \rightarrow [\lambda y.\ y/x] x$
    \item $=\lambda y.\ y$

\end{itemize}

Here's now an example of a non-terminating evaluation:

\begin{itemize}
    \item $(\lambda x.\ x\ x) (\lambda y.\ y\ y) \rightarrow [\lambda y.\ y\ y/\ x]\ x\ x$
    \item $=(\lambda y.\ y\ y)(\lambda y.\ y\ y)$
    \item $=(\lambda x.\ x\ x)(\lambda y.\ y\ y)$
\end{itemize}

\subsection{Interrogation}

Do we really have all the nice things from a \textit{real} programming language?

\begin{itemize}
    \item Local variables: yes we do, we bind an expression to a scope.
    \item Boolean values and if/then/else: yes for sure, what we actually have
        are functions that take two parameters and return the first or the
        second, for example $true =_{def} \lambda x.\ \lambda y.\ x$, and
        $false =_{def} \lambda x.\ \lambda y.\ y$. Finally we can build something
        like an if-then-else as $(\lambda x.\ \lambda y.\ x) u\ v \rightarrow (\lambda y.\ u) v \rightarrow v$
        (which should be read as if true, then $u$, else $v$).
    \item We also have records (pairs).

    \item Numbers (Church's numerals).

    \item Recursion as well (this one is rather obscure).
\end{itemize}

\section{Higher order functions}

Functions are first class values, meaning that we can move them around just
like with any other value, more importantly as arguments to other functions and
as return values from other functions.

Recall the $\rightarrow$ operator, takes two types, the input and output type
and returns a new \textit{function type}, this operator very much like the
minus operator is right associative, meaning that $Int \rightarrow Int \rightarrow Int$.
should really be read as $Int \rightarrow (Int \rightarrow Int)$ With this we
can understand that there's partial evaluation and if we pass \textit{incomplete}
parameters to a function, this will return a partially evaluated function that
takes the remaining parameters.

Haskell allows you tu use any operator as an infix by wrapping it around
backticks.

The faithful cons operator $:$ has type $(:) :: a \rightarrow [a] \rightarrow
[a]$, meaning it has a generic type $a$, and thus lists can be made out of any
type we want (for the most part).

\subsection{Diving into some concrete examples}

\begin{itemize}
    \item $map$ is a function that jogs between the elements of a list and
        applies a transformer. Aside from the basecase, the function $map$ is
        \texttt{map f (x:xs)=(f x):(map f xs)}

    \item $foldr$ is a function that takes a base value (accumulator), a
        function and a list and applies the function to the accumulator and to
        each element of the list to then store this in the accumulator. Aside
        from the basecase we have that $foldr$ is
        \texttt{foldr op base (x:xs)=x `op` (foldr op base xs)}.
\end{itemize}

\subsection{Types}

Very much like functions, types can be recursive, for example consider the
following definitions:

\begin{lstlisting}
data Shape  = Rectangle Double Double
            | Polygon [(Double, Double)]
data IntList = IEmpty  
             | IOneAndMore Int IntList 
             deriving (Show) 
\end{lstlisting}

Just as we expect, we could traverse through this objects recursively and at
each step operate on every element of the structure.

\subsection{Parameterized Types}

Very similar to the definitions above, we can also have something like this:

\begin{lstlisting}
data List a = Empty
\hfill| OneAndMore a (List a)
            deriving (Show)
\end{lstlisting}

From this definition, one may wonder, \textit{... well clearly the type for
\texttt{OneAndMore} and \texttt{Empty} is of type \texttt{List}, but what's the
type for \texttt{List} itself? ...}, the answer is that there's none, types
don't have types, they have \textbf{Kinds}, for example:

\begin{lstlisting}
ghci> :kind Int
Int :: *
ghci> :kind Char 
Char :: *
ghci> :kind Bool
Bool :: *
ghci> :kind (->) -- our faithful old friend the arrow operator
(->) :: * -> * -> *
\end{lstlisting}

\subsection{Typeclasses}

Since Haskell lacks a way to do function overloading, or to really have some
sort of inheritance what we do is use qualified types, see this example of the
type of the $+$ operator\footnote{ Recall that operators and functions are both
    first class citizens, there really isn't a distinction between both of
them}:

\begin{lstlisting}
ghci> :type (+)
(+) :: (Num a) => a -> a -> a
\end{lstlisting}

We can read it as $a$ being a type that satisfies the predicate $Num$, meaning
that $a$ has to be either of type $Integer$ or $Double$.

So what's a type class you ask? In a nutshell, a typeclass is a collection of
operations (functions) that must exist for the underlying type. For example,
for a type to be of the class $Eq$, it has to have a \texttt{(==)} and a
\texttt{(/=)} operator (each of type $a \rightarrow a \rightarrow Bool$).

\textbf{Laws}: in addition to the explicit type requirements, we also have
"laws" in in the language.

Here's how we define a \textit{typeclass} for the JSON example:

\begin{lstlisting}
> class JSON a where
>   toJSON :: a -> JVal
> instance JSON Double where
>   toJSON = JNum
> 
> instance JSON Bool where
>   toJSON = JBln
> 
> instance JSON String where
>   toJSON = JStr
\end{lstlisting}

\section{Monads and Monoids}

Monads are a great example of how you can abstract out a common programming
pattern as a definition. Before we dive into the obscure world of monads we
will define two functions.

\subsection{Functors}

Functors are a type class that allows us to have constructors we can $map$
over, for example:

\begin{lstlisting}
class Functor m where
 fmap :: (a -> b) -> m a -> m b
instance Functor [] where
  fmap f []     = []
  fmap f (x:xs) = f x : fmap f xs

instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just x) = Just (f x)

instance Functor IO where
  fmap f x = do {y <- x; return (f x)} 
\end{lstlisting}

The main idea here is that we have now constructed a \textit{sort of API} that
allows us to use the same map function regardless of the type we are dealing
with.

\subsection{Applicatives}

We can generalize $map$ to many more arguments, this is called a lift, that's
why we have applicatives, see these examples.

\begin{lstlisting}
lift1           :: (a -> b) -> [a] -> [b]
lift1 f []      = []
lift1 f (x:xs)  = f x : lift1 f xs


-- with two arguments
lift2 :: (a1 -> a2 -> b) -> [a1] -> [a2] -> [b]
lift2 f (x:xs) (y:ys) = f x y : lift2 f xs ys
lift2 f _      _      = []
\end{lstlisting}

Or instead of doing that we can do something like this:

\begin{lstlisting}
lift2 :: (a1 -> a2 -> b) -> IO a1 -> IO a2 -> IO b 
lift2 f x1 x2 = do a1 <- x1
                   a2 <- x2
                   return (f a1 a2)


lift3 :: (a1 -> a2 -> a3 -> b) 
      -> IO a1 
      -> IO a2 
      -> IO a3 
      -> IO b
\end{lstlisting}

With lift and sequencing we can then come up with the sequencing operator
\textit{>>=} read as then, for example see this implementation

\begin{lstlisting}
(>>=)   :: Maybe a -> (a -> Maybe b) -> Maybe b
m >>= f =  case m of
             Nothing -> Nothing
             Just x  -> f x


(>>=)          :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing  >>= _ = Nothing
(Just x) >>= f = f x
\end{lstlisting}

The way to read this would be by reading the first argument and if it is
$Nothing$, then the second argument is ignored, otherwise we actually proceed
to apply $x$ to $f$ and return that value.


\end{document}