Functional programming is a programming paradigm where applications are composed using pure functions, by avoiding shared mutable state, by avoiding side effects and by being declarative. We can contrast this with Object oriented programming where data and behaviour is colocate. Procedural programming is an imperative style which groups algorithms into procedures that tend to rely on shared mutable state. Functional programming allows to compose functionality using functions. Composition is a simple, elegant, and expressive way to clearly model the behaviour of software. The process of composing small, deterministic functions to create larger software components and functionality produces software that is easier to organise, understand, debug, extend, test, and maintain.
Pure Function and Side Effect
In functional programming, we will be building abstractions with functions. Functions serve as black-box abstraction. In this style we prefer pure functions. A pure function is one which given the same input, always returns same output and has no side effects. Side effect is application state change that is observable outside the called function other than its return value. Some of the ways a computation can introduce side effect are
- Modifying any external variable or object property (e.g., a global variable, or a variable in the parent function scope chain)
- Logging to the console
- Writing to the screen
- Writing to the network
- Inserting a record into a database
- Querying the DOM
- Triggering any external process
- Calling any other functions with side-effects
Side effects are mostly avoided in functional programming, only controlled side effect allowed, we manage state and component rendering in separate, loosely coupled modules.
For example, the below simple function to compute square root of a given number is pure as it gives same output no matter how many times it has been called with an input, it is devoid of any side effect and all computation is dependent on input value and return value.
/* Algorithm: sqrt(2) Guess Quotient (Number / Guess) Average ((Quotient + Guess) / 2) 1 2/1 = 2 (2 + 1)/2 = 1.5 1.5 2/1.5 = 1.3333 (1.3333 + 1.5) / 2 = 1.4167 1.4167 2/1.4167 = 1.4118 (1.4118 + 1.4167) / 2 = 1.4142 1.4142 ... ... */ function sqrt(x) { function average(a, b) { return (a + b) / 2.0; } function square(x) { return x * x; } function abs(x) { return x > 0 ? x : -x; } function sqrt_iter(guess) { return good_enough(guess) ? guess: sqrt_iter(improve(guess)); } function improve(guess) { return average(guess, x / guess); } function good_enough(guess) { return abs(square(guess) - x) < 0.001; } return sqrt_iter(1); } sqrt(2)
On the other hand, consider the below function, checkPrice , it is not pure as it depends on the value minimum which is other than its input.
let minimum = 21; const checkPrice = price => price >= minimum;
One of the important thing to notice that functional style of programming is amenable to equational reasoning. That is, we can replace the the algorithm to compute square root with an equivalent algorithm and since it is a pure function, rest of the program is not affected. Thus it is a black box abstraction.
Another hallmark of this type of programming is avoiding mutation through assignment. Every mutation creates a new value and hence assignment statement is not needed at all.In fact, the seminal book on computing “Structure and Interpretation of Computer Programs” does not use assignment at all!
Name Isolation Techniques
The parameter names passed to a function are unique to that function. The names of the parameters and local names declared inside a function are called free variables. Names of the functions declared inside a function are unique and isolated to that function. The functions sqrt_iter, improve, good_enough etc in the above example are such inner functions. Parameters to the outer function are made available in inner functions. This is called Lexical Scoping .The parameter xof available in all inner functions. Lexical scoping dictates that a name is looked up in its enclosing functions till one is found. A function can also access a variable value outside it but in the lexical scope, even after the outer function has completed execution. This is called a Closure and is a powerful technique of encapsulation employed in functional programming.
Thus a function effectively forms a module, there by achieving information hiding and name space.
Recursion and Iterative Process
Functional style uses recursion instead of explicit looping constructs. We can model recursion to achieve an iterative process for efficiency and tail call optimisation (that is, if the recursive call is at the last position i.e, tail position, stack frame can be reused) makes recursion optimal. For example, below function to compute factorial of a number is not optimal. It results in stack overflow for large value of n.
function factorial(n) { return n == 0 ? 1 : n * factorial(n - 1); }
On the other hand this recursive version where recursion happens at tail position is optimal and is equivalent to a loop.
function factorial(n) { return fact_iter(1, 1, n); } function fact_iter(product, counter, max_count) { return counter > max_count ? product : fact_iter(counter * product, counter + 1, max_count); }
Similarly, every recursive function can be recast to produce an iterative computing.
Higher Order Functions
Functions that manipulate functions – can accept functions as argument or return function as value are called Higher Order Function. Higher order functions serve as a powerful abstraction mechanism. Higher order functions are possible because in functional languages, functions are first class. By first-class, we mean functions are like any other values :
- They may be referred to using names
- They may be passed as arguments to functions
- They may be returned as results of functions
- They may be included in the data structures
In the below example, makeAdder is a higher order function as it returns a function as value.
function makeAdder(x) { return function(y) { return x + y; }; } let plus5 = makeAdder(5); console.log(plus5(10)); let plus10 = makeAdder(10); console.log(plus10(10));
In the below example, Array.prototype.map is a higher order function as it takes a function as argument.
const cars = [ { make: 'Maruti', model: 'Alto', year: 2010, }, { make: 'Hyudai', model: 'i10', year: 2018, }, ]; const makes = cars.map(car=>car.make);
Function Composition
Given two functions f and g which take x as argument, the composition of two functions, f ⊙ g , is defined as g(f(x)) , for functions f, g and h as f ⊙ g ⊙ h as h(g(f(x))) and so on. We can define a variadic function compose in Javascript which performs function composition as described.
const compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x);
Let us define a few functions:
const inc = x => x + 1; const double = x => x + x; const square = x => x * x;
We can define a composition as
let composition = compose(square, double, inc); console.log(composition(5));
which is equivalent to the below function call, but more readable and easy to reason about.
console.log(square(double(inc(5))));
Function composition holds good the mathematical property of associativity, that is
compose(f, compose(g, h)) === compose(compose(f, g), h);
If you notice carefully, function composition takes functions with only one argument. If there are functions with more than one arguments in the composition, we can convert them to one argument functions using a technique known as currying . The concept is simple: You can call a function with fewer arguments than it expects. It returns a function that takes the remaining arguments. When you supply the last argument, the actual computation takes place.
const curry = ( f, arr = [] ) => (...args) => ( a => a.length === f.length ? f(...a) : curry(f, a) )([...arr, ...args]); function sum(a, b, c) { return a + b + c; } console.log(sum(2, 3, 4)); let curriedSum = curry(sum); console.log(curriedSum(2)(3)(4));
Declarative vs Imperative
Declarative programming is way of computing by declaring what something is instead of spelling out how you get it. In imperative programming, we spell out how computation is done in explicit steps via detailed control flow statements. Declarative programs abstract the flow control process (the how gets abstracted away), and instead spend lines of code describing the data flow: that is: what to do. Functional programming, which prefers expressions over statements, uses declarative programming.
Below example of quicksort implementation in Haskell is an epitome of declarative programming
qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x: xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [a | a <- xs, a<=x] larger = [b | b <- xs, b > x]
Consider the below code snippet:
const cars = [ { make: 'Maruti', model: 'Alto', year: 2010, units: 150 }, { make: 'Hyudai', model: 'i10', year: 2018, units: 300 }, { make: 'Hyudai', model: 'i20', year: 2015, units: 150 }, { make: 'Maruti', model: 'Dezire', year: 2012, units: 200 }, ]; // Declarative, functional let totalUnits = cars .filter(car=>car.year >= 2015) .map(car=>car.units) .reduce((acc, cur) => acc + cur, 0) // Imperative let totalUnits = 0 for (let car of cars) { if (car.year >= 2015) { totalUnits += car.units } }
In imperative style, one has to follow along the control flow to deduce what is happening in the code. The operations does not stand out. This becomes problematic in large code bases to reason about the code.On the other hand, in declarative style if one knows the meaning of higher order functions map reduce and filter , the meaning of the program stands out and it becomes that much easier to reason about the code.
Functional Programming is not new
In 1930s, two mathematicians Alan Turing and Alonzo Church produced two different, but equivalent universal models of computation. Both models could compute any function computable by a Turing machine, meaning, given input n, there is a Turing machine that eventually halts and returns f(n). A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. The computation model invented by Church, which is based on function application is called Lambda Calculus. Lambda calculus is the mathematical underpinnings behind functional programming.
Lambda calculus was hugely influential on software design, and prior to about 1980, many very influential icons of computer science were building software using function composition. The programming language Lisp was created in 1958 by John McCarthy, and was heavily influenced by lambda calculus. Today, Lisp is the second-oldest language that’s still in popular use. However, pure functional languages were notorious for being inefficient and hence efficient imperative languages like C grew in popularity. Functional Programming was largely relegated to academic world. But, with the advent of modern computing hardware making functional programs fast enough and functional programming’s ability to tame the complexity of software system caused by shared mutable state, a new interest has been rekindled in FP. Rise of the popularity of Javascript, which is a functional language at its core, has been another reason for the raise of popularity of functional programming.
Indeed, functional programming has become mainstream and it is an interesting time in the area of programming paradigms.
References
- Mostly Adequate Guide to Functional Programming – https://mostly-adequate.gitbooks.io/mostly-adequate-guide/content/
- Structure and Interpretation of Computer Programs — JavaScript Adaptation – https://source-academy.github.io/sicp/
- Composing Software: An Exploration of Functional Programming and Object Composition in JavaScript by Eric Elliott
