Functional programming

Functional programming #

A functional programming language allows writing programs by (primarily) applying and composing functions.

Functional languages include Haskell, ML, Erlang/Elixir, OCaml, Clojure, F#, or Scala.

In contrast, an imperative language (like C/C++, Java, Python, JavaScript, etc.) relies on instructions that modify the state of a program (i.e. the values of variables, objects, data structures, etc.).

Foundations #

Functional programming is rooted in (typed) lambda calculus, a model of computation exclusively based on (anonymous) function composition and application.

Core principles.

  • In a functional language, a method can take a method as argument, and return another.
  • In a pure functional language, values are immutable.

As a consequence of immutability:

  • iteration can only be simulated via recursion (in other words, a functional program has no loop),
  • methods have no side effects.

Benefits and drawbacks #

Potential benefits of functional code (compared to imperative code) are:

  • a more concise syntax (with opportunities for code factorization),
  • less time spent debugging,
  • optimization opportunities (notably lazy evaluation),
  • automatic verification of (some) formal properties of a program.

Potential drawbacks are:

  • more time spent writing code (before it even compiles!),
  • programs that may be harder to read (at least for newcomers).

Usage #

Functional programming is historically linked to academic research. However, over the years:

  • some functional languages (e.g. Scala or Erlang/Elixir) have gained traction in industry, and
  • many imperative language have incorporated functional features: Python, JavaScript, C#, C++, Rust, Java, etc.

For instance, a common “functional” pattern consists in applying an input method to each elements of an input list. This can be written with a very concise syntax in Python, Java, etc.

Besides, immutability is widely advocated as a software engineering principle (in mid-sized to large projects), to simplify debugging.

in Java #

Java 8 (2014) introduced several features borrowed/adapted from functional languages (and previously available in C# and C++):

Other functional features have been introduced since, e.g. pattern matching in Java 16 (2021).

Some older features of Java, like generic types or immutability, are (often indirectly) inspired by functional programming.

Key notions #

We illustrate some standard features of functional languages. For simplicity, we use mathematical functions. This is only a (rough) analogy: in particular, a function type is not a set of mathematical functions.

Anonymous function #

Definition. An anonymous function is a function without a name.

Example. Consider the function

$$f\colon \mathbb{R} \to \mathbb{R} \text{ defined by } f(x) = x^2$$

Another common syntax to define $f$ is

$$f\colon \mathbb{R} \to \mathbb{R}\ ;\ x \mapsto x^2$$

This is (arguably) the same function as

$$g\colon \mathbb{R} \to \mathbb{R}\ ;\ x \mapsto x^2$$

So the name of these function ($f$ or $g$) is in a certain sense irrelevant. They can be both described as the function with domain $\mathbb{R}$ and co-domain $\mathbb{R}$ defined by

$$x \mapsto x^2$$

Function composition, closure and currying (illustration) #

Among the main functions $f_0, .., f_7$ below, identify which ones are equivalent.

main functions auxiliary functions
$f_0(x,y) = x^y$
$f_1(x,y) = f_0(g_1(x),y)$ $g_1(x) = x$
$f_2(x,y) = g_2(x)(y)$ $g_2(x) = y \mapsto x^y$
$f_3(x,y) = g_3(x)(y)$ $g_3(x) = y \mapsto y^x$
$f_4(x,y) = g_3(y)(x)$
$f_5(x,y) = g_5(x,x)(y)$ $g_5(x,y) = z \mapsto x^z$
$f_6(x,y) = g_6(x,y,g_1)$ $g_6(x,y,h) = h(x)^y$
$f_7(x,y) = g_7(g_1)(x,y)$ $g_7(h) = (x,y) \mapsto h(x)^y$

They are all equivalent, with the exception of $f_3$.

Function type (rough analogy) #

In the exercise above, let us assume that every $f_i$ function has domain $\mathbb{N} \times \mathbb{N}$ and codomain $\mathbb{N}$. This can be written $$ f_i\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$ for each $i$.

Complete the table below with the $g_j$ functions:

domain $\to$ codomain functions
$\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ $f_0$ to $f_7$
$\mathbb{N} \to \mathbb{N}$ $g_1$
$\mathbb{N} \times \mathbb{N} \times (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$
$(\mathbb{N} \to \mathbb{N}) \to (\mathbb{N} \times \mathbb{N} \to \mathbb{N})$
$\mathbb{N} \to (\mathbb{N} \to \mathbb{N})$
$\mathbb{N} \times \mathbb{N} \to (\mathbb{N} \to \mathbb{N})$
domain $\to$ codomain functions
$\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ $f_0$ to $f_7$
$\mathbb{N} \to \mathbb{N}$ $g_1$
$\mathbb{N} \times \mathbb{N} \times (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$ $g_6$
$(\mathbb{N} \to \mathbb{N}) \to (\mathbb{N} \times \mathbb{N} \to \mathbb{N})$ $g_7$
$\mathbb{N} \to (\mathbb{N} \to \mathbb{N})$ $g_2$ and $g_3$
$\mathbb{N} \times \mathbb{N} \to (\mathbb{N} \to \mathbb{N})$ $g_5$