Welcome,
In this bref article, I will introduce you some basic knowledge about Functional Programming, along with some examples and use cases in scala. But if you are not interested in scala or you prefer to use another language you can just focus on the basic concepts and you can search the implementation after in your own language.
So let's begin with a definition:
1) What is Functional Programming?
Let's take a look in Wikipédia:
"In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that each return a value, rather than a sequence of imperative statements which change the state of the program or world."
As you can see there is some highlighted terms which are essential for the definition,
First, Functional programming is a programming paradigm, means a style or a set of rules to write code, and it’s a declarative paradigm, what that means?
Well, for ages we used to write an imperative code, in which we write sequence of instructions (statements) to solve the problem, and that has a background from the Von Neumann computer architecture and how the machine executes our code instruction by instruction, put that data in memory, read that one, etc..., so we focus on how to solve the problem with one function or a procedure?
Let’s take an example, suppose that we have an array of integers and we want to extract an array of even numbers out of it.
In usual imperative approach, we do something like that, loop through the list, and each time we find an even number we save it into out newly created array. (code below)
So we define the full engineering of the solution in one function.
What about Declarative approach?
We can do the same in just one line of code.
As you can see we break our solution in a bunch of functions and we chain them, (here, filter function that get an anonymous callback). So here we define what we want to do first not how, and in result the code expresses itself from the first glance.
Besides this, FP has some other principles like Purity and immutability, we will explain that further in this article.
2) Origins Functional Programming
The functional programming has it’s basis from the lambda calculus..., Lambda what?! 😕
Lambda calculus is a computation model developed by the mathematician “Alonzo church” in the 30s, and it combines between the abstraction of a problem in form of functions, and the application of these functions or the computation of the problem.
Here we have an example, it’s the identity function,
λx. x
So the character besides the lambda symbol is the parameter (or the binding), the part after the “.” (point) is the core of the function.
In lambda calculus system, everything is a function (from the mathematical perspective) and Each lambda expression can be one of the following forms,
- a simple variable (a constant function) example: x or 2
- λx. M : a function or un abstraction (binding + the core),
example:
λx. x + y * 2
- M N : An application (an abstraction concatenated with another expression) in this case we can apply that expression (the N part) into the first abstraction (M) as we can see next.
example:
(λx. x) λy. y + 1 // M = λx. x, N = λy. y + 1
Beta Reduction
In lambda system we have what we call it beta reduction, it’s simply like executing the function for what it comes after it.
Let’s take an example:
λ x.x 2 -β-> 2
we have lambda x.x 2 so we apply 2 on the function we get 2.
Another example:
(λx.λy.y x)(λz.u) -β-> λy.y(λz.u) -β-> λz.u
So as you can see we have a system calculus system that is very straightforward and proved by mathematicians,
Without further details, Keep in mind !, the equivalence of a lambda expression in the programming languages is the anonymous function with a single argument. example the increment() function.
λx. x+1 ==> x => x+1 (Scala)
3) Main Principles of FP
Functional Programming has two main rules:
Purity + Immutability
Rule 1: Purity, "All functions must be pure"
What is a pure function?
Well, it’s a function that gives you always the same return value for the same arguments, like the following add() function, which calculates and returns the sum of 2 numbers (you may be saying, well that sounds ridiculous! why should a function gives me something I didn’t expect, well I will tell you why?)
def add(a: Int, b: Int): Int = a + b
There’s a principle called “referential transparency” and it’s inherited from the declarative paradigm. It says that for each possible input value if we can replace the function call inside a program by it’s assumed value, we don’t change the whole behavior of that program so this function is referential transparent and thus it’s pure,
(More about referential transparency: https://www.sitepoint.com/what-is-referential-transparency/)
If you don’t bother yourself with those theoretical aspects, keep this in mind: “A pure function is a function with no side effects”
Here we have some examples of side effects:
- First one, a function “counter” that uses a global variable. That’s not allowed in Pure FP because the result of this function doesn’t depend only on its parameter so it may give us different results for the same input!
- Another form of side effects, the operations that may fail at any time, like making an input/output operation, a database operation, an http call a logging to the command line system … etc.
But you may be wondering, so how can we make this kind of work with FP way? well the answer is not that simple 🤓, and we will see how in the next article.
Rule 2: Immutability, "No to state mutability (No variables)"
In functional programming like in maths, we don’t change the value of variables, instead we create new instances as much as we need.
var a = 2
a = a + b
Here we declared a variable a, and then we changed its value by adding b, that’s not allowed in FP.
Instead, we create a new variable “c” and we affect the new result to it,
val a = 2
val c = a + b
( In scala, because it’s a multi-paradigms language, it allows us mutate the value of a variable but it must be var not val, when we use val it’s like a lock to the variable to prevent future changes)
But you may ask me why should I care about that I have the same result anyway 😕, well, there is at least 3 reasons for that:
- Changing value => memory access => side effects
- Clean code like algebra ex: val c = h(g(f(x)))
- Another very important reason is that Mutating state is not good for parallel processing ex: multi-threads share the same variable.
... Next, you may say "OK no mutating state, only constant values, but how can I make a loop?", well that’s a good question
And the immediate answer will be: Use Recursion. And simply recursive function is a function that calls itself for different input values.
It’s true that recursion is more complex for programmers and more performance consuming then loops, but the functional programming languages are designed to simplify that and optimize the generated code machine to fit the needs, So all good ;)
Here’s an example, we want a function that returns the product of a list of numbers. If we do it, the old way: it may look like that, a test for empty lists, the a loop through the list, to calculate the product,
simple hein? 🤓
Now let’s do the same with pure functional Scala:
You may not understand the code if you are new to scala, it’s a pattern match that allow us check the form or the type of the input list, called “ints”, it’s like a switch but on Type, and Nil is a subtype of List which represents the empty list. x :: tail means x: the first element, and tail, the rest of the list , and finally we have that recursive call.
Sexy hein?! 🤓
(Be carful!, this kind of recursive functions may throw a StackOverFlow error if the list is too big, because it’s not a tail recursion. For more about tail recurtion https://alvinalexander.com/scala/fp-book/tail-recursive-algorithms/ )
__________
We came to the final part of this overview artcile and we will speak about Higher-Order Functions:
Higher-Order Functions
A higher-Order function is a function that takes other functions as parameter or it returns a function.
Example : we have an anonymous function that checks whether a number is even or odd, then the filter function takes it as parameter, and finally the increment function returns the add 1 function.
In FP that’s very helpful for mapping, filtering and for other operations that need a callback
In the next articles of this series, we will talk about Type system in Scala, Laziness and Streams, FP structures like Monads, Tail recursion, how to deal with side effects and much more… So stay tuned.
And if you liked this one don’t forget to keep a thumb up and if you have any question, a remark or anything so please let me know in a comment, be sure that read it 😉
See you soon.