Functional programming

167
5

Eventually I'm going to start several functional programming tutorials. Functional programming paradigm feels weird for those who meet it for the first time. That's why a short introduction should be given so I don't need to repeat myself for every tutorial set. This article won't teach you any functional programming language. Instead, this article is what you should read before you start learning any functional programming language.

So, you're familiar with imperative programming like C++, JavaScript, Java or C#. Imperative programming, simply put, is a list of commands. Execute this, then execute this, then this, then that. Functional programming, on the other hand, is a set of expressions.

Today there are not much programming languages which stick within a single paradigm. Instead, most of the languages offer multiparadigm approach. For example, JavaScript isn't pure functional programming language, however you can do some functional programming with JavaScript pretty fine.

Code examples in this talk are given in JavaScript, which isn't essentially functional. Some things may look too boilerplated, but don't worry. It's just to show you the idea in some familiar programming language. In real functional programming language same operations are written in a much cleaner and compact way.

So, imperative programming is “What should be done” while functional programming is “How do you express things by other things”. A short example:

function brick_volume(width, height, depth)
{
return width * height * depth;
}

This is not a complete program which you can build and run. This is “How do you express things by other things”, or, in this particular case, “How do you express brick volume by its width, height and depth”. Now, having an expression of brick volume, we could express something else with it:

function brick_volume(width, height, depth)
{
return width * height * depth;
}

function wall_volume(bricks)
{
return bricks.reduce((volume, brick) =>
{
return volume + brick_volume(brick.width, brick.height, brick.depth);
});
}

Now we've expressed volume of a wall by volume of bricks it consists of. So, in functional programming you write functions to express things. Pretty easy so far. Though, there are some specific on how you do that.

Immutability

In functional programming everything is immutable. You can't modify a variable which already has a value. So the word variable may sound confusing since its value not really vary. Why everything is immutable and what's the point?

Before discussing well-known advantages of immutable approach, consider this. In functional programming you don't just write functions, you write expressions. You express things by other things. You don't need to modify something when you express circle area by its radius, right? You just need to declare how you express something by something else. So, in functional programming functions shouldn't be considered as subroutines. Insted, you should consider them as description of relationship between things.

When everything is immutable, what does it bring?

• The global state is also immutable, so it is the same as there's no global state at all;
• Thus, function call doesn't have side effects;
• Which means function call with the same arguments gives the same result;
• Which means you can call functions in any order;
• Which also means you can call functions concurrently.

When everything is immutable, things are looking much cleaner, consistent and predictable.

Mutability

— What's the point of a program which can't modify a thing? — you may ask.

Well, something is still mutable. You can read and write data from or into a file as always. You can send or receive a data packet from or into a network socket as always. You can output some text or render some graphics on your display. Immutability doesn't apply to the external world.

In functional programming everything is immutable by default, except some special cases. On the other hand, in imperative programming everything is mutable unless something is explicitly declared as immutable.

— But I NEED mutable state! Real life program isn't some circle area function! — you may say.

Well, yes. Assume you write a video game and your hero moves around some map. You hero has some coordinates, and these coordinates should mutate.

In functional programming approach instead of modifying an existing object, you create a new one:

function createHero(name)
{
const hero =
{
name : name,
position : new Vec2(0, 0),
velocity : new Vec2(0, 0)
};

return hero;
}

function update(hero, dt)
{
const nextHero =
{
name : hero.name,
position : new Vec2
(
hero.position.x + hero.velocity.x * dt,
hero.position.y + hero.velocity.y * dt
),
velocity : hero.velocity
};

return nextHero;
}

Function update is how you express “hero after dt” by the current hero and the value of dt. You declare how future hero related with the current one.

— Isn't it inefficient to create a copy of an object each time we want to modify it? An object could be big. — you may ask.

No, it's not. In functional programming languages this procedure is higly optimized. Internally it may reallocate just a small portion of a data required, or event don't allocate at all, modifying existing data instead.

— Allright, we create a new object instead of modifying an existing one. But what's next? We need to store this new obejct somewhere, and to store — means to modify. — you will reply.

Yes, and there are two common approaches. The first one is when you don't implement top-level event loop, and the second one is when you do.

Sometimes you don't implement the whole program entirely in functional programming language. Sometimes all you have to do is to implement handling of application events. So, basically, you write a function which takes current application state, event type and its arguments, and returns a new application state. Something like we do above when we updated a hero. In that case all mutability happens somewhere out there, outside of your functional code. For example, in JavaScript on the browser's side you don't control the event loop, you just handle events.

So, what's about the case when you have to implement the event loop by yourself? In functional programming you don't write loops. You write tail recursion instead.

Simply put, it looks something like that:

function dispatch(state, msg)
{
switch(msg.type)
{
case someMessageType:
// ...
return someNewState;

case otherMessageType:
// ...
return otherNewState;

case ...:
// ...
return ...;

default:
return state;
}
}

function loop(state)
{

const newState = dispatch(state, message);

loop(newState);
}

function main()
{
const initialState = ...;

loop(initialState);
}

— Wouldn't an infinite recursion cause stack overflow? — you may ask.

No, it's not. In functional programming languages a tail recursion is optimized in such a way so under the hood it is built as a usual loop.

— So, we operate on objects like if they're immutable, but under the hood they're implemented in a mutable way. We write tail recursion like if there's no mutable state and stack size is infinite, but under the hood they're implemented as a mutable state and a real loop instead of a recurtion. So what's the point? — you may finally ask.

There is manual memory management somewhere inside garbage collector. There is resource acquisition and disposal somewhere inside RAII. There is a mutex somewhere inside threadsafe message queue. In the same way there are mutability and loops somewhere inside functional programming. We build new features and technologies on top of the old ones. We move away potentially dangerous facilities and build a better ones on top of them. There is still a mutex somewhere inside a message queue, however you can't lock it directly, so you can't get deadlocked while working with a message queue.

In the same way functional programming is a higher level technology. We consider mutablility and global state as dangerous things, so we move them away, and build a new immutable stateless technology on top of them. Functional programming is how you write code and what guarantees you get by default.

So...

So, functional programming is better than imperative one? Erlang is better than C++? Haskell is better than Java? Well, that's not so simple. Today I just wanted to give you an idea of functional programming: what it is and how it works. There are different pros and cons which are out of scope of today's talk. Somewhen we will discuss them in details.

Rate this post: