functional-programming-advantages.tex

%% LyX 2.3.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{beamer}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{babel}
\ifx\hypersetup\undefined
  \AtBeginDocument{%
    \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
  }
\else
  \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
\fi

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
% this default might be overridden by plain title style
\newcommand\makebeamertitle{\frame{\maketitle}}%
% (ERT) argument for the TOC
\AtBeginDocument{%
  \let\origtableofcontents=\tableofcontents
  \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
  \def\gobbletableofcontents#1{\origtableofcontents}
}
\newenvironment{lyxcode}
  {\par\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
    \setlength{\listparindent}{0pt}% needed for AMS classes
    \raggedright
    \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
    \normalfont\ttfamily}%
   \def\{{\char`\{}
   \def\}{\char`\}}
   \def\textasciitilde{\char`\~}
   \item[]}
  {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme[secheader]{Boadilla}
\usecolortheme{seahorse}
\title[Why functional programming]{What did functional programming ever do for us (software engineers)?}
\subtitle{An extreme pragmatic and un-academic approach}
\author{Sergei Winitzki}
\date{2020-08-22}
\institute[ABTB]{Academy by the Bay}
\setbeamertemplate{headline}{} % disable headline at top
\setbeamertemplate{navigation symbols}{} % disable navigation bar at bottom
\usepackage[all]{xy} % xypic
%\makeatletter
% Macros to assist LyX with XYpic when using scaling.
\newcommand{\xyScaleX}[1]{%
\makeatletter
\xydef@\xymatrixcolsep@{#1}
\makeatother
} % end of \xyScaleX
\makeatletter
\newcommand{\xyScaleY}[1]{%
\makeatletter
\xydef@\xymatrixrowsep@{#1}
\makeatother
} % end of \xyScaleY

% Double-stroked fonts to replace the non-working \mathbb{1}.
\usepackage{bbold}
\DeclareMathAlphabet{\bbnumcustom}{U}{BOONDOX-ds}{m}{n} % Use BOONDOX-ds or bbold.
\newcommand{\custombb}[1]{\bbnumcustom{#1}}
% The LyX document will define a macro \bbnum{#1} that calls \custombb{#1}.

\usepackage{relsize} % make math symbols larger or smaller
\usepackage{stmaryrd} % some extra symbols such as \fatsemi
% Note: using \forwardcompose inside a \text{} will cause a LaTeX error!
\newcommand{\forwardcompose}{\hspace{1.5pt}\ensuremath\mathsmaller{\fatsemi}\hspace{1.5pt}}


% Make underline green.
\definecolor{greenunder}{rgb}{0.1,0.6,0.2}
%\newcommand{\munderline}[1]{{\color{greenunder}\underline{{\color{black}#1}}\color{black}}}
\def\mathunderline#1#2{\color{#1}\underline{{\color{black}#2}}\color{black}}
% The LyX document will define a macro \gunderline{#1} that will use \mathunderline with the color `greenunder`.
%\def\gunderline#1{\mathunderline{greenunder}{#1}} % This is now defined by LyX itself with GUI support.

% Scala syntax highlighting. See https://tex.stackexchange.com/questions/202479/unable-to-define-scala-language-with-listings
%\usepackage[T1]{fontenc}
%\usepackage[utf8]{inputenc}
%\usepackage{beramono}
%\usepackage{listings}
% The listing settings are now supported by LyX in a separate section "Listings".
\usepackage{xcolor}

\definecolor{scalakeyword}{rgb}{0.16,0.07,0.5}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\definecolor{aqua}{rgb}{0.9,0.96,0.999}
\definecolor{scalatype}{rgb}{0.2,0.3,0.2}

\makeatother

\usepackage{listings}
\lstset{language=Scala,
morekeywords={{scala}},
otherkeywords={=,=>,<-,<\%,<:,>:,\#,@,:,[,],.,???},
keywordstyle={\color{scalakeyword}},
morekeywords={[2]{String,Short,Int,Long,Char,Boolean,Double,Float,BigDecimal,Seq,Map,Set,List,Option,Either,Future,Vector,Range,IndexedSeq,Try,true,false,None,Some,Left,Right,Nothing,Any,Array,Unit,Iterator,Stream}},
keywordstyle={[2]{\color{scalatype}}},
frame=tb,
aboveskip={1.5mm},
belowskip={0.5mm},
showstringspaces=false,
columns=fullflexible,
keepspaces=true,
basicstyle={\smaller\ttfamily},
extendedchars=true,
numbers=none,
numberstyle={\tiny\color{gray}},
commentstyle={\color{dkgreen}},
stringstyle={\color{mauve}},
frame=single,
framerule={0.0mm},
breaklines=true,
breakatwhitespace=true,
tabsize=3,
framexleftmargin={0.5mm},
framexrightmargin={0.5mm},
xleftmargin={1.5mm},
xrightmargin={1.5mm},
framextopmargin={0.5mm},
framexbottommargin={0.5mm},
fillcolor={\color{aqua}},
rulecolor={\color{aqua}},
rulesepcolor={\color{aqua}},
backgroundcolor={\color{aqua}},
mathescape=false,
extendedchars=true}
\begin{document}
\global\long\def\gunderline#1{\mathunderline{greenunder}{#1}}%
\global\long\def\bef{\forwardcompose}%
\global\long\def\bbnum#1{\custombb{#1}}%
\frame{\titlepage}
\begin{frame}{Overview: Advantages of functional programming}

Features of functional programming are being added to many languages
\begin{itemize}
\item What are these features?
\item What advantages do they give programmers?
\end{itemize}
Programmer-facing features listed in the increasing order of complexity 

~ ~ (and decreasing order of advantage-to-cost ratio)
\begin{enumerate}
\item Write iterative code without loops
\item Use functions parameterized by types, checked by compiler
\item Use disjunctive types to model special cases, errors, etc.
\item Use special syntax for chaining effectful computations
\end{enumerate}
\end{frame}

\begin{frame}{Feature 1: Loop-free iterative programs. Transformation}

An easy interview question:

~ ~Given an array of integers, find all pairs that sum to a given
number
\begin{itemize}
\item Solutions using loops: \href{https://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html}{10-20 lines of code}
\item FP solution with $O(n^{2})$ complexity:
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}\#~Python}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}{[}~(x,~y)~for~x~in~array~for~y~in~array~if~x~+~y~==~n~{]}}{\footnotesize\par}

\textcolor{darkgray}{\footnotesize{}//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}for~\{~x~<-~array;~y~<-~array;~if~x~+~y~==~n~\}~yield~(x,~y)}{\footnotesize\par}

\textcolor{darkgray}{\footnotesize{}-{}-~Haskell}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}do;~x~<-~array;~y~<-~array;~guard~(x~+~y~==~n);~return~(x,~y)}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item FP solution with $O(n\log n)$ complexity:
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}val~hash~=~array.toSet}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}for~\{~x~<-~hash;~if~hash~contains~(n~-~x)~\}~yield~(x,~n~-~x)}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Feature 1: Loop-free iterative programs. Aggregation}

\begin{itemize}
\item Given an array of integers, compute the sum of square roots of all
elements except negative ones 
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}\#~Python}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}sum(~{[}~sqrt(x)~for~x~in~givenArray~if~x~>=~0~{]}~)}{\footnotesize\par}

\textcolor{darkgray}{\footnotesize{}//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}givenArray.filter(\_~>=~0).map(math.sqrt).sum}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Given a set of integers, compute the sum of those integers which are
non-negative and whose square root is also present in the set 
\begin{itemize}
\item Solution using loops: \href{https://www.geeksforgeeks.org/sum-of-elements-whose-square-root-is-present-in-the-array/}{15-20 lines of code}
\item FP solution:
\end{itemize}
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}givenSet}\textcolor{darkgray}{\footnotesize{}~//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~.filter~\{~x~=>~x~>=~0~\&\&~givenSet.contains(math.sqrt(x))~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~.sum}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Compute a positive integer from a given array of its decimal digits
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}digits.reverse.zipWithIndex}\textcolor{darkgray}{\footnotesize{}~//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~.map~\{~case~(d,~i)~=>~d~{*}~math.pow(10,~i).toInt~\}~.sum}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Feature 1: Loop-free iterative programs. Induction}

\begin{itemize}
\item Compute the mean value of a given sequence in single pass
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}scala>~Seq(4,~5,~6,~7).foldLeft((0.0,~0.0))~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~|~case~((sum,~count),~x)~=>~(sum~+~x,~count~+~1)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~|~\}.pipe~\{~case~(sum,~count)~=>~sum~/~count~\}~}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}res1:~Double~=~5.5}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Any inductive definition can be converted to a ``fold''
\begin{itemize}
\item Base case is the initial value
\item Inductive step is the updater function
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Feature 1: Loop-free iterative programs. Other applications}

\begin{itemize}
\item The implementation of \texttt{\textcolor{blue}{\footnotesize{}map}},
\texttt{\textcolor{blue}{\footnotesize{}filter}}, \texttt{\textcolor{blue}{\footnotesize{}fold}},
\texttt{\textcolor{blue}{\footnotesize{}flatMap}}, \texttt{\textcolor{blue}{\footnotesize{}groupBy}},
\texttt{\textcolor{blue}{\footnotesize{}sum}}, etc., may be asynchronous
(Akka Streams), parallel, and/or distributed (Spark, Flink)
\begin{itemize}
\item The programmer writes loop-free code in the map/filter/reduce style
\item The runtime engine implements parallelism, fault tolerance, etc.
\item Many types of programmer errors are avoided automatically
\end{itemize}
\item What we need to support programming in the map/filter/reduce style:
\begin{itemize}
\item Collections with user-definable methods
\item Functions (``lambdas'') passed as parameters to other functions
\item Easy work with tuple types
\end{itemize}
\item Lambdas were added to most programming languages by 2015
\end{itemize}
\end{frame}

\begin{frame}{Feature 2: Type parameters. Usage}

\begin{itemize}
\item Collections can have types parameterized by element type
\begin{itemize}
\item Array of integers: \texttt{\textcolor{blue}{\footnotesize{}Array{[}Int{]}}} 
\item Array of strings: \texttt{\textcolor{blue}{\footnotesize{}Array{[}String{]}}} 
\item Array of arrays of pairs of integers and strings: \texttt{\textcolor{blue}{\footnotesize{}Array{[}Array{[}(Int,
String){]}{]}}} 
\end{itemize}
\item Methods such as \texttt{\textcolor{blue}{\footnotesize{}map}}, \texttt{\textcolor{blue}{\footnotesize{}zip}},
\texttt{\textcolor{blue}{\footnotesize{}flatMap}}, \texttt{\textcolor{blue}{\footnotesize{}groupBy}}
change the type parameters
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}Seq(4,~5,~6,~7)~~~~~~~~~~~~~~~~~~~~~}\textcolor{darkgray}{\footnotesize{}~//~Seq{[}Int{]}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~.zip(Seq(\textquotedbl a\textquotedbl ,~\textquotedbl b\textquotedbl ,~\textquotedbl c\textquotedbl ,~\textquotedbl d\textquotedbl ))}\textcolor{darkgray}{\footnotesize{}~~~~~~//~Seq{[}(Int,~String){]}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~.map~\{~case~(i,~s)~=>~s\textquotedbl\$s~:~\$i\textquotedbl ~\}}\textcolor{darkgray}{\footnotesize{}~//~Seq{[}String{]}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item The compiler prevents using incorrect type parameters anywhere
\end{itemize}
\end{frame}

\begin{frame}{Feature 2: Type parameters. Language features}

\begin{itemize}
\item Code can be written once, then used with different type parameters
\item Example (Scala):
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~map{[}A,~B{]}(xs:~Seq{[}A{]})(f:~A~=>~B):~Seq{[}B{]}~=~...~}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Collections (\texttt{\textcolor{blue}{\footnotesize{}Array}}, \texttt{\textcolor{blue}{\footnotesize{}Set}},
etc.) with type parameters support such methods
\item Many programming languages have type parameters
\begin{itemize}
\item Functions with type parameters were added to Java in 2006
\item C++ can imitate this functionality with templates
\item Go-lang might get type parameters in the future
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Feature 3: Disjunctive types}

\begin{itemize}
\item Enumeration type (\texttt{\textcolor{blue}{\footnotesize{}enum}})
describes a set of disjoint possibilities:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}enum~Color~\{~RED,~GREEN,~BLUE;~\}~}\textcolor{darkgray}{\footnotesize{}//~Java}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item A value of type \texttt{\textcolor{blue}{\footnotesize{}Color}} can
be only one of the three possibilities
\item Disjunctive types are ``enriched'' \texttt{\textcolor{blue}{\footnotesize{}enum}}
types, carrying extra values:
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}//~Scala~3}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}enum~RootOfEq~\{~case~NoRoots();~case~OneRoot(x:~Float);~\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item The \texttt{\textcolor{blue}{\footnotesize{}switch}} is ``enriched''
to extract data from disjunctive values
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}roots~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~OneRoot(x)~=>~}\textcolor{darkgray}{\footnotesize{}//~May~use~`x`~in~this~expression.}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~NoRoots()~=>~}\textcolor{darkgray}{\footnotesize{}//~May~not~use~`x`~here~by~mistake.}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Disjunctive types describe values from ``tagged union'' sets
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}OneRoot(x)}} $\cong$ the
set of all \texttt{\textcolor{blue}{\footnotesize{}Float}} values
\item \texttt{\textcolor{blue}{\footnotesize{}NoRoots()}} $\cong$ the set
consisting of a single value
\item \texttt{\textcolor{blue}{\footnotesize{}RootOfEq}} $\cong$ either
some \texttt{\textcolor{blue}{\footnotesize{}Float}} value or the
special value \texttt{\textcolor{blue}{\footnotesize{}NoRoots()}} 
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Feature 3: Disjunctive types. Adoption in languages}

\begin{itemize}
\item Disjunctive types and pattern matching are required for FP
\item Introduced in Standard ML (1973)
\item Supported in all FP languages (OCaml, Haskell, F\#, Scala, Swift,
...)
\item The support of disjunctive types only comes in FP-designed languages
\begin{itemize}
\item Not supported in C, C++, Java, JavaScript, Python, Go, ...
\item Not supported in relational languages (Prolog, SQL, Datalog, ...)
\item Not supported in configuration data formats (XML, JSON, YAML, ...)
\end{itemize}
\item Logical completeness of the type system:
\end{itemize}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline 
\textbf{\small{}Scala type} & \textbf{\small{}Logic operation} & \textbf{\small{}Logic notation} & \textbf{\small{}Type notation}\tabularnewline
\hline 
\hline 
\texttt{\textcolor{blue}{\footnotesize{}(A, B)}} & conjunction & $A\wedge B$ & $A\times B$\tabularnewline
\hline 
\texttt{\textcolor{blue}{\footnotesize{}Either{[}A, B{]}}} & disjunction & $A\vee B$ & $A+B$\tabularnewline
\hline 
\texttt{\textcolor{blue}{\footnotesize{}A => B}} & implication & $A\Rightarrow B$ & $A\rightarrow B$\tabularnewline
\hline 
\texttt{\textcolor{blue}{\footnotesize{}Unit}} & true & $\top$ & $\bbnum 1$\tabularnewline
\hline 
\texttt{\textcolor{blue}{\footnotesize{}Nothing}} & false & $\bot$ & $\bbnum 0$\tabularnewline
\hline 
\end{tabular}
\par\end{center}
\begin{itemize}
\item Programming is easier in languages having a \emph{complete} logic
of types
\begin{itemize}
\item ``Hindley-Milner type system''
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Motivation}

How to compose computations that may fail with an error?
\begin{itemize}
\item A ``result or error'' disjunctive type: \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
$\cong$ \texttt{\textcolor{blue}{\footnotesize{}Either{[}Throwable,
A{]}}} 
\item In Scala, \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}} is
a disjunction of \texttt{\textcolor{blue}{\footnotesize{}Failure{[}Throwable{]}}}
and \texttt{\textcolor{blue}{\footnotesize{}Success{[}A{]}}} 
\end{itemize}
Working with \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
requires two often-used code patterns:
\begin{itemize}
\item Use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}} in a computation
that cannot fail, \texttt{\textcolor{blue}{\footnotesize{}f:~A =>
B}} 
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}Success(a)}} goes to \texttt{\textcolor{blue}{\footnotesize{}Success(f(a))}}
but \texttt{\textcolor{blue}{\footnotesize{}Failure(t)}} remains unchanged
\end{itemize}
\item Use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}} in a computation
that can fail, \texttt{\textcolor{blue}{\footnotesize{}g:~A => Try{[}B{]}}} 
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}Success(a)}} goes to \texttt{\textcolor{blue}{\footnotesize{}g(a)}}
while \texttt{\textcolor{blue}{\footnotesize{}Failure(t)}} remains
unchanged
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Implementation}

Implementing the two code patterns using pattern matching:
\begin{itemize}
\item Pattern 1: use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
in a computation that cannot fail
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}tryGetFileStats()~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Success(stats)~=>~Success(stats.getTimestamp)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Pattern 2: use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
in a computation that can fail
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}tryOpenFile()~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Success(file)~=>~tryRead(file)}\textcolor{darkgray}{\footnotesize{}~//~Returns~Try{[}Array{[}Byte{]}{]}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Implementation}

\begin{itemize}
\item The two patterns may be combined at will
\end{itemize}
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}//~Read~a~file,~decode~UTF-8,~return~the~number~of~chars.}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}def~utfChars(name:~String):~Try{[}Int{]}~=~tryOpenFile(name)~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Success(file)~=>~tryRead(file)~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~case~Success(bytes)~=>~tryDecodeUTF8(bytes)~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~case~Success(decoded)~=>~Success(decoded.length)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item The code is awkwardly nested and repetitive 
\begin{itemize}
\item This sort of code is common in go-lang programs:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}err1,~res1~:=~tryOpenFile();}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}if~(res1~!=~nil)~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~err2,~res2~:=~tryRead(res1);}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~if~(res2~!=~nil)~\{~...~\}~}\textcolor{darkgray}{\footnotesize{}~//~Continue~with~no~errors.}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~else~...}\textcolor{darkgray}{\footnotesize{}~//~Handle~second~error.~}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}else~...}\textcolor{darkgray}{\footnotesize{}~~~~//~Handle~first~error.~}{\footnotesize\par}
\end{lyxcode}
\end{itemize}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Using \texttt{map} and \texttt{flatMap}}

Implement the two code patterns using \texttt{\textcolor{blue}{\footnotesize{}map}}
and \texttt{\textcolor{blue}{\footnotesize{}flatMap}}:
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}Try(a).map(f)}} -- use with
\texttt{\textcolor{blue}{\footnotesize{}f:~A => B}} that cannot fail
\item \texttt{\textcolor{blue}{\footnotesize{}Try(a).flatMap(g)}} -- use
with \texttt{\textcolor{blue}{\footnotesize{}g:~A => Try{[}B{]}}}
that can fail
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fmap{[}A,~B{]}(f:~A~=>~B):~Try{[}A{]}~=>~Try{[}B{]}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}def~flm{[}A,~B{]}(g:~A~=>~Try{[}B{]}):~Try{[}A{]}~=>~Try{[}B{]}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Pattern 1: use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
in a computation that cannot fail
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}tryGetFileStats()~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Success(stats)~=>~Success(stats.getTimestamp)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Pattern 2: use \texttt{\textcolor{blue}{\footnotesize{}Try{[}A{]}}}
in a computation that can fail
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}tryOpenFile()~match~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Success(file)~=>~read(file)}\textcolor{darkgray}{\footnotesize{}~//~Returns~Try{[}InputStream{]}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~case~Failure(exception)~=>~Failure(exception)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Special syntax}

Using \texttt{\textcolor{blue}{\footnotesize{}map}} and \texttt{\textcolor{blue}{\footnotesize{}flatMap}},
the code from the previous slide simplifies:
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}tryGetFileStats().map(stats~=>~stats.getTimestamp)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}tryOpenFile().flatMap(file~=>~read(file))}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item We can now write code like this (avoiding nesting and repetition):
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}Try(one()).map~\{~x~=>~f(x)~\}.flatMap~\{~y~=>~Try(another(y))~\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Instead of a chain of \texttt{\textcolor{blue}{\footnotesize{}map}}
and \texttt{\textcolor{blue}{\footnotesize{}flatMap}} methods, use
a special syntax:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~x~<-~Try(one())}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~y~=~f(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~z~<-~Try(another(y))}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~z}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item Resembles the syntax for nested loops (``for-comprehension'')
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x~<-~list1;~y~<-~list2~\}~yield~p(x,~y)~}\textcolor{darkgray}{\footnotesize{}//~Scala}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}{[}~p(x,~y)~for~y~in~list2~for~x~in~list1~{]}~}\textcolor{darkgray}{\footnotesize{}//~Python}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item In Haskell: ``\texttt{\textcolor{blue}{\footnotesize{}do}} notation'',
in F\#: ``computation expressions''
\end{itemize}
\end{frame}

\begin{frame}{Feature 4: Chaining of effects. Special syntax}

Using the special syntax, a chain of computations looks like this:
\begin{lyxcode}
\textcolor{darkgray}{\footnotesize{}//~Read~a~file,~decode~UTF-8,~return~the~number~of~chars.}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}def~utfChars(name:~String):~Try{[}Int{]}~=~for~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~file~~~~<-~tryOpenFile(name)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~bytes~~~<-~tryRead(file)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~decoded~<-~tryDecodeUTF8(bytes)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~length~~=~decoded.length}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}~yield~length}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Features 1-4 may be combined at will}

The main advantages in practical coding come from combining features
1-4 of functional programming
\begin{itemize}
\item Use functional methods on collections with type parameters
\item Use disjunctive types to represent program requirements
\item Avoid explicit loops and make sure all types match
\item Compose programs at high level by chaining effects (\texttt{\textcolor{blue}{\footnotesize{}Try}},
\texttt{\textcolor{blue}{\footnotesize{}Future}}, ...)
\end{itemize}
\end{frame}

\begin{frame}{Summary}
\begin{itemize}
\item FP proposes 4 essential features that make programming easier
\begin{itemize}
\item loop-free iteration, type parameters, disjunctive types, chaining
syntax
\item other, more advanced features have higher cost/advantage ratios
\end{itemize}
\item All ``FP languages'' have these features and give the same advantages
\begin{itemize}
\item OCaml, Haskell, Scala, F\#, Swift, Rust, Elm, ...
\end{itemize}
\item Most ``non-FP languages'' lack at least 2 of these features
\begin{itemize}
\item Lack of features may be compensated but raises the cost of their use
\end{itemize}
\end{itemize}
\end{frame}

\end{document}