% -*- mode: latex; coding: utf-8; TeX-master: ../thesis -*-
% !TEX TS-program = pdflatexmk
% !TEX encoding = UTF-8 Unicode
% !TEX root = ../thesis.tex

\section{Learning Functional Programming}

Within the last decade, concepts from functional programming have been brought into the daily life
of almost every programmer. There are many events that contributed to this gain in popularity:

In 2007, C\# 3.0 was released, which introduced lambda expressions and laid the foundations for
turning C\# into a hybrid Object-Oriented / Functional language\autocite{csharp-functional}.
Two years later, Ryan Dhal published the initial version of Node.js, eliminating JavaScript's
ties to the browser and introducing it as a server-side programming language, increasing the
adoption of JavaScript further.
In 2013, Java 8 was released and brought support for lambda expressions and streams.
Within the same time frame, Python has been rapidly growing in popularity\autocite{python-popularity}.

Further, many new multi-paradigm programming languages have been introduced,
including Rust, Kotlin, Go and Dart. They all have functions as first-class citizens in
the language since their initial release.

With these developments, it can be said that functional programming has emerged
from niche use-cases and academia to truly arrive in the wider programming community.
For example Rust, the `most popular programming language' for 5 years in a row (2016--2020)
according to the Stack Overflow Developer survey\autocite{rust-loved}, has been significantly
influenced by functional programming languages\autocite{rust-functional}. Further, in idiomatic
Rust code, a functional style can be clearly observed\footnote{A simple example for this may be
that variables are immutable by default.}.

Learning a purely functional programming language increases fluency with these concepts and
teaches a different way to think and approach problems when programming. Due to this, many
people recommend learning a functional programming
language\autocite{blog1-funcprog}\autocite{blog2-funcprog}\autocite{blog3-funcprog}\autocite{blog4-funcprog},
even if one may not end up using that language at all\autocite{quora-funcprog}.

Most literature about functional programming,
including academia and online resources like blogs, contain code examples written in Haskell.
Further, according to the Tiobe Index\autocite{tiobe-index}, Haskell is also the most popular
purely functional programming language\autocite{comparison-functional-languages}.

\section{Haskell}

Haskell, the \textit{lingua franca} amongst functional programmers, is a lazily-evaluated, purely functional programming
language. While Haskell's strengths stem from all it's features like its advanced type system, pattern matching and more,
these features are also what makes Haskell famously hard to learn\autocite{haskell-hard-one}\autocite{haskell-hard-two}\autocite{haskell-hard-three}\autocite{haskell-hard-four}.

Beginner Haskell programmers face a very distinctive challenge in contrast to learning a new, non-functional programming language:
Not only do they need to learn a new language with an unusual syntax (compared to imperative or object-oriented languages), they
also need to change their way of thinking and reasoning about problems.
For example, the renowned quicksort-implementation from the Haskell Introduction Page\autocite{haskell-quicksort}:

\begin{listing}
\begin{haskellcode}
quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs
\end{haskellcode}
	\caption{Quicksort implementation in Haskell}\label{code:haskell-quicksort}
\end{listing}

While this is only a very short and clean piece of code, these 6 lines already pose many challenges to non-experienced Haskellers:

\begin{itemize}
    \item The function's signature with no `fn' or `func' statement as they often appear in imperative languages
    \item The pattern matching, which would be a `switch' statement or a chain of `if / else' conditions
    \item The deconstruction of the list within the pattern matching
    \item The functional nature of the program, passing `(< p)' (a function returning a function) to another function
    \item The function call to `filter' without parenthesised arguments and no clear indicator at which arguments
        it takes and which types are returned
\end{itemize}

Although some of these constructs also exist in imperative or object-oriented languages, the cumulative difference
is not to underestimate and adds to Haskell's steep learning curve.

\section{Goals}

As demonstrated in the example above, learning a new paradigm and syntax at the same time
can be daunting and discouraging for novices.
The entry barrier for functional programming should be lowered by
using a modern, multi-paradigm language with a clear and familiar syntax. The functional
programming beginner should be able to focus on the paradigm first, and then change to a language
like Haskell to fully get into functional programming.

To achieve this goal, this thesis will consist of two parts.
In the first part, writing functional code will be made as easy as possible. This means that
a programming language with an easy and familiar syntax should be chosen. Optimally, this language
should already support functions as first-class citizens. Additionally, it should be statically
typed, as a static type system makes it easier to reason about a program and can support the
programmer while writing code.
In the second part, a linter will be created to check code for non-functional statements. To achieve
this, a definition of what functional purity means has to be selected and a ruleset has to be
worked out and implemented into a static analysis tool.

\section{Why Go}\label{sec:why-go}

The language of choice for this task is Go, a statically typed, garbage-collected programming language
designed at Google in 2009\autocite{golang-publish}. With its strong syntactic similarity to C, it should
be familiar to most programmers.

Go strives for simplicity and its syntax is extremely small and easy to learn. For example, the
language consists of only 25 keywords and purposefully omits constructs like the ternary operator
(<bool> ? <then> : <else>) as a replacement for the longer `if <bool> \{ <then> \} else \{ <else> \}'
for clarity. `A language needs only one conditional control flow construct'\autocite{go-ternary},
and this also holds true for many other constructs. In Go, there is usually only one way
to express something, improving the clarity of code.

Due to this clarity and unambiguity, the language is a perfect fit to grasp the concepts and trace
the inner workings of functional programming. It should be easy to read code and understand what
it does without a lot of experience with the language.

There are however a few downsides of using Go. Currently, Go does not have polymorphism, which means
that functions always have to be written with specific types. Due to this, Go also does not include
common list processing functions like `map', `filter', `reduce' and more\footnote{Although Go does
	have some polymorphic functions like `append', these are specified as built-in functions in the
language and not user-defined}. Further, Go does not have a built-in `list' datatype. However, Go's
`slices' cover a lot of use cases for lists already. Section~\ref{sec:go-slices} covers this topic
in more detail.

\section{Existing Work}

With Go's support of some functional aspects, patterns and best practices have emerged that make
us of functional programming constructs.
For example, in the \textit{net/http} package of the standard library, the function
\begin{gocode}
func HandleFunc(pattern string, handler func(ResponseWriter, *Request))
\end{gocode}
is used to register functions for http server handling\autocite{go-http-doc}:

\begin{code}
\begin{gocode}
func myHandler(w http.ResponseWriter, r *http.Request) {
    // Handle the given HTTP request
}

func main() {
    // register myHandler in the default ServeMux
    http.HandleFunc("/", myHandler)
    http.ListenAndServe(":8080", nil)
}
\end{gocode}
\caption{Go web server handler function}
\end{code}

Using functions as function parameters or return types is a commonly used feature in Go, not just
within the standard library. Furthermore, design patterns have emerged within the community
that use functional concepts. An example of this are `functional options'.

\subsection{Functional Options}

The `functional options' pattern has been outlined in Dave Cheney's blog post `Functional options
for friendly APIs'\autocite{functional-options} and is a great example on how to use the support for multiple paradigms.
The basic idea with functional options is that a type constructor receives an unknown (0-n) amount
of options:
\begin{code}
\begin{gocode}
func New(requiredSetting string, opts ...option) *MyType {
	t := &MyType{
		setting: requiredSetting,
		featureX: false,
	}

	for _, opt := range opts {
		opt(t)
	}

	return t
}

type option func(t *MyType)
\end{gocode}
\caption{Constructor with functional options}
\end{code}

These options can then access the instance of \mintinline{go}|MyType| to modify it accordingly,
for example:

\begin{code}
\begin{gocode}
func EnableFeatureX() option {
	return func(t *MyType) {
		t.featureX = true
	}
}
\end{gocode}
\caption{Example for a functional option}
\end{code}

To enable feature X, `New' can be called with that option:
\begin{gocode}
t := New("required", EnableFeatureX())
\end{gocode}

With this pattern, it is easy to introduce new options without breaking old usages of the API.
Furthermore, the typical `config struct' pattern can be avoided and meaningful zero values
can be set.

A more extensive example on how functional options are implemented and used can be found in
Appendix~\ref{appendix:funcopts}.

\begin{quote}
    In summary
    \begin{itemize}
        \item Functional options let you write APIs that can grow over time.
        \item They enable the default use case to be the simplest.
        \item They provide meaningful configuration parameters.
        \item Finally they give you access to the entire power of the language to initialize complex values.
    \end{itemize}\autocite{functional-options}
\end{quote}

While this is a great example of what can be done with support for functional concepts, a purely functional approach to
Go has so far been discouraged by the core Go team, which is understandable for a multi-paradigm programming language.
However, multiple developers have already researched and tested Go's ability to do functional programming.

\subsection{Functional Go?}

In his talk `Functional Go'\autocite{func-go-talk}, Francesc Campoy Flores analysed some commonly used functional
language features in Haskell and how they can be copied to Go. Ignoring speed and stack overflows due to non-existent
tail call optimisation\autocite{go-tco}, the main issue is with the type system and the missing polymorphism.

\subsection{go-functional}

In July 2017, Aaron Schlesinger, a Go programmer for Microsoft Azure, gave a talk on functional programming with Go.
He released a repository\autocite{go-functional} that contains `core utilities for functional Programming in Go'.
The project is currently unmaintained, but showcases functional programming concepts like currying, functors and
monoids in Go. In the `README' file of the repository, he also states that:
\begin{quote}
    Note that the types herein are hard-coded for specific types, but you could
    use code generation to produce these FP constructs for any type you please!
    \autocite{go-functional-readme}
\end{quote}

\section{Verdict}

The aforementioned projects showcase the main issue with functional programming in Go: the missing
helper functions that are prevalent in functional languages and that they currently cannot be implemented
in a generic way.

To make functional programming more accessible in Go, this thesis will research what the most used
higher-order functions are and implement them with a focus on usability.
Furthermore, to learn purely functional programming, a list of rules for pure functional code should
be curated and implemented in a static code analysis tool. This tool can then be used to check
existing code and report constructs that are not functional.