I really am not the best person to author such an article (I am not that into programming anymore, and I never was a real expert in it), however I am doing it, because I have been waiting for someone else to write it for years and kept noticing the following phenomena:

1. People who understand functional programming, cannot make themselves understood by the general (programming) public.
2. Many of the people who are able to make themselves understood by the public, don’t understand enough for them to be worth listening (all functional programming articles that are understandable don’t go much farther than “You should use pure functions, man!”.

Roughly the same thing has been called “the curse of the monad” by some people: “Once you understand it, you lose the ability to explain it”. It is clear now that monads are not something you get in an afternoon, but I think you can get some idea of what FP (functional programming) is. Or, you know, in a year or so. But in order to spend that time you need some motivation. You probably need someone to tell you why exactly do you need to know about FP? Why is it awesome, so to say. And so my article begins.

Before starting, keep in mind that you need a clear mind to understand FP. So for a second forget everything that you know about programming paradigms. Forget the Object Oriented religious bullshit, that you learned at school, or by reading different versions of the same blog post. Forget the old timers, who think that if they don’t have all the power at their fingertips at all times they are not as productive as they can be, forget, even, the academic type of programmers (and the beefs between the said groups).

It is important to start from the beginning. So what is functional code? It is code that can be reasoned about. This phrase is often repeated but rarely explained. When you know what a program does just by looking at it (and it really does exactly that), this is functional programming. When you don’t need to trace where and under what circumstances a given function is called in order to work around the possible states of a given system, that is functional programming. When you can boost the font of your text editor up to the point where only a few lines are visible and still do your job, that is functional programming. All other things that people usually talk about, including the ones that I talk about here, are just a result of our desire to do that.

Motivation (one for the skeptics)

I will be really professional and dedicate the first chapter to the people who are not always ready to jump on every train which promises to take them to a better place. They might be asking questions like “What is the problem that FP is solving for us?”.

I’d say the problem is the problem with shared state. Namely that the possible states of a mutable object grow exponentially based on the functions which mutate the object. Those of you who have some programming experience are probably painfully aware of what I mean but I will give an example nevertheless: This is what I would call the “four button problem”: Imagine a program which consists of just one button which modifies some internal state. Without knowing what it does and how it works, we can test the program by just pressing the button and checking if the state is modified in the right way. Now, imagine the same program but with two buttons instead of one (and one state object which is shared between them) - now we have two combinations of presses that we have to test - one is pressing “Button 1” and then “Button 2”, another is pressing “Button 2” first. With three buttons the number of possible combinations is six, which is somehow managable, but four buttons it’s 24 which is already too much. So any program has more than 4 buttons which share a state is practically impossible to test. Unless FP is involved.

The story so far

In the beginning there were computations (and the desire to do more of them). Buildings, organizations, machines - none of these things can come to life without some amount of number crunching being done. But what are computations really? For our puproses, the question is easier than it sounds like: A computation is just the process in which one arithmetical term, is reduced to another, simpler term, it is as easy as 1 + 1 = 2.

Unfortunately, however simple computations may be, we humans are not very smart creatures when it comes to them, especially the ones that have more than 10 terms. Long ago, we devised a method to overcome this weakness - the method consist of associating (or binding) terms which are too ugly or too long for us to wrap our head around them, with symbols. This method had always worked flawlessly - we just say let A = some big term and then we just type A whenever we need to type that term. This allows us to write the computation in fewer terms, without losing any information - we know that A is equivalent to this big term, so we can always replace one for the other. This even allowed us to do part of our computation even before some of the values of this term are known, the practice of which changed mathematics for ever.

Centuries passed and the computer was invented so we don’t need to do any computation by hand. Unfortunately when we started using it, our weakness for wrapping our heads around complex terms started giving us trouble again: the computer was a machine. When building it, its creators had to overcome numerous technical problems and limitations, so naturally it did not support the ability to declare some of the terms that we could not comprehend as symbols and to use symbols and terms interchangebly.

After some time some people decided to bring symbols back to programming. Their idea was to create a notation for writing computations on a computer and a program which converts that notation to a working computer code. In order to do that, they had to translate each mathematical operation that people invented to one or several instructions to the computer processor. And they decided to associate the operation that we discussed earlier - the operation of binding a simple symbol to a more complex term to the assignment operation. Here is how the assignment operation works:

1. Compute the terms right away and get the result (the computer had to use as little memory as possible, and therefore we want to compute everything as early as possible).
2. Put the result in a free memory location.
3. Translate all instances of the symbol in the program to pointers to that location in memory (because a symbol was actually interchangeble with a memory location).

The two concepts (binding and assignment) are obviously related, as the assignment was meant to work like a binding. They are both denoted with the = sign and in some situations an assignment is like a binding:

a = 1 + 1
b = 2 + 4
c = a + b

But there are some differences at how they typically function. The big difference is that assignment places a big focus over how and when the value is computed. For example we know that the right-hand side of the expression is computed before the left one. This is what enables us to make utterly unmathematical things like x = x + 1. What is the problem with this from mathematical standpoint? One problem is that it relies on the computational model that we use (the steps that I defined earlier) to work correctly. A second one is that it redefines x which does not make sense. But the bigger problem, which trancsends the mathematical is the problem that when we use something like that, we lose the reasoning model of symbols - a symbol is no longer associated with a term and the other way around. It is no longer a shortcut for a particular thing, but it is a vessel which at any time can be found to contain different things.

What happened after that? Long story short, people decided that this was OK, and it enabled them to make a more efficient use of space and by the time we could afford something better they were already too familiar with this computational model to make the change.

But anyway, where was I? Oh, yes…

Pure functions

Of course we begin our journey with pure functions. I’d know that FP has won when I see an article about it, which does not start with “What are pure functions?”. But this explanation is still needed, I think. For practical reasons you can think of a pure function in any programming language as one which:

1. In its body, it does not modify (mutate) the values of the arguments it accepts.
2. It also does not mutate, or change, the values of any external variables which it may access (although it may access external variables, provided that their values don’t change).
3. In its body, it only calls other pure functions.

Again, this is a practical definition, and for this reason it may be quite different from the ones that you may have heard (which are often based on theory). For example you may have heard that a pure function is one which is “referentially transparent” which is a fancy way of saying that it returns the same output given the same input - this is a good definition, but it is incomplete: the console.log function in JS returns the same output for every input - undefined, but that does not make it a pure function. The other problem with this definition is that it is not enough for someone who does not already know a thing or two about FP and it may leave you asking, “OK, but how do I make a function referentially transparent?”. The answer to this question is the list above.

You may have heard that pure functions are ones that don’t perform assignment. This is a nice definition, but it is a little bit sloppy. Does console.log perform any assigment? This is debatable. But does console.log modify some external variable somewhere? Well, we can be sure that the state of our console is stored in some variable somewhere and we can also be sure that this state is changed from calling the function, so for all practical reasons it does. In fact, this is the reason we are using console.log in the first place - we want the “side effect” - printing something on screen (as opposed to calling it for the value it produces).

This leads us to maybe the best (and most confusing) definition of pure functions - they are the ones which have no observable side effects. In other words, it woudn’t make any difference for our users if we call these function 10 or 100 times. It won’t make any difference to them if we called the function now, or we used some cached result from calling it 10 days ago with the same arguments. The key to this definition’s correctness is that it is a subjective one, not an objective one. And that settles some questions like:

Wait a minute, after all, all our functions write and delete some values in the registers of the CPU, so aren’t all of them are really impure? And what is this “outside world” anyways? Isn’t this all virtual?

Yes it is so in order to rigorously define pure functions we first define the events which are observable by our users (such as a sound coming from the speakers, the image on the screen, the time they spend waiting for a given resource to be fetched etc.) and we study the functions which don’t touch those. To some people side-effect-free would mean a different thing than to others. For example you may say that logging in some file is not a side effect, simply because your users won’t ever open it and you won’t run out of space, so logging “doesn’t count”. This is OK, you will have parts of your program which will do all kinds of side effects anyways. But let’s not get ahead of ourselves.

Here is something to think about: the distinction between pure and impure functions is somewhat similar to the distinction between syncronous and asyncronous functions in platforms with non-blocking IO such as node.js. What do we know about synchronous functions in node.js? They:

1. Do not perform any asynchronous operations.
2. Only call other synchronous functions.

If you substitude ‘asynchronous operations’ for ‘side effects’ and you get something close to the definition of a pure function. The non-blocking paradigm resembles functional programming in the respect that it makes it hard for you to write effectful functions. The difference is that it does that when it comes to just one type of side effect - IO operations while it allows all other types of effects.

Equational Reasoning

Why is that distinction, the one between pure and impure functions, so important? The answer is simple: because pure functions are data. If you are interested in Lisp, you may have heard that all code is data, but for pure functions, this slogan is valid in a slightly different way: Every pure function can be represented by, and is isomorphic to, a dictionary data structure, with the function’s inputs as keys, and its outputs as values. In mathematics, it is called a function table. I will give you an example with the function which converts an integer to a string:

const stringifyFn = (number) => String(number)

There are a finite number of integers, so it is entirely possible, and for some occasions even practical, to define such a function as a datastructire:

const stringifyTable = new Map([
  [1, '1'],
  [2, '2'],
  [3, '3'],
  [4, '4']
  ...
])

And behold:

stringifyFn(1) === stringifyTable.get(1) //true

This is probably the most important example you will see if you want to understand what is FP all about. Not all functions can really be represented as data structures (many of them have infinite inputs), but all of them can be reasoned about as such. One way to grasp the power of this concept is to imagine how the function-data isomorphism scales. Imagine a simple function like the one you see above being used in a more complex but also pure function. Which is being used by a yet another one… You might arrive to some very complex piece of functionality, but as long as you follow the principles stated above, what you created is an equivalent to, and can be used as, a simple datastructure, which contains keys and corresponding values. Can there be a bug in a datastructure? Well, a datastructure can be incorrect yes, but as long as it has outputs for all inputs, it will always work.

Let me reiterate that all this is valid only as long as you follow strictly the principles which I stated above, particularily the third one: that a function should only call other pure functions. When experts say that “mostly functional programming” does not work they mean exactly this - that you cannot build a program that is, you know, almost purely-functional, but it uses just a couple of side effects and get (almost) the same benefits as you would by a truly purely-functional program. This is because the reasoning model of FP and imperative programming is different (one relies heavily on binding and substitution, and the other uses assignments).

What about functions that take more than one parameter, like (a, b) => a + b. Well, you can think of them either as functions which take a compostite parameter((ab) => ab[0] + ab[1]), or as functions who return other functions((a) => (b) => a + b).

What about objects? Well, immutable objects are not excluded in any way from the party. If you have an object x with methods a and b, you can think of it either as a function x which takes one string which can be either a and b as a parameter (the name of the “message”), and one datastructure, containing the arguments. You can also think of it as a data structure x, with two functions (a and b) that just happen to have access to x. Using this approach, Even the most complex function constitutes nothing more, than a series of simple functions, and even the biggest taxonomy can be reduced to an ordinary datastructure from which you can just take the result, or results, that you need. We can even identify different paths in our system which lead to the same result for the purpose of optimization, or just to reach better understanding of our program.

Functional Runtimes

You can find a lot of information about how nice it is to have referential transparency and to be able to apply equational reasoning. You won’t, however, have much success in finding information about what to do next. That is the topic of this chapter: how the hell creating a bunch of pure functions would help me create a GUI application, for example? Or a concurrent web server? Many functional programming tutorials seem to dismiss this question as uninteresting, but for me it is essential: running side effects is a tough job, but someone has to do it. Enter the exciting, and not very well-researched topic of functional runtimes, AKA programs that bind (no pun intended) purely-functional programs to the real world. So what is the big idea? Simple: you design your program, you split it to two parts - one is the purely functional part which, if you are good, will be the better and bigger part of your program and the other will be the imperative part, which should be as simple as possible and also as generic as possible, so many different programs can use it. Don’t take the term “runtime” literally here. In some contexts, this “runtime” can be just a simple library for running purely-functional programs that solve a specific set of problems. But the runtime can also be very complex, and support many options.

The closest thing we have to a functional runtime in the traditional programming world are the domain-specific languages. Think of CSS, for example - CSS is a purely functional language that allow you to define the layout of a webpage easily and bug free. Its secret is that CSS code itself does not do anything. Most of the hard job is done by its runtime (the browser) - a runtime that is not very simple, but is very versatile and can support a whole class of programs (in this case graphical user interfaces).

CSS is, of course, not a very powerful language. Which is unfortunate: imagine having the ability to embedd some real (purely-functional) code in CSS class definition, that decides how the elements from this class be positioned, based on the position of other elements, and on other forms of state. This would allow us to be a lot more flexible when creating a dynamic layout, and still don’t worry about the layout blowing in our face, bringing us many of the benefits of having access to a powerful tool, without any of the drawbacks. The whole philosophy actually boils down to that old principle about separating your code from your data. If you consider pure functions data, that is. If you don’t, the practice of separating your code from your data would still be useful, albeit very limited - anytime you need a more complex structure you will either have to copy and paste like crazy or just to drop the whole practice altogether.

Now back to functional runtimes: as I said creating one involves splitting your program to two parts:

1. A pure function (or an immutable object containing pure just functions) which should encompass as much of your functionality as possible.
2. A bunch of imperative code supportting the pure part, which should be as small and as generic as possible.

Making this split is, for me at least, the heart of the matter over how to do FP. Generally there is no magic formula for doing it. It is different for different kinds of programs. Let me reiterate that it is crucial that you do not cheat Keep a clean distinction between the two parts - keep them in separate folders, separate files, use a linter which limits the use of non-pure language features like assignments, mutability, accessing global variables. And never say stuff like:

I’ll just insert this small mutable state here, and nobody will notice.

or:

…but otherwise I have to rework ALL of my program!

You will have much more benefit from a small purely-functional module than if most of your program is mostly-functional but not quite there yet.

Some classes of programs can be very trivially split into a purely-functional and an imperative part - think of command line tools for example, especially those of them which only use STDIN and STDOUT, like the grep tool. Such tools have a very simple runtime - one which just takes the input, feeds it to the purely-functional part and when it finishes, it passes the return value to STDOUT - you can say that they are pure functions in disguise.

So let’s see how would we implement a small version of grep in node.js. We will start with the purely functional part (called grep-pure.js) because it is the easiest:

module.exports = (input, args) => 
    input.split('\n')
        .filter((row) => row.includes(args.pattern))
        .join('\n')

Not much to see here. We just split the string to a list, and then we do our work using the well-know list operators. All these methods are analogous to pure functions, because ther don’t modify the object to which they are called. Instead what they do is to return a different object which serves as new “version” of the same object - a popular trick in FP.

The function that we define is also a pure one, because it does not modify the values of its arguments: input and args, does not access any external variables, like process for example. We access the external variable pattern in the anonymous function that we pass to filter. This is OK, provided that we don’t modify it (we don’t) and that the variable is immutable. This explanation made the whole thing sound more complicated than it is - I just wrote the function using only immutable data and whenever I needed something I defined it as an argument.

OK, now let’s get to the more interesting part - the grep-runtime.js. Because we want to be as versatile as possible, we will define a generic runtime for writing CLI applications. It is easier than it looks:

module.exports = (f) => {
    const args = require('minimist')(process.argv.slice(2))
    require('get-stdin')().then((input) => {
        console.log(f(input, Object.freeze(args)))
    })
}

Here we are using effectful functions like crazy. That is how it should be - all pure functions should be moved outside of this file. We use Object.freeze to enforce the principle that we discussed earlier - a pure function should not mutate its arguments.

We wrote a pure grep implementation as a pure function and a generic function for “lifting” pure functions into command-line tools. Our final program grep.js is what we get if we combine those two things together:

require('./grep-runtime')(require('./grep-pure'))

The result is can be used like ordinary grep - you pipe a text stream through the tool, specify the pattern and you get the results:

/> cat file.txt | ./grep.js --pattern dog
< I like dogs.
< And there I saw a big shaggy dog.

Once we realize that we can return and pass programs around some of which are impure, but the functions which operate on them would still be pure, purely-functional programming starts to feel much more feasible.

Reinventing imperative programming

Our grep implementation from the previous example is incomplete - we only implemented the functionally-friendly part. Let’s try to extend it so it also accepts filepaths as input. For this we need to extend our runtime. We will take a most naive approach when doing this, while also trying not to move away from the general-purpose aspect of the runtime. Our program will not return a value but instead it will return a “special object” which signifies to the runtime what it needs to do - an “Action” object so to say. The runtime, then, will perform the action and then it will call the callback, that would allow us to resume our execution in a pure context. In our case we have two actions - reading from a file, and reading from the stdin:

const simpleGrep = require('./grep-pure')

module.exports = (args) => {
    if (args.file !== undefined) {
        return {
            action: "readFile",
            arguments: {file: args.file},
            callback: (contents) => simpleGrep(contents, {pattern: args.pattern})
        }
    } else {
        return {
            action: "readStdin",
            arguments: {},
            callback: (input) => simpleGrep(input, args) 
        }
    }
}

The runtime needs to be extended to support actions:

const fs = require('fs')

module.exports = (f) => {
    const args = require('minimist')(process.argv.slice(2))

    const result = (f(Object.freeze(args)))

    if(result.action === 'readFile'){
        fs.readFile(result.arguments.file, 'utf8', function (err,data) {
            console.log(result.callback(data))
        })
    } else if (result.action === 'readStdin'){
        require('get-stdin')().then((input) => {
            console.log(result.callback(input))
        })
    } else {
        throw new Error('Invalid action')
    }
}

But when you think about it, isn’t print just another action, like readFile? It indeed is, and refactoring our runtime to support print as an action would make it trully general-purpose:

const simpleGrep = require('./grep-pure')

module.exports = (args) => {
    if (args.file !== undefined) {
        return {
            action: 'readFile',
            arguments: {file: args.file},
            callback: (contents) => ({
                action: 'print',                
                arguments: {
                    string: simpleGrep(contents, {pattern: args.pattern})
                },
                callback: undefined

            })
        }
    } else {
        return {
            action: 'readStdin',
            arguments: {},
            callback: (input) => ({
                action: 'print',                
                arguments: {
                    string: simpleGrep(input, {pattern: args.pattern})
                },
                callback: undefined

            })
        }
    }
}

The runtime needs to be extended to support this action:

const fs = require('fs')


const processResult = (result) => {

    if (result.action === 'readFile') {
        fs.readFile(result.arguments.file, 'utf8', function (err,data) {
            if (result.callback !== undefined) {
                processResult(result.callback(data))
            }
        })
    } else if (result.action === 'readStdin'){
        require('get-stdin')().then((input) => {
            if (result.callback !== undefined) {
                processResult(result.callback(input))
            }
        })
    } else if (result.action === 'print'){
        console.log(result.arguments.string)
        if (result.callback !== undefined) {
            processResult(result.callback())
        }
    } else {
        throw new Error('Invalid action')
    }
}

module.exports = (f) => {
    const args = require('minimist')(process.argv.slice(2))
    processResult(f(Object.freeze(args)))
}

This program, is different than the previous one and the difference does not consist solely in the addition of the readDir action. The bigger difference that you have to notice here is that callbacks can also return actions, (which return more actions and more actions ad infinitum). With the proper actions added, this runtime is capable of hosting any imperative program that you might want to write.

If you don’t believe me, check this tweaked version of the previous program written using generators:

module.exports = function*(args) {
    let input;
    if (args.file !== undefined) {
        input = yield readFile({file: args.file})
    } else {
        input = yield readStdin()
    }
    yield print({ string: simpleGrep(input, {pattern: args.pattern}) })
}

You can see the runtime for this program in this repo.

My point - cooking a runtime that would emulate imperative programming style with FP is not only possible, it is (relatively) easy. And it is not the point of FP - if we thought that imperative programming style was OK, we would stick to it, instead of learning about monads and stuff (by the way, every functional runtime which can be used to simulate imperative programming is inherently monadic). What is the point of FP then? Well, for me it lies in finding the intricate balance between a runtime that allows you to do anything and one which allows you too little. Finding the balance between your runtime and your program, and creating runtimes and recipies for runtimes that are useful not only for you, but for other people.

Appendix: Functional recipes

I wanted to end this article with some examples and these are the ones I came up with. This should give you a hint on how you can use the tips from above.

Actions as objects

Representing actions as objects is a very basic recipe in FP which is also used in the above example. At its heart is the idea that a type can be isomorphic to a given subroutine and an instance of that type - to an invocation of the subroutine. Therefore an effectful computation that calls the subroutine, can be replaced by a pure function which returns an instance of the type.

State as a function

An issue exemplified by the four-button problem is that programs often try to modify an existing state to incorporate the effects of a given action. This issue can be solved by just throwing away the old state and recomputing it from scratch from a well-defined set of input parameters.

Functions as data

When we do imperative programming, we deal with concrete (computed) values. When we deal with FP, we often deal with values that are not yet computed (functions). In FP pure functions often return other functions and it is up to the runtime to call them and produce the final value.

That’s it for now. If you want to contribute to this article, send me the most useful functional recipes you use on marinovboris@gmail.com.

Appendix 2 - on Turing machines and Lamda calculus