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.
In practice, most functional languages are not pure.
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 can be harder to read (e.g. due to closures or currying).
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 very 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++):
- first-class methods (i.e. methods as arguments and return values),
- a corresponding typing system,
- anonymous methods,
- currying,
- streams,
- etc.
Key notions #
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 (illustration) #
In the exercise above, let us assume that the $f_i$ functions all have type $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ (in other words, they map a pair of natural numbers to a natural number).
Complete the table below with the $g_j$ functions:
| type | 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})$ |
| type | 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$ |