Functional Programming Paradigm

Functional Programming Paradigm is a sub-paradigm of Declarative Programming Paradigm. It is based on Lambda Calculus developed by Alonzo Church in the year 1930. Lambda Calculus is purely mathematical and has the same computational capabilities of Turing machine. Turing machine was also proposed around the same time. It was in 1937, Alan Turing proved that Lambda Calculus is Turing complete. In this post, I’ll be covering the core concepts of Functional Programming.

Functions – The first-class members

In functional programming, functions are the primary programming construct and so, they are the first-class members. They can be,

• Passed to another function.
• Returned by a function.
• Declared to a constant or variable for usage later.

Functional Programming Paradigm has it’s roots in mathematics. In this post, I will explain it through mathematics for more context and better understanding. The mathematics part is optional, you can understand even without reading through this section.

Functions in Mathematics

Checkout this page, it gives a more information about what is a function in mathematics. The below are some properties of mathematical functions.

• Mathematical functions are declarative.
• If you call a math function f(x), for the same input, it will always return the same output.
• Objects in mathematics are immutable.
• Mathematical functions are stateless.
• Mathematical functions always return a value.
• Complex function can be divided into several smaller functions. These smaller functions can be chained to get the final result. This is functional composition.
• Can have higher-order functions.

Let’s discuss the above properties further.

For a same input, it returns the same output

Let’s consider the below mathematical function for example.

f(x) = x * 5

No matter how many times the function f(x) is called, for the same input x, the output will always be x * 5. If x is 2, the output is always 10.

What does it mean?

The function f depends only on the variable x. There are no other outside variables in play that f is dependent on. There is no concept of having an global variable that can alter the output of the function. This means, functions are also stateless and says no to side-effects.

Referential Transparency

Since, f(x) always returns the same output for the same input x, all mathematical functions are referentially transparent. A function is referentially transparent when it can be replaced with it’s computed result and this change doesn’t affect the end result.

f(x) = x + 1
g(x, y) = f(x) * y

g(1, 1) = 2 * 1 = 2
g(1, 2) = 2 * 2 = 4
g(1, 3) = 2 * 3 = 6

In the above example, for x = 1, f(x) will yield 2 at any given time. If we replace f(x) with 2, it will still continue to produce the same output.

g(y) = 2 * y

g(1) = 2 * 1 = 2
g(2) = 2 * 2 = 4
g(3) = 2 * 3 = 6

This is Referential Transparency.

Immutability

At any given context, the objects used in a function is always immutable. Let’s consider the below mathematical function for example.

f(x, y) = x + y

The above function is mathematical notation of a sum function. For any given inputs x and y, the function calculates the sum and returns the result. It doesn’t alter the values of x and y.

Always return a value

In mathematics, a function is a mapping of sets. To understand this more, below I have summarized about mathematical functions with points taken from here.

Sets in mathematics is a collection of things of same types. For example, collection of even numbers can be a set. This set will have only even numbers and doesn’t have anything else. We can say that the domain of this set is even numbers.

A mathematical function relates each element with exactly one element of the same given set.

f(x) = x * x

In the above example, when x = 2, the output is 4. 2 and 4 are of same set. The function doesn’t produce more than one outputs.

A function without a return value is of no use in mathematics. What am I going to do with x * x if I don’t get the result back?

If a function doesn’t return a value, then the domain of the function is an empty set. A function returning a value of empty set simply cannot exist.

For example, the function f, when applied to a set of even numbers, will return a result from the same set and cannot return a result from an empty set.

Functional Composition

In simple terms, functional composition is applying the result of one function to another function.

f(x) = x * x
g(x) = x + 1
// functional composition can be
h(x) = g(f(x))
// This function call will be executed as ((x * x) + 1)

In the above example, there are three functions f(x), g(x) and h(x). Calling h(x), will execute the function f first and then executes g with the result of f. This is functional composition.

Higher-Order function

Functions that operate on other functions by taking them as input or returns a function as output are called Higher-Order Functions. The function g in the previous example is a higher-order function when g(f(x), y) is called.

Now, enough with math. Let’s continue with functional programming.

Functional Programming

Functional Programming have mathematical foundation and mimics the nature of mathematical functions. For a function, the above mathematical natures are applicable.

Any mathematical function is a pure function in functional programming. But not all functions in functional programming can be mathematical functions.

Let’s discuss the core concepts of functional programming.

Pure functions

A function is pure when it strictly follows the below two rules.

• For the same input, it will always return the same output.
• Has no side-effects

For a same input, it returns the same output

This is the same as what we discussed for mathematical functions here. Let’s see the below example.

const square = (x) => x * x;
square (2) // returns 4.

In the above example, when we call the function square for any number of times with x = 2, it always returns 4. Hence, it is a pure function.

const randomize = (x) => x * Math.random();
randomize(2) // returns a random number each time.

In the above example, when we call the function randomize with x = 2, for every time we call this function, we get a different output. This is because, the function internally depends on Math.random(). This is an impure function.

Has no side-effects

For a function to be pure, it should not have any side-effects. A side-effect occurs when variables that are outside a function’s scope is referred it, resulting in unpredictable results.

let state = 1;
const add = (number) => state = state + number;
add(2) // updates value to 3.
add(3) // updates value to 6.
add(4) // updates value to 10.

The above example is an impure function. Every time when add function is called, the value of the variable state is mutated.

const add = (number, state) => state + number;
add(2, 1) // returns 3.
add(2, 1) // returns 3.
add(3, 1) // returns 4.
add(4, 1) // returns 5.

The above example is a pure function. Here, no global states are available.

Variables and Assignments

In a pure functional program, variables are immutable. In other words, a variable is only initialized once. Variables are only used as function parameters. A caller function passes down value to the callee function using parameter variables. In a function, the parameter variables cannot be reassigned. There is no assignment in functional programming. Any variables initialized inside a function is an immutable constant.

Okay.. but how are values calculated without using variables? 🤔

Pure functions simply copy the variables and calculate the new values.

const initialArray = [1, 2, 3, 4, 5, 6];
const predicate = (value) => { return value % 2 == 0};
const finalArray = _.filter(initialArray, predicate);
console.log(initialArray);    // prints  [1, 2, 3, 4, 5, 6]
console.log(finalArray);      // prints  [2, 4, 6]

For the above example, I have used Lodash, one of my favorite libraries. The filter function copies the value of initialArray, executes the predicate function on each value of initialArray, creates and returns a new array, which I assign to finalArray. Here, initialArray is not mutated but copied through the execution to create a new array.

Functional Composition

In pure functional programming, execution is based on structured function calls. A function calls other function which calls another one and this goes on. Each function can get values from other functions and returns it’s result to it’s caller. Let me try to explain this better with the below example.

const notDivisibleByThree = (value) => {
    return value % 3 != 0;
};
const notDivisibleByTen = (value) => {
    return value % 10 != 0;
};
const operate = array => array.filter(notDivisibleByTen).filter(notDivisibleByThree);

operate([1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 55, 42, 23, 17, 13])
// output is [1, 2, 4, 5, 55, 23, 17, 13]

Here, I want to filter the numbers which are divisible by 10 and 3 from a given array. In the line array.filter(notDivisibleByTen).filter(notDivisibleByThree), I call filter function twice chained one after the other. This means, that the first filter will operate on the variable array and returns a result array on which the second filter function operates. The result of the first filter function is input for the second filter function. This is functional composition.

Order of execution

For a pure functional program, execution of functions can be out of order. This is mainly because of it’s immutability and ability for not having side-effects. Let me leverage the previous example.

const notDivisibleByThree = (value) => {
    return value % 3 != 0;
};
const notDivisibleByTen = (value) => {
    return value % 10 != 0;
};
const order1 = array => array.filter(notDivisibleByTen).filter(notDivisibleByThree);
const order2 = array => array.filter(notDivisibleByThree).filter(notDivisibleByTen);
const array = [1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 55, 42, 23, 17, 13];
const array1 = order1(array);    // returns [1, 2, 4, 5, 55, 23, 17, 13]
const array2 = order2(array);    // returns [1, 2, 4, 5, 55, 23, 17, 13]

Here, both the functions order1 and order2 calls filter functions in different orders. But the result of both the functions are same.

Though there are some orders required for a program to execute, the change in the orders doesn’t affect the end result. This is one of the strength of functional programming.

Recursion

Functional Program uses recursion for repetition. If you are familiar with Imperative Programming paradigm, we use loops for repetition. Recursion is functional program way of repetition. Recursion is when a function calls itself until it cannot anymore. To exit recursion, it is must for the function to have an exit condition.

Why not loop though?

Functional program is stateless and the variables are immutable. So, same variables cannot be re-assigned with different values to alter the state of iteration. In recursion, the variables in each function call is specific and available only to itself. I really want to explain this further using call stack but that is a topic for another post.

Let’s consider a common example for recursion. I want to write a program to compute sum of a range of numbers.

function compute(n) {
    let total = 0;
    for (i = n; i > 0; i--) {
        total = total + i;
    }
    return total;
}
compute(6); // returns 21.

The above example is not a functional approach. I used for loop maintaining a state in variable total. Let’s do it with recursion in functional style 😎

function compute(n, total) {
    // exit condition
    if (n <= 0) {
        return total;
    }
    return compute(n - 1, total + n);
}
compute(6); // returns 21.

The above function is recursive. The function compute calls itself until the exit condition is met.

Is the state altered by assigning new values for n and total?

No. On each call, the function compute will maintain a different context, i.e., each function compute in the recursion will have it’s own version of the variables n and total.

compute(6, 0) // recursive call 1, n is 6, total is 0. These are specific to call 1.
compute(5, 6) // recursive call 2, n is 6, total is 0. These are specific to call 2.
compute(4, 11) // recursive call 3, n is 6, total is 0. These are specific to call 3.
compute(3, 15) // recursive call 4, n is 6, total is 0. These are specific to call 4.
compute(2, 18) // recursive call 5, n is 6, total is 0. These are specific to call 5.
compute(1, 20) // recursive call 6, n is 6, total is 0. These are specific to call 6.
compute(0, 21) // meets exit condition and exits.

Higher-Order Functions

This is same as what I explained previously for mathematical functions. Functions that operate on other functions by taking them as input or returning them as output are Higher-Order Functions. Let’s see this in detail.

Operating on other functions

One of my favorite function that operates on other function is the map function. The map function operates on an array or object, transforms each operation based on the transformation function passed to it. The result is an array or object with the transformation applied.

// Let's multiply each element of a given array by 2.
const multiply2 = (value) => {
    return value * 2;
};
const compute = array => array.map(multiply2);
compute([1, 2, 3]); // returns [2, 4, 6]

In the above example, the function map operates on another function multiply2.

Returning another function

Let’s try to write a function that would return another function. For example, I’m going to write a function that would compute the multiple of 2 of the given value.

function compute() {
    return (value) => {
        return value * 2;
    };
}
compute()(1); // returns 2
compute()(2); // returns 4
compute()(3); // returns 6

The above function compute returns another function which computes the multiple of 2 of the given value.

Partially applied functions

A partially applied function is created from a higher-order function with more than one arguments, by applying some of the arguments.

function add(value1) {
    return (value2) => {
        return value1 + value2;
    };
}
add(1)(2) // returns 3

Is the above function add a partially applied function? No. The above function is a higher-order function. Let’s make it a partially applied function.

function add(value1) {
    return (value2) => {
        return value1 + value2;
    };
}
const incrementBy3 = add(3);
incrementBy3 (2) // returns 5

In the above example, function incrementBy3 is a partially applied function. It takes a higher-order function add, partially applies arguments add(3) to create the function incrementBy3. We can now use incrementBy3 whenever we need to increment a value by 3.

Currying

The example we saw for Partially applied functions is currying. Currying is the process of breaking down a higher-order function to partial applied functions till we are left with unary functions. An unary function is a function that has only one argument. Let’s use the same example as from above.

function add(value1) {
    return (value2) => {
        return value1 + value2;
    };
}
const incrementBy3 = add(3);
incrementBy3 (2) // returns 5

We broke down the higher-order function add to an unary function incrementBy3. This is currying.

Referential Transparency

Just like the referential transparency in mathematical functions, pure functions are also referentially transparent. A function is referentially transparent when it can be replaced with it’s computed result without affecting the end result. Let us consider the below example.

const square = n => n * n;
const compute = (a, b) => (a + b) * square(2);
compute(2, 3); // returns 20

In the above example, let us assume that we get a client requirement where we have to apply the formula (a + b) * 22. We created a function square to compute the square of 2 in this formula. Being a pure function, for same input, the function square will always yield same output. Hence, here I can replace this function directly with it’s computed value 4.

const compute = (a, b) => (a + b) * 4;
compute(2, 3); // returns 20

Even after replacing the function with a direct value, the computed result is still the same 20. This is Referential Transparency.

Benefits of pure functions

Readability

Pure functions are easy read and understand.

1. It is stateless, there are no state altering variables outside of the function to worry about.
2. All the required inputs are passed as parameters.

All these properties make it more readable and understandable.

Debugging

In paradigms such as the Imperative Programming Paradigm, side-effects are problematic during debugging since it makes the program unpredictable. Without side-effects in functional programming, there are no states that could make the program unpredictable.

Testing

For a function to execute, we would be providing all the required data as input variables. When testing, we can test each function with different versions of inputs without maintaining any global state. It gives us more control in testing.

Memoization

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Wikipedia

The above definition from the mother of all truth provides a clear understanding of what is Memoization.

So how is it possible in functional programming?

So as I mentioned throughout the post, a pure function, for same inputs will always return same output. Consider a scenario where we write a big algorithm in functional style. Lets say that this algorithm consumes time and resources to execute. Frequent usage of this algorithm might result poor performance. Here we can bring in memoization. The advantage of this algorithm is being a pure function, it will return same output for the same inputs. We can cache the outputs mapped to the inputs. On invoking the algorithm, if the inputs were cached ear, we can return the output from cache without executing the algorithm.

Lazy evaluation

Lazy evaluation is one of the strength of pure functions. A pure function evaluates an expression only when it is required.

const increment = (a, b) => a + 1;
increment(1, (2 + 3)); // returns 2

In the above example, the function increment gets two input parameters a and b but uses only a. In the next line, we pass the expression (2 + 3) for the param b. The compiler does procrastinates the execution of (2 + 3) until it is required. This is lazy evaluation.

Parallelization

1. Immutability
2. Being stateless
3. No side-effects

The above properties of a pure functions makes it an ideal candidate for parallelization. All these properties makes each function to run independent of each other. Since there are no global states, one function doesn’t affect the other when run in parallel.

Disadvantage of functional programs

One of the notable disadvantage is the memory usage. While immutability and being stateless provides advantages to functional program, they lead to it’s disadvantage as well. When there is a function with high depths of recursion or simply, there are many number of functions in action during execution, immutability results in creation of many objects to store variables. This would increase the memory usage during execution. In paradigms where side-effects or states are allowed, a single variable can be reused.

Functional programming support in our computers

So do our computers support functional programming?

No. It does not because our processors are stateful and imperative in design. In a larger picture, computers are a state machine, any execution of a program will change it’s state from one to another. More on this in my post about Von Neumann Architecture.

Then how does it run functional programming?

The compilers takes care of that part. The compiler will convert the functional program to imperative machine language understandable by the processor. To run a functional program, we do not have to create processors specific to functional programs. What we need are good compilers.

---

I hope this post was helpful 😊. If you find this post informative, support us by sharing this with fellow programmers in your circle 😀.

For any suggestions, improvements, reviews or if you like us to cover a specific topic, please leave a comment.
Follow us on twitter @thegeeksclan and in Facebook.
#TheGeeksClan #DevCommunity