Get best of the week

Functional programming is what you (probably) were told. If you listened

I like conversations on the topic "I used to be told at school / institute / parents, but now I found out." If, by a lucky chance, I find myself at least a little competent in the matter under discussion, then such conversations usually come down to one of three options: “where have you heard such nonsense before?” (if the interlocutor is right), “and where did you get that this is so?” (if he’s wrong) and “you’re right, only this does not contradict what you were told before” (in the vast majority of cases). I like these conversations for the following reason: usually their initiator is not burdened with excessive preliminary knowledge of the issue, which in some cases allows him to point out some points that were accepted as obvious, but not really such. And one of the topics for such conversations was functional programming.

In general, so much has been written and said about FP that it seems to be all questions about its applicability, coolness, performance, etc. gnawed to the bone marrow. Nevertheless, such questions are raised again and again, and there will always be someone who wants to talk about what you all misunderstood, but in fact it is like that. Perhaps today I will try on myself this ungrateful role, since several posts on this long-suffering topic have recently caught my eye. The first and second once again says that AF is rubbish and studying it only spoils your future specialist’s karma. Others ( one and two) are much more adequate, in them the author aims to explain that all these your lambdas, combinators, categories are nothing more than dust in the eyes, and the FP itself is a simple, understandable and pleasant thing in life.

How true is this?

Before turning to the essence of the issue, I will make a small digression and put emphasis. The content of the first two of these posts, I think is outright nonsense of an illiterate ... specialist who, with his fingers spread apart, discusses things that he didn’t even spend a bit of his precious time studying. Good people from among the commentators have already indicated that this is nothing more than banter. The problem is that, as it turned out, I am not able to perceive the theses put forward in these translations as a banter, since I had to hear most of them live. Apparently, you can diagnose the presence of psychological trauma caused by an oversupply of nonsense that has passed through the brain.

The second two were more likely to evoke positive emotions, because in them the author applies the practice of FP to the tasks that the OOP developer understands. Despite the disagreement with the basic message of the first publication reflected in the title and doubts about the reasonableness of the implementation of the monad concept in such an explicit form in the OOP-oriented language, the author cannot be reproached for the lack of elaboration of the material. But there is one basic aspect, which I could not ignore. This is a kind of vulgarization of functional programming, an attempt to consider it as a simple set of tools and approaches to program design. Which, in my opinion, is not entirely true.

Therefore, in this article, an attempt is made to show that the properties of functional programs that the author is trying to reproduce in his code are not the foundation of functional programming, not laid down by the wise creators of Haskell and his ilk design solutions, but either a direct consequence of those concepts and models that really laid in its foundation, or, oddly enough, an attempt to compensate for the shortcomings that these foundations generate.

So to the point


In science, quite often you can observe the following metamorphosis. First, as part of the consideration of a certain process / phenomenon / theory, a certain object appears that possesses some important and useful properties. But it usually also turns out to be rather complicated in its structure, which limits its practical usefulness. Therefore, they often act in this way: they take the properties of a given object as a basis and on this basis build a new theory / model / description, within which the desired object becomes simple or even trivial, or the necessary inherent properties appear in much simpler objects. Something like this is related to the "real" functional programming and the "elements of functional programming", which are available in modern high-level languages.

Since it is usually useful to familiarize oneself with the history of its origin for understanding a phenomenon, let us recall the moments of the history of the theory of computation and programming that are important for our question. In the late nineteenth and early twentieth centuries there was a significant restructuring of the foundation of mathematical science. This not only solved a number of identified problems and contradictions that crept into the very core of the ideas at that time that there was mathematics and mathematical proof, but also posed a number of new questions. One of them was the following: what is the algorithm? Or, what is the same, what class of problems can be solved purely mechanically. I will not expand on why this question turned out to be important; I’d better go straight to the answer that Alan Turing, widely known in not very narrow circles, gave him. He formulated the thesis:"Only functions for which a Turing machine can be constructed are computable." This statement is unproven. That is, in fact, Turing simply gave a strict formal definition of what is considered a computable function, consistent with those intuitive representations that are usually embedded in this concept. This definition proved to be able to satisfy the applicants, because they are well aware of what a machine is, even with an infinite ribbon, and how it should function. But for many mathematicians, this definition is not too satisfied.which are usually invested in this concept. This definition proved to be able to satisfy the applicants, because they are well aware of what a machine is, even with an infinite ribbon, and how it should function. But for many mathematicians, this definition is not too satisfied.which are usually invested in this concept. This definition proved to be able to satisfy the applicants, because they are well aware of what a machine is, even with an infinite ribbon, and how it should function. But for many mathematicians, this definition is not too satisfied.

Apparently, the concepts that Turing operated on seemed to them insufficiently ... abstract. In this regard, they did not abandon attempts to give a different definition, which would cover a larger class of mathematical functions and at the same time still correspond to our intuitive ideas. These attempts were fruitless. Each alternative definition that was proposed and withstood criticism turned out to be equivalent to Turing's definition in the sense that it described exactly the same class of mathematical functions. However, these studies were by no means useless. Attempts to look at the object of study from a different point of view are generally rarely useless. In our case, this led to the appearance of several theories, one of which was the lambda calculus proposed by Alonzo Church.

Laziness is the engine of progress


What is so useful in lambda calculus and why is everyone so fussing with it? Everything is simple. In the model proposed by Turing, the algorithm is a sequence of instructions that is familiar to us, which again must be executed by the usual performer. It is intuitive. But Church’s definition is different. The main (and essentially the only) building mechanism in the framework of this theory is the so-called lambda terms, which in our current terms can (conditionally) be called anonymous functions. The program (algorithm) in this case is a combination of these terms built according to certain rules, the initial data are the values ​​of the free variables of the lambda term, and the calculation process is nothing more than a reduction (simplification) of the lambda term (function), which can be performedas soon as some free variable gets value. The following fact turned out to be unexpected here: as soon as a variable receives a value - that is, as soon as we present a part of the initial data to the program - we can perform the reduction, but not in one, but in two ways. In the first case, the calculation process turns out to be equivalent to that reproduced by typical mechanical calculators like a Turing machine. The rule corresponds to it: the arguments of the function must be calculated before the function itself is calculated. But there is another option - the so-called partial calculation. In this case, if only a part of the arguments is calculated, we can still calculate (reduce) that part of the function that uses only these arguments. This approach is usually called the "lazy" model of computing.In contrast to this, the Turing model of computations is sometimes called “energetic” or “greedy”; programming languages ​​built on its basis will be called imperative below. An important feature of "lazy" calculations is that if a subroutine is written as a function of, say, three arguments, but in reality uses only two, then there is no need to calculate this third argument in order to calculate the value of the function.

And this gives us interesting practical possibilities. For example, the ability to work with infinite sequences. It would be easy for anyone who began to get to know functional programming in general and with the Haskell language in particular to understand this way of getting the first n Fibonacci numbers:

fibonacci2 a b = a : (fibonacci2 b (a+b))
fibonacci = fibonacci2 1 1

nfibonacci n = take n fibonacci

Explanation for Strangers with Haskell
fibonacci2 , , fibonacci2 b (a+b). ( !) :
def fibonacci2(a, b) :
    return [a] + fibonacci2(b, a+b)

def fibonacci() :
    return fibonacci2(1, 1)

def nfibonacci(n) :
    res = []
    data = fibonacci()
    for i in range(n) :
      res.append( data[i] )
    return res

nfibonacci.

The fibonacci function (and this is precisely the function) generates an endless list of numbers. If we used the computational model familiar to us, then nfibonacci could never have ended (which, I recall, is perfectly acceptable and does not contradict the notions of its “computability”). But if we use the "lazy" model of calculations, it is easy to notice that as soon as n takes on a specific value, to get the value of the nfibonacci function , we need only the first n elements of the list that is the result of the fibonacci function . In this case, we can act like this: get the list item - perform the reduction, the next element is another reduction step, n-th argument - reduction led to obtaining the value of the function. That is, in this case we get a result for a finite time despite the "loop" of the procedure for constructing a list of Fibonacci numbers.

Here, a particularly zealous imperative-minded reader exclaims: “ But wait, only a frank idiot will implement the construction of a list of Fibonacci numbers this way! There are obvious solutions that do not lead to a loop". And he, of course, will be right. The stupid transfer of a solution involving the implementation of the model of" lazy "calculations into a program for" greedy "calculations is not really an indicator of great intelligence. If you offer this task to a programmer who has kept his entire professional life Loyalty, say, to the C language, then he will most likely offer a variant with one cycle with a counter and two state variables.

But the point is not the Fibonacci numbers themselves. The fact is that the rule for constructing a sequence in this example is separated from the method of processing its elements. And this is a useful property that it is desirable to be able to reproduce in more complex cases, when the elements of the processed sequence are generated in a rather complicated way and a simple transfer of the solution “head-on” for the Fibonacci sequence in this case is ineffective in time, memory, or simply leads to code, the understanding of which is not accessible to mere mortals. Such an aspiration is natural and can be realized, for example, through the use of iterators or generators. In python, for example, we can do this:

def fibonacci() :
    a = 1
    b = 1
    yield a
    yield b
    while True :
      c = a + b
      yield c
      a = b
      b = c
     
def nfibonacci(n) :
    return [e for e in itertools.islice(fibonacci(), n)]

Here fibonacci () is a generator that creates a sequence element by element. And in this case, instead of fibonacci, there can be a generator function of any complexity. If we bring the code completely, including the engine hood code, we get a very complex and completely imperative software design. But the final version is quite “functional”. In C ++, one could do a similar trick by having a special Fibonachi class and iterators for it. The decision will vary depending on the features of the programming language and the preferences of the programmer, but the goal will remain the same - to divide at the organization level of the program a way to build a sequence of previously unknown lengths and a way to process its elements.

The difference is that in the framework of the functional approach, such a program organization is natural and is imposed by the very method of its implementation, while in the framework of the imperative program it requires additional creative work, including the creation of additional concepts and design patterns.

Cleanliness is the key to health


Another property, in the presence of which they speak of a functional approach to programming, is the “purity” of functions. It is the absence of side effects. That is, a function call with the same set of arguments should lead to the same result. The author of the cited post described in sufficient detail why in programs executed in an imperative style, this property is also desirable. However, it is nothing more than a consequence of the model of calculations used.

The reason that all functions in a functional program must be clean is simple. Assuming the presence of these very side effects, it turns out that the order in which the function arguments get their value directly affects the result of the function. We can say that this is also true in the framework of the imperative approach, but in the case of “laziness” of calculations, everything is much worse. Even if we assume that the arguments of the function can be calculated independently of each other in arbitrary order, then “laziness” still implies that (conditionally) not all the code of the function will be executed in one sitting. It will be executed in parts, depending on two things - in fact, the structure of the function that the conditional compiler will kindly provide us with, and the order in which we will present the function with its arguments.

It’s natural for us to expect that if we first defined a function

def f(x,y) :
  ...

and after her
def g(x, y) :
  return f(y, x)

then the result of calling g (a, b) will be equal to the result of calling f (b, a) for any independently computable values ​​of a and b . But if f has side effects affecting the calculation of argument values, then our expectations can be brutally deceived . For example, when calculating b , reading from the file occurs - and when calculating f , reading from the same file also occurs. In “lazy” calculations, we don’t know in advance which part of the code (for b or for f) will be executed first. That means we don’t know what result the program will give even if we know the contents of the file that it should read. Such behavior is in principle unacceptable and therefore should be categorically excluded. So, within the framework of the model of “lazy” calculations (uncontrolled) side effects of the function should be prohibited .

If the greedy order of calculations is applied, the side effects are much more predictable. For this and only for this reason they are allowed in imperative programming. But if you abuse them, then the feature will turn into a bug. So, you should not abuse them. So, again, the concept of “purity” that is natural in functional programming is in demand in the imperative world.

Consequently, the thesis
Functional program - a program consisting of pure functions
incorrect if viewed as a definition. Yes, a functional program consists of “pure” functions, but a program consisting of pure functions does not have to be “functional” at all. This is her property, but not a defining property.

However, there is a problem. The ability to save state and even banal input-output are things directly related to side effects. And life without them is full of pain and suffering. The question arises: how to marry side effects and "lazy" calculations? The answer in general is no way. The answer is correct - in each particular case a satisfactory particular solution should be sought. It turned out that many ways of reproducing calculations with side effects without violating the concept of “purity” of calculations fit into the general concept of the monad, borrowed from category theory. I would not want to try again to explain what it is and what it is eaten with, if only because in any case it will not replace (and in my experience it will not even simplify) an explanation of how state variables can be implemented specifically,exceptions and similar things in “pure” functional languages. The main moral is that imperative programming is a source of inspiration for the functional as well as functional for the imperative. Moreover, sometimes an idea passes through a competing concept as through a filter, returns back in an altered form and leads to the appearance of a new tool.

Are monads needed in an imperative world? I have no established opinion on this issue. The author of thisfasting sure that needed. I am inclined to doubt this statement, since the use of the concept of a monad in functional programs is usually connected with the fact that a certain algorithm can be formulated regardless of which specific side effects this monad hides. In other words, if a user-defined (hypothetical, not yet created by mankind) data type satisfies the requirements for a monad, then the written algorithm for it will work correctly. This is convenient primarily in theoretical studies. But there is a couple of nuances. Firstly, it is not very clear why to hide in the wrapper side effects are effective in languages ​​for which they are a natural phenomenon. Secondly,when writing specific programs with specific data types and a specific target architecture, such a generalized algorithm is most often forced to undergo a restructuring in order to increase productivity. Writing generalized algorithms using monads in an imperative style is possible, but the appropriateness of this approach raises my doubts. The fact that some Maybe analog of type std :: optional from C ++ will be declared a monad is unlikely to somehow affect the practice of its use.

?


Higher-order functions are a tool so widely used in functional programs that the fact of supporting something similar in some programming language is enough for some strange individuals to recognize this language as functional. What are "higher order functions"? This is a function that operates on other functions as arguments, or returns a function as a result. It would seem that here can cause debate? It turns out a lot. To begin with, what is generally understood by the term “function”. Programmers usually reason simply: if something can be called as a function, then it can be considered as a function. In the framework of the imperative approach, this makes sense, since intuitively a function is that for a given set of arguments it gives a certain result.If we admit the presence of side effects, then in the practical sense there really is no difference between the "normal" function of the language and, say, the object of the class having the overloaded operator ().

But in functional programming, such a definition of a function is not constructive enough, since it does not make it possible to interpret the concept of a partial calculation of this function itself. In functional programming, a function is not “one of” the structural elements of a program, but in a certain sense the opposite: all program elements are functions. Therefore, in fact, this is “functional programming”. And then again, if everything is a function, that is, any argument of any function is a function, then any function with arguments is a higher-order function. Hence, higher-order functions are a natural element of a functional program. So much so that even their allocation in a separate class does not make much sense.

As a higher order function, map or fold is usually given.. But we will consider a more trivial - any - function of the two arguments f (x, y) . Within the framework of the model of “lazy” calculations, the arguments of this function will be calculated only when they are really needed. Suppose the first argument is x .

We calculate this argument, provide its value f and, in addition, calculate everything that we can calculate without using the value of the argument y . Then the rest of the calculations can be represented as a new function, already independent of x , for example, g (y) . But in this case, nothing prevents us formally presenting f not as a function of two arguments, but as a function of one argumentf (x) , the result of which is another function g (y) . In other words, within the framework of the functional approach, any function of N> 1 arguments is a higher order function, since it can be interpreted as a function of one argument, the result of which is the function of N-1 arguments.

Can we implement this behavior as part of an imperative approach? Of course we can. In python, we would write something like the following:

def partial(f, x) :
	def g(*args) :
		return f(x, *args)
	return g

By calling the partial function , the first argument of which is the function of N arguments, and the second is the value of its first argument, we get the function N-1 of the argument. Now we can use the new function wherever we can use the N-1 argument function . That is, they got the same thing as in the functional program. So? No not like this. If we were dealing with a truly functional program, then when we called partial , we would calculate part of what the value of the first argument is for. In some cases, it might even turn out that g is a constant value. What do we have in an imperative analogue? The passed value of the argument xjust remembered (added to the context of the function g ). When we call g , the value of x will be taken out of the bins and simply substituted into f . That is, there is no difference in form, but in content - significant.

Using functions from functions is convenient because it allows you to naturally describe many important algorithms. So, they were obliged to appear in imperative programming languages. And they appeared. But since they use a different calculation model, this would have required the development of new concepts. And they were developed. For example, the closure described above. That is, the functions of higher orders in imperative languages ​​correspond to what can be observed in functional languages, only externally. But the content is completely different. Is this important for the programmer? Probably not, but only if he understands well how those mechanisms work that implement similar features in his favorite programming language. Otherwise, you can, for example, implement "partial application", close when building a new function (well, orwhat in your case will look like a function) link instead of value and get interesting program behavior. And after that, shout about the inferiority of the functional approach.

So who was cheating on whom?


At this stage of the presentation, it is quite possible to put a semicolon and return to the main question. Since now we can formulate the following statements:

  • The main difference between functional programming and imperative programming is not the property of purity of functions, the presence of anonymous functions, higher-order functions, monads, parametric polymorphism, or anything else. The main difference is the use of a different calculation model. Everything else is nothing more than consequences.
  • , , . . , «» «» . , . .
  • , , , . . — .
  • , . , «» ; , . , - , - . .
  • , . , . , , , . .

Functional programming is what you (probably) were told about. These are beta reduction, fixed point combinators, monads, Hindley-Milner typing, and more. Do not confuse the wrapper with the content. FP is not based on the simplest mathematics; it cannot be mastered for a couple of evenings with a glass of tea; it is unlikely to be directly projected onto your pressing problems and projects; you won’t get a guaranteed and quick profit from this knowledge. But many elements of what is in the functional approach are borrowed, processed, and ultimately implemented in programming languages ​​oriented towards the development of large projects. Yes, they are arranged differently than their functional ancestors, but this does not make them less useful. Only a clinical idiot will broadcast a serious message that Haskell is a bad language,because it’s hard to write a program for any kind of accounting. A person burdened with the presence of intelligence, even from the standpoint of his professional activity, without a deep immersion in the intricacies of theory is quite capable of understanding exactly which practices from functional programming should be adopted in order to make your code better. For a convincing demonstration of which I express gratitudePsyhast.

Learn functional programming. In the name of yourself.

More articles:


All Articles