What is functional programming?

I'm planning on doing a couple of posts on the language Elm and why it may be better than JS, but to fully understand what happens in Elm you need to know some things about the functional paradigm - a clean view on what programming is, designed with mathematical perfection.

Functions

Functions everywhere.

As the name implies functional programming is all about functions. Everything is done using them, and applying the function to a parameter is the fundamental operation. In imperative languages like Python, C++ or JS, to apply a function foo to x you use parenthesis: foo(x), but in functional languages it's sufficient to write the function next to the value: foo x. Parenthesis come up when applying a function to another function's result. For a bigger example:

# Imperative:
foo(x, bar(y), baz)

vs.

-- Functional:
foo x (bar y) baz

This syntax is cleaner and more readable when most of the program is function application: not even commas are required to separate arguments.

Everything in the functional paradigm is a function. Even normal operators like + or * are considered functions. In most functional languages you can put parenthesis around them and apply them like any other function:

(x + y) = (+) x y
(x * y) = (*) x y

Functions can be passed as arguments and assigned to variables. This allows for some powerful operators that I will discuss in later posts.

Purity

No side effects allowed

Functional languages deal with pure functions, which are not allowed to alter any internal or external state. This means a pure function's output can only depend on its inputs, not on time of execution or randomness. It can also not affect outcomes of other operations in any way other than through returning values.

This may seem as overly restrictive: after all the screen is an external state, and how are we supposed to write an application that doesn't depend on time? Most functional languages have their mechanisms for dealing with those problems, usually behind the scenes, without introducing impurity to the programmer's code.

Purity has its benefits: a pure function for a given input will always return the same output, so there may not be a need to recalculate it later. The execution of a part of the program never depends on anything outside of it. This opens opportunities for optimizing compilation and makes thinking about code way easier.

Strong Types

Like in C or Java, but good.

Another property of most functional languages is that they are strongly typed. What this means is that all data flowing through the program has to be assigned a type, like String or Int or Float. Every value traveling along some path in the program has to always have the same type.

In languages like C++ or Java this leads to a ton of unnecessary type annotations that are annoying and obscure the meaning of the code. In functional programs types can almost always be inferred from their surroundings, lifting the burden of attaching labels to everything from the programmer.

Type inference means that from knowing what type the basic literals are (like 21 or "Hello"), and what types the basic operators take and return the compiler can reason about types of other values and functions, in theory requiring almost no type annotations. It's still a good practice to annotate your function definitions so that the compiler can warn you when the type you want doesn't match what is inferred.

Algebraic types

We need to go deeper...

In imperative languages data types reflect how a value is stored in computer memory: int is a four byte number, string is an array of bytes and float is a floating point number as described by The Standard. In functional languages data types reflect what the value represents. You have basic types that all have some implementation-defined representation in memory, but you can also define your own types, usually on top of existing ones.

Types are defined with constructor functions. For example Boolean may be defined as:

type Boolean = True | False

This means the Boolean type can be constructed by either True or False constructors. Neither of them take any arguments, so they always return the same values which can later be interpreted as "true" and "false". A more complex example that uses arguments is:

type Webpage
  = Loading
  | Loaded Html
  | LoadingError String

This represents the fact that a Webpage may be one of three:

• Loading, in which case no additional info about it is available,
• Loaded, in which case it has a value of type Html to display,
• LoadingError, in which case there's an error message available describing what went wrong. This allows for precise modelling of what your data means and can possibly be.

Pattern matching

Elegant conditionality

Algebraic types naturally represent options available to a given value, so the most used conditional construction in functional programming is one that branches based on the constructor. The usual syntax looks like this:

case value of
  Some pattern -> result
  Other pattern -> different result

Going with the Webpage example we could construct a function that takes a Webpage value and returns a rendered view like this:

renderPage : Webpage -> Rendered
renderPage page =
  case page of
    Loading -> renderText "Loading..."
    Loaded html -> renderHtml html
    LoadingError message -> renderText message

This may be a bit to take in, so let's go through it line by line:

• renderPage : Webpage -> Rendered
  This is how type annotations look like for functions. renderPage is a function that takes a Webpage and returns Rendered.

• renderPage page =
  Start of the function definition. page is the function argument.

• case page of
  Start of a case expression.

• Loading -> renderText "Loading..."
  If page was made with the Loading constructor display the loading text.

• Loaded html -> renderHtml html
  If page was made with the Loaded constructor render it's parameter as HTML.

• LoadingError message -> renderText message
  Finally if page was made with the LoadingError then display the error message.

You can see how a case expression can be used to deconstruct the value and assign its contents to variables (html and message in the example). This way of branching can also make sure that the program never breaks, because every possibility has to be accounted for. Any errors have to be explicit (like LoadingError in the example) and passed around openly as values.

Sidenote: Type theory

Very rough explanation.

Algebraic data types are such a powerful concept that you don't need any builtin types to make programs. You can define numbers and lists and operate on them without referencing any existing types. I have already shown the easiest example, the Boolean type, but let me explore this further.

The second simplest example is natural numbers. If you think about it, any natural numbers can be defined as either zero, or a successor of some other number. This translates to:

type Nat = Zero | Succ Nat

This type is defined recursively, which lets us define an infinite amount of numbers with a finite set of symbols. With this whenever you encounter a number you can split the logic into two cases: a simple one when the number is zero, and a recursive one when it isn't. For example addition would work like:

add : Nat -> Nat
add x y =
  case x of
    Zero -> y
    Succ x' -> add x' (Succ y)

When adding zero to y the answer is just y, and when adding a successor of something the Succ can be "moved" to y, decreasing x which guarantees that it finally reaches the base case.

As a closing remark I will add an example of a List type with a map function that transforms each element of the list. This example has some more advanced notation, so don't worry if you don't get it.

type List a = Empty | Cat a List

map : (a -> b) -> List a -> List b
map func list =
  case list of
    Empty -> Empty
    Cat head tail -> Cat (func head) (map func tail)

Conclusion

I'm back to writing!

I hope this gave you a vague idea of what you could stumble upon when dealing with functional languages. If you want some more concrete and in-depth examples look forward to my series on the programming language Elm. I barely have any formal education in functional programming and category or type theory, so if you spot any mistakes please notify me in the comments. See you soon!